Title
The performance of deferred-acceptance auctions
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ütting1316.31
Vasilis Gkatzelis213714.77
Tim Roughgarden34177353.32