A Caltech Library Service

Inapproximability for VCG-Based Combinatorial Auctions

Buchfuhrer, Dave and Dughmi, Shaddin and Fu, Hu and Kleinberg, Robert and Mossel, Elchanan and Papadimitriou, Christos and Schapira, Michael and Singer, Yaron and Umans, Chris (2010) Inapproximability for VCG-Based Combinatorial Auctions. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings in Applied Mathematics . No.135. Association for Computing Machinery , New York, NY, pp. 518-536. ISBN 978-0-898717-01-3.

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.


Use this Persistent URL to link to this item:


The existence of incentive-compatible, computationally efficient mechanisms for combinatorial auctions with good approximation ratios is the paradigmatic problem in algorithmic mechanism design. It is believed that, in many cases, good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. In this paper, we prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. Our results are tight, hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits. We show two different techniques to obtain such lower bounds: one for deterministic mechanisms that attains optimal dependence on the number of players and number of items, and one that also applies to a class of randomized mechanisms and attains optimal dependence on the number of players. Both techniques are based on novel VC dimension machinery.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Mossel, Elchanan0000-0001-7812-7886
Additional Information:© 2010 SIAM.
Series Name:Proceedings in Applied Mathematics
Issue or Number:135
Record Number:CaltechAUTHORS:20100824-073813316
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19608
Deposited By: Tony Diaz
Deposited On:30 Aug 2010 16:55
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page