Incremental mechanism design


Conference Paper

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 naïve (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.

Duke Authors

Cited Authors

  • Conitzer, V; Sandholm, T

Published Date

  • December 1, 2007

Published In

Start / End Page

  • 1251 - 1256

International Standard Serial Number (ISSN)

  • 1045-0823

Citation Source

  • Scopus