Reducing (Bayesian) Mechanism Design to Algorithm Design



Robert Kleinberg
Cornell, Department of Computer Science

Monday August 30, 2010
4:00 PM,
5130 Upson Hall



Does algorithm design become harder in the presence of incentive constraints?  The theory of algorithmic mechanism design is largely founded on the presumption that the answer is affirmative, a presumption that has been rigorously confirmed under various interpretations of the question.  This is unfortunate, since it would be very convenient if there existed generic procedures to convert any algorithm into an incentive-compatible mechanism with little or no computational overhead.
    In this talk, I will present a broad setting in which such generic procedures exist.  I will describe a polynomial-time reduction transforming an arbitrary algorithm into a Bayesian incentive-compatible mechanism, given a suitable amount of information about the type distributions of agents.  The talk will be self-contained; no prior knowledge of mechanism design theory will be assumed.
    This is joint work with Jason Hartline and Azarakhsh Malekian.