CS Paper Radar

FIXP-Completeness in Second-Price Auctions

Nobutaka Shimizu

cs.GT cs.CC ·submitted 2026-10-31 01:57 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.GT cs.CC ·2026-08-17 ·Zhengyang Liu
theory similarity 0.73
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

Pacing Equilibria in Abstract Mechanisms

cs.GT ·2026-09-23 ·Salam Afiouni, Christian Kroer
benchmarktheory similarity 0.72
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.29

On the Complexity of Exact Autobidding Equilibria

cs.GT cs.CC ·2026-11-03 ·Yiyang Huang, Zhengyang Liu, Yonglei Yan
similarity 0.71
Abstract · Full version with appendices

Autobidding equilibria link advertisers' value multipliers or participation probabilities through aggregate budget and return-on-investment (ROI) constraints. We establish the exact computational complexity of finding these equilibria across several canonical settings: exact equilibrium computation is $\mathsf{FIXP}$-complete for second-price ROI pacing, budget- or ROI-constrained generalized second-price (GSP) sponsored shopping, and second-price throttling. Furthermore, approximating the equilibrium control vector in distance to a true equilibrium is $\mathsf{FIXP}_{a}$-complete when the target accuracy is provided as input.

0.10

Complexity of Autobidding Equilibria in GSP Sponsored Shopping

cs.GT cs.CC ·2026-10-09 ·Kristoffer Arnsfelt Hansen, Yuhao Li, Xinhao Nie
similarity 0.70
Abstract

We revisit autobidding equilibria in GSP sponsored shopping auctions, recently proposed and studied in Dütting et al. On the existence side, we show that autobidding equilibria under both budget constraints (ABE-B) and return-on-investment constraints (ABE-R) always exist and, moreover, always admit equilibria with polynomial-size support over the allocation space. On the computational side, we show that computing an exact equilibrium is in FIXP, and that computing an approximate equilibrium is in PPAD. We also prove that computing an approximate equilibrium is PPAD-hard for both ABE-B and ABE-R. Together, these results provide a fairly comprehensive picture of the computational complexity of autobidding equilibria in GSP sponsored shopping auctions.

0.46

GSP Autobidding Equilibria with Few Advertisers or Slots

cs.GT ·2026-10-21 ·Yiyang Huang, Zhengyang Liu, Yonglei Yan, Zihe Wang
theory similarity 0.70
Abstract · 1 figure, 1 table, 4 algorithms

In sponsored-shopping auctions, one advertiser may win several positions, and a product that is never displayed may determine the prices of several winners. Under generalized second-price (GSP) pricing without self-pricing, these interactions couple allocation and payment through a single global ranking. We prove that exact autobidding equilibria under budget and return-on-investment (ROI) constraints can be computed in polynomial time whenever either the number $n$ of advertisers or the number $K$ of display slots is fixed. Our algorithms rely on two structural reductions. With few advertisers, the payment polytopes of tied bid layers combine by a Minkowski sum, giving a fixed-dimensional representation of exponentially many rankings. With few slots, budget equilibria admit threshold recovery and an exact submodular description of attainable payments at the display boundary. For ROI, we prove that every group-consecutive equilibrium has a representative with at most $K+2$ nonunit multipliers, preserving the item and price in every displayed slot. In each case, the reduction leads to polynomially many systems of polynomial equations and inequalities in bounded dimension. The algorithms compute exact multipliers and explicit distributions over valid group-consecutive rankings, with support at most $n+1$; for ROI with few slots, this improves to $\min\{n+1,K+3\}$.

0.07

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.69
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

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

The Complexity of Computing a Competitive Equilibrium in Fisher Markets with Chores

cs.GT ·2026-11-08 ·Christian Kroer, Ruta Mehta, Tianlong Nan
theory similarity 0.66
Abstract

We study the complexity of computing competitive equilibria in Fisher markets with divisible chores and positive rational disutility coefficients and earning requirements. For linear disutilities, we prove that exact equilibrium computation is CLS-complete. In particular, the problem remains CLS-hard even when the earning requirements are binary in $1$ and $2^k$, where $k$ is an integer. We prove hardness by encoding the first-order conditions of a box-constrained quadratic program in equilibrium prices and earning flows, using a compact minimum-cost flow construction. For convex constant-elasticity-of-substitution (CES) disutilities, exact equilibrium prices may be irrational. We formulate the problem of finite-precision equilibrium price computation, in which we seek rational prices with a certified market clearing error at most a given rational tolerance encoded in binary. We prove that this problem is CLS-complete for every fixed rational exponent $ρ>1$. To prove this hardness, we encode a quartic polynomial through the fourth-order expansion of the CES price potential function corresponding to the Eisenberg-Gale (EG) dual program, and show that every sufficiently accurate approximate equilibrium of the constructed market lies near uniform prices. Additionally, we also identify a tractable special case of chores Fisher markets. In particular, we provide a strongly polynomial algorithm for exact equilibrium computation in linear markets whose disutility matrix has rank at most two and earning requirements are arbitrary positive rationals. For $n$ agents and $m$ chores, the algorithm uses $O(nm(n+m))$ rational arithmetic operations and comparisons, with polynomial intermediate encoding length.

0.14