Designing a Two-Stage Auction for Online Advertising

In industrial display advertising systems, multi‑stage pipelines are common. This work studies the novel problem of designing a two‑stage auction mechanism that jointly considers the interaction between machine‑learning models and the optimization problem across the two stages. A subset‑selection metric called pre‑auction score (PAS) is proposed, together with a scalable approximation algorithm, and the resulting two‑stage auction is shown to satisfy incentive‑compatible economic properties. Compared with the widely used greedy two‑stage design that ignores the relationship between stages, the proposed method improves both social welfare and revenue. The approach was accepted at TheWebConf 2022 and has attracted attention from Google Research.

Background : To ensure market efficiency in ad platforms, auction mechanisms must consider both advertisers' bids and the predicted quality of ad displays (e.g., click‑through rate, CTR). Generalized second price (GSP) auctions rank ads by bid × predicted CTR. However, a single‑stage auction is infeasible in practice because sophisticated models (e.g., Wide&Deep, DIN) cannot compute CTR for thousands of ads within the required latency. Hence, a two‑stage architecture is adopted: a fast, coarse pre‑auction stage selects a subset of ads, followed by a second stage that applies a more accurate model and a GSP auction.

Problem Definition : In a one‑stage GSP auction, each ad i has a bid b_i and a predicted CTR p_i, yielding an expected click value v_i = b_i·p_i. Ads are sorted by v_i and allocated to slots, with payments ensuring monotonicity and critical pricing, thus guaranteeing incentive compatibility and individual rationality. Extending this to two stages raises two challenges: (1) preserving incentive compatibility across stages, and (2) jointly optimizing the subset selection in the pre‑auction to maximize overall social welfare.

Traditional Greedy Solution and Suboptimality : The common greedy approach (GDY) ranks ads in the pre‑auction by the coarse expected click value and passes the top K ads to the second stage. This method can be suboptimal because an ad with a low coarse estimate may have a high fine‑grained estimate, leading to missed welfare. A constructed example demonstrates that GDY can achieve strictly lower expected social welfare than a selection that accounts for the second‑stage refinement.

Pre‑Auction Design and Complexity : The subset‑selection problem (PA) is shown to be NP‑hard even when the monotonicity constraint is removed (SimPA). Directly evaluating the submodular objective is infeasible at scale. To enable scalable evaluation, an ad‑level metric called pre‑auction score (PAS) is derived from the expected recall of the true top‑K ads. PAS for ad i is defined as the probability that i belongs to the true top‑K set, which can be expressed analytically (Equation 7 in the paper).

Learning‑Based PAS Implementation : Computing PAS analytically requires the explicit distribution of fine‑grained CTRs, which is unavailable in practice. Instead, a neural network is trained to predict PAS using supervised learning. The training data consist of (features, label) pairs where features are the coarse‑stage bid and partial ad/user features, and the label is the fine‑grained expected click value from a deep interest network (DIN). A Plackett‑Luce model is used to model the permutation distribution of rankings; the network outputs logits that approximate the PL parameters. The loss is the cross‑entropy between the empirical top‑1 distribution (derived from fine‑grained values) and the model’s top‑1 distribution.

Experimental Evaluation : Experiments are conducted on both public and industrial datasets. The public setting uses DIN as the fine model and a lightweight FCN as the coarse model (GDY). The industrial setting uses logs from the production two‑stage auction (GDY) where bids serve as truthful values. Metrics include social‑welfare rate, top‑K recall, and revenue rate, all normalized by the ideal one‑stage GSP benchmark. Baselines compared are GDY, regression on coarse features (REG), and regression on coarse CTR predictions (REGCTR). Results show that PAS consistently achieves higher social welfare and revenue than the baselines across all settings.

Incentive Compatibility Test : To verify monotonicity of the learned PAS, a counterfactual test perturbs each advertiser’s bid and checks whether the pre‑auction allocation remains monotone. The failure rate is extremely low, indicating that the neural network implicitly learns a nearly monotone scoring function.

Conclusion : The paper introduces a new problem of two‑stage auction design for online advertising, highlights the welfare loss of existing greedy methods, and proposes a theoretically grounded, incentive‑compatible design where the second stage is a GSP auction and the first stage uses the PAS metric. A learning‑based implementation of PAS is provided, and extensive experiments on public and industrial data demonstrate superior welfare and revenue performance compared to widely adopted baselines.