Conference proceeding
Deferred-Acceptance Auctions for Multiple Levels of Service
EC'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, pp 21-38
01 Jan 2017
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
Deferred-acceptance (DA) auctions are mechanisms that are based on backward-greedy algorithms and possess a number of remarkable incentive properties, including implementation as an obviously-strategyproof ascending auction. All existing work on DA auctions considers only binary single-parameter problems, where each bidder either "wins" or "loses." This paper generalizes the DA auction framework to non-binary settings, and applies this generalized framework to obtain approximately welfare-maximizing DA auctions for a number of basic mechanism design problems: multiunit auctions, problems with polymatroid constraints or multiple knapsack constraints, and the problem of scheduling jobs to minimize their total weighted completion time. Our results require the design of novel backward-greedy algorithms with good approximation guarantees.
Metrics
Details
- Title
- Deferred-Acceptance Auctions for Multiple Levels of Service
- Creators
- Vasilis Gkatzelis - Drexel UniversityEvangelos Markakis - Athens University of Economics and BusinessTim Roughgarden - Stanford UniversityAssoc Comp Machinery
- Publication Details
- EC'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON ECONOMICS AND COMPUTATION, pp 21-38
- Publisher
- Assoc Computing Machinery
- Number of pages
- 18
- Grant note
- CCF-1216073; CCF-1161813; CCF-1408635; CCF-1524062 / National Science Foundation; National Science Foundation (NSF)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000628648900003
- Scopus ID
- 2-s2.0-85025815729
- Other Identifier
- 991019302020704721
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
- Computer Science, Artificial Intelligence
- Computer Science, Theory & Methods
- Economics
- Mathematics, Applied
- Operations Research & Management Science