Logo der Universität Wien

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 VCG 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 the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes.

Grafik Top
Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)
Event Title
9th Conference on Web and Internet Economics (WINE 2013)
Theory and Applications of Algorithms
Event Location
Harvard University, Cambridge, MA, USA
Event Type
Event Dates
11-14 Dec 2013
December 2013
Grafik Top
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna