CS Paper Radar

Complexity of Autobidding Equilibria in GSP Sponsored Shopping

Kristoffer Arnsfelt Hansen, Yuhao Li, Xinhao Nie

cs.GT cs.CC ·submitted 2026-10-09 15:16 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Complexity of Exact Autobidding Equilibria

cs.GT cs.CC ·2026-11-03 ·Yiyang Huang, Zhengyang Liu, Yonglei Yan
similarity 0.75
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

GSP Autobidding Equilibria with Few Advertisers or Slots

cs.GT ·2026-10-21 ·Yiyang Huang, Zhengyang Liu, Yonglei Yan, Zihe Wang
theory similarity 0.72
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

FIXP-Completeness in Second-Price Auctions

cs.GT cs.CC ·2026-10-31 ·Nobutaka Shimizu
theory similarity 0.70
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

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

Optimal Multi-Item Auctions with I.I.D. Values

cs.GT ·2026-10-08 ·Boyu Liu, Zhengyang Liu, Zihe Wang
similarity 0.66
Abstract · 51 pages, 1 table

We study revenue-maximizing multi-item auctions under dominant-strategy incentive compatibility (DSIC) and ex-post individual rationality. Buyers have additive valuations, and all item values are independent draws from a common finite distribution. For every two-point distribution and arbitrary numbers of buyers and items, we give an explicit deterministic mechanism that is optimal among all randomized mechanisms satisfying these requirements, together with a polynomial-time algorithm for computing the optimal expected revenue. For general finite-support distributions, computing the exact optimal revenue is $\#\mathrm P$-hard, both for a single buyer with an arbitrary number of items and for two items with an arbitrary number of buyers. For a single buyer, we also establish hardness of computing an optimal mechanism. Building on prior work, we also obtain exact and approximate algorithms under different parameter restrictions. Exact polynomial-time optimization is possible whenever any two of the buyer count, item count, and support size are fixed. When only the item count is fixed, a polynomial-time approximation scheme constructs a mechanism with expected revenue at least a $1-\varepsilon$ fraction of the optimum for every fixed $0<\varepsilon<1$. All these algorithms satisfy DSIC and ex-post individual rationality.

0.21

Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding

cs.GT ·2026-09-30 ·Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta +2 more
theory similarity 0.66
Abstract

Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives--such as maximizing total value subject to a return-on-spend (ROS) constraint--rather than manual per-query bids. A central question in algorithmic mechanism design is characterizing the worst-case efficiency loss, or Price of Anarchy (PoA), across auction formats in this prior-free setting. While randomized auctions are known to strictly improve efficiency over deterministic mechanisms for two bidders, two fundamental questions have remained open: (1) what is the optimal PoA for two bidders, and (2) can any mechanism beat the barrier of 2 for general $n \ge 3$ bidders? We resolve both questions using the family of $r$-proportional first-price auctions ($\text{pFPA}_r$), in which each bidder wins with probability proportional to their bid raised to an exponent $r > 0$ and pays their bid upon winning. First, for two bidders, we prove that the standard proportional first-price auction ($r = 1$) achieves a tight $\text{PoA} \le 1.5$, complemented by a matching lower bound showing that no anonymous, monotone mechanism can do better. Second, for general $n \ge 2$ bidders, setting $r = 2n$ achieves $\text{PoA} \le 2 - \frac{1}{4n+1} = 2 - Ω(1/n)$ across all undominated bid profiles, breaking the deterministic barrier of 2 for every finite $n$ and asymptotically matching the known $2 - Θ(1/n)$ lower bound.

0.46

Generalized Prophet Inequalities for Online Auctions

cs.GT ·2026-09-30 ·Twan Kroll, Rebecca Reiffenhäuser
similarity 0.65
Abstract

Prophet Inequalities for online auctions, as many classical auction settings, traditionally consider agents who strive to maximize quasi-linear utility, i.e. their obtained value minus the price paid. This simplified view of the agents' objectives does not capture real-world settings where agents are almost always constrained by budgets, and can have different objectives altogether (e.g., very prominently, value maximizers in autobidding). We generalize classic prophet inequality auction settings to accommodate unknown, varying types of agent objectives and budgets, modeling them as stochastic input similar to the traditional valuation distributions. In this new model, we analyze (anonymous) posted-price mechanisms, one main category of which are the balanced prices central to many auction results in the prophet inequality model. We demonstrate both the resilience and limits of balanced price mechanisms for generalized prophet inequalities with stochastic agent objectives, budgets and valuations: our generalization of the balanced prices framework incorporates budget constraints and mixed objectives. We show constant competitive ratios for some the most central settings, spanning all the way up to agents with subadditive valuation functions. On the way, we establish trade-offs between competitive ratio and agents' price-sensitivity, and give a general reduction from the budgeted setting to budget-free value maximizers.

0.17

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

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