Impossibility of No-Regret in Multi-Agent Bidding

Zongjun Yang, Rachitesh Kumar, Christian KroerarXiv 2026 · arXiv

TL;DR

In the high-stakes world of automated ad auctions, bidders use "pacing" algorithms to stretch their budgets across the day. This paper proves a sobering "impossibility result": it is computationally impossible for all bidders in a multi-agent system to simultaneously achieve "no-regret" performance while satisfying budget or ROI constraints. The authors show that when everyone tries to optimize at once, the system often falls into high-variance cycles that guarantee someone will always be left wishing they had bid differently.

What Problem Does This Paper Address?

Online advertising is powered by billions of repeated auctions. To manage these, advertisers use automated bidding agents that employ pacing. Pacing involves scaling a bidder's true value by a multiplier (e.g., bidding 50% of the true value) to ensure they don't blow their budget too early or fail to meet a target Return on Investment (ROI).

From the perspective of a single bidder, "no-regret" algorithms are well-understood; if the environment is stable, a bidder can easily find an optimal pacing strategy. However, in the real world, the "environment" consists of other automated bidders who are also constantly adjusting their pacing. This paper asks a fundamental question: Does there exist a pacing algorithm that leads to sub-linear regret for everyone when simultaneously deployed by every agent?

Methods

The authors tackle this problem using a mix of optimization theory, computational complexity, and dynamical systems analysis:

  1. Primal-Dual Framework: They interpret pacing multipliers as "dual variables" in an online optimization problem. This allows them to use the tools of convex duality to analyze bidder behavior.
  2. Regret Decomposition: They derive a novel deterministic lower bound for regret. Crucially, they show that a bidder's regret is directly tied to the variance of their pacing multipliers over time. If your bid-scaling factor is oscillating wildly, your regret is mathematically guaranteed to be high.
  3. Complexity Theory (PPAD-Hardness): To prove the impossibility result, the authors show that if a low-regret state could be reached efficiently, one could "extract" a pacing equilibrium from it. Since finding such an equilibrium is known to be PPAD-hard (a class of problems, like finding Nash equilibria, believed to be computationally intractable), achieving joint no-regret must also be impossible for any efficient algorithm.
  4. Simulation of Bidding Dynamics: The authors simulate common algorithms, including PID controllers and Online Mirror Descent (OMD), on a "Rock-Paper-Scissors" market instance to observe how they behave in practice.

The paper defines two primary auction environments for their analysis:

  • Setting 1: A standard stochastic setting with discrete item arrivals. Setting 1: Multi-Agent Bidding in Repeated Second-Price Auctions
  • Setting 2: A "fluid" setting where items are treated as a continuous mass, simplifying the mathematical analysis of the bidding dynamics. Setting 2: Multi-Agent Bidding in Repeated Fluid-Item Second-Price Auctions
Setting 1: Multi-Agent Bidding in Repeated Second-Price Auctions
Setting 2: Multi-Agent Bidding in Repeated Fluid-Item Second-Price Auctions

Datasets

The paper does not use large-scale real-world datasets. Instead, it relies on:

  • Synthetic Market Instances: Specifically, a three-bidder "Rock-Paper-Scissors" instance where bidder A beats B, B beats C, and C beats A. This setup is designed to trigger unstable, cyclic bidding behavior.
  • Hard Instances for Reductions: The authors construct specific, mathematically "hard" auction instances to prove their complexity results, building on existing theoretical benchmarks in the pacing equilibrium literature.

Key Insights and Ideas

  • Variance $\implies$ Regret: This is the "aha moment" of the paper. The authors prove that instability is not just an annoyance; it is a direct cause of regret. If a platform sees pacing multipliers oscillating, it is a "smoking gun" that bidders are suffering high regret.
  • The Equilibrium Extraction Trap: The reason we can't have joint no-regret is that if we did, we would have solved a problem (PPAD) that computer scientists believe is unsolvable in a reasonable amount of time.
  • Cycling is Inevitable: Even in very simple markets (just 3 bidders), standard algorithms like PID controllers—which are used everywhere in industry—fail to converge. Instead, they enter stable limit cycles or even chaotic orbits.

Key Results

  • The Impossibility Theorems (4.1 & 5.1): The authors prove that no polynomial-time bidding dynamic can guarantee sub-linear regret ($O(T^{1-\epsilon})$) for all bidders simultaneously. In these competitive settings, regret for at least one bidder must grow linearly with time ($O(T)$).
  • Linear Regret in Practice: Simulations show that for both budget-constrained and ROI-constrained bidders, common algorithms like OMD and PID controllers result in cumulative regret that climbs steadily and linearly, confirming the theoretical predictions.
  • Platform Implications: For ad platforms (like Google or Meta), this means they cannot generally promise all advertisers an outcome close to their "hindsight optimal" strategy if everyone is using automated bidding.

Limitations and Future Work

  • Pacing-Only Strategies: The results focus on "bid-scaling" (pacing) strategies. While these are the industry standard, the paper doesn't rule out the possibility of more complex, non-pacing strategies achieving better results (though this seems unlikely).
  • Market Assumptions: The hardness results rely on "hard" market instances. A promising future direction is identifying specific market structures (e.g., "smooth" or "monotone" markets) where joint no-regret might actually be possible.
  • Alternative Objectives: Since individual no-regret is impossible, future work could focus on optimizing aggregate metrics like "liquid welfare" or "platform revenue," which might be more stable than individual bidder satisfaction.

Summary updated

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.
BibTeX
@misc{yang2026impossibility,
  author = {Zongjun Yang and Rachitesh Kumar and Christian Kroer},
  title = {{Impossibility of No-Regret in Multi-Agent Bidding}},
  year = {2026},
  eprint = {2610.36666},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36666},
}
Figure