Christodoulou, G, Gkatzelis, V and Schoepflin, D
(2022)
Optimal Deterministic Clock Auctions and Beyond.
In: Innovations in Theoretical Computer Science.
|
Text
Optimal_Deterministic_Clock_Auctions_and_Beyond__Camera_ready_.pdf - Author Accepted Manuscript Download (605kB) | Preview |
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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 14 Jan 2022 11:21 |
| Last Modified: | 18 Jan 2023 21:17 |
| DOI: | 10.4230/LIPIcs.ITCS.2022.49 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3146182 |
Dimensions
Dimensions
