Efficient Bayesian Algorithmic Mechanism Design

  • Brendan Lucier | University of Toronto

The principal problem in algorithmic mechanism design is to merge the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability. In this talk we will consider the problem of designing computationally feasible mechanisms when we relax the common goal (in Computer Science) of dominant strategy incentive compatibility (IC) to Bayesian incentive compatibility (BIC), where truthtelling is a Bayes-Nash equilibrium.

For welfare maximization in single-parameter agent settings, we give a general black-box reduction that turns any approximation algorithm into a BIC mechanism with essentially the same approximation factor and computational efficiency. We also show that, for the stronger goal of constructing IC mechanisms, such a general transformation is not possible: any polynomial time reduction must incur a certain constant-factor loss in approximation quality for some algorithms.

Based on joint work with Jason Hartline, Shuchi Chawla, and Nicole Immorlica.

发言人详细信息

Brendan Lucier received his B.Math and M.Math from the University of Waterloo, and is currently pursuing a Ph.D from the University of Toronto under the advisement of Mike Molloy and Allan Borodin. His research is focused mainly on computational issues in mechanism design and the theory of social networks.

接下来观看