Converting any Algorithm into an Incentive-Compatible Mechanism

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 identify two broad settings in which such generic procedures exist. First, I will present a reduction that removes the computational overhead of computing payments in truthful mechanisms: it transforms any monotone allocation function into a randomized, truthful-in-expectation mechanism that evaluates the allocation function only once. Second, I will present 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 first result is joint work with Moshe Babaioff and Alex Slivkins; the second result is joint work with Jason Hartline and Azarakhsh Malekian.

发言人详细信息

Robert Kleinberg is an Assistant Professor of Computer Science at Cornell University. His research studies the design and analysis of algorithms, and their applications to electronic commerce, networking, information retrieval, and other areas. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies, where he assisted in designing the world’s largest Internet Content Delivery Network. He is the recipient of a Microsoft Research New Faculty Fellowship, an Alfred P. Sloan Foundation Fellowship, and an NSF CAREER Award.

日期：
演讲者：
Robert Kleinberg
所属机构：
Cornell University