pith. sign in

arxiv: 2605.20069 · v1 · pith:62PZUHJJnew · submitted 2026-05-19 · 💻 cs.LG · cs.GT

Smooth Partial Lotteries for Stable Randomized Selection

Alexander Goldberg , Giulia Fanti , Nihar B. Shah This is my paper

Pith reviewed 2026-05-20 06:31 UTC · model grok-4.3

classification 💻 cs.LG cs.GT
keywords selectionlotteryclippedlinearlotteriesscorepartialprobabilities
0
0 comments X

The pith

The Clipped Linear Lottery formalizes smoothness via a Lipschitz condition and achieves near-optimal worst-case regret while outperforming prior partial lotteries on stability and utility in both theory and real peer-review data.

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

Selection processes often score applicants and then randomly pick some to avoid over-relying on small score gaps. Existing random methods can be unstable: a one-point score change can swing a candidate's selection chance from near zero to near one. The authors define smoothness as requiring that small score changes produce only proportionally small probability changes. Their Clipped Linear Lottery sets probability to zero below a lower threshold, one above an upper threshold, and linear in between. They prove this design's regret is within a small factor of the best possible for any smooth rule. Tests on actual review scores from ICLR, NeurIPS, and a national science foundation show existing lotteries shift probabilities sharply with single-score tweaks, while the new method stays stable and keeps good overall selection quality.

Core claim

We prove that the Clipped Linear Lottery's worst-case regret matches a lower bound for any smooth selection rule up to a factor of (1 - k/n), where k/n is the acceptance rate.

Load-bearing premise

That the Lipschitz smoothness condition on the score-to-probability map is the appropriate stability notion and that the worst-case regret analysis under this condition captures the practical instability observed in real review data.

Figures

Figures reproduced from arXiv: 2605.20069 by Alexander Goldberg, Giulia Fanti, Nihar B. Shah.

Figure 1
Figure 1. Figure 1: Clipped Linear Lottery responds smoothly to score perturbations. Marginal selection probabilities before and after a one-point increase in proposal 5’s review score, with 2 awards for 8 candidates. Under the thresholded partial lottery, proposal 8 is selected deterministi￾cally, while the remaining award is allocated with equal probability among proposals 6 and 7; the score increase lifts proposal 5, split… view at source ↗
Figure 2
Figure 2. Figure 2: A concrete example of the Clipped Linear Lottery with [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Regret–smoothness tradeoff for existing partial lottery mechanisms. Down and to the left [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Regret vs. smoothness L at acceptance rate 10%. Down and to the left indicates a better tradeoff. The Clipped Linear Lottery achieves lower regret than softmax at every smoothness level across all datasets. 7.2 Regret–Smoothness Tradeoff We next measure regret as a function of the smoothness parameter L. For each dataset and acceptance rate, we compute the regret of the Clipped Linear Lottery and top-k sof… view at source ↗
Figure 5
Figure 5. Figure 5: Worst-case empirical smoothness vs. target global smoothness [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: CCDF of mean normalized utilities across datasets. Swiss NSF and Beta have heavier [PITH_FULL_IMAGE:figures/full_fig_p030_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Regret vs. Beta shape parameter α = β at acceptance rate 10%. As the distribution concentrates around 0.5 (larger α), regret decreases for both selection rules because the worst-case utility gap narrows. 0.2 0.4 0.6 0.8 1.0 L (lower is smoother) 0.00 0.05 0.10 0.15 0.20 Regret / k Beta 0.2 0.4 0.6 0.8 1.0 L (lower is smoother) 0.00 0.02 0.04 0.06 0.08 ICLR 0.2 0.4 0.6 0.8 1.0 L (lower is smoother) 0.00 0.0… view at source ↗
Figure 8
Figure 8. Figure 8: Regret vs. smoothness L at acceptance rate 33%. advantage over the softmax rule, consistent with the theoretical gap of O(log n). Figures 8 and 9 show the tradeoff between regret and smoothness at higher acceptance rates. In both cases, the Clipped Linear Lottery still outperforms softmax, although the gap is smaller. Intuitively, as the acceptance rate increases, regret normalized by the number of selecte… view at source ↗
Figure 9
Figure 9. Figure 9: Regret vs. smoothness L at acceptance rate 50%. 31 [PITH_FULL_IMAGE:figures/full_fig_p031_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Regret–smoothness tradeoff at acceptance rate 50%. Points show MERIT and Swiss NSF [PITH_FULL_IMAGE:figures/full_fig_p033_10.png] view at source ↗
read the original abstract

Competitive selection processes, from scientific funding to admissions and hiring, use evaluations to score candidates, and eventually choose a subset of them based on those scores. Recently, many organizations have adopted partial lotteries, which randomize selection based on evaluation scores. However, existing lottery designs are inherently unstable, as a small change to a single candidate's score can cause large shifts in their selection probabilities. This instability undermines a key goal of lotteries: reducing the influence of fine-grained score distinctions near the decision boundary. We propose smoothness as a design principle for partial lotteries, formalizing it as a Lipschitz condition on the mapping from review scores over candidates to selection probabilities. We introduce the Clipped Linear Lottery, a simple mechanism in which selection probabilities scale linearly with estimated quality between an upper threshold, above which we always accept, and a lower threshold, below which we always reject. We prove that the Clipped Linear Lottery's worst-case regret matches a lower bound for any smooth selection rule up to a factor of $(1 - k/n)$, where $k/n$ is the acceptance rate. We compare smooth selection to other stability notions like Individual Fairness and Differential Privacy, showing that the Clipped Linear Lottery achieves a better smoothness-regret tradeoff than alternatives. Experiments on real peer review data from ICLR 2025, NeurIPS 2024, and the Swiss National Science Foundation demonstrate that existing lottery designs are highly unstable in practice even under perturbations to a single score. Our experiments also confirm the tightness of our theoretical analysis and show that our proposed Clipped Linear Lottery achieves a better smoothness-utility tradeoff than alternatives in practice.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes smoothness, formalized as a Lipschitz condition on the mapping from candidate review scores to selection probabilities, as a design principle for partial lotteries in competitive selection. It introduces the Clipped Linear Lottery, in which selection probabilities scale linearly with estimated quality between fixed upper and lower thresholds. The central theoretical result is a proof that this mechanism's worst-case regret matches a lower bound for any smooth selection rule up to a multiplicative factor of (1 - k/n), where k/n is the acceptance rate. The work compares smoothness to individual fairness and differential privacy, and validates the approach with experiments on real peer-review data from ICLR 2025, NeurIPS 2024, and the Swiss National Science Foundation showing improved stability-utility tradeoffs over existing lottery designs.

Significance. If the regret-matching result holds under a norm that controls single-score perturbations, the paper supplies a simple, near-optimal mechanism that directly mitigates the practical instability observed when small score changes near the decision boundary produce large probability swings. The explicit comparison to alternative stability notions and the use of real peer-review datasets are strengths; the work supplies falsifiable predictions via the (1 - k/n) factor and reproducible experimental protocols that can be checked against the stated lower bound.

major comments (2)
  1. [§3 and §4] §3 (smoothness definition) and §4 (regret analysis): the Lipschitz condition is stated on the score-to-probability map, yet the norm (ℓ_∞ versus ℓ_2 or averaged) is left unspecified in the abstract and early sections. The claimed matching of the worst-case regret to the smooth-rule lower bound up to (1 - k/n) is load-bearing only if the norm ensures that an ε change in a single coordinate changes any probability by at most Lε; an ℓ_2 norm would permit large single-score swings while still satisfying the formal bound, severing the link between the theorem and the single-score instability demonstrated in the ICLR/NeurIPS experiments.
  2. [Theorem 1 / regret analysis] Theorem 1 (or equivalent regret statement): the proof sketch must explicitly invoke the norm chosen for the Lipschitz condition when deriving the (1 - k/n) factor; without this, it is unclear whether the lower-bound matching survives the single-coordinate perturbations used in the empirical section.
minor comments (2)
  1. [Experiments] Experiments section: report the exact perturbation magnitude and the number of trials used when measuring probability shifts under single-score changes; this would make the empirical confirmation of the theoretical tightness easier to reproduce.
  2. [Notation and tables] Notation: ensure the acceptance rate k/n is defined consistently between the theorem statement and the experimental tables.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and valuable comments, which highlight the importance of precisely specifying the norm in our smoothness definition to connect the theoretical guarantees with the empirical single-score perturbations. We address each major comment below and will revise the manuscript to improve clarity.

read point-by-point responses

  1. Referee: [§3 and §4] §3 (smoothness definition) and §4 (regret analysis): the Lipschitz condition is stated on the score-to-probability map, yet the norm (ℓ_∞ versus ℓ_2 or averaged) is left unspecified in the abstract and early sections. The claimed matching of the worst-case regret to the smooth-rule lower bound up to (1 - k/n) is load-bearing only if the norm ensures that an ε change in a single coordinate changes any probability by at most Lε; an ℓ_2 norm would permit large single-score swings while still satisfying the formal bound, severing the link between the theorem and the single-score instability demonstrated in the ICLR/NeurIPS experiments.

    Authors: We agree that explicit specification of the norm is necessary for the claimed connection. The Lipschitz condition in the manuscript is defined with respect to the ℓ_∞ norm on the score vector: for selection probability vectors p and p', ||p - p'|| ≤ L ||s - s'||_∞. This ensures that a perturbation of size ε in any single score (where ||Δs||_∞ = ε) changes probabilities by at most Lε, directly addressing the single-score instability in the experiments. We will revise the abstract, §3, and early sections to state this norm explicitly and will add a sentence clarifying why ℓ_∞ is the appropriate choice for controlling per-candidate score changes. revision: yes

  2. Referee: [Theorem 1 / regret analysis] Theorem 1 (or equivalent regret statement): the proof sketch must explicitly invoke the norm chosen for the Lipschitz condition when deriving the (1 - k/n) factor; without this, it is unclear whether the lower-bound matching survives the single-coordinate perturbations used in the empirical section.

    Authors: We thank the referee for this observation. The proof of the regret bound in Theorem 1 applies the ℓ_∞ Lipschitz property precisely when bounding the effect of single-coordinate score changes: if two score vectors differ by at most ε in one coordinate, the resulting probability difference is at most Lε, which is used to show that the worst-case regret is at most (1 - k/n) times the lower bound that holds for any L-smooth rule. We will expand the proof sketch in §4 to explicitly reference the ℓ_∞ norm at each invocation of the Lipschitz condition and will add a remark confirming that the (1 - k/n) factor therefore carries over to the single-score perturbations studied empirically. revision: yes

Circularity Check

0 steps flagged

No circularity detected in the near-optimality claim

full rationale

The paper introduces smoothness as a Lipschitz condition on the score-to-probability mapping and derives a lower bound on worst-case regret that applies to every mechanism satisfying the condition. It then proves that the Clipped Linear Lottery attains regret within a (1-k/n) factor of that class-wide lower bound. This is a standard matching upper bound for a newly defined class rather than a reduction of the result to a fitted parameter, self-definition, or self-citation chain. The derivation remains self-contained against the stated assumptions and external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central contribution rests on introducing a Lipschitz smoothness condition as the stability requirement and on a linear interpolation between thresholds; no free parameters or new invented entities are visible from the abstract.

axioms (1)
  • domain assumption Selection probabilities must satisfy a Lipschitz condition with respect to changes in review scores.
    Formalized as the design principle for stability in the abstract.

pith-pipeline@v0.9.0 · 5823 in / 1237 out tokens · 50427 ms · 2026-05-20T06:31:06.104918+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 2 internal anchors

  1. [1]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. InTheory of Cryptography, 3rd Theory of Cryptography Conference, TCC 2006, volume 3876 ofLecture Notes in Computer Science, pages 265–284. Springer,

    work page 2006

  2. [2]

    doi: 10.1007/11681878

    work page doi:10.1007/11681878

  3. [3]

    Ferric C Fang and Arturo Casadevall

    Accessed: 2025-05-07. Ferric C Fang and Arturo Casadevall. Research funding: The case for a modified lottery,

    work page 2025

  4. [4]

    Ref. no. 2025–01621. Alexander Goldberg, Giulia Fanti, and Nihar B Shah. A principled approach to randomized se- lection under uncertainty: Applications to peer review and grant funding. InThe Thirty-ninth Annual Conference on Neural Information Processing Systems,

    work page 2025

  5. [5]

    Rankmax: An adaptive projection alternative to the softmax function

    Weiwei Kong, Walid Krichene, Nicolas Mayoraz, Steffen Rendle, and Li Zhang. Rankmax: An adaptive projection alternative to the softmax function. InAdvances in Neural Information Processing Systems 33 (NeurIPS 2020),

    work page 2020

  6. [6]

    NeurIPS 2024 Conference Submissions.https://openreview.net/submissions? venue=NeurIPS.cc/2024/Conference,

    OpenReview. NeurIPS 2024 Conference Submissions.https://openreview.net/submissions? venue=NeurIPS.cc/2024/Conference,

    work page 2024

  7. [7]

    ICLR 2025 Conference Submissions.https://openreview.net/submissions? venue=ICLR.cc/2025/Conference,

    OpenReview. ICLR 2025 Conference Submissions.https://openreview.net/submissions? venue=ICLR.cc/2025/Conference,

    work page 2025

  8. [8]

    Nihar B Shah, Melisa Bok, Xukun Liu, and Andrew McCallum

    Accessed: 2025-05-07. Nihar B Shah, Melisa Bok, Xukun Liu, and Andrew McCallum. Identity theft in ai conference peer review.Communications of the ACM, 68(12):32–34,

    work page 2025

  9. [9]

    SIGMOD 2025 call for research papers.https://2025

    SIGMOD 2025 Program Committee. SIGMOD 2025 call for research papers.https://2025. sigmod.org/calls_papers_sigmod_research.shtml,

    work page 2025

  10. [10]

    Tight lower bounds for differentially private selection

    Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 552–

    work page 2017

  11. [11]

    Tight Lower Bounds for Differentially Private Selection

    doi: 10.1109/FOCS.2017.57.https://arxiv.org/abs/ 1704.03024. The British Academy. Partial randomisation trial extended after diversity of ap- plicants and award holders increases.https://www.thebritishacademy.ac.uk/news/ partial-randomisation-trial-extended-small-research-grants/, April

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/focs.2017.57.https://arxiv.org/abs/ 2017

  12. [12]

    Giulia Trentacosti

    Accessed: 2025-05-07. Giulia Trentacosti. Using lotteries to allocate research funding: Perspec- tives from switzerland. Open Science Blog, University of Groningen Li- brary, September

    work page 2025

  13. [13]

    Interview with Marco Bieri, Swiss National Science Foundation

    URLhttps://www.rug.nl/library/open-access/blog/ using-lotteries-to-allocate-research-funding-perspectives-from-switzerland? lang=en. Interview with Marco Bieri, Swiss National Science Foundation. UK Metascience Unit. A year in metascience (2025). Technical report, Department for Sci- ence, Innovation and Technology, June 30

    work page 2025

  14. [14]

    Published 30 June

    URLhttps://www.gov.uk/government/ publications/a-year-in-metascience-2025. Published 30 June

    work page 2025

  15. [15]

    USENIX security 2025 conference format.https: //github.com/USENIX-Security-2025/conference-format, April

    USENIX Security 2025 Program Committee. USENIX security 2025 conference format.https: //github.com/USENIX-Security-2025/conference-format, April

    work page 2025

  16. [16]

    Projection onto the capped simplex

    Accessed: 2025-05-07. Weiran Wang and Canyi Lu. Projection onto the capped simplex.arXiv preprint arXiv:1503.01002,

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  17. [17]

    Conditioning onG −j, there is a deterministic thresholdθ j such thatjis selected iffv j +G j ≥θ j, namely thek-th largest among{v ℓ+Gℓ :ℓ̸=j}

    Combining, the column sum equals P i |∂jpi|= 2∂ jpj. Conditioning onG −j, there is a deterministic thresholdθ j such thatjis selected iffv j +G j ≥θ j, namely thek-th largest among{v ℓ+Gℓ :ℓ̸=j}. Hencep j(v) =E G−j[1−FG(θj−vj)]. Differentiating and usingf G(x)≤1/(eτ),∂ jpj =E G−j[fG(θj −v j)]≤1/(eτ).Thus every column ofJhasℓ 1 norm at most 2/(eτ), so∥p(u)...

    work page 2025

  18. [18]

    Since log P i∈Rt eui/τ ≥M t/τand H(p t)≤log|R t|,M t −E[u it |R t]≤τlog|R t|

    The conditional one-step regretM t −E[u it |R t], whereM t = max i∈Rt ui, is bounded via the variational form of log-sum-exp:E[u it |R t] = τlog P i∈Rt eui/τ −τ H(p t) wherep t is the softmax onR t. Since log P i∈Rt eui/τ ≥M t/τand H(p t)≤log|R t|,M t −E[u it |R t]≤τlog|R t|. Summing overtand bounding log(n−t+ 1)≤logn yields R(D;u)≤kτlogn. A.7 Individual ...

    work page 2023

  19. [19]

    For completeness, Algorithm 2 outlines an exact, non-iterative implementation with runtimeO(n 2), adapted from Wang and Lu (2015)

    and water-filling methods (Bairaktari et al., 2023). For completeness, Algorithm 2 outlines an exact, non-iterative implementation with runtimeO(n 2), adapted from Wang and Lu (2015). The algorithm first finds the 2nbreakpoints at whichS(b) changes (where a candidate’s probability hits the floor of 0 or the ceiling of 1), then locates the interval of brea...

    work page 2023

  20. [20]

    ,0| {z } h+1 , δ,

    1 1 (0, . . . ,0| {z } h+1 , δ, . . . , δ| {z } h ) flip one 0 toδ Remark D.2.For each of the above utilities,d u =D u. In general,D u is a worst-case global upper bound on the Lipschitz quotient over all row pairs, whereasd u is a guarantee on the maximum achievable quotient for any distance budget up to 1/du. It always holds thatd u ≤D u, with equality ...

    work page 2019

  21. [21]

    It effectively requires the funder to relax their ex post validity constraint

    This resolution suggests that a funder could preserve exact smoothness by padding intervals to be wide enough relative to 1/w(equivalently, setting a stricter standard for asserting dominance). It effectively requires the funder to relax their ex post validity constraint. Resolution 2: Projection onto valid marginals.When the core-width condition fails, a...

    work page 2025