Beyond the PPAD hardness of Auto-bidding Auctions
2026-08-03 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors explain that finding autobidding equilibria can be computationally hard in theory, but this rarely happens in real markets because bidder values are spread out continuously, not in fixed chunks. They introduce a new way called diffuse analysis to study these more realistic cases, showing that the problem becomes easier to solve. They develop a new method that reliably and quickly finds equilibria when values come from smooth distributions, matching what is seen in practice. Their framework also covers well-known cases like budget pacing and throttling.
autobidding equilibriaPPAD complexitynonatomic distributiongeneralized Nash equilibriumdiffuse analysislast iterate convergencebudget pacingthrottling equilibriumfirst price auctionsecond price auction
Authors
Li Chen, Jamie Morgenstern, Yuanyuan Yang
Abstract
Computing certain autobidding equilibria is PPAD complete in the worst case. Yet such instances rarely arise in practice, where advertisers running simple, decentralized learning strategies usually converge quickly. We show there is no contradiction: the hardness requires atomicity and vanishes once the value distribution is nonatomic, as it is in real world markets. To bridge worst case hardness and practical convergence, we introduce diffuse analysis, a beyond worst case framework that studies equilibrium computation when bidder values are drawn from general nonatomic distributions. Under this framework, the autobidding equilibrium becomes a separately monotone generalized Nash equilibrium (GNE). For this GNE, we give the first solver with last iterate linear convergence. Thus, the equilibrium has polynomial diffuse complexity, matching the convergence observed in real-world markets. Concretely, our framework subsumes the budget pacing and the throttling equilibrium as special cases when the payment rule is a convex combination of first and second price.