Failures of the VCG mechanism in combinatorial auctions and exchanges


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Conitzer, V; Sandholm, T

Published Date

  • December 1, 2006

Published In

  • Proceedings of the International Conference on Autonomous Agents

Volume / Issue

  • 2006 /

Start / End Page

  • 521 - 528

Digital Object Identifier (DOI)

  • 10.1145/1160633.1160729

Citation Source

  • Scopus