Speaker: Robert Kleinberg

Robert Kleinberg, Cornell, talks about Converting any algorithm into an incentive-compatible mechanism".

• Date: November 19, 2010
• Time: 1:00 pm
• Location: CSIC 2107

Does the complexity of algorithms increase dramatically when redesigning them to account for the incentives of selfish users? 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