Abstract | ||
---|---|---|
Deferred-acceptance auctions are auctions for binary single-parameter mechanism design problems whose allocation rule can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal [2014] recently introduced these auctions and proved that they satisfy a remarkable list of incentive guarantees: in addition to being dominant-strategy incentive-compatible, they are weakly group-strategyproof, can be implemented by ascending-clock auctions, and admit outcome-equivalent full-information pay-as-bid versions. Neither forward greedy mechanisms nor the VCG mechanism generally possess any of these additional incentive properties. The goal of this paper is to initiate the study of deferred-acceptance auctions from an approximation standpoint. We study these auctions through the lens of two canonical welfare-maximization problems, in knapsack auctions and in combinatorial auctions with single-minded bidders. For knapsack auctions, we prove a separation between deferred-acceptance auctions and arbitrary dominant-strategy incentive-compatible mechanisms. While the more general class can achieve an arbitrarily good approximation in polynomial time, and a constant-factor approximation via forward greedy algorithms, the former class cannot obtain an approximation guarantee sub-logarithmic in the number of items m, even with unbounded computation. We also give a polynomial-time deferred-acceptance auction that achieves an approximation guarantee of O(log m) for knapsack auctions. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1287/moor.2016.0835 | Math. Oper. Res. |
Keywords | Field | DocType |
deferred-acceptance auctions,economics,general,single-parameter combinatorial auctions | Mathematical optimization,Mathematical economics,Computer science,Combinatorial auction,Microeconomics,Greedy algorithm,Common value auction,Vickrey–Clarke–Groves auction,Mechanism design,Knapsack problem,Time complexity,Binary number | Conference |
Volume | Issue | ISSN |
42 | 4 | 0364-765X |
Citations | PageRank | References |
7 | 0.48 | 28 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paul Dütting | 1 | 31 | 6.31 |
Vasilis Gkatzelis | 2 | 137 | 14.77 |
Tim Roughgarden | 3 | 4177 | 353.32 |