Philosophy Faculty Database
Philosophy
Arts & Sciences
Duke University

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

Publications [#236233] of Vincent Conitzer

Duke :: Philosophy :: Faculty :: Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Conitzer, V; Sandholm, T, Failures of the VCG mechanism in combinatorial auctions and exchanges, Proceedings of the International Conference on Autonomous Agents, vol. 2006 (December, 2006), pp. 521-528, ACM Press [doi].
    (last updated on 2024/03/29)

    Abstract:
    The VCG mechanism is the canonical method for motivating bidders in combinatorial auctions and exchanges to bid truthfully. We study two related problems concerning the VCG mechanism: the problem of revenue guarantees, and that of collusion. The existence of these problems even in one-item settings is well-known; in this paper, we lay out their full extent in multi-item settings. We study four settings: combinatorial forward auctions with free disposal, combinatorial reverse auctions with free disposal, combinatorial forward (or reverse) auctions without free disposal, and combinatorial exchanges. In each setting, we give an example of how additional bidders (colluders) can make the outcome much worse (less revenue or higher cost) under the VCG mechanism (but not under a first price mechanism); derive necessary and sufficient conditions for such an effective collusion to be possible under the VCG mechanism; and (when nontrivial) study the computational complexity of deciding whether these conditions hold. Copyright 2006 ACM.


Duke University * Arts & Sciences * Philosophy * Faculty * Staff * Grad * Reload * Login