Valuation compressions in VCG-based combinatorial auctions

Paul Dütting, Monika Henzinger and Martin Starnberger

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

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 increased expressiveness can give rise to additional equilibria of poorer efficiency.

Keywords: algorithms; economics; theory; simplified mechanisms; combinatorial auctions with item bidding; price of anarchy (search for similar items in EconPapers)
JEL-codes: J1 (search for similar items in EconPapers)
Pages: 18 pages
Date: 2018-10-31
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Published in ACM Transactions on Economics and Computation, 31, October, 2018, 6(2). ISSN: 2167-8375

Downloads: (external link)
http://eprints.lse.ac.uk/87419/ Open access version. (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ehl:lserod:87419

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().