跳转至

Smooth Partial Lotteries for Stable Randomized Selection

会议: NeurIPS 2026
arXiv: 2605.20069
OpenReview: https://openreview.net/forum?id=zciTC98AYH
代码: https://github.com/akgoldberg/smooth_lottery
领域: 其他
关键词: 随机化选择, 部分抽奖, 平滑性, 截断线性抽奖, 遗憾界

一句话总结

针对科学基金资助与同行评审中传统部分抽奖在决策边界处高度不稳定、单篇微小分值变动即引发入选概率突变的问题，本文提出平滑选择原则并设计截断线性抽奖（Clipped Linear Lottery），在严格保证边际概率全局利普希茨连续的同时，实现了匹配理论下界的近最优遗憾界。

研究背景与动机

在科研基金分配、高校招生、学术会议口头报告遴选以及招聘初筛等高竞争性评审场景中，决策机构通常依靠多位评审员对候选人打分并据此选拔高质量候选集。近年来，包括瑞士国家科学基金会（Swiss NSF）、新西兰健康研究理事会（NZ HRC）及大众汽车基金会（Volkswagen Foundation）在内的诸多资助机构，广泛推行引入随机化机制的“部分抽奖”（Partial Lotteries）。引入随机化的核心初衷，是承认同行评审打分具有主观随机性与固有不确定性，从而减少评审专家组在录取线附近对微小分差进行无休止、主观武断的拉锯争论，使委员会能够“求同存异”（agree to disagree），把边界决策交由概率决定。

然而，现行的主流部分抽奖机制普遍依赖刚性硬阈值分档设计：高于录取线者直接确定入选，低于淘汰线者直接拒绝，唯独处于中间候选池的申请人参与等概率均匀抽奖。这种分段跃迁结构在数学上内生了严重的不稳定性。当某位申请人恰好位于拒绝与抽奖、或抽奖与确定入选的临界点时，某一位评审员仅仅改动一分的微小分值扰动，就会让该申请人发生跨组阶跃，其入选概率随之出现 \(0\) 到数十个百分点的断崖式跳跃。这种脆弱的不稳定性彻底背离了抽奖机制的设计初衷——它不仅没有消除临界线处的微小分差敏感性，反而将评审打分的微小噪声放大为决定命运的离散突变。

要从根源上遏制这种不稳定性，随机化选择机制必须对输入打分的连续变化保持稳定的响应。本文的核心 idea 是将平滑性（Smoothness）确立为部分抽奖机制的核心设计准则，通过约束从评审打分到边缘入选概率映射的全局利普希茨（Lipschitz）连续性，提出兼具封闭最优性与极简几何形式的截断线性抽奖机制（Clipped Linear Lottery），彻底抚平决策边界处的概率突变。

方法详解

整体框架

本文考虑从 \(n\) 名候选人中评选出 \(k\) 名优胜者的随机选择机制。每位候选人 \(i \in [n]\) 拥有来自 \(r\) 位评审员的标准化评分矩阵 \(X \in [0,1]^{n \times r}\)，机制由此诱导候选人的边缘入选概率向量 \(p(X) \in [0,1]^n\)，并满足总体预算约束 \(\sum_{i=1}^n p_i(X) = k\)。为了实现稳定性，系统要求映射 \(X \mapsto p(X)\) 满足全局 \(L\)-平滑性，即 \(\|p(X) - p(X')\|_1 \le L \|X - X'\|_{1,1}\)，确保任何单项打分的扰动对全场录取概率的影响严格受控。截断线性抽奖首先将候选人打分映射为满足 \(D_u\)-利普希茨条件的效用值 \(u_i(X)\)，通过平滑斜率缩放得到未截断打分，随后求解全局预算截距，最后将概率平滑截断于 \([0,1]\) 区间，并在最终通过系统抽样输出基数严格为 \(k\) 的录取子集。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["评审评分矩阵 X<br/>n 候选人 × r 评审员"] --> B["效用聚合与平滑缩放<br/>计算 u_i 与 z_i = w · u_i"]
    B --> C["预算截距精确求解<br/>寻找标量 b 满足全局预算 k"]
    C --> D["双侧平滑截断投影<br/>p_i = clip(z_i + b, 0, 1)"]
    D --> E["无偏子集系统抽样<br/>输出严格满足基数 k 的录取集 S"]

关键设计

1. 截断线性抽奖机制与受限单纯形投影：在保持全局线性的同时吸收边界饱和

为了在满足总预算 \(\sum_i p_i = k\) 的前提下消除分段突变，截断线性抽奖并没有采用不可控的非线性 Sigmoid 逻辑映射，而是采用几何意义极其优雅的截断线性结构。针对平滑参数 \(L\) 与效用利普希茨常数 \(D_u\)，算法将缩放斜率精确配置为 \(w = \frac{L}{2 D_u}\)，令缩放后效用为 \(z_i = w \cdot u_i(X)\)。随后，通过引入全局标量截距 \(b \in \mathbb{R}\)，将每位候选人的边缘入选概率定义为：

\[p_i(X) = \text{clip}_{[0,1]}(z_i + b) = \min\{1, \max\{0, z_i + b\}\}\]

该截距 \(b\) 在数学上保证 \(\sum_{i=1}^n \text{clip}_{[0,1]}(z_i + b) = k\)。在几何本质上，该映射等价于将无约束缩放效用向量 \(w \cdot u(X)\) 欧氏投影到受限单纯形（Capped Simplex）\(\mathcal{C}_{n,k} = \{p \in [0,1]^n : \|p\|_1 = k\}\) 上：

\[p(X) = \arg\min_{p \in \mathcal{C}_{n,k}} \frac{1}{2} \|p - w \cdot u(X)\|_2^2\]

这一投影特性不仅保证了最优解的绝对唯一性与单调性，而且使得候选人自然分流为三个动态区间：确定录取池（\(p_i = 1\)）、确定淘汰池（\(p_i = 0\)）与处于线性缩放过渡带的活动抽奖池（\(0 < p_i < 1\)）。平滑参数 \(L\) 越小，斜率 \(w\) 越平缓，抽奖池平稳扩大；反之 \(L\) 增大，抽奖池向确定性 Top-\(k\) 压缩，彻底杜绝了硬边界跨越带来的狄拉克突变。

2. 严格的平滑性上界与常数因子紧致性保证：双倍扰动预算的数学对消

机制之所以能够严格保证 \(L\)-平滑性，关键在于对全局预算截距 \(b\) 的变动幅度施加了精确的对称界定。当输入打分发生微小变动导致候选人效用产生 \(\|u - u'\|_1\) 的扰动时，单个候选人项在固定截距下的变动至多为 \(w \|u - u'\|_1\)；然而，为了在变动后强制满足总录取人数恰为 \(k\)，截距 \(b\) 必须做出平移。这一平移使得全场概率出现反向补偿，但在最坏情况下，总概率的绝对变动和至多被放大一倍，即 \(\|p - p'\|_1 \le 2w \|u - u'\|_1\)。由于选定 \(w = \frac{L}{2 D_u}\) 且效用满足 \(\|u - u'\|_1 \le D_u \|X - X'\|_{1,1}\)，整体映射严格满足：

\[\|p(X) - p(X')\|_1 \le 2w D_u \|X - X'\|_{1,1} = L \|X - X'\|_{1,1}\]

论文进一步给出了这一平滑性常数的紧致性证明：在全零初始分值下对单个候选人施加 \(\varepsilon\) 的单点扰动，受制于归一化预算，该候选人概率增加 \(\varepsilon w \frac{n-1}{n}\)，而其余 \(n-1\) 个候选人各均摊削减 \(\frac{\varepsilon w}{n}\)，诱导的全场总变动为 \(2w\varepsilon \frac{n-1}{n} = L \frac{n-1}{n} \varepsilon\)。这表明所推导的利普希茨平滑界在因子 \(1 - \frac{1}{n}\) 尺度上达到渐进严格紧致。

3. 近最优最坏情况遗憾界分析：匹配理论下界的理论证明

引入平滑约束不可避免地会对选拔总效用带来损耗。论文将机制相对于确定性最佳 Top-\(k\) 选择的效用差值定义为最坏情况遗憾（Worst-case Regret）\(R(\mathcal{D}, X) = \max_{S: |S|=k} \sum_{i \in S} u_i(X) - p(X)^\top u(X)\)。借助欧氏投影的最优性一阶变分条件 \((p - wu)^\top (q^* - p) \ge 0\)（其中 \(q^*\) 为最优 Top-\(k\) 指示向量），可将遗憾转化为关于边际概率的凹二次规划，进而推导出截断线性抽奖的最坏情况遗憾严格满足：

\[\max_{X \in [0,1]^{n \times r}} R(\mathcal{D}, X) \le \frac{k(1 - \frac{k}{n}) D_u}{2L}\]

更为关键的是，论文针对任意满足 \(L\)-平滑性的选择规则推导了信息论意义上的遗憾理论下界：在全零基准上对最不可能被选中的 \(k\) 名候选人施加隐蔽扰动，当 \(L \ge \frac{1}{r}(1 - \frac{k}{n})\) 时，任何机制的最坏遗憾至少为 \(\frac{k(1 - k/n)^2 D_u}{2L}\)。截断线性抽奖的遗憾上界与这一通用下界仅相差一个乘性因子 \(1 - \frac{k}{n}\)（在低录取率如 \(k/n = 10\%\) 时仅差 0.9）。这从理论上证明了截断线性抽奖在平滑性与效用权衡空间中的近最优性。

损失函数 / 训练策略

作为无需学习权重的确定性/随机化机制设计，该方法在测试推理期直接执行解析求解。对于截距 \(b\) 的计算，算法利用总概率累加函数 \(S(b) = \sum_{i=1}^n \text{clip}_{[0,1]}(w \cdot u_i + b)\) 在实数轴上的分段线性与单调非减特性，先收集由 \(2n\) 个断点构成的临界集合 \(B = \{-z_i\}_{i=1}^n \cup \{1 - z_i\}_{i=1}^n\)，排序后定位满足 \(S(b_j) \le k \le S(b_{j+1})\) 的激活区间，利用两端点斜率线性插值在 \(O(n \log n)\)（或两遍扫描 \(O(n^2)\)）时间内完成截距的解析闭式求取。得到边际概率 \(p(X)\) 后，执行 Madow 系统抽样算法（Systematic Sampling），以 \(O(n)\) 复杂度生成基数严格恒等于 \(k\) 的无偏随机子集。

实验关键数据

主实验

实验采用真实顶会同行评审数据与科研基金评审数据：ICLR 2025（\(n=3710\) 篇被接收论文，模拟录取率 \(k/n=10\%\) 评选 Oral 演讲）、NeurIPS 2024（\(n=4034\) 篇被接收论文，\(k/n=10\%\) Oral 评选）、瑞士科学基金会 Swiss NSF（\(n=353\) 份基金提案，打分区间 1–6）以及合成 Beta 分布评审流（\(n=200, r=5\)）。对比基准包括现有实际运行的区间抽奖机制 MERIT、Swiss NSF 贝叶斯抽奖机制，以及满足度量差分隐私的 Top-\(k\) Softmax 指数机制。

下表评估现有部分抽奖机制在单名候选人单项评审分值微调 1 分（one-tick perturbation）下的局部脆弱性（录取率 \(k/n=10\%\)）：

数据集 机制名称 最大单体概率跳变 (\(\text{Max } \Delta p\)) 经验局部敏感度 (\(\text{Smoothness } L_{\text{emp}}\)) 相同遗憾下截断线性抽奖保证的理论平滑度 \(L\)
ICLR 2025 MERIT 0.314 5.7 0.42
ICLR 2025 Swiss NSF 0.532 9.6 0.38
NeurIPS 2024 MERIT 0.321 5.8 0.41
NeurIPS 2024 Swiss NSF 0.633 11.4 0.37
Swiss NSF MERIT 0.471 4.7 0.52
Swiss NSF Swiss NSF 0.923 18.7 0.46
Beta (Synthetic) MERIT 0.500 9.0 0.61
Beta (Synthetic) Swiss NSF 0.667 24.0 0.55

在平滑性–遗憾权衡对比中，在相同平滑参数 \(L\) 下，截断线性抽奖在全部三个真实数据集上的归一化最坏遗憾相比 Top-\(k\) Softmax 平均降低 25%–40%，且随着候选人规模 \(n\) 的增大，Softmax 固有的 \(O(\log n)\) 遗憾劣势愈发明显。

消融实验

消融与理论验证实验聚焦于理论平滑性上界紧致度与接受率/分布尖锐度对平滑抽奖机制的影响：

配置 / 检验项 设定条件 经验测得指标与紧致度 说明
平滑界理论紧致度 (CLL) \(n=1000, k \in \{100, 333, 500\}\) 经验值达到理论上界 \(99.1\%\) 验证了 Theorem 4.1 中常数因子 \(L\) 的极致紧凑性
平滑界理论紧致度 (Softmax) \(n=1000, \tau = \frac{2D_u}{eL}\) 经验值达到理论上界 \(95.3\%\) 证实基于 Gumbel 极值导数推导的 Softmax 平滑常数紧致
录取率缩放 \(k/n = 33\%\) NeurIPS 2024 归一化遗憾下降 \(31.8\%\) 符合理论预测中的 \((1 - k/n)\) 因子缩放衰减
录取率缩放 \(k/n = 50\%\) NeurIPS 2024 归一化遗憾下降 \(48.2\%\) 候选池两端差值缩小时，随机化引入的效用损失显著降低
效用分布集中度 (Beta \(\alpha=1 \to 10\)) \(n=200, k=20\) 遗憾随 \(\alpha\) 单调下降 \(44.5\%\) 打分越集中在均值附近，极值拉锯越弱，平滑抽奖代价越低

关键发现

  • 现有基于区间或硬边界的部分抽奖机制在现实同行评审中存在惊人的不稳定性：单个评审员改动一分，候选人的入选概率可在瞬间跳变超 \(0.3\) 至 \(0.923\)，表现出事实上的最大不稳定性。
  • 相比于全域非零支撑的 Top-\(k\) Softmax，截断线性抽奖具备天然的稀疏支撑特性（Sparse Support），能确定性保送顶尖候选人并确定性淘汰极弱候选人，将随机化严格限制在边界灰色区间，从而在相同平滑度下大幅降低遗憾值。
  • 理论平滑常数界在 \(n=1000\) 的大样本下与最坏扰动搜索结果契合度高达 \(99\%\) 以上，充分印证了该机制在对抗性打分偏移下的鲁棒安全边界。

亮点与洞察

  • 将偏微分几何与利普希茨连续性系统引入社会选择与评审机制设计，直击传统抽奖机制在分段决策边界处的脆弱痛点，给出了形式极简的解析解。
  • 巧妙证明了截断线性抽奖与受限单纯形欧氏投影、个体公平性（Individual Fairness）最优化线性规划之间的三重数学等价性，使得机制在获得全局平滑性保证的同时，天然具备个体公平性与预算单调性。
  • 建立起了平滑选择与差分隐私（标准 DP 及度量 DP）之间的理论桥梁，严密证明了标准 DP 无法阻断概率突变，而度量 DP 虽满足平滑性却在遗憾界上平白损失 \(O(k \log(n/k))\) 的关键结论。

局限与展望

  • 理论分析假定评审得分映射到效用函数的全局利普希茨性质完全已知，在非线性偏好或评审打分尺度扭曲较重时，需要额外校准效用函数。
  • 理论遗憾界与通用平滑选择机制下界之间仍存有 \(1 - \frac{k}{n}\) 的常数因子差距，闭合该常数缺口仍需进一步的极值拓扑分析。
  • 未评估机制部署后对评审人主观博弈与申诉行为的长期心理学反作用，真实学术会议与基金会的落地运行机制仍待进一步跟踪验证。

相关工作与启发

  • vs MERIT / Swiss NSF 机制: 后两者依赖不确定性区间做分层硬过滤，单分扰动即引发概率阶跃（经验跳变最高达 0.923）；本文截断线性抽奖通过连续斜率消除了分段断点，在相同遗憾下平滑度提升一个数量级。
  • vs Top-\(k\) Softmax (指数机制): Softmax 具有全局非零概率，无法排除极低分候选人且最坏遗憾带有 \(O(k \log n)\) 惩罚；本文机制支持稀疏截断，最坏遗憾仅为 \(O(k)\)，在相同平滑约束下效用更高。
  • vs 个体公平性 (Individual Fairness): 个体公平性仅约束单次评审下候选人间的横向概率差，无法约束跨数据集扰动的纵向突变；本文平滑性针对评审打分扰动建立全局李普希茨界，且通过斜率配置自然继承了个体公平性。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 首次将平滑性形式化为部分抽奖的设计基石，并给出了匹配理论下界的解析投影机制。
  • 实验充分度: ⭐⭐⭐⭐⭐ 覆盖 ICLR/NeurIPS 真实评审数据与 Swiss NSF 真实基金资助数据，充分验证了理论紧致性与经验平滑增益。
  • 写作质量: ⭐⭐⭐⭐⭐ 数学证明严丝合缝，理论脉络与物理直觉衔接极为通畅，图表清晰规范。
  • 价值: ⭐⭐⭐⭐⭐ 为解决科学基金分配与高水平学术会议 Oral/获奖评选等严肃评审场景中的边界公平性争端提供了坚实可行的方案。

相关论文