Impossibility of No-Regret in Multi-Agent Bidding

Zongjun Yang; Rachitesh Kumar; Christian Kroer

cs.GTOct 27, 2026

Impossibility of No-Regret in Multi-Agent Bidding

Authors: Zongjun Yang, Rachitesh Kumar, Christian Kroer

Organizations: Columbia University. · Carnegie Mellon University.

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.

Figures & tables

Figure 1: Cycling of pacing multipliers under the PID dynamics. Left: the pacing multipliers

\alpha_{i}(t)

in a time segment. Right: orbits of

(\alpha_{1}(t),\alpha_{2}(t))

from three different initializations.

Figure 2: Cumulative regret of each bidder under the PID dynamics.

Figure 3: Pacing multipliers under Euclidean OMD (left) and entropic OMD (right) with a fixed learning rate.

Figure 4: Fluid regret of each bidder under Euclidean OMD (left) and entropic OMD (right), with

\eta

proportional to

1/\sqrt{T}

Figure 5: Cycling of pacing multipliers of value maximizers under the PID dynamics. Left: the pacing multipliers

\alpha_{i}(t)

in a time segment. Right: orbits of

(\alpha_{1}(t),\alpha_{2}(t))

from three different initializations.

Figure 6: Cumulative regret of each value maximizer under the PID dynamics.

Figure 7: Pacing multipliers of value maximizers under Euclidean OMD (left) and entropic OMD (right) with a fixed learning rate.

Figure 8: Fluid regret of bidder 1 under Euclidean OMD (left) and entropic OMD (right), with

\eta

proportional to

1/\sqrt{T}

; the other two value maximizers have nearly identical regret.

Regret Minimization

Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.

See all 113 papers

Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback
May 27, 2026Benjamin Heymann, Otmane SakhiGame Theory Automated Bidding
Criteo AI Lab
Learning to Bid in Discriminatory Auctions with Budget Constraints
Jun 28, 2026Negin Golrezaei, Sourav SahooGame Theory Automated Bidding
Sloan School of Management, Massachusetts Institute of Technology · Operations Research Center, Massachusetts Institute of Technology
Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions
May 21, 2026Luigi Foscari, Matilde Tullii, Vianney PerchetGame Theory Automated Bidding
LAILA, Università degli Studi di Milano · Fairplay Team, Crest-Ensae, IP Paris · Fairplay Team, Crest-Ensae, IP Paris, CRITEO AI Team, Paris

May 27, 2026J/K move · Enter open · S save

Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback

Benjamin Heymann, Otmane Sakhi

Criteo AI Lab

Game Theory Automated Bidding

Open paper AskPDF arXiv

We study the problem of learning to bid when the bidder's value is dynamic, i.e., when the current value depends on past outcomes. Specifically, we consider a bidder participating in repeated second-price auctions whose value depends on the time elapsed since their last successful bid, with auctions arriving in continuous time and only aggregated feedback revealed at the end of the horizon. Such a bidder must (1) balance the immediate benefit of winning the current auction against its impact on future values and (2) learn unknown environmental parameters. We derive regret bounds for a class of learning methods that combine plug-in estimators with a differential-equation characterization of the optimal policy, and show that a specific confidence bound algorithm learns the optimal policy with a near optimal regret of

\widetilde{O}(\log N)

for piecewise linear primitives, and

\widetilde{O}(N^{1/3})

for general, smooth primitives, achieving these regrets without explicit randomization. These theoretical results are supported by numerical experiments.

Abstract

Regret Minimization

Explore similar work

Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback

Learning to Bid in Discriminatory Auctions with Budget Constraints

Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions