Collaborative Research: Mechanism Design and Approximation

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

• 批准号: 0830773
• 负责人: Jason Hartline
• 金额: $ 29.96万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830773&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.

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