VC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension

Simple item page
dc.creatorMossel, Elchanan
dc.creatorPapadimitriou, Christos
dc.creatorSchapira, Michael
dc.creatorSinger, Yaron
dc.date2009-05-13
dc.date.accessioned2026-07-07T13:14:25Z
dc.date.available2026-07-07T13:14:25Z
dc.descriptionThe existence of incentive-compatible computationally-efficient protocols for combinatorial auctions with decent approximation ratios is the paradigmatic problem in computational 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. However, to date, researchers lack the machinery to prove such results. In this paper, we present a new approach that we believe holds great promise for making progress on this important problem. We take the first steps towards the development of new technologies for lower bounding the VC dimension of k-tuples of disjoint sets. We apply this machinery to prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. These results hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits.
dc.identifierhttps://arxiv.org/abs/0905.1995
dc.identifierhttp://arxiv.org/abs/0905.1995
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/230201
dc.subjectComputer Science and Game Theory
dc.subjectDiscrete Mathematics
dc.titleVC v. VCG: Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
dc.typetext

Files

Collections

arXiv