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 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(log1-ε n) approximation of the optimal social welfare for any ε>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 guarantees whenever the advice is accurate (consistency), while maintaining worst-case guarantees even if this advice is arbitrarily inaccurate (robustness). Our first clock auction achieves the best of both worlds: (1+ε)-consistency for any ε>0 and O(logn) 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 auctions 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 achievable robustness if we also require that the performance of the auction degrades smoothly as a function of the prediction error.