The design of algorithms or protocols that are able to align the goals of the planner with the selfish interests of the agents involved in these protocols is of paramount importance in almost every decentralized setting (such as, computer networks, markets, etc.) as shown by the rich literature in Mechanism Design. Recently, huge interest has been devoted to the design of mechanisms for imperfectly rational agents, i.e., mechanisms for which agents are able to easily grasp that there is no action different from following the protocol that would satisfy their interests better. This work has culminated in the definition of Obviously Strategyproof (OSP) Mechanisms, that have been shown to capture the incentives of agents without contingent reasoning skills. Without an understanding of the algorithmic nature of OSP mechanisms, it is hard to assess how well these mechanisms can satisfy the goals of the planner. For the case of binary allocation problems and agents whose private type is a single number, recent work has shown that a generalization of greedy completely characterizes OSP. In this work, we strengthen the connection between greedy and OSP by providing a characterization of OSP mechanisms for all optimization problems involving these single-parameter agents. Specifically, we prove that OSP mechanisms must essentially work as follows: they either greedily look for agents with ``better'' types and allocate them larger outcomes; or reverse greedily look for agents with ``worse'' types and allocate them smaller outcomes; or, finally, split the domain of agents in ``good'' and ``bad'' types, and subsequently proceed in a reverse greedy fashion for the former and greedily for the latter. We further demonstrate how to use this characterization to give bounds on the approximation guarantee of OSP mechanisms for the well known scheduling related machines problem.


翻译:设计能够使计划者的目标与参与这些议定书的代理人的私利利益相一致的算法或协议的设计,在几乎每一个分散的环境下(例如计算机网络、市场等),都是至关重要的,正如《机制设计》中丰富的文献所显示的那样。最近,人们对设计不完全理性的代理人机制,即代理人能够很容易地理解,与遵守议定书没有不同行动可以更好地满足其利益的机制,设计能够使计划者的目标与计划者目标相一致的算法或协议的设计,在几乎每一个分散的环境下(例如计算机网络、市场等),都是至关重要的。最近,对于设计机制设计机制,为不完全理性的代理人,即代理者能够很容易地认识到,与协议者没有不同,因此,在定义明显不受战略约束的(OSP)机制时,已经表现出了代理人的动机。如果不了解OSP机制的算法性质,则很难评估这些机制能够很好地满足计划者的目标。关于二进制分配问题和私人类型为单一数字的代理人,最近的工作表明,贪婪的概括性是OSP问题的全部特征。在这项工作中,我们如何加强贪婪和OSP之间的联系,我们加强OSP之间的联系,通过提供一种机制的描述Oral-selfrial机制,在它们进一步处理涉及这些单一代理人代理代理人代理代理人代理代理代理人的处理问题时,然后又能的工作。</s>

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
27+阅读 · 2023年2月10日
Arxiv
11+阅读 · 2022年9月1日
Arxiv
64+阅读 · 2021年6月18日
Arxiv
92+阅读 · 2021年5月17日
Arxiv
16+阅读 · 2020年5月20日
Arxiv
110+阅读 · 2020年2月5日
VIP会员
相关VIP内容
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员