Smoothing method speeds up budgeted ad auction pricing at scale
Computing Multi-Slot First-Price Pacing Equilibria at Scale via Entropic Smoothing
Computer Science and Game Theory
Summary
Many advertisers have budgets and compete for multiple ad slots in online auctions, which makes it complicated to find a stable pricing setup that respects budgets. The authors found a way to smooth the problem using ideas from physics (entropy), turning a difficult jumping problem into a smooth one that is easier to solve with computers. Their method lets them quickly find prices that balance advertiser budgets and slot allocations, even on large real-world data. They also built software that runs on several GPUs to test this approach in practice.
What this means in practice
- •For online ad platform engineers: Calculate stable, budget-aware prices for ads displayed across multiple slots efficiently at production scale.
- •For digital marketing analysts: Provide campaigns with hindsight cost estimates per key result to improve budget planning and campaign evaluation.
Authors
Yuchen Xie, Shenyinying Tu, Yuan Gao, Yi Zhang, Deepak Kumar
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.