Normalize, Then Personalize: Two-Speed Reserve Prices for Autobidding Markets

Ad exchanges can earn much more when each advertiser faces their own minimum price, a personalized reserve, instead of one floor for everyone. Theory shows the gain is real. Second-price auctions with personalized reserves can capture up to 77.8% of the revenue of the fully optimal auction (Separation between Second Price Auctions with Personalized Reserves and the Revenue Optimal Auction). The best practical algorithm for choosing those reserves, however, solves a linear program over historical bids offline (Linear Program-Based Approximation for Personalized Reserve Prices). Live markets do not stay still between solves. Traffic swings roughly 30x between peak and off-peak hours (BAT: Benchmark for Auto-bidding Task), and automated bidding agents constantly rescale their bids to spend budgets evenly. A reserve vector that was near-optimal at 3 a.m. can shut out legitimate bidders or leave money on the table by noon.

The obvious fix is to split the system into layers: a slow tier solves the optimization and a fast tier applies the result within the auction's millisecond budget. We argue that the hard design question is not whether to layer. It is what quantity crosses the interface between the layers. Our proposal is to pass down each bidder's reserve as a ratio to a market-level price index. The slow tier learns that ratio on bids normalized by the index. The fast tier rebuilds the reserve by multiplying the ratio by a live index computed from everyone's bids except the bidder's own. If diurnal swings are mostly a common multiplicative rescaling, normalization makes the slow tier's problem nearly stationary, so offline guarantees survive between solves. Excluding the bidder's own bids from their index means no advertiser can lower their own reserve by shading.

Core Claim

Let $b_{i}(t)$ be bidder $i$'s bid at time $t$. Let $m_{-i}(t)$ be a rolling quantile of the competing bids in bidder $i$'s auctions over a short recent window, excluding $i$'s own bids. Let $\rho_i$ be a per-bidder ratio that the slow tier recomputes, say nightly. The fast tier sets

$$r_i(t) = \rho_i \cdot m_{-i}(t),$$

where $\rho_i$ is the output of the profile-based LP rounding algorithm applied to normalized historical bids $b_i(t)/m_{-i}(t)$.

The claim has two parts. First, suppose bids factor as a common time-varying scale times a stationary normalized component. Then the approximation guarantee of the LP rounding method applies to the normalized problem, because the eager reserve auction's allocation is invariant to a common rescaling of bids and reserves. Revenue loss from staleness then scales with drift in the normalized bid distribution rather than the raw one. That quantity should be small under the 30x swing if the swing is largely multiplicative, and measuring whether it is small is itself a result. Second, bidder $i$ has zero influence on $m_{-i}$. Their influence on other bidders' indices is bounded by their share of the window, so the incentive to shade bids in order to move future reserves is bounded by market share rather than being unconstrained.

Relation to Prior Work

The closest system is Dynamic Reserve Price Design with Distributed Solving Algorithm. It already layers reserve pricing. A Spark job solves a Lagrangian dual offline, and the online tier sets each query's reserve as traffic features times the precomputed shadow prices. Its reserves are query-level and identical for all competing advertisers, so it treats bidders as symmetric. We keep its two-speed split but move the personalization into the slow tier and the market adaptation into the fast tier.

The method we reuse is Pro-LPR from Linear Program-Based Approximation for Personalized Reserve Prices. It projects bid histories into a compact profile space, solves a polynomial-size LP, and rounds the solution to reserves with a 0.684 approximation ratio. Its authors name the move to online operation as open. We do not make the LP online; we make its output durable.

Two further works motivate and constrain the design. Individual Welfare Guarantees in the Autobidding World with Machine-learned Advice shows that personalized reserves built from reliable lower bounds on value protect small advertisers from dominant autobidders. The guarantee requires the lower bound to stay within a factor $\beta$ of true value, and staleness is exactly what erodes $\beta$. Online Auction Design Using Distribution-Free Uncertainty Quantification with Applications to E-Commerce sets reserves from conformal lower bounds, which are prediction intervals with guaranteed coverage. It assumes exchangeable calibration data and runs as a single pipeline. We evaluate both of these as competitors rather than components.

On the systems side, Optimizing the Implementation of Clinical Predictive Models to Minimize National Costs: Sepsis Case Study separates a scoring layer from a policy layer that sets thresholds for each category. It found that the choice of policy layer drove the gains (about $700 million over a uniform threshold). This supports our framing that the interface matters more than the model, but that setting has no strategic agents.

Research Program

The work has three parts. The first is an analysis. We will state the scale-invariance argument formally and derive a staleness bound in terms of the distance between normalized bid distributions at solve time and at use time. We will also bound a strategic bidder's gain from shading when it holds share $s$ of the index window.

The second part is an empirical decomposition of the BAT traffic swing into a common multiplicative factor and a residual. This decomposition decides whether normalization should work at all.

The third part is the system. The slow tier runs Pro-LPR on normalized bids nightly. The fast tier keeps per-bidder rolling quantile sketches and applies one multiply per candidate. We will measure fast-tier latency per auction directly. We expect it to be microseconds, but that is a hypothesis to measure, not a reported figure.

Baselines

The naive reference is no reserve, plus a single anonymous reserve re-tuned hourly by grid search on the previous hour. Both run on the same replayed traffic.

The strongest personalized competitor is Pro-LPR solved nightly on raw bids and cached as fixed reserves. This is the obvious layered design. Its paper reports that it captures at least 98% of optimal LP revenue and a median 6–7% revenue gain over the greedy baseline on synthetic log-normal instances (Linear Program-Based Approximation for Personalized Reserve Prices). We also run an upper-reference version re-solved every hour with the same solver, so compute cost is reported alongside revenue. Beating the cached version means higher revenue and a lower share of welfare-losing advertisers over the full day. Matching the hourly re-solve at a fraction of its compute is a meaningful win.

The strongest non-personalized competitor is a query-level dynamic reserve in the style of Dynamic Reserve Price Design with Distributed Solving Algorithm. That paper reports a -1.35% revenue impact alongside a 23.67% gain in click-through rate in live A/B tests. Its alternatives Opt-DRP and Ada-DRP lost between 3% and 5% of revenue. Those numbers are measured on a different objective and platform, so we reimplement the method on our data instead of comparing against them directly.

We also run COAD from Online Auction Design Using Distribution-Free Uncertainty Quantification with Applications to E-Commerce, for which no reported revenue number was found on Lacuna, only that it beat second-price and empirical Myerson on eBay data with 90% coverage. Finally, we run a per-bidder zeroth-order online reserve update adapted from Reserve Price Optimization for First Price Auctions in Display Advertising, which reports finding reserves capturing at least 95% of theoretical maximum revenue. All methods get the same historical window, the same features, and the same hyperparameter search budget.

Two ablations isolate the key ingredient. One normalizes by an index that includes the bidder's own bids, which isolates the leave-own-out choice. The other passes a fixed absolute reserve but adds a conformal safety margin, which isolates normalization.

Why not just…?

Why not just re-solve Pro-LPR every hour? This is the real threat. If LP solves are cheap enough and hourly granularity tracks the swing, factorization adds nothing for revenue. We will report the revenue-versus-solve-frequency curve for raw re-solving against our nightly normalized solve. If hourly re-solving matches us, the remaining case for the design rests on manipulability. Frequent re-solving on a bidder's own recent bids lets that bidder shade today to lower tomorrow's reserve. We will measure that directly with a strategic-bidder test.

Why not just use a time-varying anonymous reserve, as Lazada does? The known gap between personalized and anonymous pricing, a constant factor near 2.62 for regular asymmetric distributions (Lu et al.), is a worst-case bound. Real BAT campaigns may be symmetric enough that personalization barely matters. The anonymous dynamic baseline measures this. If it comes within noise of our method, we will report that personalization is not worth its complexity on this traffic.

Why not just let the fast tier learn each bidder's reserve online? Per-bidder zeroth-order updates need many auctions per bidder to converge and are noisy under first-price bid shading. The quantile truncation in Reserve Price Optimization for First Price Auctions in Display Advertising was needed even across aggregate traffic slices. Updating reserves from a bidder's own outcomes also reintroduces the feedback loop that breaks truthfulness. Our comparison will show whether it converges within a day for small campaigns, where we expect it to fail first.

Proposed Experiments

The first test is on the synthetic log-normal setup of Pro-LPR (two bidders, three correlation regimes, 50 instances). We inject a known multiplicative diurnal factor with 30x amplitude plus a controllable non-multiplicative residual. We then check that our revenue as a fraction of the per-hour LP upper bound degrades with the residual but not with the amplitude. The cached raw Pro-LPR baseline should degrade with both.

The main test replays the BAT first-price track (10M auctions, about 9,000 campaigns) and VCG track (1M auctions, about 2,500 campaigns). The competing bidders are driven by the benchmark's own autobidders: TA-PID, M-PID and Mystique, with Mystique reported as the most uniform spender. We measure revenue, total welfare, latency, and the share of advertisers whose welfare falls below 0.8 of their competitive-equilibrium value. For that last metric, Individual Welfare Guarantees in the Autobidding World with Machine-learned Advice reports a drop from 17% to 8% with accurate advice. iPinYou (Real-Time Bidding Benchmarking with iPinYou Dataset) serves as a second-price replication.

The decisive checks are three. First, the fraction of BAT's hourly bid variance explained by a common multiplicative factor. If it is low, the premise fails and we say so. Second, whether nightly normalized reserves match hourly raw re-solves in revenue. Third, the manipulation test. A strategic bidder with share $s$ searches over shading strategies to minimize its payments over a week. Its gain should be near zero under leave-own-out indexing and should grow with $s$ under the own-inclusive ablation and under frequent raw re-solving.