arXiv CSopen access

Smooth Partial Lotteries for Stable Randomized Selection

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

Smooth Partial Lotteries for Stable Randomized Selection Alexander Goldberg, Giulia Fanti, and Nihar B. Shah Carnegie Mellon University

arXiv:2605.20069v1 [cs.LG] 19 May 2026

{akgoldbe,gfanti,nihars}@andrew.cmu.edu

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.

Introduction

In settings like scientific funding, peer review, job screening, and university admissions, decision makers evaluate candidates and then select a subset for acceptance. Typically, multiple reviewers evaluate each candidate, these reviews are aggregated into a rank-ordered list, and then candidates are selected from the top down until the selection budget is exhausted. Recently, there has been growing interest in introducing randomization into such selection processes. Most prominently, many scientific funding agencies have adopted “partial lotteries” to allocate research grants, including the New Zealand Health Research Council (Liu et al., 2020), the Swiss National Science Foundation (Adam, 2019), the European Research Council (European Research Council, 2023), and many other funders (Science Foundation Ireland, 2024; Volkswagen Foundation, 2025; The British Academy, 2025; Austrian Science Fund (FWF), 2026; Formas, 2026; Luebber et al., 2025). 1

before

small increase in one review

0.8

0.6

0.4

0.2

change

0.75

Marginal selection probability

Aggregated review score

after

large probability jump

0.5

0.25

0.75

small change

0.5

0.25

Proposal index

(sorted by initial score)

(a) Aggregated review scores

(b) Thresholded partial lottery

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 deterministically, while the remaining award is allocated with equal probability among proposals 6 and 7; the score increase lifts proposal 5, splitting the award three ways at 1/3 each. A one-point change thus causes a discontinuous jump (proposal 5 from 0 to 1/3) and abrupt drops for proposals 6 and 7. Under our Clipped Linear Lottery, the same perturbation induces only small, smoothly varying changes in every proposal’s selection probability. In a partial lottery, a decision maker elicits quality evaluations and then selects candidates in a randomized fashion according to a probability distribution determined by those evaluations. A key practical motivation for randomization is to reduce deliberation over small quality differences: [Randomization] reduces the time needed for an assessment or moderation panel to discuss applications. Panellists are less likely to spend time trying to arbitrarily differentiate between applications receiving similar quality-based scores that fall around the funding line, because they can “agree to disagree” by simply leaving it to chance (UK Metascience Unit, 2025).

Indeed, numerous funding agencies have cited reducing reviewer deliberation time as a justification when adopting partial randomization (Liu et al., 2020; Trentacosti, 2021; Formas, 2026). Proponents of randomization have also argued that a partial lottery reduces arbitrariness near the funding line, encourages high-risk research, and mitigates reviewer partiality (Fang and Casadevall, 2016; Horbach et al., 2022; Gould et al., 2025; Feliciani et al., 2024). In practice, existing lottery designs for scientific funding sort proposals into three groups: proposals above a high-quality threshold are funded automatically, proposals below a low-quality threshold are rejected, and proposals in the middle are entered into a uniform lottery with equal selection probabilities. This three-tier design is inherently unstable. As illustrated in Figure 1, a small increase in one review can move the highlighted candidate from rejection into the lottery group, causing a large jump in selection probability. More generally, any candidate near the bound2

ary between reject, lottery, and accept groups may experience a discontinuous change in selection probability after an arbitrarily small score perturbation. In fact, Goldberg et al. (2025) show that existing lottery designs can exhibit “maximum instability,” where an arbitrarily small change to a single review can shift the mechanism from deterministic selection to uniform random selection over all applicants. Our empirical results in this work show that this instability is not only theoretical. In Section 7.1, we find that in real peer review processes at ICLR, NeurIPS, and the Swiss NSF, changing a single review by one point can change an applicant’s selection probability by more than 0.3 under existing lottery designs. Instability is problematic because it reintroduces the kind of arbitrariness from small changes to review scores that randomization is meant to prevent. If two candidates have nearly identical evaluations, a small change to one review should not sharply change chances of selection. We capture this requirement through smoothness: a selection rule is smooth if small changes in review scores can produce only bounded changes in selection probabilities. In order to guarantee smoothness, we propose a Clipped Linear Lottery. Our Clipped Linear Lottery rule first aggregates reviews into a score for each candidate. It then assigns selection probabilities that increase linearly with this score, with probabilities clipped at zero and one when candidates are sufficiently weak or strong. As illustrated in Figure 1, a small review perturbation moves the highlighted candidate only slightly along the linear part of the probability curve. The result is a small change in selection probability, rather than a discontinuous jump across a decision boundary. The Clipped Linear Lottery has several practical benefits: • Stability. We formally prove that small changes in individual reviews can only produce bounded changes in selection probabilities. • Quality awareness. Higher-scoring candidates receive higher selection probabilities. • Transparency. The rule is easy to explain, as selection probabilities increase linearly with estimated quality until they are clipped at zero or one. • Fairness. The intuitive notion of Individual Fairness (Dwork et al., 2012) requires that candidates with similar reviews receive similar selection probabilities. Bairaktari et al. (2023) show that the clipped-linear form of the Clipped Linear Lottery is optimal for trading off Individual Fairness and selection quality. This gives an additional reason to adopt the Clipped Linear Lottery to ensure fairness in the treatment of similarly evaluated candidates. These benefits require balancing smoothness against selection quality. A selection rule can be perfectly smooth by ignoring the reviews entirely, for example by sampling uniformly from all candidates. At the other extreme, a utility-maximizing rule deterministically selects the top-k candidates, but is not smooth. We formalize this tradeoff between smoothness and utility and show that the Clipped Linear Lottery is near-optimal. Our primary contributions are: (1) Formalizing smoothness for partial lotteries. We define smooth selection rules using a Lipschitz condition on the mapping from review scores to marginal selection probabilities. This gives the interpretable guarantee that changing any single review score by one point shifts total selection probabilities by a bounded amount. (2) Design and analysis of the Clipped Linear Lottery. We introduce the Clipped Linear Lottery and prove that it is L-smooth. We also prove a worst-case regret bound matching a

lower bound for any smooth selection rule within a factor of up to a factor of (1 − k/n), where k/n is the acceptance rate. (3) Comparison to alternative stability notions. We show that standard Differential Privacy (DP) does not imply smoothness, while the generalization of Metric DP gives smoothness but at a factor-k regret penalty in the worst case. We then analyze top-k softmax sampling and prove that it achieves smooth marginal selection probabilities, but incurs higher regret than the Clipped Linear Lottery. (4) Empirical validation on real peer review data. On three real peer review datasets (ICLR 2025, NeurIPS 2024, Swiss NSF) we demonstrate that existing partial lottery designs are highly unstable under single-review perturbations and show that the Clipped Linear Lottery gives significantly better smoothness–utility tradeoffs than existing lottery designs in practice. We also demonstrate that the Clipped Linear Lottery dominates the softmax rule across smoothness levels and empirically confirm tightness of our theoretical bounds. An open-source implementation of our algorithm and all experimental code are available at github.com/akgoldberg/smooth lottery.

Related Work

Partial Lotteries for Scientific Funding and Peer Review. Recent works have designed algorithms for partial lotteries in scientific funding and peer review. MERIT (Goldberg et al., 2025) and the Swiss NSF Partial Lottery (Heyard et al., 2022) estimate intervals for proposal quality, with overlapping intervals indicating uncertainty about the relative quality of proposals. These methods use intervals to decide when randomization is appropriate. Our work targets a different design goal. Rather than explicitly modeling uncertainty about proposal quality, we require the mapping from review scores to marginal selection probabilities to be stable. Empirically, we show that existing interval-based lotteries are highly non-smooth in practice; see Section 7.1 for details. A key difference between this prior work and our formulation is what information each approach extracts from review scores. In particular, MERIT (Goldberg et al., 2025) emphasizes the use of ordinal information: intervals encode which proposals may or may not dominate others, making the approach natural when the numerical scale of review scores is not trusted or a funder wishes to avoid making assumptions about how reviewers interpret the scale. In contrast, our smoothness framework treats the review scale as meaningful enough to define small perturbations, and asks that these perturbations have only limited effects on marginal selection probabilities. In Section 6, we discuss how smoothness can be combined with intervalbased validity constraints when a funder also wants to enforce them. In practice, the choice depends on what concern is most important. If the funder wants the lottery to reflect uncertainty about which proposals are better, especially when numerical review scores are not fully trusted, then an interval-based method such as MERIT (Goldberg et al., 2025) is a natural fit. If the funder wants to limit how much any one review score can affect selection probabilities, then Clipped Linear Lottery is the more direct tool. These concerns can overlap, but the two mechanisms prioritize different failure modes. Randomized Selection and the Clipped Linear Lottery. The Clipped Linear Lottery has appeared independently under different names in several contexts. In machine learning, Kong 4

et al. (2020) introduced it as the RankMax operator, an adaptive projection alternative to the softmax function, while Martins and Astudillo (2016) proposed the closely related sparsemax (for the k = 1 case). Most relevant to our work, Bairaktari et al. (2023) studied fair cohort selection and proved that the clipped-linear rule is exactly instance-optimal for maximizing linear utility subject to Individual Fairness constraints; we discuss this result in detail in Section 5.1. However, the Clipped Linear Lottery has not previously been proposed or analyzed as a mechanism for designing partial lotteries in evaluation and selection settings such as peer review, and it is not obvious a priori that it is a good mechanism for our problem of interest. We provide a novel smoothness analysis—formalizing a Lipschitz condition on the mapping from review scores to selection probabilities—together with near-matching upper and lower bounds on the worst-case regret of any smooth selection rule. These results establish that the Clipped Linear Lottery is near-optimal for a fundamentally different objective (the smoothness–regret tradeoff) than those considered in prior work, and that it achieves a more efficient smoothness–regret tradeoff than natural alternatives like the softmax. Stable Selection. There is extensive literature on algorithmic stability notions for selection mechanisms, most prominently Differential Privacy (DP) (Dwork et al., 2006; Dwork and Roth, 2014) and Individual Fairness (IF) (Dwork et al., 2012). We compare our smoothness definition and the Clipped Linear Lottery to these alternatives in Section 5, showing that standard DP does not imply smooth marginals, that Metric DP implies smooth marginals but at a factor-k regret penalty (Steinke and Ullman, 2017; Bafna and Ullman, 2017), and that IF and smoothness are formally incomparable. As part of this comparison, we give a novel analysis of the Lipschitz constant of the top-k softmax mechanism (McSherry and Talwar, 2007; Kool et al., 2019) (known as the Exponential Mechanism in the DP literature), extending recent bounds for the k = 1 case (Nair, 2025) to the combinatorial setting of k > 1, which may be of independent theoretical interest. Randomization in other aspects of peer review. There are a few other parts of the peer review process where explicit randomization is used in practice. Computer science conferences employ automated methods to assign reviewers to papers, and randomization (Jecmen et al., 2020) is used in this assignment to mitigate problems of fraud via collusion rings (Littman, 2021) and identity thefts (Shah et al., 2025). The idea here is that no matter how a malicious reviewer and/or author games the system (Hsieh et al., 2025), there is a bounded probability of the target reviewer getting assigned target paper. Some computer science conferences use randomization to select which of the accepted papers will be presented as oral presentations (USENIX Security 2025 Program Committee, 2024; SIGMOD 2025 Program Committee, 2025). A consequence of interest is that randomization can allow for causal analysis of policies adopted in the review process (Saveski et al., 2023).

Problem Formulation

Our methods apply to settings such as admissions, scientific peer review, and job screening, where decision makers estimate candidate quality and select the top candidates. For concreteness, throughout we will describe a funder evaluating candidates.

Randomized Selection Rule. The funder evaluates n candidates and seeks to select k candidates of highest quality. Each candidate receives r numeric reviews, with scores normalized to lie in the unit interval. The review data is therefore represented as a matrix X ∈ [0, 1]n×r , where Xi,j denotes the score assigned to candidate i ∈ [n] by reviewer j ∈ [r].1 For simplicity of exposition, we assume each candidate receives the same number of reviews; our formulation naturally extends to variable numbers of reviews (Appendix C). The funder randomizes decisions by specifying a randomized selection rule D : [0, 1]n×r → ∆(K), where K = {S ⊆ [n] : |S| = k} is the set of all k-size subsets of candidates, and ∆(K) denotes the set of probability distributions over K. Given review data X, the rule D(X) defines a distribution over size-k subsets of candidates. Since candidates experience decisions through individual acceptance probabilities, we focus on the induced marginal selection probabilities p : [0, 1]n×r → [0, 1]n , defined by pi (X) = PS∼D(X) [ i ∈ S ] for i ∈ [n]. Smoothness. We formalize the requirement that the selection rule be stable to changes in review scores as a smoothness property: small changes in review scores should lead to small changes in candidates’ chances of acceptance. Since these chances are determined by the marginal probabilities, we define smoothness as a Lipschitz condition on p: Definition 3.1 (L-smooth selection rule). For L ≥ 0, the selection rule D is L-smooth if its induced marginal probability function p satisfies ∥p(X) − p(X ′ )∥1 ≤ L ∥X − X ′ ∥1,1 where ∥A∥1,1 =

for all X, X ′ ∈ [0, 1]n×r ,

i,j |Ai,j |.

This condition ensures the stability of candidates’ selection chances with respect to review scores: if a single review changes by δ, the total absolute change in selection probabilities is at most L δ. Utility. A selection rule should also select high-quality candidates. Hence, we introduce a utility function that depends on reviews. Given review data X, the funder has utility vector u(X) ∈ Rn , where ui (X) represents the utility of selecting candidate i. The funder’s utility when selecting a set of candidates is the sum of the selected candidates’ utilities. Since D induces marginal probabilities p, its expected utility is p(X)⊤ u(X). The regret of a selection rule is its utility loss relative to optimal deterministic selection, R(D; X) = OPT(X) − p(X)⊤ u(X), where OPT(X) is the utility obtained by selecting the k candidates with highest utility. Our goal is to design a L-smooth selection rule that minimizes the worst-case regret, giving the minimax design problem: n o min max OPT(X) − p(X)⊤ u(X) D:[0,1]n×r →∆(K)

subject to

X∈[0,1]n×r

∥p(X) − p(X ′ )∥1 ≤ L∥X − X ′ ∥1,1 ,

∀X, X ′ ∈ [0, 1]n×r ,

where p denotes the marginal selection probabilities induced by D. 1

We use the standard notation [κ] to denote the set {1, . . . , κ} for any positive integer κ.

Utilities u(X) = (0.1, 0.4, 0.7, 1.0)

Shift by b = −0.6 (−0.4, 0.2, 0.8, 1.4)

Scale by w = 2 (0.2, 0.8, 1.4, 2.0)

Clip to [0, 1] p(X) = (0, 0.2, 0.8, 1)

Figure 2: A concrete example of the Clipped Linear Lottery with n = 4 candidates and budget k = 2, following Algorithm 1. Utilities are scaled by w = 2, then shifted by an intercept b = −0.6 chosen so that the clipped probabilities sum to the budget. Clipping the shifted values to [0, 1] gives marginals p(X) = (0, 0.2, 0.8, 1), which sum to k = 2. Thus, the lowest-utility candidate is auto-rejected, the highest is auto-accepted, and the two middle candidates form the active lottery pool. Smooth Utility Function. We assume the funder evaluates candidates using a utility function that varies smoothly with the review scores. Specifically: Definition 3.2 (Du -Lipschitz utility function). Utility function u : [0, 1]n×r → Rn is Du -Lipschitz if for all review matrices X, X ′ ∈ [0, 1]n×r , ∥u(X) − u(X ′ )∥1 ≤ Du ∥X − X ′ ∥1,1 . P For example, the mean score ui (X) = 1r rj=1 Xi,j is Du -Lipschitz for Du = 1/r. The median, min, and max score are all 1-Lipschitz. The Lipschitz utility function assumption is necessary. If the utility function were arbitrarily non-smooth, then a small change in review scores could produce a large change in utility, making it impossible for any smooth selection rule to achieve low worst-case regret with respect to this utility function.

Optimal Smooth Lottery Design

In Section 4.1, we introduce a simple, efficient, and interpretable Clipped Linear Lottery and analyze its smoothness and regret; in Section 4.2, we prove a lower bound establishing optimality of the 1 Clipped Linear Lottery up to a factor of 1−k/n . Since smoothness and regret depend only on the marginal probabilities, we design mappings from review data to selection probabilities; any sampling scheme implementing these marginals can be used for the final selection.

4.1

Clipped Linear Lottery

We now introduce the Clipped Linear Lottery, a clipped-linear partial lottery described in Algorithm 1. The selection rule assigns marginal selection probabilities by scaling candidate utilities, shifting them by a common intercept to satisfy the budget, and clipping the result to [0, 1]. This partitions candidates into three tiers: an auto-accept pool (pi = 1), an auto-reject pool (pi = 0), and a lottery pool where selection probabilities scale linearly with estimated quality. The slope w controls the smoothness–utility trade-off. Smaller L gives a flatter slope, expanding the lottery pool toward uniform selection. Larger L gives a steeper slope, shrinking the lottery pool toward deterministic top-k selection. Figure 2 illustrates the Clipped Linear Lottery on a concrete example. The Clipped Linear Lottery has several useful properties. Uniqueness. For every utility vector and budget, the Clipped Linear Lottery produces a unique probability vector (Wang and Lu, 2015).

Algorithm 1 Clipped Linear Lottery (Kong et al., 2020; Bairaktari et al., 2023) Input: Reviews X, utility u with Lipschitz constant Du , smoothness parameter L > 0, budget k 1: Compute utilities ui ← ui (X) for all i ∈ [n] 2: Set the slope w ← L/(2Du ) 3: Scale utilities zi ← w · ui 4: Compute intercept b ∈ R satisfying budget constraint, n X

clip[0,1] (zi + b) = k

i=1

where clip[0,1] (x) = min{1, max{0, x}}, using Algorithm 2 (Appendix B.1). 5: Set marginal probabilities

pi (X) ← clip[0,1] (zi + b),

i ∈ [n]

6: Sample size-k set S ⊂ [n] with marginal probabilities p(X), e.g., using systematic sampling (Madow,

1949) 7: return Marginal probabilities p(X) and selected set S

Efficient computation. There are two computationally nontrivial steps in Algorithm 1. First, we must compute an intercept b satisfying the budget constraint (line 4). This can be done efficiently using existing algorithms for projection onto the capped simplex (Wang and Lu, 2015; Bairaktari et al., 2023); for completeness, Algorithm 2 in Appendix B.1 gives one exact implementation. Second, the Clipped Linear Lottery specifies marginal selection probabilities rather than a unique joint distribution over selected sets. Given marginals p, any sampling scheme that returns size-k subsets with these marginals can be used for the final selection (line 6). One simple option is classical systematic sampling (Madow, 1949). Monotonicity in budget. For fixed utilities and smoothness parameter L, increasing the budget k can never decrease any candidate’s selection probability. This contrasts with existing lottery designs, which can violate this natural monotonicity property (Goldberg et al., 2025). Monotonicity of the lottery pool. For fixed utilities and budget, the size of the active lottery pool {i : 0 < pi < 1} is non-increasing in the smoothness parameter L. Equivalently, enforcing a smoother lottery by decreasing L can only increase, or leave unchanged, the number of candidates subject to randomization. Thus, a funder that wants to cap the lottery-pool size, for example for political or institutional reasons, can sweep over L and choose the smoothest lottery that satisfies this constraint. Formal statements and proofs of the monotonicity properties appear in Appendix B.2. 4.1.1

Smoothness

We first show that the Clipped Linear Lottery satisfies the target smoothness guarantee. The following theorem shows that setting w = L/(2Du ), as in Algorithm 1, is sufficient to guarantee L-smoothness. Theorem 4.1 (Smoothness of the Clipped Linear Lottery). If u is Du -Lipschitz, then the Clipped Linear Lottery in Algorithm 1 guarantees L-smoothness. 8

This smoothness bound is tight within a factor of 1 − n1 ; that is, there are instances where the Clipped Linear Lottery is at least (1 − n1 )L-smooth. We give the full proof in Appendix A.1 and empirically validate tightness in Section 7.3. The proof intuition is as follows. If b were fixed, then changing the reviews by magnitude δ could change the scaled utilities by at most wDu δ, since u is Du -Lipschitz and clipping is 1-Lipschitz. The P remaining factor of 2 comes from enforcing the budget. The intercept b must shift so that i pi (X) = k, and this common shift can change many candidates’ probabilities at once. In the worst case, this doubles the total ℓ1 change in marginal probabilities, giving at most 2wDu δ. Thus choosing w = L/(2Du ) guarantees L-smoothness. 4.1.2

Regret

We next bound the worst-case regret. Before doing so, we establish a geometric characterization of the Clipped Linear Lottery that plays a central role in the analysis. Proposition 4.2 (Projection characterization (Kong et al., 2020)). For every X, the Clipped Linear Lottery outputs the Euclidean projection of w · u(X) onto the capped simplex Cn,k = {p ∈ [0, 1]n : ∥p∥1 = k}. That is, p(X) = arg minp∈Cn,k 21 ∥p − w · u(X)∥22 . Because the Clipped Linear Lottery finds the valid probability distribution that is geometrically closest to the scaled utilities, we can use the properties of this projection to bound regret. Our proof (Appendix A.2) leverages this interpretation, algebraically rewriting the regret as a simple quadratic function that depends only on the chosen probabilities: Theorem 4.3 (Regret of the Clipped Linear Lottery). The worst-case regret of the Clipped Linear Lottery satisfies k 1 − nk Du max R(D; X) ≤ . X 2L Corollary 4.4 (Mean utility). If utilities are given by the mean review score for each candidate, then the worst-case regret of the Clipped Linear Lottery satisfies k 1 − nk max R(D; X) ≤ . X 2 Lr To interpret the bound, note that regret always lies in [0, k] because utilities lie in [0, 1]. Uniform random selection among all candidates is perfectly smooth and has worst-case regret k(1 − k/n). Theorem 4.3 bounds the regret of the Clipped Linear Lottery by this natural baseline scaled by Du /(2L): larger L permits a steeper rule and therefore yields a smaller regret bound. Corollary 4.4 follows immediately because the mean utility has Lipschitz constant Du = 1/r. Intuitively, as the number of reviews per candidate increases, each individual review has less influence on the mean, so the worst-case regret bound decreases for any fixed smoothness parameter.

4.2

Regret Lower Bound

We next show that the Clipped Linear Lottery achieves nearly the lowest regret attainable by any smooth mechanism. For simplicity, we state the result for mean utility in the main text; however, the proof technique and near-optimality guarantee extend to many other utility functions, including the median, minimum, and maximum review score (Appendix D.1). 9

Theorem 4.5 (Regret lower bound for L-smooth selection rules with mean utility). Let utilities 1 Pr be the mean review scores ui (X) = r j=1 Xi,j , and let D be any L-smooth selection rule. Then, the worst-case regret of D is at least  2  k 1 − nk k 1    1− , , if L ≥  2rL r n max R(D; X) ≥  X  1 k k L r   , if L < 1− . k 1 − − n 2 r n Theorem 4.5 shows that the Clipped Linear Lottery is near-optimal for the smoothness–regret tradeoff. In the regime L ≥ 1r (1 − nk ), the lower bound differs from the regret upper bound of the Clipped Linear Lottery (Corollary 4.4) only by a factor of 1− nk . Thus, no smooth selection rule can substantially improve over the Clipped Linear Lottery in worst-case regret. The regime L ≥ 1/r is especially natural because the mean review score itself is (1/r)-Lipschitz, so this corresponds to requiring selection probabilities to be roughly as smooth as the utility function. In the opposite limit, as L → 0, the lower bound approaches k(1 − k/n), matching the regret of uniform random selection, whose probabilities are completely independent of the reviews. The proof, given in Appendix A.3, uses an indistinguishability argument. Start from a baseline instance in which all candidates receive identical zero scores. Since the mechanism must select k candidates in expectation, some candidates must receive relatively low selection probability. We then perturb the scores of these least-likely candidates by a small amount δ, making them the uniquely best candidates. Smoothness limits how much their selection probabilities can increase in response to this perturbation. As a result, any smooth rule must leave substantial probability mass on lower-quality candidates, incurring regret that scales with the strictness of the smoothness constraint. Our argument extends to many row-wise utility functions beyond the mean, including the minimum, maximum, and median review score. Appendix D.1 gives the general version and shows that the Clipped Linear Lottery remains near-optimal, up to the same factor of 1 − nk , for these utility functions as well.

Alternative Approaches to Stable Selection

We compare our smooth selection constraint against three prominent alternatives: Individual Fairness (IF), Differential Privacy (DP), and softmax-based randomized selection. As summarized in Table 1, these perspectives lead to sharply different guarantees. IF and smooth marginals are formally incomparable, although the Clipped Linear Lottery is also instance-optimal for IF (Section 5.1). Standard DP does not imply ℓ1,1 -smooth marginals because its neighboring relation treats arbitrarily small and large single review changes the same way (Section 5.2). Metric DP fixes this discontinuity issue and implies smooth marginals, but using it to certify L-smoothness incurs a k log(n/k)-fold regret penalty compared to the Clipped Linear Lottery. Finally, top-k softmax achieves smooth marginals but with higher regret than the Clipped Linear Lottery (Section 5.3).

5.1

Individual Fairness

Individual Fairness (IF) (Dwork et al., 2012) requires that candidates with similar utilities receive similar selection probabilities (formally: |pi (X) − pj (X)| ≤ α |ui (X) − uj (X)| for all i, j on every 10

Definition

Implication

Regret

Smooth selection (Def. 3.1)

Marginal selection probabilities vary smoothly with review scores.

No DP or IF guarantee.

Clipped Linear Lottery achieves near-optimal regret.

Individual fairness (IF)

Candidates with similar utilities receive similar selection probabilities.

No smooth marginals guarantee.

Clipped Linear Lottery is optimal.

Differential privacy (ε-DP)

Joint distribution over accepted candidates is stable under oneentry changes to the review matrix.

Does not imply ℓ1,1 -smooth marginals; arbitrarily small score changes may still cause discontinuous marginal changes.

Not a direct certification of smoothness.

Metric DP

Joint distribution changes with exp(ε∥X − X ′ ∥1,1 ).

Implies smooth marginals with L ≤ εk.

Regret worse by a factor of k log(n/k).

Table 1: Comparison of algorithmic stability definitions for selecting k of n candidates. X). IF and our smooth-marginals condition are formally incomparable: smoothness bounds how the same candidates’ probabilities change across review matrices, whereas IF bounds how different candidates’ probabilities differ on the same matrix; neither implies the other (Appendix A.7). Remarkably, prior work shows that the Clipped Linear Lottery (with w = α) is the exact, instanceoptimal solution to the IF-constrained utility-maximization LP (Bairaktari et al., 2023, Theorem 3). Thus, the Clipped Linear Lottery is not only near-optimal for smoothness across datasets, but also instance-optimal for individual fairness on any fixed review matrix.

5.2

Differential Privacy

Perhaps the most widely studied notion of algorithmic stability is differential privacy (DP) (Dwork et al., 2006). DP ensures that an algorithm’s output does not reveal too much about any single individual in the dataset. In our setting, DP constrains how much the joint distribution over selected subsets can change when a single review score is perturbed. Definition 5.1 (ε-Differential Privacy). A selection rule D : [0, 1]n×r → ∆(K) satisfies ε-differential privacy (ε-DP) if for all review matrices X, X ′ ∈ [0, 1]n×r differing in at most one entry, and every subset S ∈ K, Pr[D(X) = S] ≤ eε Pr[D(X ′ ) = S]. Our L-smoothness condition is a statement about marginal selection probabilities, and does not imply DP. A perfectly smooth selection rule can output uniform marginals (k/n, . . . , k/n) on all inputs, but implement those marginals using different joint distributions with disjoint support, which would not satisfy DP. Conversely, standard DP does not imply our ℓ1,1 -smoothness condition. The issue is that standard DP uses a discrete neighboring relation: any change to one review score is treated as one neighboring change, regardless of whether that score changes by an arbitrarily small amount or by a large amount. Thus, standard DP bounds the size of a change in the marginal probabilities, but this bound is constant and does not scale linearly with the magnitude of the change in review 11

scores. Hence, in general, there need not exist a finite L such that the smoothness condition holds for arbitrarily small changes in a single entry of the review matrix X, as we show in the following proposition. Proposition 5.1 (Standard DP does not imply smooth marginals). For every ε > 0, there exists an ε-DP selection rule that is not L-smooth with respect to ∥ · ∥1,1 for any finite L. We prove Proposition 5.1 by counterexample in Appendix A.4. The mechanism randomizes between two selected sets, S1 = {1, . . . , k} and S2 = {k + 1, . . . , 2k}, by looking at only a single review score, X1,1 , thresholding it at 1/2, and using randomized response on the resulting bit to decide whether to favor S1 or S2 . Since the probability ratio is bounded by eε , the rule is ε-DP under the standard one-entry replacement definition. But the marginals are discontinuous at the threshold: an arbitrarily small perturbation of X1,1 can change which set is favored, producing a constant-size change in the marginal probabilities. Hence standard DP does not imply smooth marginals. To obtain a DP-style condition that rules out such discontinuities, the privacy definition must scale with the distance between inputs. We use metric differential privacy, which generalizes DP by replacing the discrete neighboring relation with an arbitrary metric on the input space (Chatzikokolakis et al., 2013). Definition 5.2 (ε-Metric Differential Privacy). A selection rule D : [0, 1]n×r → ∆(K) satisfies ε-metric differential privacy with respect to ∥ · ∥1,1 if for all review matrices X, X ′ ∈ [0, 1]n×r and every subset S ∈ K, Pr[D(X) = S] ≤ exp ε∥X − X ′ ∥1,1 Pr[D(X ′ ) = S]. Metric DP controls the joint output distribution using the same distance on review matrices as our smoothness definition. This gives a bound on the smoothness of marginals: Proposition 5.2 (Metric DP implies smoothness of marginals). If a selection rule D satisfies εmetric differential privacy with respect to ∥ · ∥1,1 , then its induced marginals p are L-smooth for some L ≤ εk. This bound is tight as ε∥X − X ′ ∥1,1 → 0; see Appendix A.5. Metric DP is not regret-optimal for enforcing smooth marginals. Metric DP gives one way to certify L-smooth marginals: by Proposition 5.2, it suffices to take ε ≤ L/k. Since metric DP implies standard DP for one-entry changes, known lower bounds for pure-DP top-k selection imply error Ω(kDu log(n/k)/ε) (Steinke and Ullman, 2017; Bafna and Ullman, 2017). Setting ε ≈ L/k gives regret Ω(k 2 Du log(n/k)/L). This is larger than the lower bound for L-smooth rules in Theorem 4.5 by an additional factor k log(n/k). Thus, metric DP does not by itself navigate the smoothness–regret tradeoff well.

5.3

Softmax (Exponential Mechanism)

Section 5.2 shows that metric differential privacy does not, in itself, yield a good smoothness– utility tradeoff; however, Proposition 5.2 is a worst-case guarantee and does not rule out that specific metric-differentially private mechanisms perform better than the generic smoothness bound 12

in Proposition 5.2. We therefore study a well-known private selection mechanism: the Exponential Mechanism (McSherry and Talwar, 2007). Given utilities u ∈ Rn and temperature τ > 0, the softmax distribution is X στ (u)i = exp(ui /τ )/ exp(uj /τ ). j

By the top-k softmax rule we mean the procedure that samples k items without replacement by repeatedly sampling from the re-normalized softmax distribution over the remaining items. Equivalently, this is the Gumbel-top-k procedure obtained by adding i.i.d. Gumbel noise to utilities and selecting the k largest perturbed utilities (Kool et al., 2019). The exponential mechanism naturally extends to metric differential privacy: if the utility function is Du -Lipschitz with respect to a given metric, then sampling one item with probability proportional to exp(ui (X)/τ ) satisfies (2Du /τ )-metric DP (Kamalaruban et al., 2020). Theorem 5.3 (Smoothness and Regret of the Top-k Softmax Rule). Assume u is Du -Lipschitz. The top-k softmax rule with temperature τ induces L-smooth marginal selection probabilities with u L ≤ 2D eτ , and the worst-case regret satisfies maxX R(D; X) ≤ k τ log n. Theorem 5.3 shows that top-k softmax, like the Clipped Linear Lottery, can be tuned to satisfy u any desired smoothness level. In particular, setting τ = 2D eL guarantees L-smooth marginals and k log n gives regret at most 2DueL . This smoothness guarantee is stronger than what follows from the generic differential privacy argument above, since it does not lose an additional factor of k. However, it is still worse than the Clipped Linear Lottery’s regret bound by a logarithmic factor in n: the Clipped Linear Lottery scales as O(k/L), while top-k softmax scales as O(k log(n)/L). Thus, the Clipped Linear Lottery provides a better worst-case smoothness–regret tradeoff. This comparison is based on our theoretical upper bound on worst-case regret of the softmax. A sharper smoothness analysis for softmax could in principle narrow the gap, but our empirical results in Section 7.3 find instances where the bound is tight to within 5%. As an additional practical advantage, the Clipped Linear Lottery has sparse support—deterministically funding the strongest proposals and rejecting the weakest, restricting randomness to borderline cases—whereas the softmax rule has full support and assigns strictly positive inclusion probability to every candidate. The regret bound follows by extending standard guarantees for the Exponential Mechanism in the differential privacy literature (Dwork and Roth, 2014). However, the smoothness bound requires a novel analysis of the marginal inclusion probabilities induced by the top-k softmax rule, given in Appendix A.6.

Existing partial lottery designs

The most common lottery design used in practice partitions candidates into three tiers based on a score or rank statistic: auto-accept above a high threshold, auto-reject below a low threshold, and uniform randomization among candidates in the middle tier (Liu et al., 2020; Heyard et al., 2022; Volkswagen Foundation, 2025; The British Academy, 2025). As discussed in the Introduction and illustrated in Figure 1, these designs share a structural source of instability. Since tier membership is determined by sharp thresholds, an arbitrarily small perturbation to a single review can move a

candidate across a tier boundary, changing their selection probability by a constant amount. They are therefore inherently non-smooth. Recent lottery designs, including the Swiss NSF procedure (Adam, 2019; Heyard et al., 2022) and MERIT (Goldberg et al., 2025), also take interval estimates of candidate quality as input. For example, an interval might be formed from the minimum and maximum review scores assigned to a proposal. These intervals capture uncertainty about the relative quality of proposals: if two candidates’ intervals overlap, the funder treats their ordering as uncertain; if one candidate’s interval lies strictly above another’s, the funder treats the higher-scoring candidate as clearly dominating the lower-scoring one. This idea is formalized through an ex post validity constraint (Goldberg et al., 2025): if candidate i’s lower bound exceeds candidate j’s upper bound, then j should not be selected unless i is selected as well. This guarantee limits randomization to candidates who are plausibly comparable, preventing outcomes in which a clearly dominated candidate is selected while the candidate who dominates them is not. Can we combine ex post validity with smoothness? In general, the two desiderata may conflict. Suppose all candidates have near-zero-width, non-overlapping intervals. Then ex post validity forces deterministic rank-based selection: the top k candidates must be selected, and the remaining candidates must be rejected. But an arbitrarily small perturbation could move the k-th candidate below the (k +1)-st candidate, causing their selection probability to jump from 1 to 0. This directly conflicts with smoothness, which requires selection probabilities to change gradually under small review perturbations. Appendix E gives two ways to reconcile the Clipped Linear Lottery with ex post validity, depending on which guarantee the funder wants to enforce exactly. If the funder prioritizes exact smoothness, then it can relax the dominance relation by using intervals wide enough relative to the smoothness scale. Under this condition, whenever one candidate clearly dominates another, the Clipped Linear Lottery already assigns probability 1 to the dominant candidate or probability 0 to the dominated candidate, so ex post validity holds automatically. If the funder instead prioritizes exact ex post validity, then it can project the Clipped Linear Lottery marginals onto the polytope of ex post valid marginal probabilities and sample only from valid sets. This preserves interval dominance in every realized outcome, but may weaken the global smoothness guarantee. Thus, smoothness and ex post validity are not diametrically opposed design goals, but combining them requires making explicit which guarantee is enforced exactly and which is relaxed.

Empirical Comparison

We complement our theory with experiments on real peer review datasets and synthetic data. Experimental setup. We evaluate the Clipped Linear Lottery and top-k softmax at acceptance rates k/n ∈ {10%, 33%, 50%}, and compare against existing partial lottery designs. We use ICLR 2025 (OpenReview, 2025) (n = 3,710, rmin = 3, scores 1–10), NeurIPS 2024 (OpenReview, 2024) (n = 4,034, rmin = 3, scores 1–10), Swiss NSF (Heyard et al., 2022) (n = 353, rmin = 5, scores 1–6), and synthetic Beta reviews (n = 200, r = 5), drawn i.i.d. from Beta(α, α) on [0, 1] and discretized to 10 levels. For ICLR and NeurIPS, we restrict to accepted papers and simulate allocating oral presentations, a randomized-selection setting recently used at multiple computer science conferences (USENIX Security 2025 Program Committee, 2024; SIGMOD 2025 Program Committee, 2025). Since an allocation rate of roughly 10% matches historical oral-presentation 14

Linear Lottery

MERIT

ICLR

NeurIPS

Regret / k

0.06 0.04 0.02 0.00

2.5

5.0

7.5

Swiss NSF

10.0 12.5

L (lower is smoother)

0.05 0.04 0.03 0.02 0.01 0.00

0.025

Swiss NSF Funding Data

0.020 0.015 0.010 0.005 5

L (lower is smoother)

15 0.000

L (lower is smoother)

(a) Acceptance rate k/n = 10%.

ICLR

0.05

Regret / k

0.05

Swiss NSF Funding Data 0.008

0.04

0.006

0.03

0.03 0.02 0.01 0.00

NeurIPS

L (lower is smoother)

0.02

0.004

0.01

0.002

0.00100

101

102

L (lower is smoother)

0.000 2.5

5.0

7.5

10.0 12.5

L (lower is smoother)

(b) Acceptance rate k/n = 33%.

Figure 3: Regret–smoothness tradeoff for existing partial lottery mechanisms. Down and to the left indicates a better tradeoff. Points show MERIT and Swiss NSF at their empirical local smoothness under the worst one-review perturbation. Hollow red markers show worst-case smoothness guarantee of the Clipped Linear Lottery at the same regret level. rates at NeurIPS and ICLR, we present k/n = 10% results in the main text and defer k/n ∈ {33%, 50%} results to Appendix G.

7.1

Smoothness of Existing Partial Lottery Designs

We first test whether existing partial lottery designs are smooth in practice. We evaluate two interval-based mechanisms, MERIT (Goldberg et al., 2025) and the Swiss NSF procedure (Heyard et al., 2022). For each mechanism and dataset, we search over all single-review one-tick perturbations and identify the perturbation that maximizes the ℓ1 change in marginal selection probabilities. We report the resulting empirical local smoothness, defined as ∥∆p∥1 /∥∆X∥1,1 . Both mechanisms take point estimates and intervals of utility as input. For all datasets, we use the mean review score as the utility and construct intervals using “leave-one-out intervals” (Goldberg et al., 2025), computing the range of possible mean scores obtained by leaving out one reviewer at a time. Figure 3 compares existing partial lottery designs with the Clipped Linear Lottery. Existing mechanisms can be highly unstable under small perturbations. For example, on both NeurIPS and ICLR, a single one-point review change can change a paper’s selection probability by more than 0.3 under either MERIT or the Swiss NSF mechanism; full results appear in Appendix G. By contrast, the Clipped Linear Lottery achieves much better smoothness at the same level of regret.

Regret / k

Linear Lottery 0.35 0.30 0.25 0.20 0.15 0.10 0.05 0.00

Beta

0.2

0.4

0.6

0.8

0.14 0.12 0.10 0.08 0.06 0.04 0.02 1.0 0.00 0.2

L (lower is smoother)

ICLR

Softmax

NeurIPS

0.12

Swiss NSF 0.30

0.10

0.25

0.08

0.4

0.6

0.8

0.20

0.06

0.15

0.04

0.10

0.02

0.05

1.0 0.00 0.2

L (lower is smoother)

0.4

0.6

0.8

1.0 0.00

L (lower is smoother)

0.2

0.4

0.6

0.8

1.0

L (lower is smoother)

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 softmax over a grid of target smoothness values. The Clipped Linear Lottery’s regret is computed exactly, while softmax regret is estimated using Monte Carlo sampling with 10,000 samples per estimate. Figure 4 shows the regret–smoothness tradeoff at acceptance rate k/n = 10%. We report regret normalized by the budget k; under this normalization, the Clipped Linear Lottery bound depends on the acceptance rate only through the factor (1 − k/n), so the curves have similar shape at other acceptance rates. Appendix G shows the same qualitative pattern for k/n ∈ {33%, 50%}. As predicted by theory, the Clipped Linear Lottery consistently achieves lower normalized regret than top-k softmax across datasets and smoothness levels.

7.3

Tightness of Smoothness Guarantees

Finally, we test whether our smoothness upper bounds are close to tight. For both the Clipped Linear Lottery and top-k softmax, we construct near-worst-case utility profiles with ui = 1 for i < k, uk = B ∈ [0, 1], and ui = 0 for i > k. We then perturb uk to uk ± ε and grid-search over B, ε, and the perturbation direction to maximize the empirical ratio ∥∆p∥1 /∥∆X∥1,1 . Figure 5 compares the worst-case empirical smoothness to the target smoothness L. For the Clipped Linear Lottery, the empirical lower bound is within 99% of the theoretical upper bound at n = 1000, confirming that Theorem 4.1 is essentially tight. For top-k softmax, the empirical worst-case coefficient is within 95% of the bound from Theorem 5.3, showing that our softmax analysis is also close to tight.

Discussion

We propose smoothness as a design principle for partial lotteries, requiring that small changes in review scores induce only small changes in selection probabilities. To satisfy this property, we propose the Clipped Linear Lottery, analyze its smoothness and regret, and show that it is near-optimal for the resulting tradeoff up to a factor of 1 − nk . We compare smooth selection to 16

k=100

k=333

k=500

Theoretical bound

Empirical Smoothness

Linear Lottery

Softmax

1.0 0.8 0.6 0.4 0.2 0.0 0.0

0.2

0.4

0.6

Target L

0.8

1.0

0.0

0.2

0.4

0.6

Target L

0.8

1.0

Figure 5: Worst-case empirical smoothness vs. target global smoothness L for n = 1000 and k ∈ {100, 333, 500}. The dashed line shows the theoretical upper bound. The bounds from Theorems 4.1 and 5.3 are essentially tight for both mechanisms. Individual Fairness, Differential Privacy, and top-k softmax sampling, and show empirically on real peer review datasets that the Clipped Linear Lottery achieves lower regret than softmax at matched smoothness, while existing partial lottery designs can be highly unstable under small review perturbations. Our results demonstrate that smoothness is a useful and tractable design principle for randomized selection in evaluation settings, and that the Clipped Linear Lottery provides a simple, effective, and interpretable mechanism for enforcing it. Limitations. First, our analysis assumes an exact, globally Lipschitz utility function, whereas practical utility estimates may be noisy, misspecified, or only locally smooth. Second, our regret bounds leave a factor of (1 − k/n) gap between the Clipped Linear Lottery upper bound and our lower bound for any smooth rule. Although this is a small constant factor in many selection settings, closing this gap would sharpen the optimality guarantees for smooth lotteries. Third, we do not study how smooth lotteries affect reviewer behavior or institutional decision-making in practice. An important direction for future work is to evaluate whether smoother mechanisms reduce fruitless deliberation near decision thresholds, and whether reviewers and applicants perceive them as more legitimate than threshold-based partial lotteries. Future work. A natural next step is to study smooth lotteries in deployed evaluation settings, including whether they reduce deliberation near decision thresholds, improve perceived legitimacy among reviewers and applicants, or change reviewer behavior. Another direction is to extend the theory beyond exact, globally Lipschitz utilities to noisy, locally smooth, or learned utility functions. Ideas from differential privacy, such as calibrating noise to local or smooth sensitivity rather than worst-case global sensitivity, may be useful for designing instance-adaptive lotteries.

References David Adam. Science funders gamble on grant lotteries. Nature, 575(7784):574–575, 2019. doi: 10. 1038/d41586-019-03572-7. URL https://www.nature.com/articles/d41586-019-03572-7. Austrian Science Fund (FWF). 1000 ideas programme, 2026. URL https://www.fwf.ac.at/en/ funding/portfolio/projects/1000-ideas.

Mitali Bafna and Jonathan Ullman. The price of selection in differential privacy. In Conference on Learning Theory, pages 151–168. PMLR, 2017. Konstantina Bairaktari, Paul Tsela Langton, Huy Nguyen, Niklas Smedemark-Margulies, and Jonathan Ullman. Fair and useful cohort selection. Transactions on Machine Learning Research, 2023. Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metrics. In International Symposium on Privacy Enhancing Technologies, pages 82–102. Springer, 2013. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and trends® in theoretical computer science, 9(3-4):211–487, 2014. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, 3rd Theory of Cryptography Conference, TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006. doi: 10.1007/11681878 14. Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226, 2012. European Research Council. Peer review – not perfect but still the best system that we have. https://erc.europa.eu/news-events/magazine-article/ peer-review-not-perfect-still-best-system-we-have, November 2023. Accessed: 2025-05-07. Ferric C Fang and Arturo Casadevall. Research funding: The case for a modified lottery, 2016. Thomas Feliciani, Junwen Luo, and Kalpana Shankar. Funding lotteries for research grant allocation: An extended taxonomy and evaluation of their fairness. Research Evaluation, 33:rvae025, 2024. Formas. Process description for partial randomisation in explore 2025. Pm, Swedish Research Council for Sustainable Development (Formas), 2026. Ref. no. 2025–01621. Alexander Goldberg, Giulia Fanti, and Nihar B Shah. A principled approach to randomized selection under uncertainty: Applications to peer review and grant funding. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. Joanie Sims Gould, Anne M Lasinsky, Adrian Mota, Karim M Khan, and Clare L Ardern. Threats to grant peer review: A qualitative study. BMJ Open, 15(2):e091666, 2025. Rachel Heyard, Manuela Ott, Georgia Salanti, and Matthias Egger. Rethinking the funding line at the swiss national science foundation: Bayesian ranking and lottery. Statistics and Public Policy, 9(1):110–121, 2022. Serge PJM Horbach, Joeri K Tijdink, and Lex M Bouter. Partial lottery can make grant allocation more fair, more efficient, and more diverse. Science and Public Policy, 49(4):580–582, 2022. 18

Janet Hsieh, Aditi Raghunathan, Nihar B Shah, et al. Vulnerability of text-matching in ml/ai conference reviewer assignments to collusions. In USENIX Security, 2025. Steven Jecmen, Hanrui Zhang, Ryan Liu, Nihar B. Shah, Vincent Conitzer, and Fei Fang. Mitigating manipulation in peer review via randomized reviewer assignments. In NeurIPS, 2020. Parameswaran Kamalaruban, Victor Perrier, Hassan Jameel Asghar, and Mohamed Ali Kaafar. Not all attributes are created equal: dx-private mechanisms for linear queries. Proceedings on Privacy Enhancing Technologies, 2020. Weiwei Kong, Walid Krichene, Nicolas Mayoraz, Steffen Rendle, and Li Zhang. Rankmax: An adaptive projection alternative to the softmax function. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020. Wouter Kool, Herke Van Hoof, and Max Welling. Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. In International conference on machine learning, pages 3499–3508. PMLR, 2019. Michael L Littman. Collusion rings threaten the integrity of computer science research. Communications of the ACM, 64(6):43–44, 2021. Mengyao Liu, Vernon Choy, Philip Clarke, Adrian Barnett, Tony Blakely, and Lucy Pomeroy. The acceptability of using a lottery to allocate research funding: A survey of applicants. Research Integrity and Peer Review, 5:1–7, 2020. Finn Luebber, Sören Krach, Frieder M. Paulus, Lena Rademacher, and Rima-Maria Rahal. Lottery before peer review is associated with increased female representation and reduced estimated economic cost in a german funding line. Nature Communications, 16(1):9824, 2025. doi: 10. 1038/s41467-025-65660-9. URL https://www.nature.com/articles/s41467-025-65660-9. William G Madow. On the theory of systematic sampling, ii. The Annals of Mathematical Statistics, 20(3):333–354, 1949. Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In Proceedings of The 33rd International Conference on Machine Learning (ICML), pages 1614–1623. PMLR, 2016. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94–103. IEEE, 2007. Pravin Nair. Softmax is 1/2-Lipschitz: A tight bound across all ℓp norms. Transactions on Machine Learning Research, 2025. OpenReview. NeurIPS 2024 Conference Submissions. https://openreview.net/submissions? venue=NeurIPS.cc/2024/Conference, 2024. Accessed May 5, 2026. OpenReview. ICLR 2025 Conference Submissions. https://openreview.net/submissions? venue=ICLR.cc/2025/Conference, 2025. Accessed May 5, 2026.

Martin Saveski, Steven Jecmen, Nihar B Shah, and Johan Ugander. Counterfactual evaluation of peer-review assignment policies. In NeurIPS, 2023. Science Foundation Ireland. Innovate for ireland programme. https://www.sfi.ie/funding/ funding-calls/innovate-for-ireland/, August 2024. 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, 2025. SIGMOD 2025 Program Committee. SIGMOD 2025 call for research papers. https://2025. sigmod.org/calls_papers_sigmod_research.shtml, 2025. Accessed May 5, 2026. 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– 563. IEEE Computer Society, 2017. doi: 10.1109/FOCS.2017.57. https://arxiv.org/abs/ 1704.03024. The British Academy. Partial randomisation trial extended after diversity of applicants and award holders increases. https://www.thebritishacademy.ac.uk/news/ partial-randomisation-trial-extended-small-research-grants/, April 2025. Accessed: 2025-05-07. Giulia Trentacosti. Using lotteries to allocate research funding: Perspectives from switzerland. Open Science Blog, University of Groningen Library, September 2021. URL https://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 Science, Innovation and Technology, June 30 2025. URL https://www.gov.uk/government/ publications/a-year-in-metascience-2025. Published 30 June 2025. USENIX Security 2025 Program Committee. USENIX security 2025 conference format. https: //github.com/USENIX-Security-2025/conference-format, April 2024. Version 1.1. Volkswagen Foundation. Partially randomized procedure – lottery and peer review. https://www.volkswagenstiftung.de/en/funding/peer-review/ partially-randomized-procedure-lottery-and-peer-review, May 2025. Accessed: 2025-05-07. Weiran Wang and Canyi Lu. Projection onto the capped simplex. arXiv preprint arXiv:1503.01002, 2015.

Appendices

Proofs

A.1

Smoothness of Clipped Linear Lottery (Theorem 4.1)

Proof. Let u = u(X) and u′ = u(X ′ ). Let b and b′ denote the intercepts for the Clipped Linear Lottery on X and X ′ , respectively. For each coordinate i, the selection probability is pi = clip[0,1] (wui + b). By the triangle inequality: |pi − p′i | ≤ | clip[0,1] (wui + b) − clip[0,1] (wu′i + b)| + | clip[0,1] (wu′i + b) − clip[0,1] (wu′i + b′ )| . | {z } | {z } (Ai )

(Bi )

P Since clip[0,1] (·) is 1-Lipschitz, Ai ≤ w|ui − u′i | and summing over i yields i Ai ≤ w∥u − u′ ∥1 . For the second term, define hi (β) = clip[0,1] (wu′i + β). (β) is non-decreasing in β for all i, the PSince hiP P ′ ′ differences P hi (b) − hP = | i hi (b) − i hi (b )|. Using the budget i (b ) share the same Psign, so i Bi P constraint i pi = i p′i = k, we have i hi (b′ ) = k = i clip[0,1] (wui + b). Substituting: X

Bi =

clip[0,1] (wu′i + b) −

clip[0,1] (wui + b) .

P By the triangle inequality, this is bounded by i Ai ≤ w∥u − u′ ∥1 . Hence, ∥p − p′ ∥1 ≤ 2w∥u − u′ ∥1 . L , ∥p − p′ ∥1 ≤ L∥X − X ′ ∥1,1 . Since u is Du -Lipschitz and w = 2D u Tightness. Consider u(X) = (0, . . . , 0) and u(X ′ ) = (ε, 0, . . . , 0) for small ε > 0. The Clipped Linear Lottery gives p(X) = (k/n, . . . , k/n), and on perturbed utilities yields p1 (X ′ ) = k/n+εw n−1 n and pi (X ′ ) = k/n − εw/n for i > 1. Hence ∥p(X) − p(X ′ )∥1 = 2wε n−1 n , demonstrating a realized L n−1 n Lipschitz constant.

A.2

Regret of Clipped Linear Lottery (Theorem 4.3)

Proof. Let u = u(X) and let p be the probability vector selected by the Clipped Linear Lottery. Viewing the Clipped Linear Lottery as Euclidean projection into Cn,k (Proposition 4.2), by projection optimality (p − wu)⊤ (q − p) ≥ 0 for all q ∈ Cn,k . Let q ∗ ∈ Cn,k be the indicator vector for the top-k items. Substituting q = q ∗ and rearranging yields wu⊤ (q ∗ − p) ≤ p⊤ (q ∗ − p). The left-hand side is exactly w · R(D; X). Thus ⊤

∗

p (q − p) =

pi (1 − pi ) −

i∈T

X i∈T /

p2i =

X i∈T

pi −

n X

p2i ,

(1)

i=1

where T is the set of top-k candidates by utility. Maximizing (1) over p ∈ Cn,k is concave quadratic; by KKT conditions the optimal pi = 12 (1 + k/n) for i ∈ T and pi = k/(2n) otherwise, giving L p⊤ (q ∗ − p) ≤ k(1 − k/n)/4. Therefore R(D; X) ≤ k(1−k/n) and taking w = 2D completes the 4w u proof.

A.3

Proof of Regret Lower Bound (Theorem 4.5)

0 0 Proof. Let X 0 be the all-zero P 0matrix and p = Pp(X 0). Let2 T be the k candidates with smallest 0 probabilities in p . Since i pi = k, we have i∈T pi ≤ k /n. Fix δ ∈ [0, 1] and define X (T ) by

(T )

setting Xi,j = δ for i ∈ T , j ∈ [r], and 0 otherwise; then ∥X (T ) − X 0 ∥1,1 = krδ. Let p = p(X (T ) ). P P P 1 0 0 By smoothness, ∥p − p0 ∥1 ≤ Lkrδ. Since i pi = i p0i = k, i∈T (pi − pi ) ≤ 2 ∥p − p ∥1 , so P 2 + Lkrδ/2. On X (T ) , ui = δ for i ∈ T and 0 otherwise, so OPT = kδ and the rule i∈T pi ≤ k /n P attains utility δ i∈T pi . Thus R(D; X (T ) ) ≥ kδ 1 − nk − Lrδ . 2 Maximizing over δ ∈ [0, 1] yields the claimed bound: δ ∗ = (1 − k/n)/(Lr) if L ≥ 1r (1 − nk ), else δ ∗ = 1.

A.4

Proof of Standard DP Does Not Imply Smooth Marginals (Section 5.2)

Proposition A.1. For every ε > 0, there exists an ε-DP selection rule whose induced marginal probabilities are not L-smooth for any finite L. Proof. Fix any 1 ≤ k < n. Let S1 = {1, . . . , k},

S2 = {2, . . . , k + 1}.

Thus S1 and S2 are both feasible selected sets of size k, and they differ only by swapping candidate 1 for candidate k + 1. Let the selection rule depend only on the review entry X1,1 . Define a=

eε . 1 + eε

If X1,1 < 1/2, the rule selects S1 with probability a and S2 with probability 1 − a. If X1,1 ≥ 1/2, the rule swaps these probabilities, selecting S1 with probability 1 − a and S2 with probability a. This rule is ε-DP under the standard neighboring relation, as it is a version of randomized response. However, the induced marginal probabilities are discontinuous. For any δ > 0, let X, X ′ satisfy ′ X1,1 = 1/2 − δ, X1,1 = 1/2 + δ, with all other entries equal. Then ∥X − X ′ ∥1,1 = 2δ. The only candidates whose marginal probabilities change are candidates 1 and k + 1. Therefore, ∥p(X) − p(X ′ )∥1 = 2 tanh(ε/2). The marginal change is constant in δ, while the review distance tends to zero as δ → 0. Hence no finite L can satisfy ∥p(X) − p(X ′ )∥1 ≤ L∥X − X ′ ∥1,1 for all X, X ′ . Thus standard DP does not imply smooth marginals.

A.5

Proof of Metric DP Implies Smooth Marginals (Proposition 5.2)

Proof. Fix review matrices X, X ′ and write d = ∥X − X ′ ∥1,1 . Let q, q ′ be the distributions over K induced by D(X) and D(X ′ ), respectively. By ε-metric DP, q(S) ≤ eεd q ′ (S)

q ′ (S) ≤ eεd q(S)

and

for every S ∈ K. Thus the likelihood ratio between q and q ′ is bounded by eεd , which implies εd eεd − 1 ′ . dTV (q, q ) ≤ εd = tanh 2 e +1 We now relate total variation distance over selected sets to ℓ1 distance between marginal probabilities. For each candidate i, X pi (X) − pi (X ′ ) = q(S) − q ′ (S) . S∋i

Applying the triangle inequality and using |S| = k for every S ∈ K, ′

∥p(X) − p(X )∥1 ≤

n X X

|q(S) − q ′ (S)|

i=1 S∋i

|S| · |q(S) − q ′ (S)|

S∈K

= k∥q − q ′ ∥1 = 2k dTV (q, q ′ ) εd ≤ 2k tanh . 2 Using tanh(x) ≤ x gives ∥p(X) − p(X ′ )∥1 ≤ εkd = εk∥X − X ′ ∥1,1 . Therefore the induced marginals are L-smooth with L ≤ εk. The leading constant is tight as εd → 0. To see this, take two disjoint sets S1 , S2 ∈ K and consider two binary distributions supported only on S1 and S2 with likelihood ratio eεd : eεd 1 , q ′ (S1 ) = , εd 1+e 1 + eεd and q(S2 ) = 1 − q(S1 ), q ′ (S2 ) = 1 − q ′ (S1 ). Then εd ′ dTV (q, q ) = tanh . 2 q(S1 ) =

Since S1 and S2 are disjoint, εd ∥p(X) − p(X )∥1 = 2k dTV (q, q ) = 2k tanh . 2 ′

′

As εd → 0, this equals εkd + o(d), so the linear constant εk cannot be improved in general. 23

A.6

Proof of Smoothness and Regret of Softmax (Theorem 5.3)

Proof of smoothness. Let u = u(X) and u′ = u(X ′ ), and p(u), p(u′ ) the corresponding marginals under top-k softmax with temperature τ . We prove v 7→ p(v) is (2/(eτ ))-Lipschitz w.r.t. utilities. By integrating the Jacobian along vt = (1 − t)u + tu′ , ∥p(u′ ) − p(u)∥1 ≤ supt ∥J(vt )∥1→1 ∥u′ − u∥1 . Fix j ∈ [n]. With G1 , . . . , Gn i.i.d. Gumbel(0, τ ) and Yi (v) = vi + Gi , holding noise fixed, increasing vj can only P improve j’s rankPand worsen others’: ∂j pj ≥ 0 and ∂j pi ≤ 0 for i ̸=Pj. The fixed-budget identity i pi (v) = k gives i ∂j pi = 0. Combining, the column sum equals i |∂j pi | = 2∂j pj . Conditioning on G−j , there is a deterministic threshold θj such that j is selected iff vj +Gj ≥ θj , namely the k-th largest among {vℓ +Gℓ : ℓ ̸= j}. Hence pj (v) = EG−j [1−FG (θj −vj )]. Differentiating and using fG (x) ≤ 1/(eτ ), ∂j pj = EG−j [fG (θj − vj )] ≤ 1/(eτ ). Thus every column of J has ℓ1 norm 2 at most 2/(eτ ), so ∥p(u) − p(u′ )∥1 ≤ eτ ∥u − u′ ∥1 . Combined with ∥u − u′ ∥1 ≤ Du ∥X − X ′ ∥1,1 gives the stated bound. Relation to prior softmax Lipschitz analyses. Recent work establishes that the standard softmax map (the k = 1 case) is exactly 1/2-Lipschitz with respect to ℓp norms via its closed-form Jacobian (Nair, 2025). The Gumbel-top-k inclusion map does not possess a simple closed-form Jacobian. We overcome this by analyzing the marginal inclusion map directly: a shared-Gumbel coupling gives coordinate-wise monotonicity, the fixed-budget identity bounds the full Jacobian column sum via its diagonal, and a threshold representation combined with a Gumbel density bound controls the diagonal. Our 2/e ≈ 0.736 is within a small constant of the tight 1/2 for k = 1; we conjecture our bound is essentially tight for general k, and our experiments in Section 7.3 support this. Proof of regret bound. Fix u ∈ Rn and consider the top-k softmax rule with temperature τ implemented as sequential sampling without replacement. Let it denote the item selected at step t and Rt the remaining items, so |Rt | = n − t + 1. The conditional one-step regret Mt − E[uit | Rt ], wherePMt = maxi∈Rt ui , is bounded via the variational form of log-sum-exp: E[uit | Rt ] = P τ log i∈Rt eui /τ − τ H(pt ) where pt is the softmax on Rt . Since log i∈Rt eui /τ ≥ Mt /τ and H(pt ) ≤ log |Rt |, Mt − E[uit | Rt ] ≤ τ log |Rt |. Summing over t and bounding log(n − t + 1) ≤ log n yields R(D; u) ≤ kτ log n.

A.7

Individual Fairness Details

Definition A.1 (α-Individual Fairness). For a parameter α ≥ 0, a selection rule D is α-individually fair (α-IF) if its induced marginal probabilities p satisfy |pi (X) − pj (X)| ≤ α |ui (X) − uj (X)| for all X ∈ [0, 1]n×r and all i, j ∈ [n]. Optimality of the Clipped Linear Lottery for IF. For any fixed review matrix X, finding the utility-maximizing marginal probabilities that satisfy α-IF can be written as the linear program max

p∈[0,1]n

s.t.

p⊤ u(X)

(IF-LP)

|pi − pj | ≤ α |ui (X) − uj (X)| Pn i=1 pi = k.

∀i, j ∈ [n],

Configuring the Clipped Linear Lottery with w = α yields the exact, instance-optimal solution p∗ to (IF-LP) (Bairaktari et al., 2023, Theorem 3). 24

Smoothness ⇏ IF. A trivial selection rule that completely ignores review scores and always selects the first k candidates is perfectly stable (0-smooth across datasets), but can arbitrarily violate IF because candidates with identical utilities receive maximally different selection probabilities (1 vs. 0). IF ⇏ Smoothness. Because IF does not constrain behavior across datasets, an IF-compliant mechanism can be arbitrarily discontinuous. Consider a review matrix X yielding utilities u(X) = (1, . . . , 1, 0, . . . , 0) with exactly k ones. A 1-IF mechanism could output p(X) = (1, . . . , 1, 0, . . . , 0). For a perturbed matrix X ′ where the first candidate’s utility drops by δ so that u(X ′ ) = (1 − δ, 1, . . . , 1, 0, . . . , 0), the mechanism could instead output a uniform lottery p(X ′ ) = (k/n, . . . , k/n), which still satisfies IF. The change in the first candidate’s selection probability is |1 − k/n|, while the input perturbation is only δ. As δ → 0, the Lipschitz constant must satisfy L ≥ |1 − k/n|/δ, which diverges to infinity.

Details of the Clipped Linear Lottery

B.1

Efficient Computation of the Clipped Linear Lottery

The Clipped Linear Lottery guarantees a unique Pnvalid probability assignment (Wang and Lu, 2015). Because the total probability function S(b) = i=1 clip[0,1] (zi + b) is continuous and monotonically non-decreasing from 0 to n, a valid intercept exists for any budget k ∈ [0, n]. While multiple intercepts b might satisfy the budget if S(b) contains flat regions, these plateaus only occur when all candidate probabilities are saturated at 0 or 1, ensuring the resulting probability vector itself is strictly unique. Implementing the Clipped Linear Lottery requires finding this intercept b that satisfies the budget constraint. There are many computationally efficient implementations given in prior work, including binary search (Kong et al., 2020) and water-filling methods (Bairaktari et al., 2023). For completeness, Algorithm 2 outlines an exact, non-iterative implementation with runtime O(n2 ), adapted from Wang and Lu (2015). The algorithm first finds the 2n breakpoints at which S(b) changes (where a candidate’s probability hits the floor of 0 or the ceiling of 1), then locates the interval of breakpoints [bj , bj+1 ] that contains a budget-feasible intercept and computes the exact intercept in this interval. Algorithm 2 Simple Exact Clipped Linear Lottery via Breakpoint Search Input: Scaled utilities z ∈ Rn where zi = w · ui , budget k 1: Initialize breakpoints where probabilities hit 0 or 1: B ← {−zi | i ∈ [n]} ∪ {1 − zi | i ∈ [n]} 2: Sort B in ascending order: b1 ≤ b2 ≤ · · · ≤ b2n Pn 3: Define the total probability function: S(b) = i=1 clip[0,1] (zi + b) 4: for j = 1 to 2n − 1 do 5: Slow ← S(bj ), Shigh ← S(bj+1 ) 6: if Slow ≤ k ≤ Shigh then k−Slow 7: return bj if Slow = Shigh else bj + (bj+1 − bj ) Shigh −Slow 8: end if 9: end for

B.2

Monotonicity Properties of the Clipped Linear Lottery

Proposition B.1 (Monotonicity Properties). The Clipped Linear Lottery satisfies: 1. Monotonicity in budget: For any fixed utilities u ∈ Rn and slope w > 0, if p and p′ are the solution vectors for budgets k and k ′ respectively, then k ′ > k =⇒ p′i ≥ pi for all i ∈ [n]. 2. Monotonicity of size of lottery pool: For any fixed utilities u ∈ Rn and budget k ∈ (0, n), the size of the active lottery pool, R(w) = {i ∈ [n] | 0 < pi < 1}, is monotonically nonincreasing in w. P Proof of (1). Let S(b) = j clip[0,1] (wuj + b). Each term is non-decreasing in b, so S is nondecreasing. Let b1 , b2 correspond to budgets k1 < k2 . If b2 < b1 then k2 = S(b2 ) ≤ S(b1 ) = k1 , a contradiction. Thus b2 ≥ b1 , and since clip[0,1] is non-decreasing, pi (b2 ) ≥ pi (b1 ) for all i. P Proof of (2). Reparameterize b = −wτ , so pi = clip[0,1] (w(ui −τ )). Define F (w, τ ) = i clip[0,1] (w(ui − τ )); for fixed w, F is non-increasing in τ , and for fixed τ , non-decreasing in w. Let τ (w) satisfy F (w, τ (w)) = k. If w2 > w1 , then for every τ , F (w2 , τ ) ≥ F (w1 , τ ), hence τ (w2 ) ≥ τ (w1 ). Moreover 0 < pi < 1 ⇐⇒ τ < ui < τ + 1/w, so R(w) = {i : τ (w) < ui < τ (w) + 1/w}. Combining τ (w2 ) ≥ τ (w1 ) and 1/w2 ≤ 1/w1 , (τ (w2 ), τ (w2 ) + 1/w2 ) ⊆ (τ (w1 ), τ (w1 ) + 1/w1 ), so R(w2 ) ⊆ R(w1 ).

Varying Number of Reviews Per Candidate

For simplicity, the main text assumes that every candidate receives the same number r of reviews. This assumption is not essential. Suppose instead that candidate i receives ri reviews, with ri ≥ 1, and let rmin := min ri . i∈[n]

The review data is then a ragged array consisting of entries Xi,j ∈ [0, 1] for j ∈ [ri ], and we define ′

∥X − X ∥1,1 =

ri n X X

′ |Xi,j − Xi,j |.

i=1 j=1

All definitions in the main text extend directly with this metric: smoothness is still a Lipschitz condition on the induced marginal selection probabilities with respect to ∥ · ∥1,1 . The theory also extends without change once the utility Lipschitz constant is updated. For example, if utility is the mean score r

i 1 X ui (X) = Xi,j , ri

j=1

then changing candidate i’s reviews by total amount δ changes ui by at most δ/ri . Hence the mean-score utility is Du -Lipschitz with Du = max i

1 1 = . ri rmin

Thus, all upper-bound results for the Clipped Linear Lottery continue to hold by replacing r with rmin in the mean-score case. In particular, setting the Clipped Linear Lottery slope to w=

Lrmin L = 2Du 2

guarantees L-smoothness, and the regret bound becomes max R(D; X) ≤ X

k(1 − k/n) . 2rmin L

This extension is conservative. Candidates with more than rmin reviews have mean utilities that are less sensitive to any single review perturbation, so the actual local smoothness of the Clipped Linear Lottery may be better than the worst-case bound suggests. The lower-bound construction in the main text should also be interpreted with rmin as the worst-case review count: when candidates with the minimum number of reviews are available for the construction, the same indistinguishability argument applies verbatim. More generally, heterogeneous review counts can only make some candidates’ utilities less sensitive to review perturbations, so using rmin gives a simple worst-case guarantee rather than a tight instance-specific characterization. We use this construction throughout our experiments where there is variation in the number of reviews per paper or proposal in real peer review datasets.

Additional Theoretical Results

D.1

General Regret Lower Bound

Definition D.1 (Lower Lipschitz Condition). Row-wise utility function u : [0, 1]r → [0, 1] satisfies the du -lower Lipschitz condition if inf δ∈(0,1/du ] maxx,y:∥x−y∥1 =δ |u(x)−u(y)| ≥ du . ∥x−y∥1 Lemma D.1 (Utilities satisfying the du -lower Lipschitz condition). The following utility functions satisfy the du -lower Lipschitz condition with the specified constants. The table also lists the ℓ1 Lipschitz constant Du (Definition 3.2) of each utility function. Utility u

Baseline row x0 (δ)

Perturbed row x(δ)

Mean

1 r

(0, . . . , 0)

( rδ , . . . , rδ )

Max

(0, . . . , 0)

(δ, 0, . . . , 0)

Min

(0, δ, . . . , δ)

(δ, δ, . . . , δ)

Median (odd r = 2h + 1)

(0, . . . , 0, δ, . . . , δ ) | {z } | {z }

flip one 0 to δ

h+1

Remark D.2. For each of the above utilities, du = Du . In general, Du is a worst-case global upper bound on the Lipschitz quotient over all row pairs, whereas du is a guarantee on the maximum achievable quotient for any distance budget up to 1/du . It always holds that du ≤ Du , with equality when these worst-case witnesses achieve the global upper bound.

Theorem D.3 (Generic regret lower bound). Let u be a row-wise utility function ui (X) = u(Xi,1 , . . . , Xi,r ) where u satisfies the du -lower Lipschitz condition. Let D be any L-smooth selection rule. Then  k 2   k du(1− n ) , if L ≥ du 1 − nk , 2L max R(D; X) ≥  X k 1 − k − L , if L < du 1 − k . n 2 du n Proof. Fix δ ∈ (0, 1/du ] and let x(δ), x0 (δ) achieve the maximum in the du -lower Lipschitz condition, ordered so u(x(δ)) ≥ u(x0 (δ)). Define X 0 with every row equal P to x0 (δ), let p0 = p(X 0 ), and let 0 T be the k candidates with smallest probabilities under p ; then i∈T p0i ≤ k 2 /n. Construct X (T ) (T ) − X 0 ∥ 0 by replacing rows in T with 1,1 = kδ and by smoothness, ∥p − p ∥1 ≤ Lkδ, Px(δ). Then P 0∥X P (T ) 2 (T ) where p = p(X ). Since i pi = i pi = k, i∈T pi ≤ k /n + Lkδ/2. On X , each i ∈ T gains at least du δ utility, so R(D; X (T ) ) ≥ kdu δ(1 − k/n − Lδ/2). Maximizing over δ ∈ (0, 1/du ] yields the two-regime bound. Remark D.4. Since du = Du for the mean, max, min, and median by Lemma D.1, the lower 2D u bound on the worst-case regret of any L-smooth selection rule is k(1−k/n) when L ≥ Du (1−k/n), 2L matching the upper bound for the Clipped Linear Lottery (Theorem 4.3) up to a factor of 1 − k/n.

Ex Post Valid Sampling

Several lottery designs take interval estimates of candidate quality as input rather than (or in addition to) point scores. The Swiss NSF procedure (Adam, 2019; Heyard et al., 2022) sets the funding line using uncertainty intervals, and MERIT (Goldberg et al., 2025) selects candidates to maximize worst-case utility over all rankings consistent with such intervals. A central requirement in interval-based designs is ex post validity: every realized outcome should be consistent with the interval estimates, in the sense that no selected candidate is clearly dominated by an unselected one. Definition E.1 (Ex post validity). Given intervals [ℓi , ri ] for each candidate, define the dominance relation i ≻ j if ℓi > rj . A selected set S is ex post valid if i ≻ j and j ∈ S imply i ∈ S. Smoothness and ex post validity may be incompatible: if many candidates have near-zero-width non-overlapping intervals, ex post validity demands a deterministic selection while smoothness requires that selection probabilities remain close. The Clipped Linear Lottery specifies marginal selection probabilities p ∈ Cn,k , but many joint distributions over size-k subsets can implement the same marginals; we give two resolutions to this tension depending on the funder’s priorities. Resolution 1: Core-width compatibility. If the intervals are sufficiently wide relative to the smoothness scale, the tension does not arise. Specifically, if ℓi ≤ ui −

1 2w

and

ri ≥ ui +

1 2w

∀i ∈ [n],

(2)

then any dominance pair i ≻ j implies ui −uj > 1/w, and the Clipped Linear Lottery automatically respects every dominance relation:

Proposition E.1 (Automatic ex post validity under core-width). Let p be the marginals produced by the Clipped Linear Lottery with slope w > 0. If (2) holds for all i ∈ [n], then for every dominance pair i ≻ j, pi = 1 or pj = 0. Consequently, every subset in the support of any sampling scheme implementing these marginals is ex post valid. 1 1 Proof. Suppose i ≻ j, so ℓi > rj . By (2), ui − 2w ≥ ℓi > rj ≥ uj + 2w , hence ui − uj > 1/w. Writing pi = clip[0,1] (w(ui − τ )) for budget-enforcing threshold τ , w(ui − τ ) > w(uj − τ ) + 1. If pj > 0, then w(uj − τ ) > 0, so w(ui − τ ) > 1 and pi = 1.

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 funder could sacrifice smoothness by projecting the Clipped Linear Lottery marginals onto the set of all ex post valid marginal probabilities. Let R denote the family of ex post valid subsets and define the valid marginal polytope PR = conv{1S : S ∈ R}. Given Clipped Linear Lottery marginals plin , define the ex post feasible projection p̂ = arg min ∥p − plin ∥22 .

(3)

p∈PR

This quadratic program over PR can be solved via Frank–Wolfe iteration, where the linear minimization oracle at each step requires finding a minimum-weight ex post valid subset, solvable in polynomial time over interval orders (Goldberg et al., 2025). After T iterations, the iterate is a convex combination of at most T valid subsets, yielding an explicit sampling distribution supported on ex post valid outcomes. This resolution preserves exact ex post validity but may sacrifice the global smoothness guarantee. Design choice. Core-width compatibility preserves smoothness but requires wider intervals; projection preserves the original intervals and enforces strict ex post validity but may weaken smoothness. The choice depends on whether the funder prioritizes stable probabilities under score perturbations or strict interval-dominance in every realized outcome.

Details on Datasets and Experimental Setup

We use three real peer review datasets and one synthetic family: • ICLR 2025 (n = 3,710, rmin = 3): review scores on a 1–10 scale. • NeurIPS 2024 (n = 4,034, rmin = 3): review scores on a 1–10 scale. • Swiss NSF (n = 353, rmin = 5): review scores on a 1–6 scale. • Beta (synthetic) (n = 200, r = 5): each review drawn i.i.d. from a symmetric Beta(α, α) distribution on [0, 1], discretized to 10 levels. In the main experiments we use α = 2; in our Beta sweep we vary α ∈ {1, 2, . . . , 10}.

1.0

Beta ICLR NeurIPS Swiss NSF

CCDF: P(U > u)

0.8 0.6 0.4 0.2 0.0 0.0

0.2

0.4 0.6 Utility (normalized to [0,1])

0.8

1.0

Figure 6: CCDF of mean normalized utilities across datasets. Swiss NSF and Beta have heavier tails with larger utility gaps, while ICLR and NeurIPS are concentrated near the center. All review scores are normalized to [0, 1] using the known review scale, and utility is the mean normalized score. Unless otherwise noted, we set the softmax temperature to τ = 2Du /(eL) so that its smoothness matches the Clipped Linear Lottery’s target L (Theorem 5.3). For comparisons against existing baselines, we use L = 1/r, matching the Lipschitz constant of the mean utility function.

Additional Experimental Results

In this section, we provide additional experimental results. Figure 6 shows the complementary cumulative distribution function (CCDF) of mean utilities across datasets. The ICLR and NeurIPS datasets have utility distributions tightly concentrated around 0.5–0.6, with narrow interquartile ranges, while the Swiss NSF and Beta datasets spread utilities more broadly, creating larger gaps between candidates near typical acceptance thresholds. As we show below, this structure directly affects regret: datasets with more compressed utility distributions near the acceptance boundary incur higher regret under smooth selection rules, because the mechanism has less room to differentiate between candidates while satisfying the smoothness constraint.

G.1

Regret-Smoothness Trade-off

In this section, we provide additional results characterizing the tradeoff between regret and smoothness (Section 7.2 in the main text). The Beta sweep (Figure 7) confirms this intuition that datasets with more compressed utility distributions near the acceptance boundary incur higher regret under smooth selection rules. As α = β increases, the Beta distribution concentrates around 0.5, narrowing the range of realized utilities. Both the Clipped Linear Lottery and softmax exhibit decreasing regret with increasing concentration. Across all shape parameters, the Clipped Linear Lottery maintains its regret 30

L = 1.0 (1/r)

L = 2.0 (1/r)

0.35

0.25

0.30

0.20 Regret / k

Regret / k

0.25 0.20 0.15

0.15 0.10

0.10 0.05

0.05 0.00

4 5 6 7 8 Symmetric Beta Shape =

0.00

Linear Lottery

Softmax

4 5 6 7 8 Symmetric Beta Shape =

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. Linear Lottery

Beta

ICLR

0.08

Regret / k

0.20 0.06

0.15

0.04

0.10

0.02

0.05 0.00

0.2

0.4

0.6

0.8

1.0 0.00 0.2

L (lower is smoother)

0.4

0.6

0.8

Softmax

0.07 0.06 0.05 0.04 0.03 0.02 0.01 1.0 0.00 0.2

L (lower is smoother)

NeurIPS

Swiss NSF 0.20 0.15 0.10 0.05

0.4

0.6

0.8

1.0 0.00

L (lower is smoother)

0.2

0.4

0.6

0.8

1.0

L (lower is smoother)

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 selected candidates k decreases because there are fewer rejected candidates that could have been selected instead, and randomization becomes less costly relative to the optimal top-k set. This is also reflected in our theoretical bounds, which scale with (1 − nk ). Linear Lottery

Regret / k

Beta 0.150 0.125 0.100 0.075 0.050 0.025 0.000

ICLR 0.04 0.03

0.4

0.6

0.8

NeurIPS

0.05

0.2

Softmax

0.04

0.125

0.03

0.100 0.075

0.02

0.01

1.0 0.00 0.2

L (lower is smoother)

0.4

0.6

0.8

L (lower is smoother)

Swiss NSF 0.150

0.050 0.025 0.4

0.6

0.8

1.0 0.000

L (lower is smoother)

0.2

0.4

Figure 9: Regret vs. smoothness L at acceptance rate 50%.

0.6

0.8

1.0

L (lower is smoother)

MERIT Swiss NSF Max ∆p Smoothness Max ∆p Smoothness

Dataset ICLR NeurIPS Swiss NSF Beta

0.314 0.321 0.471 0.500

5.7 5.8 4.7 9.0

0.532 0.633 0.923 0.667

9.6 11.4 18.7 24.0

Table 2: Empirical evaluation of smoothness of existing partial lotteries under a single-review onetick perturbation (k = 10%). Max ∆p is the maximum coordinate change and Smoothness is local sensitivity (∆pL1 /input perturbation magnitude). Existing lotteries are highly non-smooth, as a one-point change in a single review induces large changes in selection probabilities across all datasets. MERIT Swiss NSF Max ∆p Smoothness Max ∆p Smoothness

Dataset

ICLR ICLR

33% 50%

0.001 0.504

5.4 11.4

0.634 0.565

11.4 10.2

NeurIPS NeurIPS

33% 50%

0.846 0.536

187.1 1852.9

0.585 0.572

10.5 10.3

Swiss NSF 33% Swiss NSF 50%

0.571 0.564

10.0 7.0

0.524 0.429

5.2 21.4

Beta Beta

0.500 0.367

18.0 7.0

0.625 0.556

17.0 28.0

33% 50%

Table 3: Existing baseline partial lotteries, k ∈ {33%, 50%}. Local sensitivity under a singlereview one-tick perturbation. Max ∆p is the maximum coordinate change and Smoothness is local sensitivity (∆pL1 /input perturbation magnitude).

G.2

Smoothness of Existing Partial Lottery Designs

We now present additional results on the smoothness of two existing partial lottery mechanisms, MERIT and the Swiss NSF mechanism (Section 7.1 in the main text). Tables 2 and 3 show that these mechanisms can be highly unstable under small review perturbations. Across datasets and acceptance rates, changing a single review score by one tick can induce large jumps in marginal selection probabilities for both mechanisms. This confirms that the instability of threshold-based partial lotteries is not just a worst-case theoretical concern, but appears empirically on real peer review and grant-funding data. Figure 10 compares the Clipped Linear Lottery to MERIT and the Swiss NSF mechanism at acceptance rates of 50%. The Clipped Linear Lottery consistently gives a better regret–smoothness tradeoff, achieving substantially better smoothness at the same regret level.

Linear Lottery

ICLR

0.04

Regret / k

0.03

MERIT

Swiss NSF

NeurIPS

0.008

0.03

0.006

0.02

0.004

0.01

0.002

0.00

L (lower is smoother)

0.00 100

101

102

103

L (lower is smoother)

0.000

Swiss NSF Funding Data

L (lower is smoother)

Figure 10: Regret–smoothness tradeoff at acceptance rate 50%. Points show MERIT and Swiss NSF at their empirical local sensitivity under the worst one-review perturbation. Hollow red markers show worst-case smoothness guarantee of Clipped Linear Lottery at the same regret level.

Record · ID 204785 · SHA-256 8420324a3112d95b
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.