Eastern Great Lakes Theory Workshop Talk

Bayesian Algorithmic Mechanism Design

Brendan Lucier, University of Toronto

Saturday, October 9, 5:30-6:00pm

ABSTRACT

The principal problem in algorithmic mechanism design is in merging the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability. In this talk we will consider relaxing the common goal of (ex post) 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. We also show that, for the stronger goal of constructing IC mechanisms, such a general reduction is not possible: any polytime reduction must incur a certain constant-factor loss in approximation ratio for some algorithms.

Slides

Speaker Bio

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.

< Schedule < EaGL-III homepage