Tight Inapproximability of Pacing and Throttling Equilibria in Second-Price Auctions
2026-08-17 • Computer Science and Game Theory
Computer Science and Game TheoryComputational Complexity
AI summaryⓘ
The authors study two ways advertisers control spending in auctions: pacing, which scales bids, and throttling, which randomly limits participation. They show that finding even approximate stable outcomes (equilibria) in these settings is computationally very hard, classified as PPAD-hard, meaning no efficient method is known. This difficulty holds true for both pacing and throttling at almost all levels of approximation except the trivial case where no bids are made. Essentially, the authors show that trying to approximate solutions doesn't make the problem any easier in practice.
budget-constrained advertiserspacingthrottlingsecond-price auctionsapproximate equilibriumPPAD-hardnesscomputational complexityfixed-point theoremauction theory
Authors
Zhengyang Liu
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.