Pith. sign in

REVIEW 3 major objections 5 minor 21 references

Optimal Traffic Allocation for Multi-Slot Sponsored Search: Balance of Efficiency and Fairness

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sponsored-search ad allocation can run without auctions: solve a per-query convex problem balancing clicks against a Gini fairness term, then sample slots to match the solution in expectation, yielding a Gini index up to 35% lower than…

desk verdict A genuinely useful industrial allocation scheme, but the fairness guarantee is asserted rather than proven: per-query squared Gini is not shown to control the global Gini, so the headline claim needs a theorem or a softer empirical framing. read the letter →

arxiv 2502.01862 v1 pith:IUJK7DRM submitted 2025-02-03 cs.GT

Anastasiia Soboleva , Alexander Ledovsky , Yuriy Dorn , Egor Samosvat , Andrey Tikhanov , Fyodor Prazdnikov This is my paper · ORCID
classification cs.GT
keywords sponsoredsearchtrafficallocationbudgetpacingfairnessGiniindexonlineFrank-Wolfeprobabilisticranking
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that sponsored-search traffic can be allocated to advertisers without an auction by solving one small convex optimization per search query, and that this gives a fairer spread of impressions across advertising budgets without losing clicks. The fairness target is the Gini index, a standard inequality measure from 0 (equal) to 1 (concentrated), computed on impressions per unit budget; the paper combines it with a click-efficiency objective into a single per-query program, and solves that program with a Frank-Wolfe iteration whose linear step only needs to pick the top slot positions. A second, probabilistic ranking step turns the computed distribution into actual ad-slot assignments, matching the target distribution in expectation. On a five-day production-style dataset, the resulting OTA algorithm reports a Gini index about 23% lower than a dual-mirror-descent baseline and about 35% lower than a risk-constrained pacing baseline at comparable click efficiency. If the claim holds, marketplaces can offer a budget-only advertising product for small sellers and can use OTA as an offline benchmark for the fairness of existing auction systems.

What carries the argument

The load-bearing object is the virtual impression vector $\alpha \in \mathbb{R}^N$, a per-query stand-in for real slot placements that only tracks how much visibility each item should receive, plus the squared Gini proxy $G_q(\alpha) = \frac{1}{N^2}\sum_{j,h}(\alpha_j/B_j - \alpha_h/B_h)^2$. The proxy turns an absolute-value metric into a quadratic whose matrix $B$ is fixed by budgets alone, which makes the per-query problem (12) a convex quadratic program solvable by the Frank-Wolfe method; each iteration's linear oracle reduces to picking the top components of a vector, so the per-query cost is $O(N)$ per iteration. The second stage, probabilistic ranking, is the other half of the machinery: it samples slots without replacement with probability proportional to $\alpha$, which realizes the intended distribution in expectation and turns the optimizer's output into actual ad placements.

What would settle it

Run the five-day dataset again and compute the global Gini index from OTA's final impression counts rather than from the per-query targets; if the gap between realized and target Gini stays large as the number of repeated queries grows, the local-to-global link fails. A sharper check: construct a two-query example with different CTR vectors where per-query optimization gives a higher global Gini than a fixed static split of impressions, which would show the per-query proxy does not guarantee global fairness.

Watch

Extended reading notes

Core claim

The central claim is that the global allocation problem in equation (6), which couples all queries through a Gini mean difference of impressions per budget, can be replaced without practical loss by independent per-query problems over a virtual impression vector $\alpha$ summing to $\Gamma(t)$. The paper replaces the absolute-value Gini term with a squared $L^2$ proxy $G_q(\alpha)$, whose Hessian depends only on budgets, and proves that Frank-Wolfe applied to the resulting quadratic $\frac12 \lambda \langle Bx,x\rangle - (1-\lambda)\langle c,x\rangle$ converges at rate $2\lambda\|B\|_\infty/(t+2)$. It then shows empirically that sampling slots without replacement with probabilities proportional to $\alpha$ reproduces the target distribution's efficiency and fairness metrics on repeated synthetic queries. On real data, OTA's measured Gini index is lower than the baselines' at matched efficiency, with the paper's headline comparison showing 23.1% lower than DMD and 34.6% lower than RCPacing, so the authors claim the fairness-efficiency trade-off is better than auction-based pacing.

Load-bearing premise

The whole method rests on the idea that what is fair for each search query separately is also fair across the whole day; the paper does not prove that solving one small optimization per query keeps the day-long spread of impressions per budget low.

Editorial extensions

If this is right

  • Marketplaces could run sponsored search with only budget and campaign length as advertiser controls, since OTA takes budgets and CTR estimates as inputs and never asks for bids or a maximum click price.
  • Because each query's optimization is $O(N)$ per Frank-Wolfe iteration and needs no historical data storage, the method is positioned as feasible for real-time, high-traffic query streams.
  • Equalizing impressions per unit budget should stop a small set of high-CTR sellers from capturing a disproportionate share of traffic at low cost, which is the unfairness the paper starts from.
  • OTA can serve as an offline benchmark: run on logged queries, it produces a fairness-efficiency frontier that auction-based systems can be measured against.
  • With $\lambda$ near 0.8–0.9 the paper reports Gini indices around 0.3–0.4 and efficiency at 0.5–0.6 of CTR-ranking, giving platforms a concrete operating point for tuning the trade-off.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural test, not run in the paper, is to replace the squared proxy $G_q$ with the true absolute-value GMD inside the Frank-Wolfe linear oracle; this is likely still cheap and would settle whether the proxy is the reason for the fairness gain.
  • The paper's fairness metric counts impressions per budget, not value per budget; if sellers differ in profit per click, equalizing impressions could still leave value-per-budget unequal, suggesting a weighted version of $G_q$ as an extension.
  • The probabilistic ranking stage introduces sampling variance; a deterministic soft-ranking variant would trade a small amount of efficiency for lower variance, which the paper does not explore but which the synthetic experiments make testable.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes Optimal Traffic Allocation (OTA), a two-stage non-auction algorithm for sponsored search. In Stage 1, for each query t, OTD-FW solves a convex program (12) over a virtual impression vector alpha: maximize (1-lambda) * sum_j c_j alpha_j - lambda * G_q(alpha) subject to sum_j alpha_j = Gamma(t), with G_q the squared L2 analogue of the Gini mean difference. In Stage 2, Algorithm 2 samples items without replacement for the K slots with probabilities proportional to alpha. The paper proves a Frank-Wolfe convergence rate for the per-query problem (Section 5.1), verifies aggregate convergence on repeated synthetic queries (Section 6.1), and evaluates OTA against DMD, RCPacing, and CTR-ranking on five days of production logs using the Gini index of impressions per unit budget and expected clicks per query (Section 6.2). The abstract claims superior fairness without sacrificing efficiency and real-time applicability.

Significance. If the global fairness claim could be established, OTA would be a valuable alternative to auction-based pacing: it avoids bid and pacing control parameters, gives a per-query convex solve with a standard convergence bound, and uses an externally standard Gini-index metric and public baseline implementations. The per-query optimization machinery is sound and the industrial dataset lends practical relevance. However, the paper's headline claim depends on two unproved links, namely the step from the per-query squared proxy to the global Gini index and the step from the optimized alpha to the realized slot allocation, so the significance is conditional.

major comments (3)
  1. [Section 4, Eqs. (8)-(12); Section 5.1] The central fairness claim is that solving the per-query problem (12) with the squared proxy G_q controls the global Gini index (3) of total impressions per budget. This is not established. The global objective (6) does not decompose into per-query problems, because the GMD of sums is not a sum of per-query GMDs, and the substitution of the L2 proxy (10) for the L1 GMD (2)/(8) is given without proof. The convergence result in Section 5.1 bounds only f(x_t)-f(x*) for the per-query objective and says nothing about the global Gini. Consequently the reductions in Tables 1-2 are empirical observations on a single dataset, not consequences of the optimized objective. The authors should either prove a bound relating the global Gini (or GMD) to the per-query quantities actually optimized, or explicitly reframe the fairness contribution as per-query and treat the global Gini improvements as empirical.
  2. [Section 5.2, Algorithm 2] Sampling without replacement with slot-dependent probabilities proportional to alpha does not, in general, make the marginal inclusion probabilities of the displayed set equal to alpha, which is what 'approximated in expectation' requires. For example, with N=3, K=2, Gamma=2 and alpha=(1,0.6,0.4), the marginal display probabilities are approximately (0.84,0.68,0.49), not (1,0.6,0.4). The synthetic convergence check in Section 6.1 compares only the aggregate metrics E_q(alpha)/Gamma and G_q(alpha), which do not detect per-item inclusion biases. Therefore the realized allocation can differ systematically from the optimized alpha, and the OTA columns in Tables 1-2 cannot be assumed to inherit the OTD-FW properties.
  3. [Section 6.2.3, Tables 1-2 and Figure 2] The claims of superior fairness and comparable efficiency are based on percentage differences 'under fixed efficiency' and 'under fixed Gini', but the matching procedure is not described, no standard errors or confidence intervals are reported, and the evaluation uses a single five-day, one-category dataset. Without knowing how the equal-efficiency and equal-Gini comparisons are constructed, and without any measure of variability, the general conclusion that OTA achieves superior fairness without sacrificing efficiency is not supported beyond this particular log sample.
minor comments (5)
  1. [Section 3, Eq. (5)] Equation (5) is labeled as the efficiency definition but there is no Eq. (4); the numbering gap should be fixed.
  2. [Section 5.1, proof of Proposition] The domain D is written with the inequality constraint <s,e> <= Gamma, whereas the optimization problem (14) has equality; the authors should state why the relaxation is valid or match the constraint.
  3. [Algorithm 2, line 4] The notation P[d_k^l = 1] ~ alpha[l] is informal; the conditional probabilities over the remaining items in L_k should be written explicitly, and the behavior when all remaining alpha entries are zero should be specified.
  4. [Figure 2 caption] The caption says 'PRPacing' instead of 'RCPacing'.
  5. [Abstract and Conclusion] The paper claims real-time applicability, but no runtime, latency, or throughput measurements are provided; this claim should be softened or supported by an experiment.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the fairness metric and optimization are independently grounded, the convergence analysis is a direct application of an external theorem, and the baselines are third-party implementations.

full rationale

The paper's derivation chain is not circular in the technical sense. The Gini-based fairness metric (Eqs. 2–3) is a standard external measure, not defined in terms of the proposed algorithm. The per-query objective (Eq. 12) uses an explicitly introduced squared proxy Gq (Eq. 10); the paper does not claim Gq is identical to the global GMD, so this is an unproved modeling step rather than a self-definitional one. The convergence result for OTD-FW is imported from Bubeck et al. Theorem 3.8 and restated for the specific quadratic objective with stated smoothness parameters; no fitted parameter is disguised as a prediction. The empirical comparison uses RCPacing and DMD implementations from an external GitHub repository, and the reported Gini metric is the standard index rather than the algorithm's own objective. The synthetic experiments verify that the randomized ranking stage approximates the distribution produced by OTD-FW in aggregate; this is an implementation sanity check, not a circular derivation of an external claim. Any concern about the local-to-global equivalence of the L2 proxy and the global Gini is a soundness and validation issue, not circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The paper's central claim rests mainly on two unproven modeling steps: the per-query relaxation of the global Gini objective and the squared-L2 proxy for the Gini mean difference. The only fitted or hand-chosen model parameter is the trade-off lambda. No new physical or system entities are postulated.

free parameters (1)
  • lambda = swept over [0,1]; authors recommend 0.8-0.9
    Trade-off parameter between efficiency and fairness in objectives (6) and (12). No automatic selection method is provided; the platform must choose it.
assumptions (5)
  • domain assumption CTRs c_jt and position multipliers gamma_k are known to the platform for each query.
    Section 3 states 'We expect that CTR and position multipliers are known to the platform.' The whole optimization depends on these values.
  • ad hoc to paper The per-query optimal distribution alpha_t with fixed lambda yields a global allocation that improves the global Gini (3).
    Section 4 replaces the global problem (6) with independent per-query problems (12) without proving equivalence or a bound. This is the key unproven step.
  • ad hoc to paper The squared deviation G_q (10) behaves similarly to the Gini mean difference GMD (2).
    Section 4 states the proxy 'exhibits similar behavior' without proof; the reported fairness metric remains the L1-based Gini.
  • ad hoc to paper The probabilistic ranking stage (Algorithm 2) produces impressions with expectation close to alpha.
    Section 5.2 asserts approximation in expectation; only synthetic experiments illustrate convergence, with no formal guarantee for K>1 and fractional Gamma.
  • standard math Frank-Wolfe convergence theorem (Bubeck Theorem 3.8) applies to the quadratic program (13)-(14).
    Used in Section 5.1 to derive the O(1/t) convergence rate; B is PSD so f is convex and smooth.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Traffic Allocation for Multi-Slot Sponsored Search: Balance of Efficiency and Fairness." pith.science (2026). https://pith.science/paper/IUJK7DRM

@misc{pith2026250201862,
  author       = {Pith},
  title        = {Pith review of: Optimal Traffic Allocation for Multi-Slot Sponsored Search: Balance of Efficiency and Fairness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IUJK7DRM}},
  note         = {Machine review of arXiv:2502.01862}
}
read the original abstract

The majority of online marketplaces offer promotion programs to sellers to acquire additional customers for their products. These programs typically allow sellers to allocate advertising budgets to promote their products, with higher budgets generally correlating to improve ad performance. Auction mechanisms with budget pacing are commonly employed to implement such ad systems. While auctions deliver satisfactory average effectiveness, ad performance under allocated budgets can be unfair in practice. To address this issue, we propose a novel ad allocation model that departs from traditional auction mechanics. Our approach focuses on solving a global optimization problem that balances traffic allocation while considering platform efficiency and fairness constraints. This study presents the following contributions. First, we introduce a fairness metric based on the Gini index. Second, we formulate the optimization problem incorporating efficiency and fairness objectives. Third, we offer an online algorithm to solve this optimization problem. Finally, we demonstrate that our approach achieves superior fairness compared to baseline auction-based algorithms without sacrificing efficiency. We contend that our proposed method can be effectively applied in real-time ad allocation scenarios and as an offline benchmark for evaluating the fairness-efficiency trade-off of existing auction-based systems.

Figures

Figures reproduced from arXiv: 2502.01862 by the authors.

Figure 1
Figure 1. Convergence of OT A to the theoretical distribution by OT D − FW To verify the correctness of OTA’s probabilistic ranking we created a synthetic dataset consisting of a single repeated query extracted from our production logs. The number of items N was set to 1000. The number of repeated queries varied in three scenarios: [10, 50, 100]. Additionally we explored three distinct slot configurations: [1, 10, 30]. We exe… view at source ↗
Figure 2
Figure 2. Values of Efficiency and Gini metrics for the following algorithms: OTA, RCPacing, DMD and CTR-ranking. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 18 canonical work pages

  1. [1]

    Optimization-based budget pacing in ebay sponsored search

    [Chen et al.(2024)Chen, Nguyen, and Gligorijevic] Qinyi Chen, Phuong Ha Nguyen, and Djordje Gligorijevic. Optimization-based budget pacing in ebay sponsored search. In Companion Proceedings of the ACM on Web Conference 2024, WWW ’24, page 328–337. ACM, May

    work page 2024

  2. [6]

    URL http://dx.doi.org/10.1145/3589335

    doi:10.1145/3589335.3648342. URL http://dx.doi.org/10.1145/3589335. 3648342. [Lucier et al.(2023)Lucier, Pattathil, Slivkins, and Zhang] Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. Autobidders with budget and roi constraints: Efficiency, regret, and pacing dynamics. ArXiv, abs/2301.13306,

    work page arXiv 2023

  3. [7]

    [Balseiro et al.(2020)Balseiro, Lu, and Mirrokni] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni

    URL https://api.semanticscholar.org/CorpusID:256416216. [Balseiro et al.(2020)Balseiro, Lu, and Mirrokni] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In International Conference on Machine Learning, pages 613–628. PMLR,

    work page 2020

  4. [10]

    [Xinying Chen and Hooker(2023)] Violet Xinying Chen and J. N. Hooker. A guide to formulating fairness in an optimization model. Annals of Operations Research , 326(1):581–619, April

    work page 2023

  5. [11]

    doi:10.1007/s10479-023-05264-y

    ISSN 1572-9338. doi:10.1007/s10479-023-05264-y. URL http://dx.doi.org/10.1007/s10479-023-05264-y . [Atkinson(1970)] Anthony B Atkinson. On the measurement of inequality. Journal of Economic Theory, 2(3):244–263, September

    doi:10.1007/s10479-023-05264-y 1970

  6. [17]

    doi:10.1007/978-1-4614- 4720-7_2

    ISBN 9781461447207. doi:10.1007/978-1-4614- 4720-7_2. URL http://dx.doi.org/10.1007/978-1-4614-4720-7_2 . [Lejeune and Turner(2019)] Miguel A Lejeune and John Turner. Planning online advertising using gini indices. Operations Research, 67(5):1222–1245,

    doi:10.1007/978-1-4614- 2019

  7. [19]

    Optimizing generalized gini indices for fairness in rankings

    [Do and Usunier(2022)] Virginie Do and Nicolas Usunier. Optimizing generalized gini indices for fairness in rankings. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 737–747,

    work page 2022

  8. [20]

    Online adver- tisement allocation under customer choices and algorithmic fairness

    [Li et al.(2024)Li, Rong, Zhang, and Zheng] Xiaolong Li, Ying Rong, Renyu Zhang, and Huan Zheng. Online adver- tisement allocation under customer choices and algorithmic fairness. Management Science,

    work page 2024

Show all 21 references
  1. [21]

    Click models for web search

    [Chuklin et al.(2022)Chuklin, Markov, and De Rijke] Aleksandr Chuklin, Ilya Markov, and Maarten De Rijke. Click models for web search. Springer Nature,

    2022

  2. [22]

    Convex optimization: Algorithms and complexity

    [Bubeck et al.(2015)] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3-4):231–357,

    2015

  3. [1912]

    11 arXiv Template A PREPRINT [Yitzhaki and Schechtman(2012)] Shlomo Yitzhaki and Edna Schechtman

    URL https://books.google.ru/books?id=fqjaBPMxB9kC. 11 arXiv Template A PREPRINT [Yitzhaki and Schechtman(2012)] Shlomo Yitzhaki and Edna Schechtman. More Than a Dozen Alternative Ways of Spelling Gini, page 11–31. Springer New York, August

    2012

  4. [1970]

    doi:10.1016/0022-0531(70)90039-6

    ISSN 0022-0531. doi:10.1016/0022-0531(70)90039-6. URL http://dx.doi.org/10.1016/ 0022-0531(70)90039-6. [Bertsimas et al.(2012)Bertsimas, Farias, and Trichakis] Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. On the efficiency-fairness trade-off. Management Science...

    2012 doi

  5. [2010]

    semanticscholar.org/CorpusID:612212

    URL https://api. semanticscholar.org/CorpusID:612212. [Dai et al.(2024)Dai, Lyu, Zhang, Zhao, Zu, Wang, and Zheng] Liang Dai, Kejie Lyu, Chengcheng Zhang, Guang- ming Zhao, Zhonglin Zu, Liang Wang, and Bo Zheng. Percentile risk-constrained budget pacing for guaranteed display ...

    2024

  6. [2012]

    doi:10.1287/mnsc.1120.1549

    ISSN 1526-5501. doi:10.1287/mnsc.1120.1549. URL http://dx.doi.org/10.1287/mnsc.1120.1549. [Bateni et al.(2022)Bateni, Chen, Ciocan, and Mirrokni] MohammadHossein Bateni, Yiwei Chen, Dragos Florin Cio- can, and Vahab Mirrokni. Fair resource allocation in a volatile marketplace....

    2022

  7. [2013]

    URL http://dx.doi.org/10.1145/2433396.2433483

    doi:10.1145/2433396.2433483. URL http://dx.doi.org/10.1145/2433396.2433483. [Stram et al.(2024)Stram, Abboud, Shtoff, Somekh, Raviv, and Koren] Rotem Stram, Rani Abboud, Alex Shtoff, Oren Somekh, Ariel Raviv, and Yair Koren. Mystique: A budget pacing system for performance opt...

    2024

  8. [2014]

    URL http://dx.doi.org/10.1145/2623330.2623366

    doi:10.1145/2623330.2623366. URL http://dx.doi.org/10.1145/2623330.2623366. [Karande et al.(2013)Karande, Mehta, and Srikant] Chinmay Karande, Aranyak Mehta, and Ramakrishnan Srikant. Optimizing budget constrained spend in search advertising. In Proceedings of the sixth ACM in...

    2013

  9. [2019]

    Two-sided fairness in rankings via lorenz dominance

    [Do et al.(2021)Do, Corbett-Davies, Atif, and Usunier] Virginie Do, Sam Corbett-Davies, Jamal Atif, and Nicolas Usunier. Two-sided fairness in rankings via lorenz dominance. Advances in Neural Information Processing Systems, 34:8596–8608,

    2021

  10. [2020]

    Tomlin, Jayavel Shanmugasundaram, Tasos Anastasakos, and Oliver Kennedy

    [Yang et al.(2010)Yang, Vee, Vassilvitskii, Tomlin, Shanmugasundaram, Anastasakos, and Kennedy]Jian Yang, Erik Vee, Sergei Vassilvitskii, John A. Tomlin, Jayavel Shanmugasundaram, Tasos Anastasakos, and Oliver Kennedy. Inventory allocation for online graphical display advertis...

    2010 arXiv

  11. [2021]

    [Gini(1912)] C. Gini. Variabilità e mutabilità: contributo allo studio delle distribuzioni e delle relazioni statistiche. [Fasc. I.]. Studi economico-giuridici pubblicati per cura della facoltà di Giurisprudenza della R. Università di Cagliari. Tipogr. di P. Cuppini,

    1912

  12. [2022]

    Regularized online allocation problems: Fairness and beyond

    [Balseiro et al.(2021)Balseiro, Lu, and Mirrokni] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fairness and beyond. In International Conference on Machine Learning , pages 630–639. PMLR,

    2021

  13. [2023]

    [Agarwal et al.(2014)Agarwal, Ghosh, Wei, and You] Deepak Agarwal, Souvik Ghosh, Kai Wei, and Siyu You

    URL https: //api.semanticscholar.org/CorpusID:261367675. [Agarwal et al.(2014)Agarwal, Ghosh, Wei, and You] Deepak Agarwal, Souvik Ghosh, Kai Wei, and Siyu You. Budget pacing for targeted online advertisements at linkedin. In Proceedings of the 20th ACM SIGKDD international co...

    2014

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.