Where: 1507 NSH
When: 2008-03-19 Noon
Speaker: Abe Othman
Title: Beyond the Revelation Principle: Manipulation-Optimal Mechanisms
Abstract:
Rational, self-interested agents will lie to a mechanism if it benefits them. Despite this, the revelation principle states that any outcome a mechanism implements can also be implemented by a mechanism where agents are motivated to tell the truth. In this paper, we introduce the concept of manipulation-optimal mechanisms: non-truthful mechanisms that always do as well as the best truthful mechanism, and strictly better if any agent fails to find/play its best manipulation (lie).
Though the existence of such a mechanism has been shown previously in an artificial context, we study how broadly the paradigm applies in general. We curtail it with an impossibility result: in a manipulation-optimal mechanism, each agent can have at most one manipulable type. For such settings, we show that manipulation-optimal mechanisms can exist if the goal is social welfare maximization, but not when agents are symmetric and the mechanism is anonymous. We also show that there exist anonymous manipulation-optimal mechanisms with the goal of affine welfare maximization, even with symmetric players.
We then explore a way around our impossibility result: natural restrictions on the agents’ strategies. We study the Generalized Second-Price auction used by Google, Yahoo!, and MSN to auction billions of dollars of search keywords annually. This mechanism has been criticized because it is manipulable. Under two common assumptions, however, we show that it is manipulation optimal. Thus, switching to a truthful mechanism could only be deleterious to profits.
Joint work with Tuomas Sandholm.
