Philosophy Faculty Database
Philosophy
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Philosophy > Faculty    Search Help Login pdf version printable version 

Publications [#236193] of Vincent Conitzer

Duke :: Philosophy :: Faculty :: Vincent Conitzer

Conference articles PUBLISHED

  1. Conitzer, V; Sandholm, T, Incremental mechanism design, edited by Veloso, MM, IJCAI International Joint Conference on Artificial Intelligence (December, 2007), pp. 1251-1256 [html].
    (last updated on 2024/03/28)

    Abstract:
    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 University * Arts & Sciences * Philosophy * Faculty * Staff * Grad * Reload * Login