Learning Lotteries with Minimal Stakeholder Violations from Membership Queries¶

会议: NeurIPS 2026
arXiv: 2610.37828
代码: https://github.com/nicteh/Learning-Lotteries-Minimal-Stakeholder-Violations
领域: 学习理论
关键词: 概率社会选择, 成员查询, 极小化违背, 抽样泛化保证, 确定性下界

一句话总结¶

本文针对多利益相关者需求冲突时无法达成全员一致的 AI 部署困境，在成员查询模型下研究如何最小化拒绝主体数（Min-Viol），证明了其 APX-Hardness，给出了基于均匀抽样的无参人口级泛化误差界与多项式时间凸松弛 LP，并严格证明确定性算法对未查询主体无法提供任何非平凡保障。

研究背景与动机¶

在现代人工智能系统的部署中，开发者往往面临多个候选模型版本（例如在安全性与有用性之间权衡不同的拒答阈值、推理延迟或针对特定下游任务优化的模型），并可以通过在线混合路由（A/B 测试或灰度发布）将用户请求按概率分布指派给不同版本。每个利益相关方（如内容安全审计团队、监管机构或拥有私有评测数据的商业客户）各自拥有其接受阈值，当混合策略的期望性能（如不安全回复率或拒答率）满足该标准时方可被接受。由于各方指标在混合分布下满足期望线性性，每个主体的可接受策略集合自然构成概率单纯形上的一个闭半空间。

然而，在实际治理与合规交互中，利益相关方出于商业机密或数据隐私绝不会公开私有评测集与效用函数，监管准则也多以复杂的法律文本呈现；决策者唯有通过提出具体的候选混合方案，向主体发起二元成员查询（“该方案对你是否可接受？”）来探查偏好。此前工作（Choo et al., ICML 2026）在此查询模型下聚焦于寻找全员一致可接受的彩票方案（Unanimity）。但当安全红线与可用性发生根本冲突时，全员可行的单纯形交集往往为空集，一味追求一致性不仅无法给出一句“不存在可行解”之外的落地建议，还会让单一苛刻主体拥有否决整套系统的过度权力。

面对不可避免的需求冲突，决策者必须在有限的查询预算下，寻找一个令尽可能少的主体产生违背（拒绝）的混合彩票（Min-Viol）。核心 idea：将多主体冲突部署建模为概率单纯形上的极小化违背半空间问题（Min-Viol），揭示其即便在全信息下亦属 APX-Hard 的计算本质，进而证明只需对主体进行不依赖总体规模 \(n\) 的均匀随机抽样，即可获得强统计泛化上界与多项式时间 LP 松弛解，同时从理论上封死确定性自适应查询向未见主体迁移的可能性。

方法详解¶

整体框架¶

Min-Viol 的目标是在 \(m\) 个候选备选项 \(S=\{s_1,\dots,s_m\}\)（构成单纯形 \(\Delta(S)\)）与 \(n\) 个利益相关主体 \(N=[n]\) 的设定下，通过最少的主体成员查询，找到使拒绝主体数 \(\mathrm{viol}(\mathbf{x}):=|\{i\in N:\langle u_i,\mathbf{x}\rangle < \tau_i\}|\) 最小的彩票 \(\mathbf{x}\in\Delta(S)\)。每个主体的规范化效用向量为 \(u_i\in[0,1]^m\)，接受阈值为 \(\tau_i\in(0,1]\)，其接受集 \(A_i=\{\mathbf{x}\in\Delta(S):\langle u_i,\mathbf{x}\rangle\ge \tau_i\}\) 为单纯形上的半空间。

整个技术体系围绕“全信息复杂性基准 \(\to\) 结构化精确求解 \(\to\) 均匀抽样统计学习 \(\to\) 凸松弛多项式算法 \(\to\) 确定性最坏情形下界”层层展开：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["利益相关主体需求与私有评测集<br/>（隐式半空间约束）"] --> B["全信息难度界定：APX-Hardness<br/>与参数化精确算法"]
    B --> C["均匀抽样与统计泛化学习<br/>VC 维与相对误差界"]
    C --> D["大动作空间凸松弛 LP<br/>单侧铰链罚项设计"]
    D --> E["确定性查询下界阻断<br/>严苛下界证明"]
    E --> F["输出兼具理论安全边界与<br/>低违背率的最优部署彩票"]

关键设计¶

1. 全信息难度界定：APX-Hardness 与参数化精确算法

当决策者已知全部主体的半空间约束时，Min-Viol 本质上对应概率单纯形上的最大可行子系统（Max-FS）与极小未满足约束（Min-ULR）问题。本文通过从三次图上的最小顶点覆盖问题（Minimum Vertex Cover on cubic graphs，已知为 APX-Hard）构建保持近似比的归约，证明即使所有主体的效用均为二元 0/1 且拥有全信息，Min-Viol 依然是 APX-Hard，排除了存在多项式时间近似方案（PTAS）的可能。在算法层面，本文利用单纯形顶点的几何性质，证明最优解必位于至多 \(m-1\) 个超平面边界与单纯形边界的交点上，给出了时间复杂度为 \(\mathcal{O}(\binom{n+m}{m-1}(m^3+nm))\) 的确定性精确枚举算法（在备选数 \(m\) 固定时属于 XP 复杂度）。此外，当预期的违背数 \(v\) 较小时，借助 Helly 定理对不可行超平面族进行递归分支排除，构建了运行时间为 \(m^v\cdot\mathrm{poly}(n,m)\) 的固定参数可解（FPT）算法；而若仅以违背数 \(v\) 为参数（\(m\) 任意），则证明了其属于 W[2]-Hard。

2. 均匀抽样与统计泛化学习：不依赖总体规模的样本复杂度

为了避免对全部 \(n\) 个主体发起高成本成员查询，算法独立均匀抽取 \(k\ge m\) 个主体，利用二分网格检索恢复被抽样主体的可接受半空间。由于单纯形上诱导拒绝集合 \(\{i:\langle u_i-\tau_i\mathbf{1},\mathbf{x}\rangle < 0\}\) 对应于 \(\mathbb{R}^m\) 中过原点的半空间分类器族，其 VC 维严格受限于备选项数目 \(m\)。借助一致收敛性与 VC 不等式，本文证明：以至少 \(1-\delta\) 的概率，在抽样集上极小化违背数的任意经验最优彩票 \(\widehat{\mathbf{x}}\)，在全人口上的违背数满足：

\[\mathrm{viol}(\widehat{\mathbf{x}})\le \mathrm{OPT} + 8n\sqrt{\frac{m\log(2ek/m)+\log(8/\delta)}{k}}\]

该结果揭示了一个深刻的治理结论：为了将全量主体的额外违背比例控制在常数 \(\epsilon\) 内，所需的抽样主体数 \(k\) 仅取决于备选模型数 \(m\) 与置信度 \(\delta\)，而与总体规模 \(n\) 完全无关。无论是面对一千家还是上百万家客户，所需的抽样评估规模保持恒定。当最优违背规模满足 \(\mathrm{OPT}\ge \rho n\) 时，结合相对误差界进一步给出了保证 \((1+\zeta)\mathrm{OPT}\) 的乘性近似样本界 \(\mathcal{O}((m\log(1/\rho)+\log(1/\delta))/(\zeta^2\rho))\)。

3. 大动作空间凸松弛 LP：单侧铰链罚项设计

当备选模型数量 \(m\) 随维度膨胀时，在抽样集上执行离散 Min-Viol 同样面临 NP 困难。为此，本文设计了一个带间隔裕度 \(\eta\in(0,1]\) 的凸松弛目标函数。对每个抽样主体 \(i_t\)，定义单侧铰链惩罚变量 \(z_t\ge \max\{0, (\tau_{i_t}+\eta-\langle u_{i_t},\mathbf{x}\rangle)/\eta\}\)。当主体被满足且裕度超过 \(\eta\) 时罚分为 0，处于接受边界时罚分为 1，而产生违背时罚分线性递增（至多 \(1+1/\eta\)）。通过求解标准线性规划：

\[\min_{\mathbf{x}\in\Delta(S), \mathbf{z}\ge 0} \frac{1}{k}\sum_{t=1}^k z_t \quad \text{s.t.} \quad z_t\ge \frac{1}{\eta}\left(\tau_{i_t}+\eta-\langle u_{i_t},\mathbf{x}\rangle\right), \ \forall t\in[k]\]

利用 Rademacher 复杂度与凸包 Lipschitz 组合性质，证明该 LP 在任意 \(m\) 下均可在多项式时间内求解，且其解 \(\widehat{\mathbf{x}}_\eta\) 以高概率满足违背上界 \((1+1/\eta)\mathrm{viol}(\mathbf{x}) + |B_\eta(\mathbf{x})| + \mathcal{O}(\frac{n}{\eta}\sqrt{\frac{\log m+\log(1/\delta)}{k}})\)。该保证在存在裕度充裕的候选解时尤为紧凑，抽样误差仅以 \(\sqrt{\log m}\) 缓慢增长。

4. 确定性查询下界阻断：非自适应与不可迁移性证明

针对工业界常倾向于“固定咨询几个核心大客户或内部安全组”的直觉做法，本文构造了强有力的对抗反例证明：对于任意 \(m\ge 3\) 的确定性查询算法，只要其总共仅访问了 \(K\) 个相异主体（无论在这些主体上耗费多少次自适应精细提问），对抗环境总能构造一组二元效用与单位阈值的主体配置，使得所有被查询的 \(K\) 个主体对输出方案反馈满意，但所有未被查询的 \(n-K\) 个主体全部拒绝该输出；与此同时，存在一个全局纯策略彩票（如 \(s_1\) 或 \(s_2\)）能同时满足所有 \(n\) 个主体（\(\mathrm{OPT}=0\)）。该结论严格证明确定性算法的加性误差下界必然达到 \(n-K\)。换言之，对未受访主体做出任何统计保证的唯一数学源泉是主体的“随机抽样”，任何确定性策略对未见主体都只能给出平凡结果。

损失函数 / 训练策略¶

本方法在推断与策略求解阶段不需要梯度微调模型权重，而是直接在决策单纯形 \(\Delta(S)\) 上运行离散或凸优化算法。当备选模型集合 \(m\le 3\) 时，采用多边形边界交点枚举结合单纯形过滤实现精确求解；对于高维场景（如 \(m=500\)），则通过 SciPy / HiGHS 求解器对线性规划 (1) 进行高精度内点法求解。对于带噪成员查询（主体以概率 \(p<1/2\) 独立翻转判断），算法通过设置重复查询轮数 \(r=\lceil 2\log(Q/\delta)/(1-2p)^2\rceil\) 并采纳多数投票机制，即可在增加至多 \(r\) 倍查询开销下完整保持全部无噪统计保证。

实验关键数据¶

主实验¶

实验在 \(n=500\) 个主体、\(m=3\) 个备选模型的模拟环境中评估，分为两类种群：分离设定（Separated，真实接受主体裕度 \(\ge 0.05\)）与临界设定（Near-threshold，接受主体裕度 \(<0.05\)）。种群中预设 \(15\%\) 主体拒绝基准彩票。对比样本规模 \(k\in\{30, 120, 480\}\) 下的样本精确极小化与不同裕度参数 \(\eta\) 的 LP 松弛方法。

评估方法	抽样主体数 \(k\)	分离设定额外违背率 (%)	临界设定额外违背率 (%)	理论对齐特性
样本精确极小化 (Exact)	\(k=30\)	6.81 (95th: 19.24)	6.25 (95th: 15.81)	小样本经验违背波动较大
样本精确极小化 (Exact)	\(k=120\)	1.67 (95th: 4.22)	1.36 (95th: 3.41)	误差降至 2% 以下，远优于 VC 最坏界
样本精确极小化 (Exact)	\(k=480\)	0.43 (95th: 1.40)	0.23 (95th: 0.80)	接近全局全信息最优
凸松弛 LP (\(\eta=0.02\))	\(k=120\)	1.96 (95th: 5.60)	3.60 (95th: 6.80)	较小裕度在临界分布下表现更稳健
凸松弛 LP (\(\eta=0.05\))	\(k=120\)	0.53 (95th: 1.61)	9.20 (95th: 17.82)	分离设定优于 Exact，临界设定发生欠拟合
全信息 LP (\(\eta=0.02\))	全量 \(n=500\)	0.51 (95th: 1.67)	1.86 (95th: 3.80)	消除抽样方差后的纯松弛逼近误差
全信息 LP (\(\eta=0.05\))	全量 \(n=500\)	0.28 (95th: 0.80)	5.22 (95th: 8.22)	充分反映罚分因子 \(1+1/\eta\) 的权衡

消融实验¶

针对确定性查询与随机查询的差距，测试固定抽取 \(K\) 个相异主体并极小化其内部违背时，在总体 \(n=500\) 上的加性误差 \((\mathrm{viol}(\widehat{\mathbf{x}})-\mathrm{OPT})\) 相对于理论最坏值 \(n-K\) 的比率（%）。

查询主体数 \(K\)	最坏情形理论界 (\(n-K\))	分离设定实际差距占 \((n-K)\) 比例 (%)	临界设定实际差距占 \((n-K)\) 比例 (%)	对抗构造轮次实际差距
\(K=10\)	490	13.01% (约 63.7 人)	19.17% (约 93.9 人)	490 (100% 饱和)
\(K=25\)	475	8.62% (约 40.9 人)	7.79% (约 37.0 人)	475 (100% 饱和)
\(K=50\)	450	3.77% (约 17.0 人)	3.66% (约 16.5 人)	450 (100% 饱和)
\(K=100\)	400	2.11% (约 8.46 人)	2.00% (约 7.99 人)	400 (100% 饱和)
\(K=200\)	300	1.23% (约 3.69 人)	0.88% (约 2.64 人)	300 (100% 饱和)
\(K=400\)	100	0.58% (约 0.58 人)	0.57% (约 0.57 人)	100 (100% 饱和)

关键发现¶

经验收敛速度显著优于理论上界：在 \(n=500\) 的群体中，仅抽取 \(k=120\) 个主体（不足全量的四分之一），经验最优解的额外违背率即收敛至 \(1.5\%\) 左右，而理论上的显式 VC 上界在此样本量下仍大于 \(n\)；样本量每扩大 4 倍，额外违背均值下降约 3.9 至 5.9 倍，收敛速率显著快于理论保证的 \(\mathcal{O}(1/\sqrt{k})\)。
LP 松弛裕度参数 \(\eta\) 的两极效应：在真实解具备充裕裕度（Separated）时，LP 采用 \(\eta=0.05\) 的表现甚至超越了样本精确极小化（0.53% vs 1.67%），因为精确极小化倾向于贴着样本约束边界选点，而 LP 显式鼓励向内部收缩；但在大量主体紧贴阈值时，过大的 \(\eta\) 会惩罚合法主体，导致违背率激增至 9.20%。
高维单纯形稀疏稀释验证：在 \(n=1000, m=500, \eta=0.15\) 的大规模备选实验中，定理 4.2 证明 \(s_\eta=169\) 个备选项足以保持效用损失在 \(\eta\) 之内；实测表明在充裕裕度下，抽取 169 个备选项在 480 次实验中完全没有产生任何新增违背，甚至缩减至 50 个备选项时依然有 471 次零新增违背，证实了彩票支撑集极具稀疏化潜力。

亮点与洞察¶

样本复杂度与总体规模的脱钩性：论文将多主体治理冲突严谨转化为单纯形上的半空间 VC 维问题，确立了样本规模 \(k\) 完全独立于人口规模 \(n\) 的优良性质，为千万级用户平台与企业级 AI 服务的代表性合规审计提供了坚实理论依据。
确定性查询盲区的警示价值：定理 6.1 与 6.2 证明了对未被直接询问的主体无法通过任何确定性自适应策略建立推断保障（最坏情况损失必然达到 \(n-K\)）。这一发现指出了工业界依赖固定客户代表或单一评审团做系统部署决策的巨大合规盲区，确立了“必须采用随机抽样”的不可替代性。
凸松弛与裕度几何的精巧连接：通过将不可微的指示函数松弛为单侧折线罚分，结合 Rademacher 复杂度，使得在大规模备选版本集合 \(m\) 下的高效求解成为可能，且证明了当系统存在高裕度可行解时松弛完全不损失精度。

局限与展望¶

线性期望效用假设的边界：模型严格建立在 von Neumann–Morgenstern 线性期望模型上，假设利益相关方的评价只取决于混合策略的平均概率与均值表现；对于关注方差风险、极值尾部风险或非线性概率加权的主体（如前景理论），该半空间划分假设不再成立。
二元无噪声交互的理想化假设：虽然文中给出了基于重复多数表决的简单噪声扩展，但在现实人机交互或人工评估中，主体偏好可能存在持续性系统偏差（adversarial shift）或随上下文漂移，缺乏对动态演化偏好与主动式序列轮询的建模。
离散网格恢复依赖：精确重构主体的半空间超平面法向量依赖于预设的浮点网格二分搜索，虽然在多项式时间内可完成，但在实际评估系统中对连续参数空间的密集二元询问依然存在工程开销。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性形式化并解决了成员查询下的极小化违背彩票学习问题，填补了一致性失败后的理论空白。
实验充分度: ⭐⭐⭐⭐ 包含细致的合成基准验证、MIP 对账消融与高维单纯形稀疏验证，虽缺少真实模型部署评测，但紧密呼应了理论定理。
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰严谨，从全信息复杂性、抽样界到下界构造层层递进，数学表述与直观洞见结合优异。
价值: ⭐⭐⭐⭐⭐ 为大模型多目标对齐、版本混合部署路由以及代表性利益相关方合规审计提供了基石性的理论指引。