Logo image
Back
Clock Auctions Augmented with Unreliable Advice
Preprint   Open access

Clock Auctions Augmented with Unreliable Advice

Vasilis Gkatzelis, Daniel Schoepflin and Xizhi Tan
arXiv.org
12 Aug 2024
DOI: https://doi.org/10.48550/arxiv.2408.06483
url
https://arxiv.org/abs/2408.06483View
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute,  Open

Abstract

Computer Science - Computer Science and Game Theory
We provide the first analysis of clock auctions through the learning-augmented framework. Deferred-acceptance clock auctions are a compelling class of mechanisms satisfying a unique list of highly practical properties, including obvious strategy-proofness, transparency, and unconditional winner privacy, making them particularly well-suited for real-world applications. However, early work that evaluated their performance from a worst-case analysis standpoint concluded that no deterministic clock auction can achieve much better than an $O(\log n)$ approximation of the optimal social welfare (where $n$ is the number of bidders participating in the auction), even in seemingly very simple settings. To overcome this overly pessimistic impossibility result, which heavily depends on the assumption that the designer has no information regarding the preferences of the participating bidders, we leverage the learning-augmented framework. This framework assumes that the designer is provided with some advice regarding what the optimal solution may be. This advice may be the product of machine-learning algorithms applied to historical data, so it can provide very useful guidance, but it can also be highly unreliable. Our main results are learning-augmented clock auctions that use this advice to achieve much stronger performance guarantees whenever the advice is accurate (known as consistency), while simultaneously maintaining worst-case guarantees even if this advice is arbitrarily inaccurate (known as robustness). Specifically, for the standard notion of consistency, we provide a clock auction that achieves the best of both worlds: $(1+\epsilon)$-consistency for any constant $\epsilon > 0$ and $O(\log n)$ robustness. We then also consider a much stronger notion of consistency and provide an auction that achieves the optimal trade-off between this notion of consistency and robustness.

Metrics

13 Record Views

Details

Logo image