Collaborative Research: Mechanism Design and 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.