Revenue failures and collusion in combinatorial auctions and exchanges with VCG payments
Pages 1 - 14
Abstract
In 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 bidders misreport their true preferences in order to effect a better outcome for themselves. The VCG payment scheme is the canonical method for motivating the bidders to bid truthfully. We study two related problems concerning the VCG payment scheme: the problem of revenue guarantees, and that of collusion. The existence of such problems is known by many; in this paper, we lay out their full extent.
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 payment scheme (but not under a first price scheme); derive necessary and sufficient conditions for such an effective collusion to be possible under the VCG payment scheme; and (when nontrivial) study the computational complexity of deciding whether these conditions hold.
References
[1]
Lawrence Ausubel and Paul Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1, 2002. No. 1, Article 1.
[2]
Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi-unit combinatorial auctions. In Theoretical Aspects of Rationality and Knowledge (TARK), 2003.
[3]
Ed H. Clarke. Multipart pricing of public goods. Public Choice, 11:17-33, 1971.
[4]
Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. In UAI, 2002.
[5]
Vincent Conitzer and Tuomas Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In ACM-EC, 2004.
[6]
Rica Gonen and Daniel Lehmann. Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics. In ACM-EC, 2000.
[7]
J Green and J-J Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427-438, 1977.
[8]
Theodore Groves. Incentives in teams. Econometrica, 41:617-631, 1973.
[9]
Ron Lavi, Ahuva Mu'Alem, and Noam Nisan. Towards a characterization of truthful combinatorial auctions. In FOCS, 2003.
[10]
Daniel Lehmann, Lidian Ita O'Callaghan, and Yoav Shoham. Truth revelation in rapid, approximately efficient combinatorial auctions. JACM, 49(5):577-602, 2002.
[11]
Andreu Mas-Colell, Michael Whinston, and Jerry R. Green. Microeconomic Theory. Oxford University Press, 1995.
[12]
Noam Nisan. Bidding and allocation in combinatorial auctions. In ACM-EC, 2000.
[13]
Noam Nisan and Amir Ronen. Computationally feasible VCG mechanisms. ACM-EC, 2000.
[14]
David Parkes. iBundle: An efficient ascending price bundle auction. In ACM-EC, 1999.
[15]
Michael Rothkopf, Aleksandar Pekeč, and Ronald Harstad. Computationally manageable combinatorial auctions. Management Science, 44(8):1131-1147, 1998.
[16]
Tuomas Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135:1-54, 2002.
[17]
Tuomas Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. CABOB: A fast optimal algorithm for combinatorial auctions. In IJCAI, 2001.
[18]
W Vickrey. Counterspeculation, auctions, and competitive sealed tenders. J. Finance, 1961.
[19]
PeterWurman and MichaelWellman. AkBA: A progressive, anonymous-price combinatorial auction. In ACM-EC, 2000.
[20]
Makoto Yokoo. The characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol. In IJCAI, 2003.
- Revenue failures and collusion in combinatorial auctions and exchanges with VCG payments
Recommendations
Failures of the VCG mechanism in combinatorial auctions and exchanges
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systemsThe 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 ...
Revenue failures and collusion in combinatorial auctions and exchanges with vcg payments
EC '04: Proceedings of the 5th ACM conference on Electronic commerceValuation 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
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- IFMAS: The International Foundation for Multiagent Systems
- SIGAI: ACM Special Interest Group on Artificial Intelligence
- ATAL: The International Workshop on Agent Theories, Architectures, and Languages
- Siemens
- Microsoft Reasearch: Microsoft Reasearch
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 19 July 2004
Check for updates
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in