PaperlayerView exact revision on arXiv

Source-linked AI summary

Impossibility of No-Regret in Multi-Agent Bidding

Zongjun Yang, Rachitesh Kumar, Christian Kroer

arXiv:2610.36666v1cs.GTcs.CCcs.LG

TL;DR

When bidders’ automated decisions affect one another, it is unclear whether all can achieve sublinear regret while meeting budget or ROI constraints. The paper links regret to pacing-multiplier variance and uses that connection to establish a computational barrier. Under its complexity assumption, efficient dynamics cannot guarantee sublinear regret and constraint violation for every bidder.

  • Problem

    In multi-agent auctions, bidders’ algorithms adapt to outcomes that depend on one another, leaving unclear whether every bidder can receive no-regret guarantees under budget or ROI constraints.

    Source: §1 · p. 2

  • Method

    The paper derives a regret lower bound involving pacing-multiplier variance and uses the connection between low variance and pacing equilibria to prove computational hardness.

    Source: §1.1 · pp. 2–3

  • Results

    Unless PPAD-hard problems can be solved by polynomial-time randomized algorithms, no polynomial-time multi-agent bidding dynamic can guarantee O(n−εT) regret and constraint violation for every bidder, for any fixed ε > 0.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    Under the stated complexity assumption, platforms cannot generally guarantee every constrained bidder sublinear regret through efficient multi-agent bidding dynamics.

    Source: §1 · p. 2, §1.1 · p. 3

    The hardness result applies to sufficiently large horizons polynomial in n, but not exponentially many auctions, when bidders could compute a pacing equilibrium by brute force.

    Source: §4.1 · p. 11

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether pacing agents can simultaneously achieve sublinear regret under budget or ROI constraints when their bidding decisions affect one another. It answers that question with a variance-based regret connection, a computational impossibility result, and evidence of cycling in common algorithms.

1 Introduction

  • Unlike single-bidder settings with exogenous competition, multi-agent bidding lets each bidder’s adaptive environment depend on other bidders’ decisions, leaving platform guarantees under long-term constraints unclear.The central question is whether one pacing algorithm can yield sublinear regret when every agent deploys it.Source: §1 · pp. 1–2

1.1 Our Contributions

  • Under smoothness, a bidder’s regret is lower-bounded by variance in its pacing multipliers, up to slack and negligible errors; cycling therefore implies high regret.The relationship also extends to general online resource-allocation systems with multiple agents running primal-dual algorithms.Source: §1.1 · p. 2
  • Unless PPAD-hard problems admit polynomial-time randomized solutions, efficient dynamics cannot guarantee sublinear regret for every bidder while respecting budget or ROI constraints.The result rules out extending single-bidder stationary-i.i.d. sublinear-regret guarantees to the competitive multi-agent setting in general.Source: §1.1 · p. 3
  • In simulations with three bidders, PID controllers and online dual mirror descent cycle under both budget and ROI constraints, with every bidder’s variance and regret growing linearly over time.The instances use the construction of Paes Leme et al. [42].Source: §1.1 · p. 3

1.2 Related Work

  • Existing pacing-equilibrium hardness does not rule out low-regret behavior away from equilibrium, while positive results rely on added market structure or group-level objectives.Examples include a strong monotonicity assumption and liquid-welfare guarantees rather than the same individual hindsight-regret benchmark.Source: §1.2 · pp. 4–5

2 Preliminaries

The preliminaries define repeated second-price auctions, bidder objectives and constraints, and the pacing strategies used in the analysis. Regret compares realized performance with an individual hindsight benchmark against the realized competition.

2 Preliminaries

  • In each of T sequential second-price auctions, bidders submit bids, the highest bidder receives the item, and the winner pays the second-highest bid.Values are bounded, and the value vectors are i.i.d. across rounds while allowing within-round correlations across bidders.Source: §2 · p. 5
  • The analysis considers utility maximizers with per-round budgets and value maximizers whose total value must meet an ROI target relative to total expenditure.The two bidder types optimize different objectives under their respective expenditure constraints.Source: §2 · p. 5
  • Pacing scales each bidder’s value by a multiplier chosen before that round’s private value is observed, and may be chosen centrally.Individual regret is the gap between the hindsight-optimal objective, given competing bids, and the bidder’s realized utility or value.Source: §2 · pp. 6–7
  • In the fluid-item setting, each round contains value points weighted by their distributional mass, and bidders use one pacing multiplier uniformly across those points.The fluid setting also has a corresponding individual hindsight benchmark and regret.Source: §2 · pp. 7–8

3 A General Regret Lower Bound

The section decomposes primal regret for online constrained optimization and identifies when multiplier instability forces regret. Its key condition is strong convexity of the dual losses, corresponding to smoothness of reward in spending.

3 A General Regret Lower Bound

  • For general online resource allocation, primal regret splits into the dual-regret linearization gap, complementary slack, and duality gap.The deterministic decomposition applies broadly to primal-dual decision rules; the duality gap is bounded by the maximum per-round reward under compactness.Source: §3 · pp. 8–9
  • When dual losses are strongly convex, the linearization gap has a lower bound involving the variance of the dual iterates.The theorem applies on an interval containing the iterates and the optimal dual solution.Source: §3 · pp. 9–10
  • Because dual variables map to pacing multipliers, smooth reward in spending makes multiplier variance relevant; for feasible bidders, high variance implies high regret.The result also supports the paper’s hardness argument and its evidence that cycling algorithms can incur large regret.Source: §3 · p. 10

4 Impossibility for Utility Maximizers with Budgets

For utility-maximizing bidders with budgets, the paper studies whether all agents can achieve no-regret while remaining budget-feasible. It establishes a computational impossibility for polynomial-time dynamics under a PPAD-hardness assumption, with a stated horizon boundary.

4 Impossibility for Utility Maximizers with Budgets

  • The section presents theoretical hardness results and numerical evidence that common bidding algorithms can display high variance and incur high regret.The overview focuses on utility maximizers with budgets.Source: §4 · p. 10

4.1 Computational Complexity of Joint No-Regret

  • Unless PPAD-hard problems are solvable by polynomial-time randomized algorithms, no polynomial-time dynamic guarantees all bidders no-regret and budget-feasible up to O(T/poly(n)) error in the stochastic and fluid settings.The result is stated in Theorem 4.1.Source: §4.1 · pp. 10–11
  • The hardness assumption rules out polynomial-time randomized solutions to PPAD-hard problems with probability at least 2/3.The paper identifies this as the standard randomized version of PPAD ≠ P.Source: §4.1 · p. 10
  • The theorem applies to sufficiently large auction horizons polynomial in n, ruling out regret guarantees that diminish at a polynomial rate.The hardness result does not cover horizons exponentially large in n, when bidders could use rounds to agree on a pacing equilibrium by brute force.Source: §4.1 · p. 11

Appendix B.

Appendix B connects low regret to extractable approximate fluid SPPEs and establishes hardness using regularized instances and a stochastic-to-fluid reduction. Section 4.2 presents cycling and growing-regret behavior under PID and OMD dynamics.

Appendix B.

  • F0 selects two bidders uniformly and draws their values independently from Uniform[0, v̄], spreading values continuously to give fluid dual losses curvature.Source: Appendix B · p. 11
  • Low fluid regret and approximate budget feasibility allow an approximate fluid SPPE to be extracted when budget violation, multiplier variance, and slack are sufficiently small.Source: Appendix B · p. 12
  • Computing a γ-approximate fluid SPPE remains PPAD-hard for distributions mixing a hard atomic instance with a small amount of the regularizer F0.Source: Appendix B · p. 12
  • A stochastic bidding dynamic can be simulated to obtain a fluid process with nearly the same regret and expenditure up to sublinear terms, with high probability.Source: Appendix B · p. 13

4.2 Evidence of High Variance in Bidding Systems

  • With a fixed learning rate, pacing multipliers oscillate under both Euclidean and entropic OMD.Source: §4.2 · p. 15, Figure 3 · p. 15
  • Each bidder’s regret still grows linearly in T when the stepsize is chosen with knowledge of the horizon.Source: §4.2 · p. 15

5 Impossibility for Value Maximizers with ROI Targets

For ROI-constrained value maximizers, the section outlines how low regret and small ROI violations can yield an approximate fluid equilibrium, then examines cycling and regret under PID and mirror-descent dynamics.

5.1 Computational Complexity of Joint No-Regret

  • The proof handles unbounded dual variables by projecting iterates onto a bounded interval, which restores strong convexity on that interval.The section also introduces a regularizer that randomly gives bidders values at price zero to bound dual minimizers and control relative ROI errors.Source: §5.1 · pp. 16–17
  • Low regret and small ROI violations control key terms from which an approximate fluid autobidding equilibrium can be extracted efficiently.The proof plan also establishes hardness for computing an approximate equilibrium under regularization and reduces from fluid to stochastic i.i.d. auctions.Source: §5.1 · pp. 17–18

5.2 Evidence of High Variance in Bidding Systems

  • Under PID dynamics, the pacing multiplier increases when value exceeds payment and decreases otherwise; the simulations reproduce cycling and show cumulative regret growth.Figure 5 shows multiplier cycling; Figure 6 reports cumulative regret for each value maximizer.Source: Figure 5 · p. 18, §5.2 · p. 19, Figure 6 · p. 19
  • With a fixed learning rate, Euclidean and entropic OMD multipliers oscillate, while fluid regret grows linearly in T.The other two value maximizers have nearly identical regret.Source: §5.2 · pp. 19–20, Figure 7 · p. 19, Figure 8 · p. 20

A.1 Derivation of the Dual for Utility Maximizers with Budgets

The appendix sets up the utility-maximizer budget benchmark and records bounds on dual minimizers and the duality gap.

A.1 Derivation of the Dual for Utility Maximizers with Budgets

  • The hindsight benchmark is represented with a binary action whose reward is value minus payment and whose cost is payment, under bidder i’s budget.The passage identifies the reward, cost, and budget parameterization but does not provide the full displayed benchmark.Source: §A.1 · p. 25
  • Convexity implies that both dual objectives attain their minima in [0, μ̄_i].The right derivative at μ̄_i is bounded below by zero.Source: §A.1 · p. 25
  • For the stated reward–cost sets, both duality gaps lie in [0, v̄].Source: §A.1 · p. 25

A.2 Derivation of the Dual for Value Maximizers with ROI Targets

The appendix develops the ROI-constrained dual and supporting lemmas, including a bounded duality gap, equivalence between pacing bids and the algorithm, and a comparison of regret quantities.

A.2 Derivation of the Dual for Value Maximizers with ROI Targets

  • For ROI targets, the hindsight benchmark uses value as reward and ROI-adjusted payment minus value as cost; the dual minimum exists under the stated coercivity condition.For the specified distribution, the dual objective attains its minimum.Source: §A.2 · p. 25

A.3 Proof of Lemma 3.1

  • The duality gap for the stated ROI reward–cost sets lies in [0, v̄].The general proposition bounds the gap by v̄ when each round’s reward–cost set is compact; its proof rounds a convex relaxation with at most one round incurring reward loss.Source: §A.2 · p. 26, §A.3 · p. 26

A.4 Proof of Lemma 3.2

  • Bidding b_i,t = α_i,t v_i,t is equivalent to Algorithm 1 because its dual-variable maximizers are exactly the second-price allocations under that bid.For ROI targets, the dual variable is μ_i,t = 1/(α_i,t r_i − 1).Source: §A.4 · p. 26

A.5 Proof of Lemma 3.3

  • For any comparator μ ≥ 0, the regret quantity R_D(μ) is bounded above by its extended version, eR_D(μ).The proof compares per-round dual losses using the same decision and sums the resulting inequalities.Source: §A.5 · pp. 26–27

A.6 Proof of Lemma 3.4

The proof fragment identifies two components of Lemma 3.4 and begins from each round’s maximizing decision.

A.6 Proof of Lemma 3.4

  • The lemma’s displayed decomposition labels a regret linearization gap and complementary slack.Source: §A.6 · p. 27
  • The proof uses that each round’s decision maximizes f_t(x) − μ_t a_t(x) over X.Source: §A.6 · p. 27
  • The proof then rearranges terms using the definitions of the extended and ordinary regret quantities.Source: §A.6 · p. 27

A.7 Proof of Theorem 3.1

The proof uses strong convexity to compare each dual loss along the segment from the current multiplier to the optimum, then derives the claimed inequality using a convexity bound and Lemma 3.4.

A.7 Proof of Theorem 3.1

  • Strong convexity makes the loss minus its quadratic term convex between each current multiplier and the optimum.The proof applies this convexity along the segment connecting the two points.Source: §A.7 · p. 28
  • A bound from Lemma 3.3 supplies the next inequality, after which the proof takes the segment parameter to zero.The proof then adds the corresponding quadratic difference to both sides.Source: §A.7 · p. 28
  • Expanding the square and using the identity in Lemma 3.4 yields the claimed inequality.Source: §A.7 · p. 28

B.1 Proof of Lemma 4.1

This section develops the proof machinery for efficient extraction of approximate fluid SPPEs and PPAD-hardness, using reductions between fluid and discrete markets and simulation and discretization tools. It outlines proof steps based on conditioning on the nonzero-value bidder pair, convexity, and bounded multiplier and dual variables.

B.1 Proof of Lemma 4.1

  • The proof establishes strong convexity of the dual loss for the constructed F0 regularizer.Source: §B.1 · p. 29
  • The text describes a construction in which approximate SPPE pacing multipliers use the average of online dual variables, and an offline fluid allocation is constructed by taking an average.Source: §B.1 · p. 30
  • Computing a γ-approximate fluid SPPE is PPAD-hard for distributions (1 − η)F1 + ηF0, for some constants η, γ ∈ (0, 1).Source: §B.1 · p. 33
  • Hardness persists for computing an approximate discrete SPPE when budget feasibility is relaxed, via a polynomial-time reduction to the unrelaxed notion.Source: §B.1 · p. 33
  • A γ-approximate fluid SPPE can yield a λ-approximate discrete SPPE by restriction to the m items when the stated parameter inequalities hold.The construction is polynomial, and the hard-instance family permits fixed γ and sufficiently small η independent of the instance.Source: §B.1 · pp. 34–35
  • A fluid process can be constructed by simulating a stochastic bidding dynamic and using its pacing multipliers and allocations.Source: §B.1 · p. 36

B.5 Discretization

  • The discretization proof uses F0,K in place of F0 in the mixture, with separate lemmas bounding discretization error and establishing strong-convexity-like properties.Lemma 4.3 also applies with F0,K.Source: §B.5 · p. 38

B.1 Proof of Lemma 4.1

  • The proof conditions on bidders i and j being the nonzero-value pair and integrates over bidder i’s value.It then invokes strong convexity of DF1, basic convexity, and bounds on the multiplier and dual variable; the excerpt does not state the resulting bound.Source: §B.5 · pp. 39–40

B.6 Proof of Theorem 4.1

The proof reduces a low-regret bidding process to an approximate fluid pacing equilibrium, then uses that extraction to contradict the assumed hardness of the source problem. It also establishes the computational and convexity ingredients used in this argument and in the related equilibrium-extraction lemma.

B.6 Proof of Theorem 4.1

  • The construction embeds the hard instance among s bidders, adds auxiliary bidders in a disjoint market component, and restricts the fluid process back to the original bidders.The restricted distribution is described as a mixture of the regularized distribution and the zero-value outcome.Source: §B.6 · p. 41
  • The reduction obtains a γ-approximate fluid SPPE with probability at least 3/4, yielding a polynomial-time algorithm for a PPAD-hard problem and a contradiction.The theorem assumes no polynomial-time randomized algorithm solves PPAD-hard problems.Source: §B.6 · pp. 40, 44

B.7 Computational Details

  • The reduction is implemented as a polynomial-time randomized algorithm that succeeds with probability greater than 2/3.The proof accounts for finite-support simulation and sampling error.Source: §B.7 · p. 44

C.1 Proof of Lemma 5.1

  • The regularizer F0 makes the dual loss strongly convex on [0, H], with a bound determined by the smallest competing pacing multiplier.The proof conditions on a selected bidder pair and lower-bounds the second derivative over the interval.Source: §C.1 · p. 45

C.2 Proof of Lemma 5.2

  • The proof constructs allocations from adjusted online allocations and averages them to extract an approximate fluid autobidding equilibrium from online history.The lemma states that extraction is efficient when its listed conditions hold.Source: §C.2 · pp. 45–46

C.3 Lemma C.1 and Its Proof

The appendix reduces a known hard discrete autobidding-equilibrium problem to a fluid setting, then develops simulation and discretization tools used in the analysis.

C.3 Lemma C.1 and Its Proof

  • The fluid-equilibrium problem with cap M is PPAD-hard by reduction from a hard discrete autobidding-equilibrium problem.The construction produces the discrete equilibrium in polynomially many operations; the source problem is PPAD-hard for sufficiently small constant approximation error.Source: §C.3 · pp. 48, 50
  • The reduction extracts a discrete approximate equilibrium from a fluid one when each bidder receives value at least b and has multiplier at most A.For the hard family, the proof establishes b = 1/16 and A = 6 < M.Source: §C.3 · pp. 48, 50, 51

C.4 Lemma C.2 and Its Proof

  • The proof simulates a stochastic bidding dynamic in the fluid setting and compares hindsight benchmarks when their optimal dual solutions lie in [0,H] with probability at least 1−ζ.The analysis uses scaled outcomes, which allocate min{1,P/pt} of the item at the same price.Source: §C.4 · p. 52

C.5 Discretization

  • Discretizing the regularizer preserves a strong-convexity-like bound under bounded opponent multipliers and price scaling.Lemma C.3 states the bound for H > 0, L > 1, P ≥ L v̄, and an opponent multiplier at most L.Source: §C.5 · pp. 53–54

C.6 Proof of Theorem 5.1

The proof shows that hypothetical simultaneous low regret and ROI violation for all bidders would yield a randomized solution to a PPAD-hard problem. This gives a conditional impossibility for polynomial-time bidding dynamics.

C.6 Proof of Theorem 5.1

  • Under the stated PPAD assumption, a polynomial-time bidding dynamic cannot guarantee low expected regret and low ROI violation for every bidder on every eligible instance.The contradiction argument supposes both quantities are small for all bidders and constructs an algorithm for the PPAD-hard source problem.Source: §C.6 · pp. 55, 61
  • The reduction embeds an s-bidder hard instance in a larger fluid market by adding a disjoint component of auxiliary bidders.The construction uses n = sr bidders and m = 15s/11 items for the original hard instance.Source: §C.6 · p. 55
  • If the original process has low regret and ROI violation, the extracted s-bidder fluid process inherits those properties and yields an approximate fluid equilibrium with probability at least 3/4.The reduction discards exceptional rounds and caps pacing multipliers before checking the extraction conditions.Source: §C.6 · pp. 55, 57, 58, 61

C.7 Computational Details

  • The computational details implement the reduction as a randomized polynomial-time algorithm that succeeds with probability at least 2/3.The finite-support fluid dual objective is convex and piecewise linear, so a minimizer is found by evaluating breakpoints and interval endpoints.Source: §C.7 · pp. 61–62
Loading 2610.36666v1…