Name
Abstract | ||
|---|---|---|
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 in-approximability 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.5555/1873601.1873646 | SODA |
Keywords | DocType | Volume |
algorithmic mechanism design,vcg-based combinatorial auction,complexity assumption,optimal dependence,good approximation ratio,vcg-based mechanism,combinatorial auction,attains optimal dependence,important class,incentive-compatible mechanism,good approximation,computational complexity,incentive compatibility,lower bound | Conference | 135 |
ISBN | Citations | PageRank |
978-0-89871-698-6 | 30 | 1.33 |
References | Authors | |
27 | 9 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dave Buchfuhrer | 1 | 49 | 2.18 |
| Shaddin Dughmi | 2 | 417 | 31.14 |
| Hu Fu | 3 | 310 | 23.33 |
| Robert Kleinberg | 4 | 2886 | 202.55 |
| Elchanan Mossel | 5 | 1725 | 145.16 |
| Christos H. Papadimitriou | 6 | 16671 | 3192.54 |
| Michael Schapira | 7 | 1122 | 79.89 |
| Yaron Singer | 8 | 516 | 37.15 |
| Christopher Umans | 9 | 879 | 55.36 |