Collaborative Research: Mechanism Design and Approximation

合作研究：机制设计与近似

• 批准号: 0830494
• 负责人: Shuchi Chawla
• 金额: $ 22.81万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830494&HistoricalAwards=false
• 关键词: Collaborative; Research; Mechanism; Design; Approximation

Mechanism design lays the economic foundations for the design and analysis of protocols, services, and applications in computer networks where users may act selfishly in their own best interest. The economics literature provides nice characterizations of optimal mechanisms in simple enough settings, that can then inform the design of real mechanisms. Unfortunately, in many other settings impossibility results show that there is no simple description of an optimal mechanism. The PIs' research advocates using algorithmic approaches to identify simple and natural descriptions of approximately optimal mechanisms; it addresses economic settings that are both challenge problems in economics and relevant to the design of computer systems. A primary focus of this research is the biggest open problem in mechanism design: domains where each user's preference is given by multiple parameters. Especially interesting special cases that the PIs plan to study include the role of randomization in the mechanism and user preferences with budgets. Another area of focus deals with the design and analysis of non-truthful mechanisms. The computer science literature on mechanism design almost exclusively restricts attention to the design of mechanisms where "truthful bidding" is an optimal strategy for each user. Most mechanisms used in practice are not truthful. However CS literature lacks techniques for going from truthful mechanisms to natural, practical (probably non-truthful) mechanisms, or a theory of designing natural non-truthful mechanisms in the first place. Where the natural, practical mechanism is not optimal, theory for quantifying its approximation factor, a.k.a., "price of anarchy", is of interest. The PIs' research will develop tools for designing non-truthful mechanisms and for price of anarchy analyses in the resulting games of incomplete information.

机制设计为设计和分析计算机网络中的协议、服务和应用程序奠定了经济基础，在计算机网络中，用户可能为了自己的最佳利益而采取自私行为。经济学文献很好地描述了在足够简单的环境下的最优机制，然后可以为真正的机制的设计提供信息。不幸的是，在许多其他情况下，不可能的结果表明，没有最优机制的简单描述。PIS的研究主张使用算法方法来识别对近似最优机制的简单和自然的描述；它解决了既是经济学中的挑战问题又与计算机系统设计相关的经济环境。这项研究的一个主要焦点是机制设计中最大的开放问题：每个用户的偏好由多个参数给出的领域。PIs计划研究的特别有趣的特殊情况包括随机化在机制中的作用以及用户对预算的偏好。另一个重点领域涉及非真实机制的设计和分析。关于机制设计的计算机科学文献几乎完全将注意力限制在机制的设计上，在这种机制中，“真实竞价”是每个用户的最佳策略。实践中使用的大多数机制都是不真实的。然而，CS文献缺乏从真实机制到自然的、实用的(可能是非真实的)机制的技术，或者首先缺乏设计自然的非真实机制的理论。在自然的、实用的机制不是最优的情况下，量化其近似因子的理论，也就是“无政府状态的代价”，是有意义的。私人投资机构的研究将开发工具，用于设计不真实的机制，并为由此产生的不完全信息博弈中的无政府状态分析定价。