Valuation compressions in VCG-based combinatorial auctions

DOI10.1007/978-3-642-45046-4_13zbMATH Open1406.91172arXiv1310.3153OpenAlexW2891591616MaRDI QIDQ2937754FDOQ2937754

Authors: Paul Dütting, Martin Starnberger, Monika R. Henzinger 

Publication date: 12 January 2015

Published in: Web and Internet Economics (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/1310.3153

Recommendations

• Computationally feasible VCG mechanisms
• Limitations of VCG-based mechanisms
• Limitations of VCG-based mechanisms
• Inapproximability for VCG-based combinatorial auctions
• Bundling equilibrium in combinatorial auctions

zbMATH Keywords

VCG mechanismcombinatorial auctions

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cited In (9)

• Expressiveness and robustness of first-price position auctions
• Limitations of VCG-based mechanisms
• Best-response dynamics in combinatorial auctions with item bidding
• Simultaneous auctions without complements are (almost) efficient
• Exploring the VCG mechanism in combinatorial auctions: the threshold revenue and the threshold-price rule
• Algorithms as mechanisms: the price of anarchy of relax and round
• The combinatorial world (of auctions) according to GARP
• Title not available (Why is that?)
• Limitations of VCG-based mechanisms

This page was built for publication: Valuation compressions in VCG-based combinatorial auctions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2937754)