Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing
Abstract
Pacing equilibria describe how budget-constrained advertisers clear an ad market, but computing one at production scale is hard when every request fills several slots: the allocation jumps whenever two campaigns' scores cross. We consider the first-price pacing equilibrium (FPPE) of auctions with K homogeneous slots and unit-demand campaigns, whose Eisenberg-Gale dual reduces, via a TopK identity, to a convex program over bids. Regularizing each request's allocation with the binary (Fermi-Dirac) entropy gives a smooth, strictly convex dual whose gradient is exactly spend minus budget and whose evaluation splits into independent one-dimensional threshold solves, one per request. The smoothed equilibrium converges to the hard one at an explicit O(√T) rate, and a duality gap certifies how far any bids are from the hard equilibrium. We implement an efficient multi-GPU solver and test it on a production ad workload. We use it to compute an equilibrium price anchor: each campaign's hindsight equilibrium cost per key result.
Related
- Discrete eigenvalue optimization from entropic smoothing and first-order methods
- Computing Stationary Equilibria in Measure-Dependent Markov Systems
- Computing Equilibria in Integer Programming Games with Shared Constraints
- A Fast and High-Accuracy Finite-Time Sliding-Mode Algorithm for Computing Local Stackelberg Equilibria in Nonlinear Bilevel Games
- Computing Equilibria in Simulation-Based Insurance Markets with Discontinuous Demand
BibTeX
@misc{xie2026computing,
title = {{Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing}},
author = {Yuchen Xie and Shenyinying Tu and Yuan Gao and Yi Zhang and Deepak Kumar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24323},
eprint = {2610.24323},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24323},
}
RIS
TY - UNPB
TI - Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing
AU - Yuchen Xie
AU - Shenyinying Tu
AU - Yuan Gao
AU - Yi Zhang
AU - Deepak Kumar
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.24323
UR - https://arxiv.org/abs/2610.24323
AB - Pacing equilibria describe how budget-constrained advertisers clear an ad market, but computing one at production scale is hard when every request fills several slots: the allocation jumps whenever two campaigns' scores cross. We consider the first-price pacing equilibrium (FPPE) of auctions with K homogeneous slots and unit-demand campaigns, whose Eisenberg-Gale dual reduces, via a TopK identity, to a convex program over bids. Regularizing each request's allocation with the binary (Fermi-Dirac) entropy gives a smooth, strictly convex dual whose gradient is exactly spend minus budget and whose evaluation splits into independent one-dimensional threshold solves, one per request. The smoothed equilibrium converges to the hard one at an explicit O(√T) rate, and a duality gap certifies how far any bids are from the hard equilibrium. We implement an efficient multi-GPU solver and test it on a production ad workload. We use it to compute an equilibrium price anchor: each campaign's hindsight equilibrium cost per key result.
ER -