Incremental Mechanism Design

Vincent Conitzer, Tuomas Sandholm

Mechanism design has traditionally focused almost exclusively on the design of truthful mechanisms. There are several drawbacks to this: 1. in certain settings (e.g. voting settings), no desirable strategy-proof mechanisms exist; 2. truthful mechanisms are unable to take advantage of the fact that computationally bounded agents may not be able to find the best manipulation, and 3. when designing mechanisms automatically, this approach leads to constrained optimization problems for which current techniques do not scale to very large instances. In this paper, we suggest an entirely different approach: we start with a naive (manipulable) mechanism, and incrementally make it more strategy-proof over a sequence of iterations. We give examples of mechanisms that (variants of) our approach generate, including the VCG mechanism in general settings with payments, and the plurality-with-runoff voting rule. We also provide several basic algorithms for automatically executing our approach in general settings. Finally, we discuss how computationally hard it is for agents to find any remaining beneficial manipulation.