Collaborative Research: Mechanism Design and Approximation

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

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.