Files and links (1)
Accepted (AM)Open Access (License Unspecified), Open
Journal article
The Performance of Deferred-Acceptance Auctions
Mathematics of operations research, v 42(4), pp 897-914
01 Nov 2017
Featured in Collection : UN Sustainable Development Goals @ Drexel
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.
Metrics
Details
- Title
- The Performance of Deferred-Acceptance Auctions
- Creators
- Paul Dutting - London Sch Econ, Dept Math, London WC2A 2AE, EnglandVasilis Gkatzelis - Drexel UniversityTim Roughgarden - Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
- Publication Details
- Mathematics of operations research, v 42(4), pp 897-914
- Publisher
- Informs
- Number of pages
- 18
- Grant note
- Swiss National Science Foundation; Swiss National Science Foundation (SNSF); European Commission Office of Naval Research PECASE; Office of Naval Research CCF-1016885; CCF-1215965 / National Science Foundation; National Science Foundation (NSF)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000414320800001
- Scopus ID
- 2-s2.0-85032884697
- Other Identifier
- 991019302290704721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Mathematics, Applied
- Operations Research & Management Science