Failures of the VCG mechanism in combinatorial auctions and exchanges
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.
