CS Paper Radar

On the Role of Tie-Breaking Rules in the Convergence of Fictitious Play for Symmetric First-Price Auctions

Benjamin Heymann

cs.GT math.OC ·submitted 2026-09-16 15:53 UTC · v1

Abstract

We study continuous-time fictitious play in 2-bidder, symmetric first-price auctions with independently distributed discrete values and a discrete bid set. We first exhibit a minimal instance --- two bidders, two values, three positive bids --- on which fictitious play with the standard uniform-split tie-breaking rule does \emph{not} converge to the symmetric Bayes--Nash equilibrium: the equilibrium is unstable and the dynamics converge to a stable limit cycle far from the Nash equilibrium. We then show that a small modification of the tie-breaking rule --- awarding a payoff of zero to every bidder in case of a tie --- restores convergence: fictitious play converges to a Nash equilibrium of the modified game. This limit is an $ε$-equilibrium of the original auction in a broad range of settings.

Closest papers

Nearest neighbours by meaning across the whole index.

Nash Equilibria in Auctions with Pacing Strategies: Complexity and Inefficiency

cs.GT cs.CC ·2026-09-28 ·Aris Filos-Ratsikas, Charalampos Kokkalis, Mohamad Latifian
publishedtheory similarity 0.66
Abstract · 29 pages, to appear in The 22nd Conference on Web and Internet Economics (WINE 2026)

We introduce and study Auctions with Pacing Strategies (APS) games, a full-information model in which utility-maximizing bidders compete across many simultaneous first-price auctions, each choosing a single pacing multiplier that uniformly scales their values into bids. We settle three central questions. First, we show that there are instances that admit no approximate pure Nash equilibria. Then, we prove that the problem of deciding whether an APS game admits an (approximate) equilibrium is NP-complete in general, but can be solved in polynomial time if either the number of bidders or the number of items is fixed. Finally, when an equilibrium does exist, we characterize its inefficiency exactly, showing that both the Price of Anarchy and the Price of Stability equal $\frac{e}{e-1}$.

0.34

A 1.283 Price-of-Anarchy Bound for the Repeated Virtual First-Price Auction

cs.GT econ.TH ·2026-08-28 ·Endre Csóka
similarity 0.66
Abstract

We study the repeated allocation of a single indivisible resource among $n$ strategic players. Each player $i$ has a privately known value distribution $D_i$, and values are drawn independently across players and periods. The goal is to find fair and efficient mechanisms. We apply the repeated first-price auction with equal initial endowments of virtual money. We show that each player can asymptotically secure the same fair-floor guarantee $f(D_i)$ as in Csóka 2026; consequently, the mechanism is $1.283$-optimal. This provides a simpler and more robust alternative mechanism for this special case and may also help derive sharper upper bounds on the price of anarchy.

0.38

On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated Priors

cs.GT cs.CC ·2026-10-06 ·Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell
similarity 0.64
Abstract

We show that computing an approximate mixed Bayes-Nash equilibrium in a discrete first-price auction with correlated priors is PPAD-complete. The key intermediate step in our reduction is the PPAD-completeness of computing an approximate Nash equilibrium in a new normal-form game, the hypergraph discrete first-price auction, which may be of independent interest.

0.40

Tight Inapproximability of Pacing and Throttling Equilibria in Second-Price Auctions

cs.GT cs.CC ·2026-08-17 ·Zhengyang Liu
theory similarity 0.64
Abstract

Budget-constrained advertisers commonly rely on two control mechanisms: pacing scales bids, whereas throttling randomizes participation. We prove that, in second-price auctions, these two different mechanisms share the same sharp approximation-hardness threshold. For pacing, computing a $γ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $γ\in[0,1)$. For throttling, computing a $δ$-approximate equilibrium is $\mathsf{PPAD}$-hard for every constant $δ\in(0,1)$. At parameter $1$, the complementarity requirement becomes vacuous and the all-zero solution is feasible. That is, approximation does not eliminate the fixed-point barrier at any nontrivial parameter value.

0.46

Impossibility of No-Regret in Multi-Agent Bidding

cs.GT cs.CCcs.LG ·2026-10-27 ·Zongjun Yang, Rachitesh Kumar, Christian Kroer
theory similarity 0.63
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.

0.08

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality

cs.GT ·2026-09-30 ·Twan Kroll, Guido Schäfer, Artem Tsikiridis
theory similarity 0.63
Abstract

We study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy (PoA) bounds for coarse correlated equilibria (CCE). To this end, we develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program. The LP is formulated over a small number of per-bidder equilibrium statistics, incorporates constraints implied by the auction setting and equilibrium behavior, and captures a novel smoothness notion tailored to budget-constrained environments; we provide a reduction from classical smoothness to this new notion. Our approach enables simple and tight PoA analyses across a broad range of auction formats. Using our framework, we obtain tight liquid welfare guarantees for simultaneous first-price, second-price, and all-pay auctions, simultaneous auctions with restricted uniform bidding interfaces, discriminatory and uniform price multi-unit auctions, and generalized first-price position auctions. Beyond budget-constrained settings, we derive new lower bounds for the budget-free uniform price auction and generalized second-price auction; in particular, our lower bound for the uniform price auction matches the upper bound of $3.146$ by de Keijzer et al. (2013).

0.16

FIXP-Completeness in Second-Price Auctions

cs.GT cs.CC ·2026-10-31 ·Nobutaka Shimizu
theory similarity 0.63
Abstract

Computing equilibria is a fundamental algorithmic problem in game theory and economics. Although general frameworks are available for proving membership in FIXP, the class capturing exact fixed-point computation, establishing FIXP-completeness often remains challenging. We prove FIXP-completeness of exact equilibrium computation in three second-price auction models: (1). pacing with return-on-investment constraints, with multiplier cap $1+δ$ for every fixed rational $δ>0$ [Filos-Ratsikas, Hansen, Høgh, and Hollender (2024)]; (2). budget-constrained generalized second-price sponsored shopping [Hansen, Li, and Nie (2026)]; (3). budget-constrained throttling [Liu (2026)]. These results resolve open questions on the exact complexity of automated bidding. Our technical ingredient is a FIXP-complete generalized-circuit problem using only clipped affine gates and the reciprocal $x\mapsto1/(1+τx)$, for any fixed positive rational $τ$. This gate basis provides a common framework for the three auction reductions: simulating these gates in each model establishes FIXP-hardness without directly implementing multiplication or squaring.

0.15

Pacing Equilibria in Abstract Mechanisms

cs.GT ·2026-09-23 ·Salam Afiouni, Christian Kroer
benchmarktheory similarity 0.62
Abstract

Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which scales buyers' bids so that campaign-level budgets are spent gradually. Although pacing is operationally simple, its aggregate behavior depends on the underlying mechanism. In first-price single-item auction markets, pacing enjoys strong structural and computational properties that often fail in second-price auctions. It is unclear whether these properties extend to richer platform mechanisms. We develop a unified theory of pacing equilibria across a hierarchy of mechanisms. We first show that, even in first-price position auctions, the market-equilibrium interpretation of the single-item benchmark can fail. We then identify bid-maximizing pay-your-bid mechanisms as a broad class in which pacing equilibria exist, are unique, and admit an Eisenberg-Gale-type convex-program characterization. This implies efficient computation, Pareto-efficiency, and liquid-welfare guarantees, enabling pacing integration into large-scale optimization-based allocation routines. Finally, for abstract mechanisms satisfying a payment monotonicity condition, we prove equilibrium existence by smoothing discontinuities. With additional conditions and appropriate tie-breaking, we obtain uniqueness, revenue maximality among budget-feasible pacing vectors, and shill-proof implementability, and provide convergent budget-adjustment dynamics for approximate equilibria. Overall, many favorable properties of first-price pacing extend beyond single-item auctions under appropriate mechanism-level conditions.

0.28