arXiv preprint ·
Impossibility of No-Regret in Multi-Agent Bidding
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We consider $T$ repeated second-price auctions across $n$ pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective budget or return-on-investment constraints. Therefore, in the prominent internet auction systems where buyers simultaneously deploy pacing algorithms or automated bidding agents, we cannot hope to achieve joint no-regret guarantees in general. We establish a deterministic relationship that high variance in online bidding systems implies high regret. By showing that one can extract a pacing equilibrium from a low-variance system, we prove PPAD-hardness of attaining joint no-regret. For several widely used bidding algorithms, we also show evidence from dynamical systems and numerical simulations that they can indeed display high-variance behavior through cycling, even on simple market instances.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
PDE-Based Bounds on Optimal Exponents in Active Simple Hypothesis Testing
What Can Firms Do in the Face of Model Distillation?
Vendster: An Evaluation Arena to Investigate How Forecasting Tool Quality Affects LLM Agent Behaviors in Buyer-Vendor Negotiation
Conservative Policy Iteration For Zero-Sum POSGs
Game-Theoretic Foundations for Undiscounted Bisimulation Metrics
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.