License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.49
URN: urn:nbn:de:0030-drops-156453
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15645/
Christodoulou, Giorgos ;
Gkatzelis, Vasilis ;
Schoepflin, Daniel
Optimal Deterministic Clock Auctions and Beyond
Abstract
We design and analyze deterministic and randomized clock auctions for single-parameter domains with downward-closed feasibility constraints, aiming to maximize the social welfare. Clock auctions have been shown to satisfy a list of compelling incentive properties making them a very practical solution for real-world applications, partly because they require very little reasoning from the participating bidders. However, the first results regarding the worst-case performance of deterministic clock auctions from a welfare maximization perspective indicated that they face obstacles even for a seemingly very simple family of instances, leading to a logarithmic inapproximability result; this inapproximability result is information-theoretic and holds even if the auction has unbounded computational power. In this paper we propose a deterministic clock auction that achieves a logarithmic approximation for any downward-closed set system, using black box access to a solver for the underlying optimization problem. This proves that our clock auction is optimal and that the aforementioned family of instances exactly captures the information limitations of deterministic clock auctions. We then move beyond deterministic auctions and design randomized clock auctions that achieve improved approximation guarantees for a generalization of this family of instances, suggesting that the earlier indications regarding the performance of clock auctions may have been overly pessimistic.
BibTeX - Entry
@InProceedings{christodoulou_et_al:LIPIcs.ITCS.2022.49,
author = {Christodoulou, Giorgos and Gkatzelis, Vasilis and Schoepflin, Daniel},
title = {{Optimal Deterministic Clock Auctions and Beyond}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {49:1--49:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15645},
URN = {urn:nbn:de:0030-drops-156453},
doi = {10.4230/LIPIcs.ITCS.2022.49},
annote = {Keywords: Auctions, Obvious Strategyproofness, Mechanism Design}
}
|
Keywords: |
|
Auctions, Obvious Strategyproofness, Mechanism Design |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
