Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing
Yuchen Xie, Shenyinying Tu, Yuan Gao, Yi Zhang, Deepak Kumar
math.OC
Oct 16, 2026 · v1
cs.GT
TL;DR
All lemmas, propositions, theorems and corollaries of Sections 3–5 are machine-checked in Lean 4 using Mathlib and the Optlib optimization library.
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(\sqrt{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.
Problem
Computing first-price pacing equilibria for budget-constrained advertisers is hard at production scale when each request fills several slots. The top-K allocation is piecewise constant in the bids, so first-order methods oscillate near score ties.
Approach
A TopK identity reduces the multi-slot Eisenberg-Gale dual to a convex program over bids. Each request's allocation is regularized with the binary (Fermi-Dirac) entropy, which gives a smooth, strictly convex dual whose gradient is exactly spend minus budget. Each gradient evaluation splits into one-dimensional threshold root solves per request, implemented as a multi-GPU solver. The theoretical results of Sections 3–5 are formalized in Lean 4 with Mathlib and Optlib, with no unproved steps.
Results
The smoothed equilibrium converges to the hard equilibrium at an O(√T) rate, and a duality gap certifies the distance of any bids from it. On a LinkedIn feed-ad workload the solver met its stopping rule in 174 iterations, about one minute on four H100 GPUs, with median relative spend deviation 4.0e-5. Under hard top-K allocation with the same update, 56% of active campaigns stayed more than 1% from budget.
