New algorithm solves pacing equilibria in online ad auctions

In online advertising, second-price auctions are ubiquitous for selling ad slots, but finding an equilibrium where both buyers and the platform agree on pacing multipliers (budget constraints) has been computationally challenging. This paper, by Yiyang Huang, Yonglei Yan, Zihe Wang, and Zhengyang Liu (arXiv:2605.09332), introduces a breakthrough polynomial-time algorithm for computing exact second-price pacing equilibria (SPPEs) when the number of goods (e.g., distinct ad slots) is constant. The core innovation is a geometric approach: the authors map each buyer's pacing multiplier to the highest bid on each good, effectively dividing the parameter space into a finite set of cells. By enumerating these cells, they fix the relative order of all bids, turning the equilibrium problem into a linear feasibility program that can be solved efficiently. This reduces what was previously an open problem in algorithm design to a tractable computation.

The authors further show that this tractability extends beyond the constant-goods case to large-scale markets with an arbitrary number of goods, as long as those goods can be aggregated into a constant number of valuation types. This is a practical insight: real-world ad exchanges often cluster similar ad slots (e.g., by audience segment or time of day). The work has immediate implications for programmatic advertising platforms, enabling faster and exact computation of pacing equilibria rather than relying on approximations. While the paper is theoretical (10 pages, preprint), its algorithmic clarity suggests potential for real-world adoption. The authors provide no code, but the described method is implementable with standard solvers.