Vincent Conitzer
Tuomas Sandholm
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.
- A. Archer and E. Tardos. Truthful mechanisms for one-parameter agents. In FOCS, 2001. Google Scholar
Digital Library
- A. Archer and E. Tardos. Frugal path mechanisms. In SODA, 991--999, 2002. Google ScholarDigital Library
- L. M. Ausubel and P. Milgrom. The lovely but lonely Vickrey auction. In P. Cramton. Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions, chapter 1. MIT Press, 2006.Google Scholar
- M. Babaioff, R. Lavi, and E. Pavlov. Mechanism design for single-value domains. In AAAI, 2005. Google ScholarDigital Library
- E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.Google ScholarCross Ref
- Y. Fujishima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In IJCAI, 548--553, 1999. Google ScholarDigital Library
- M. Garey and D. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.Google ScholarDigital Library
- J. Green and J.-J. Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427--438, 1977.Google ScholarCross Ref
- T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.Google ScholarCross Ref
- R. Lavi, A. Mu'Alem, and N. Nisan. Towards a characterization of truthful combinatorial auctions. In FOCS, 574--583, 2003. Google ScholarDigital Library
- D. Lehmann, L. I. O'Callaghan, and Y. Shoham. Truth revelation in rapid, approximately efficient combinatorial auctions. Journal of the ACM, 49(5):577--602, 2002. Google ScholarDigital Library
- A. Mu'alem and N. Nisan. Truthful approximate mechanisms for restricted combinatorial auctions. In AAAI, 379--384, 2002. Google ScholarDigital Library
- D. Parkes and G. Schoenebeck. GROWRANGE: Anytime VCG-based mechanisms. In AAAI, 34--41, 2004. Google ScholarDigital Library
- D. Parkes and J. Shneidman. Distributed implementations of generalized Vickrey-Clarke-Groves auctions. In AAMAS, 261--268, 2004. Google ScholarDigital Library
- K. Roberts. The characterization of implementable social choice rules. In J.-J. Laffont, editor, Aggregation and Revelation of Preferences. North-Holland Publishing Company, 1979.Google Scholar
- M. Rothkopf, A. Pekeč, and R. Harstad. Computationally manageable combinatorial auctions. Management Science, 44(8):1131--1147, 1998. Google ScholarDigital Library
- M. E. Saks and L. Yu. Weak monotonicity suffices for truthfulness on convex domains. In ACM-EC, 286--293, 2005. Google ScholarDigital Library
- T. Sandholm. Issues in computational Vickrey auctions. International Journal of Electronic Commerce, 4(3):107--129, 2000. Early version appeared in ICMAS-96. Google ScholarDigital Library
- T. Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135:1--54, Jan. 2002. Google ScholarDigital Library
- W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.Google ScholarCross Ref
- M. Yokoo. The characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol. In IJCAI, 733--742, 2003. Google ScholarDigital Library
- M. Yokoo, Y. Sakurai, and S. Matsubara. Robust combinatorial auction protocol against false-name bids. Artificial Intelligence, 130(2), 2004. Google ScholarDigital Library
Index Terms
- Failures of the VCG mechanism in combinatorial auctions and exchanges
Recommendations
Revenue failures and collusion in combinatorial auctions and exchanges with VCG payments
AAMAS'04: Proceedings of the 6th AAMAS international conference on Agent-Mediated Electronic Commerce: theories for and Engineering of Distributed Mechanisms and SystemsIn a combinatorial auction, there are multiple items for sale, and bidders are allowed to place a bid on a bundle of these items rather than just on the individual items. A key problem in this and similar settings is that of strategic bidding, where ...
Competing Combinatorial Auctions
Combinatorial auctions are auctions in which bids can be submitted on sets of items, rather than just on individual items. These auctions are generally beneficial to both auctioneers and bidders, as they allow bidders to express their synergies for sets ...
We investigate whether revenue-maximizing auctioneers selling heterogeneous items will allow for combinatorial bidding in the presence of auctioneer competition. We compare the choice of auction format by two competing auctioneers with that of a single ...
Valuation Compressions in VCG-Based Combinatorial Auctions
The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful direct-revelation mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism. For many ...
Comments