Clock Auctions Augmented with Unreliable Advice

We provide the first analysis of (deferred acceptance) clock auctions in the learning-augmented framework. These auctions satisfy a unique list of very appealing properties, including obvious strategyproofness, 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 perspective concluded that no deterministic clock auction with n bidders can achieve a O(log 1-ϵ n) approximation of the optimal social welfare for a constant ϵ > 0, even in very simple settings. This overly pessimistic impossibility result heavily depends on the assumption that the designer has no information regarding the bidders' values. Leveraging the learning-augmented framework, we instead consider a designer equipped with some (machine-learned) advice regarding the optimal solution; this advice can provide useful guidance if accurate, but it may be 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 maintaining worst-case guarantees even if this advice is arbitrarily inaccurate (known as robustness). Our first clock auction achieves the best of both worlds: (1+ϵ)-consistency for any desired constant ϵ > 0 and O(log n) robustness; we also extend this auction to achieve error tolerance. We then consider a much stronger notion of consistency, which we refer to as consistency ∞ , and provide an auction that achieves a near-optimal trade-off between consistency ∞ and robustness. Finally, using our impossibility results regarding this trade-off, we prove lower bounds on the "cost of smoothness," i.e., on the robustness that is achievable if we also require that the performance of the auction degrades smoothly as a function of the prediction error.