FOCS 2012 Workshop on Bayesian Mechanism Design

   Saturday, October 20 2012 - Hyatt Regency, New Brunswick, New Jersey

   Organizers: Costis Daskalakis, Jason Hartline

    Speakers: Shuchi Chawla, Costis Daskalakis, Jason Hartline, Nicole Immorlica, Tim Roughgarden, Eva Tardos

Mechanism design is the subfield of economics that looks at economic systems from the point of view of an optimizing designer. This designer would like to build a system whose agents' individual optimization leads in equilibrium to global optimization of a desired objective. While it is desirable to be able to perform this optimization in the "worst case," that is, in the absence of any assumption on the input, this is often not possible. On the other hand, stochastic prior information about the agents' private preferences can circumvent such impossibility results. A celebrated example is Myerson's revenue optimal single-item auction [Myerson 1981].

Over the last few years a number of works have demonstrated the benefits of using stochastic information about the bidders' preferences to circumvent impossibilities in the worst case, as well as of applying computer science techniques such as approximation to classical problems in the economic theory of Bayesian, i.e. with stochastic prior information, mechanism design. These include, for example, combinatorial algorithms for revenue optimization in multi-item auctions, black-box reductions from mechanism to algorithm design, simplicity versus optimality tradeoffs. At the same time, mechanism design has lent itself to the development of compelling new models bridging between the worst-case and the Bayesian model, such as prior-independent and detail-free mechanism design.

The goal of this workshop is to introduce the broad CS theory community to central problems in mechanism design, present a rich set of models that, inspired by computation, interpolate between the worst- and average-case model, and stimulate new directions for the interactions between theory of computation and mechanism design.

Workshop Schedule

        Coffee Break (provided) (4:00pm-4:30pm)


Simple/Prior-Independent Auctions
Speaker: Tim Roughgarden (Stanford)

Optimal mechanisms are often complex and depend on the details of the distribution of bidders' preferences. On the other hand, strong impossibility results hold under worst-case input assumptions, as discussed above. To mediate between these extremes the literature has proposed interesting models bridging worst- and average-case models, and compelling positive results have been obtained for such models. Examples include simple, approximately optimal mechanisms, which are only parameterized by minimal properties of the distribution; and prior-independent auctions, whose guarantees hold under the assumption that the agents' preferences are stochastic, but without knowledge of the underlying distributions of preferences. This lecture will survey work on this front.

Revenue-optimization in multi-item auctions
Speaker: Costis Daskalakis (MIT)

While welfare optimizing mechanism design has been solved in very general settings, even under worst-case assumptions about the agents' preferences, research on revenue optimization has been stagnant. Myerson's seminal work provides a revenue-optimizing single-item auction, but generalizing this auction to more general settings, e.g. multi-item auctions, has been challenging to economists. Algorithmic techniques have enabled breakthroughs on this problem, enabling exactly optimal mechanisms. This lecture will survey work on designing revenue optimal auctions, discuss the relevant combinatorial optimization techniques, and present open problems going forward.

Black-box reductions from mechanism to algorithm design
Speaker: Nicole Immorlica

Computational considerations aside, welfare optimizing mechanism design has been solved, even under worst-case assumptions about the bidders' preferences. It has also been shown that, under worst-case assumptions, not all welfare problems that can be efficiently approximated can also be approximated in a mechanism design setting. On the other hand, Bayesian information about the agents' preferences enables very general, black-box reductions from mechanism to algorithm design. This lecture will survey work on this frontier, outlining challenges in going beyond the fully Bayesian model and the welfare objectives.

Non-linear objectives in mechanism design
Speaker: Shuchi Chawla (University of Wisconsin-Madison)

The mechanism design literature commonly focuses on the welfare and revenue objectives. Less is known for other objectives and typically results are negative, e.g. for minimizing makespan in scheduling jobs to strategic machines. Here, too, the Bayesian perspective has provided ways to circumvent worst-case impossibility results. This lecture will survey work on mechanism design with general objectives.

Price of Anarchy of Practical Auctions
Speaker: Eva Tardos (Cornell)

Auctions used in practice, such as the generalized second price auction of sponsored search, are often not optimal theoretically. Recent work has quantified the loss in objective, e.g. welfare, of using such suboptimal auctions. This lecture will survey this work, outlining challenges in analyzing incomplete information settings.