Research map / Bandits and online learning / Online convex optimization and games
Smooth Partial Lotteries for Stable Randomized Selection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes smoothness (Lipschitz condition from review scores to marginal selection probabilities) as a design principle for partial lotteries and the clipped-linear "smooth lottery" mechanism, with near-optimal regret and empirical tests on peer review data.
Problem
Existing partial lottery designs for funding/admissions are unstable: small changes to one review score can cause large jumps in selection probability. The paper seeks selection rules whose marginals vary smoothly with review scores while keeping low regret.
Approach
Define smoothness as an l1-Lipschitz condition from review matrix to marginal selection probabilities, and use a clipped-linear lottery (selection probabilities = clip(slope*utility + intercept) with budget-satisfying intercept), whose slope is set to alpha/(2L) to guarantee smoothness alpha; show near-matching regret lower bound and compare to IF, DP, and softmax.
Key results
- Under MERIT or Swiss NSF mechanisms, a single one-point review change can shift selection probability by more than 0.3 on NeurIPS and ICLR.
- The smooth lottery achieves lower normalized regret than top-k softmax at every smoothness level across datasets.
- Empirical worst-case smoothness of the smooth lottery is within 99% of the theoretical upper bound at n=1000.
Surprising findings
- Standard differential privacy does not imply smooth marginals; a DP randomized-response rule can have discontinuous marginals.
Limitations
- Assumes exact globally Lipschitz utility functions, while practical utility estimates may be noisy.
- Factor (1 - k/n) gap between upper and lower regret bounds.
- Does not study effects on reviewer behavior or institutional decision-making.
Experimental setup
Datasets: ICLR 2025 reviews NeurIPS 2024 reviews Swiss National Science Foundation review data synthetic Beta-distributed reviews
Benchmarks: ICLR 2025 reviews NeurIPS 2024 reviews Swiss NSF reviews synthetic Beta reviews
Metrics: empirical local smoothness (l1 change in marginals / l1 chan normalized regret tightness ratio of smoothness bound
Baselines: MERIT Swiss NSF partial lottery top-k softmax (Gumbel-top-k) three-tier uniform lottery
Builds on: Individual Fairness metric differential privacy exponential mechanism RankMax sparsemax
Closest papers by meaning
- A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding (NeurIPS 2025 · similarity 0.88)
- Learning Fair Policies for Multi-Stage Selection Problems from Observational Data (AAAI 2024 · similarity 0.86)
- Competition among Pairwise Lottery Contests (AAAI 2024 · similarity 0.84)
- Centralized Selection with Preferences in the Presence of Biases (ICML 2024 · similarity 0.83)
- Fair Lotteries for Participatory Budgeting (AAAI 2024 · similarity 0.83)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.