Learning and pricing in repeated generalized second-price auctions with unknown click-through rates

The seller-side learning-and-pricing framework of Yang, Xiao, and Wu (2020) for repeated generalized second-price (GSP) auctions in search advertising learns the bidders' unknown value distribution online and sets reserve prices with high-probability regret guarantees, but rests on Assumption 1 that the position click-through rates (CTR ratios) are known to the seller and the bidders. The open problem is to extend this framework to the regime in which the position CTRs are themselves unknown parameters that must be estimated from realized click feedback: design a seller policy that jointly estimates the CTRs and the value distribution from repeated-auction data while setting reserve prices, derive finite-sample bounds on the deviation between estimated and true CTRs, and quantify how CTR-estimation error propagates into the revenue function and the regret guarantee.

Background

Search-advertising platforms sell the sponsored slots that appear alongside organic search results through repeated auctions. The predominant selling rule is the generalized second-price (GSP) auction: bidders submit per-click bids, the $k$ slots are allocated in decreasing bid order, and each winner pays the bid of the next-ranked bidder (or the seller's reserve price, if that is higher). Slots differ in prominence, so the expected number of clicks an ad receives in position $i$ is modeled by a position click-through rate (CTR) $c_i$, with $c_1>c_2>\cdots>c_k>0$; in the standard separable model these position effects are common to all advertisers.

The theory of GSP centers on the locally envy-free equilibrium (Edelman, Ostrovsky, and Schwarz 2007; Varian 2007): a bid profile in which no bidder wants to swap positions with the bidder ranked immediately above. This equilibrium induces a deterministic recursion linking the ordered bids to the ordered private per-click values — each bidder effectively pays the minimal amount needed to beat the competitor one position below. Sellers additionally set reserve prices (minimum acceptable bids), their main lever for raising expected revenue; choosing a revenue-maximizing reserve requires knowledge of the distribution $F$ of bidders' per-click values, which is private.

Yang, Xiao, and Wu (2020) study the seller's problem in a repeated multi-slot GSP auction with $n>k$ risk-neutral bidders whose per-click values are independent draws from an unknown distribution $F$ on $[0,1]$. They derive a closed-form expected-revenue function of a single reserve $r$ in terms of $F$ and order statistics (the sorted values $V_{(1)}\ge\cdots\ge V_{(n)}$, whose distributions follow from $F$); they estimate $F$ online by inverting observed bids through the locally envy-free recursion; and they prove finite-sample uniform concentration for the resulting empirical distribution using the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality, a distribution-free bound on the deviation between an empirical cumulative distribution function and the true one. A staged learning algorithm (exploration stages of lengths $T_s=T^{1-2^{-s}}$) then achieves cumulative revenue regret — revenue loss relative to the reserve that is optimal under full knowledge of $F$ — of order $\tilde{O}((\sum_i c_i)\sqrt{nT})$ with high probability (the notation $\tilde{O}$ suppresses logarithmic factors in the horizon $T$), and a second algorithm with position-specific reserves handles bidding that need not follow the equilibrium. A companion Bayesian model treats unknown demand parameters in revenue management (Xiao and Yang 2021).

A structural limitation is Assumption 1 of that paper: the position CTRs, equivalently the ratios $c_i/c_{i+1}$, are known to the seller and the bidders and are fixed throughout. The CTRs enter both the equilibrium bid mapping — so inverting bids into values already requires them — and the revenue function itself. In reality, position effects must be estimated from realized clicks, and the click feedback that reveals them is shaped by the seller's own reserve and allocation choices, which determine which ads occupy which positions. Adjacent strands leave this gap open: batch learning of GSP reserve prices assumes known CTRs (Mohri and Medina 2015); learning mechanisms for multi-slot sponsored search estimate advertiser-specific CTRs inside truthful Vickrey–Clarke–Groves (VCG)-type allocation mechanisms — mechanisms in which truthful bidding is a dominant strategy — rather than the position effects of GSP reserve pricing (Gatti, Lazaric, Rocco, and Trovò 2015); dynamic reserve learning in repeated auctions concerns the single-slot value distribution (Kanoria and Nazerzadeh 2020); reinforcement-learning reserve pricing in sponsored search is empirical, without statistical guarantees (Shen et al. 2017); and adaptive ad-load design learns how many slots to show rather than reserve prices under unknown CTRs (Rashid and Yoganarasimhan 2026). The open question is the extension of the learning-and-pricing guarantees to unknown position CTRs estimated from endogenous click feedback.

Problem Statement

In the repeated multi-slot GSP auction setting of Yang, Xiao, and Wu (2020) — $n>k$ risk-neutral bidders with independent per-click values drawn from an unknown distribution $F$ on $[0,1]$, $k$ ordered positions with position CTRs $c_1>\cdots>c_k>0$, a seller choosing reserve price(s) over a $T$-auction horizon, and outcomes observed as they accrue — relax Assumption 1 that the position CTRs (equivalently the ratios $c_i/c_{i+1}$) are known to the seller and the bidders. Construct and analyze a seller-side learning-and-pricing policy that treats the CTRs as additional unknown parameters estimated online from the observed data (bids and, as available, realized clicks), jointly with the unknown value distribution $F$. The information structure of the relaxed model must be made explicit as part of the analysis, and that analysis must cover at least the case in which the bidders also lack knowledge of the CTRs — in which case the locally envy-free bid-to-value recursion must be reformulated in terms of bidders' beliefs or estimates; the case in which bidders know the true CTRs and bid accordingly while only the seller must learn them may be treated as a special case of the bidder-belief formulation. Likewise, which realized clicks the seller observes for which slots must be specified. On that basis, establish: (i) finite-sample bounds on the deviation between the estimated and true CTRs; and (ii) how the CTR-estimation error propagates into the estimated revenue function and into the cumulative revenue regret relative to the reserve price that would be chosen with full knowledge of both $F$ and the CTRs — in particular, whether regret sublinear in $T$ of an order comparable to the known-CTR case can be retained, under explicitly stated and non-vacuous identification or bidder-behavior conditions.

References

1. Wei Yang, Baichun Xiao, Lifang Wu (2020). Learning and pricing models for repeated generalized second-price auction in search advertising. European Journal of Operational Research 282(2):696–711. DOI: 10.1016/j.ejor.2019.09.051. https://doi.org/10.1016/j.ejor.2019.09.051
2. Wei Yang, Baichun Xiao, Lifang Wu (2025). Learning unknown private valuation in Generalized Second Price position auction. Electronic Commerce Research and Applications 72:101507. DOI: 10.1016/j.elerap.2025.101507. https://doi.org/10.1016/j.elerap.2025.101507
3. Benjamin Edelman, Michael Ostrovsky, Michael Schwarz (2007). Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords. American Economic Review 97(1):242–259. DOI: 10.1257/aer.97.1.242. https://doi.org/10.1257/aer.97.1.242
4. Hal R. Varian (2007). Position auctions. International Journal of Industrial Organization 25(6):1163–1178. DOI: 10.1016/j.ijindorg.2006.10.002. https://doi.org/10.1016/j.ijindorg.2006.10.002
5. Mehryar Mohri, Andres Munoz Medina (2015). Non-parametric Revenue Optimization for Generalized Second Price Auctions. arXiv:1506.02719. https://arxiv.org/abs/1506.02719
6. Nicola Gatti, Alessandro Lazaric, Marco Rocco, Francesco Trovò (2015). Truthful learning mechanisms for multi-slot sponsored search auctions with externalities. Artificial Intelligence 227:93–139. DOI: 10.1016/j.artint.2015.05.012. https://doi.org/10.1016/j.artint.2015.05.012
7. Yash Kanoria, Hamid Nazerzadeh (2020). Dynamic Reserve Prices for Repeated Auctions: Learning from Bids. arXiv:2002.07331. https://arxiv.org/abs/2002.07331
8. Weiran Shen, Binghui Peng, Hanpeng Liu, Michael Zhang, Ruohan Qian, Yan Hong, Zhi Guo, Zongyao Ding, Pengjun Lu, Pingzhong Tang (2017). Reinforcement Mechanism Design, with Applications to Dynamic Pricing in Sponsored Search Auctions. arXiv:1711.10279. https://arxiv.org/abs/1711.10279
9. Mohammad Rashid, Hema Yoganarasimhan (2026). Adaptive Ad Load Design for Sponsored Search Markets: Evidence, Theory, and Deployment. arXiv:2607.14418. https://arxiv.org/abs/2607.14418
10. Baichun Xiao, Wei Yang (2021). A Bayesian learning model for estimating unknown demand parameter in revenue management. European Journal of Operational Research 293(1):248–262. DOI: 10.1016/j.ejor.2020.11.049. https://doi.org/10.1016/j.ejor.2020.11.049
11. Ksenia Shakhgildyan (2023). Nonparametric Identification and Estimation of the Generalized Second-Price Auction. SSRN preprint. DOI: 10.2139/ssrn.4575379. https://doi.org/10.2139/ssrn.4575379