Efficient Bayesian Algorithmic Mechanism Design

Speaker  Brendan Lucier

Affiliation  University of Toronto

Host  Christian Borgs

Duration  01:02:57

Date recorded  24 January 2011

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.

©2011 Microsoft Corporation. All rights reserved.
> Efficient Bayesian Algorithmic Mechanism Design