{"id":"4c46a270-58c1-4f91-99db-5657c6b9f24c","arxiv_id":"2502.01862","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"OTA, a two-stage convex optimization and probabilistic ranking algorithm, improves Gini fairness of sponsored-search impressions over RCPacing and DMD baselines without losing click efficiency.","lead":"This paper proposes a non-auction method for allocating sponsored search ad slots that balances platform click efficiency with advertiser fairness, measured by a Gini index of impressions per budget. It could matter to online marketplaces because it offers a real-time alternative to auction-based systems and a benchmark for judging their fairness-efficiency trade-offs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central fairness claim rests on an unproven local-to-global link: per-query squared Gini proxy G_q (Eq. 10) is not shown to control the global Gini (Eq. 3) of total impressions per budget; the two-stage algorithm's decomposition lacks a supporting theorem.","rationale":"The paper contributes a practical heuristic with a clear algorithmic description, a correct convex reformulation, and a standard Frank-Wolfe convergence argument; the synthetic experiment attempts to validate the probabilistic ranking, and the real-data comparison is a useful data point. However, the central claim that OTA optimizes a global fairness-efficiency objective is undercut by the missing local-to-global connection. The reader's weakest_assumption identifies exactly this premise: per-query optimization of the squared proxy G_q is not shown to control the global Gini index of total impressions per budget. My analysis adds that a sufficient local-to-global guarantee would require minimizing the per-query L1 GMD, and that the squared L2 proxy weakens the connection further. I also note that Algorithm 2's without-replacement sampling does not in general reproduce α in expectation, so even the proxy allocation may not be realized; the paper's synthetic validation does not verify per-item marginals. Both issues are addressable: a supporting theorem or a controlled offline comparison (as proposed in concrete_test) would settle the local-to-global question, and a direct simulation of inclusion probabilities would validate or correct the sampling step. Since the empirical result remains a suggestive but unsupported observation rather than a consequence of the stated mechanism, the reader's conditional verdict is appropriate and should not be changed.","tokens_in":10874,"tokens_out":10555,"duration_ms":103490,"concrete_test":"To settle the local-to-global question, solve the global problem (6) exhaustively on a small instance (e.g., N=5 items, T=20 single-slot queries with fixed CTRs and budgets) and compare its optimal global Gini against the global Gini of the allocation obtained by running OTD-FW per query (summing the α_t over t) for several λ values. If the OTA allocation's global Gini is more than 20% above the global optimum and no better than a budget-proportional allocation, then per-query squared-proxy optimization does not control the reported metric.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The global objective (6) is defined in terms of the L1-based GMD over total impressions per budget across the whole horizon. The online algorithm instead solves, per query t, problem (12) with the squared L2 proxy G_q(α) = (1/N^2)Σ_{j,h}(α_j/B_j − α_h/B_h)^2, subject to Σ_j α_j = Γ(t). No theorem links solutions of (12) to the global Gini (3): the GMD of sums does not decompose into sums of per-query GMDs, and the squared proxy is not the same functional as the GMD used in the reported metric. By the triangle inequality one can bound the global GMD by the sum of per-query L1 GMDs, so minimizing the per-query L1 quantity would be a sufficient decomposition; the L2 proxy is a further, unproved substitution. Consequently, even a perfect per-query solution does not guarantee a low global Gini, and the claims in Section 6.2.3 (Tables 1–2) are empirical observations on a single five-day dataset, not consequences of the optimized objective. A secondary issue is that Algorithm 2's sampling without replacement from probabilities proportional to α does not, in general, yield marginal inclusion probabilities equal to α; for example, with N=3, K=2, Γ=2 and α=(1, 0.6, 0.4), the empirical marginals are approximately (0.5, 0.675, 0.486). The synthetic convergence check in Section 6.1 validates only aggregate metrics Eq and Gq, not per-item marginals, so the allocation actually deployed may differ from the optimized α.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11236,"tokens_out":7793,"duration_ms":71154,"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":[{"comment":"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.","section":"Section 4, Eqs. (8)-(12); Section 5.1"},{"comment":"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.","section":"Section 5.2, Algorithm 2"},{"comment":"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.","section":"Section 6.2.3, Tables 1-2 and Figure 2"}],"minor_comments":[{"comment":"Equation (5) is labeled as the efficiency definition but there is no Eq. (4); the numbering gap should be fixed.","section":"Section 3, Eq. (5)"},{"comment":"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.","section":"Section 5.1, proof of Proposition"},{"comment":"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.","section":"Algorithm 2, line 4"},{"comment":"The caption says 'PRPacing' instead of 'RCPacing'.","section":"Figure 2 caption"},{"comment":"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.","section":"Abstract and Conclusion"}],"recommendation":"major_revision","confidential_remarks":"The main unresolved issue is the gap between the per-query objective and the global fairness metric; this is a correctness-risk concern rather than a style issue. The empirical section is too thin to carry the global claim on its own. If the authors add a supporting bound or explicitly limit the claims to the per-query objective, the paper could become publishable. I would not recommend rejection because the per-query machinery and the dataset are real and the claims are in principle testable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: a genuinely useful industrial allocation scheme, but the fairness guarantee is asserted rather than proven. Worth a serious referee; needs a major revision.\n\nWhat is new here: a budget-only, non-auction product for sponsored search. The per-query virtual impression relaxation, squared-Gini quadratic objective, Frank-Wolfe solver, and probabilistic ranking are not in the cited prior work; the closest Gini papers are offline inventory allocation or ranking fairness. The convex reformulation is correct, and the convergence proposition is a clean application of Bubeck's theorem. The experiment compares against implementations from another group, uses the standard Gini index, and reports quantified improvements (roughly 23-35% lower Gini at comparable efficiency). That is real work and a useful baseline for future comparisons.\n\nThe soft spots are proportionate to how much the headline claim leans on them. The biggest one: there is no theorem connecting the per-query problem (12) to the global Gini (3). The global GMD of sums does not decompose into per-query GMDs, and (10) replaces the L1 GMD with an L2 proxy without argument. Minimizing per-query squared Gini may or may not control total-impression inequality; the Section 6.2.3 numbers are empirical observations on one five-day, single-category, single-slot dataset, not consequences of the optimized objective. That is the central gap.\n\nSecond: Algorithm 2 samples without replacement with probabilities proportional to alpha; the marginal inclusion probabilities are not alpha in general (a simple N=3, K=2, alpha=(1,0.6,0.4) gives marginals roughly (0.5,0.675,0.486)). The synthetic check validates aggregate E_q and G_q, not per-item marginals, so the deployed allocation can drift from the optimized distribution. This may be quantitatively minor, but it is unquantified, and there are no error bars anywhere.\n\nEvaluation limitations: no released code or data, only one ad slot, no true auction-based baseline. All fixable.\n\nWho it is for: ad-system engineers and online-allocation researchers. As an offline fairness-efficiency benchmark, OTA is immediately usable; as a proposed online mechanism with a fairness guarantee, it needs more work.\n\nRecommendation: accept for peer review, but with major revision. The authors should either prove a bound linking the per-query objective to global Gini, or reframe the paper as an empirical mechanism with no guarantee. Add marginal-inclusion analysis for the sampling stage.","headline":"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.","tokens_in":11776,"tokens_out":3679,"would_cite":true,"duration_ms":38509,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["sponsored search","traffic allocation","budget pacing","fairness","Gini index","online allocation","Frank-Wolfe","probabilistic ranking"],"falsifier":"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.","tokens_in":10635,"feed_emoji":"⚖️","tokens_out":10137,"duration_ms":83659,"temperature":0.7,"pith_summary":"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.","feed_headline":"Budget-only ad allocation cuts impression inequality by about a third","feed_subtitle":"Per-query convex optimizer beats auction pacing on fairness while keeping click efficiency.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Frank-Wolfe convergence theorem (Theorem 3.8) that the paper adapts to prove the per-query solver's rate.","marker":"Bubeck et al. 2015"},{"why":"Origin of the Gini mean difference and Gini index that the fairness objective is built on.","marker":"Gini 1912"},{"why":"The two-stage distribution-then-allocation idea the paper draws on for its virtual impression reformulation.","marker":"Li et al. 2024"},{"why":"Source of the RCPacing baseline and of the DMD/RCPacing implementations used in the real-data comparison.","marker":"Dai et al. 2024"},{"why":"Defines the dual mirror descent online allocation framework that serves as the DMD baseline.","marker":"Balseiro et al. 2020"},{"why":"Provides the click model with position multipliers $\\gamma_k$ and CTRs that defines impressions and efficiency.","marker":"Chuklin et al. 2022"},{"why":"Shows a Gini-based objective can be optimized for ad inventory allocation, motivating the Gini choice here.","marker":"Lejeune and Turner 2019"}],"fun_headline_variants":["Global ad optimizer cuts Gini unfairness by a third","Fairer ads without efficiency loss: a new allocation model","Swap auctions for convex optimization to slash ad inequality","Per-query convex solver beats auction pacing on fairness","New algorithm balances ad fairness and efficiency in real time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Global ad optimizer cuts Gini unfairness by a third","Fairer ads without efficiency loss: a new allocation model","Swap auctions for convex optimization to slash ad inequality","Per-query convex solver beats auction pacing on fairness","New algorithm balances ad fairness and efficiency in real time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000657,"raw_usage":{"total_tokens":3016,"prompt_tokens":964,"completion_tokens":2052,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":1975}},"tokens_in":580,"tokens_out":2052,"duration_ms":15796,"temperature":1.0,"reasoning_tokens":1975,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T14:12:47.341115+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Convex optimization: Algorithms and complexity","cited_arxiv_id":null,"evidence_quote":"Supplies the Frank-Wolfe convergence theorem (Theorem 3.8) that the paper adapts to prove the per-query solver's rate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Origin of the Gini mean difference and Gini index that the fairness objective is built on."},{"cited_title":"Click models for web search","cited_arxiv_id":null,"evidence_quote":"Provides the click model with position multipliers $\\gamma_k$ and CTRs that defines impressions and efficiency."}],"review_version":1}