Valuation compressions in VCG-based combinatorial auctions

Dütting P, Henzinger MH, Starnberger M. 2018. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Dütting, Paul; Henzinger, MonikaISTA ; Starnberger, Martin
Abstract
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 valuation spaces, computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency.
Publishing Year
Date Published
2018-05-01
Journal Title
ACM Transactions on Economics and Computation
Publisher
Association for Computing Machinery
Volume
6
Issue
2
Article Number
5
ISSN
eISSN
IST-REx-ID

Cite this

Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 2018;6(2). doi:10.1145/3232860
Dütting, P., Henzinger, M. H., & Starnberger, M. (2018). Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. Association for Computing Machinery. https://doi.org/10.1145/3232860
Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2018. https://doi.org/10.1145/3232860.
P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” ACM Transactions on Economics and Computation, vol. 6, no. 2. Association for Computing Machinery, 2018.
Dütting P, Henzinger MH, Starnberger M. 2018. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.
Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.” ACM Transactions on Economics and Computation, vol. 6, no. 2, 5, Association for Computing Machinery, 2018, doi:10.1145/3232860.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1310.3153

Search this title in

Google Scholar