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.