Pacing Equilibria in Second-Price Auctions with Few Goods
This work provides the first polynomial-time algorithm for exact SPPEs in settings with few goods, solving a computational bottleneck for a foundational model in online advertising.
The paper presents a polynomial-time algorithm for computing exact second-price pacing equilibria in online advertising auctions with a constant number of goods, and extends this tractability to markets with arbitrary goods that can be aggregated into a constant number of valuation types.
In this paper, we investigate the computation of second-price pacing equilibria (SPPEs), a foundational model in online advertising auctions. We present a polynomial-time algorithm for computing exact SPPEs in instances with a constant number of goods. Our core technique maps buyers' pacing multipliers to the highest bids on each good, effectively partitioning the parameter space into a set of distinct geometric cells. By enumerating these cells, we fix the relative ordering of the bids and reduce the problem of equilibrium computation to a linear feasibility program. Finally, we demonstrate that this tractability extends to large-scale markets with an arbitrary number of goods, provided the goods can be aggregated into a constant number of valuation types.