The Performance of Deferred-Acceptance Auctions

Paul Dütting (), Vasilis Gkatzelis () and Tim Roughgarden ()
Additional contact information
Paul Dütting: Department of Mathematics, London School of Economics, London, WC2A 2AE, United Kingdom
Vasilis Gkatzelis: Department of Computer Science, Drexel University, Philadelphia, PA 19104
Tim Roughgarden: Department of Computer Science, Stanford University, Stanford, California 94305

Mathematics of Operations Research, 2017, vol. 42, issue 4, 897-914

Abstract: Deferred-acceptance auctions are mechanisms whose allocation rule can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal recently introduced these auctions and proved that they satisfy remarkable incentive guarantees: in addition to being dominant strategy and incentive compatible, they are weakly group-strategyproof and can be implemented by ascending-clock auctions. 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 what fraction of the optimal social welfare can be guaranteed by these auctions in two canonical problems, knapsack auctions and combinatorial auctions with single-minded bidders. For knapsack auctions, we prove a separation between deferred-acceptance auctions and arbitrary dominant-strategy incentive-compatible mechanisms. For combinatorial auctions with single-minded bidders, we design novel polynomial-time mechanisms that achieve the best of both worlds: the incentive guarantees of a deferred-acceptance auction, and approximation guarantees close to the best possible.

Keywords: single-parameter combinatorial auctions; deferred-acceptance auctions (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0835 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:4:p:897-914

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().