online ad platform engineers

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.

Abstract: We study learning-augmented online bipartite allocation with multiple stages. In the $k$-stage vertex-weighted fractional bipartite matching problem, demand vertices arrive in $k$ stages, and the algorithm receives possibly inaccurate predictions of the allocation in each stage. While tight consistency-robustness tradeoffs were known for the two-stage case, no nontrivial tradeoff was known for an arbitrary number of stages. Our main result is the first consistency-robustness tradeoff for $k$-stage vertex-weighted fractional bipartite matching with predictions, for every $k\ge2$. Let $R_k=1-(1-1/k)^k$. For every $R\in[0,R_k]$, our algorithm is $R$-robust and $C_k(R)$-consistent, where $C_k(R)=k(1-R)^{1/k}+R-(k-1)$. This simultaneously recovers the known tight two-stage tradeoff and the optimal prediction-free $k$-stage competitive guarantee $R_k = C_k(R_k)$, while strictly dominating the natural randomized coin-flip baseline between these endpoints. We also present an algorithm for the classical online setting, where demands arrive one by one and the number of demands is unknown in advance. It has a consistency ratio of at least $C_\infty(R)=1+R+\ln(1-R)$ for a given robustness $R\in[0,1-1/e]$, improving the best previously known tradeoff for this problem. Finally, we extend the framework to fractional AdWords and fractional predictions. Our algorithms are based on stage-wise convex programs with carefully calibrated vertex-dependent penalties. The penalties maintain a dynamic safety reserve for each supply vertex, balancing protection against adversarial future arrivals with the ability to exploit the predicted allocation.