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.

Subjects: 7.1 Multi-Agent Systems; 7. Distributed AI

Submitted: Oct 16, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.