Envy-Free Allocation of Indivisible Goods via Noisy Queries¶

会议: ICML 2026
arXiv: 2602.06361
代码: 无
领域: 多智能体 / 公平分配 / 算法博弈论
关键词: 无嫉妒分配, 噪声查询, 高斯噪声, 多臂老虎机, 样本复杂度

一句话总结¶

本文首次给"用噪声查询估值来寻找无嫉妒分配"这个新问题立了样本复杂度的尺：在两个智能体、加性高斯噪声、\(m\) 件物品、最优负嫉妒缺口 \(\Delta\) 的设定下，证明所需查询次数的紧界为 \(\widetilde{\Theta}(m^{2.5}/\Delta^2)\)（当 \(\Delta\gg m^{1/4}\)），上界由非自适应查询 + 单物品阈值多项式时间算法实现，下界对自适应查询和任意计算时间都成立。

研究背景与动机¶

领域现状：不可分物品的公平分配是经济学与算法博弈论交叉处的核心问题，最常用的公平准则是无嫉妒 (EF)：每个智能体认为自己得到的那份不比别人那份差。由于精确 EF 经常不存在，文献里大量研究放宽到 EF1 / EFX。绝大多数工作有一个默认前提：每个智能体对每件物品的效用 \(u_i^\nu\) 是精确已知的，或可以一次查清。

现有痛点：现实里这个假设常常不成立——估值要么靠随机仿真估计、要么是一群人的平均、要么是评估过程本身有噪声。一旦把"精确效用"换成"含噪观测"，几乎所有现有 EF/EF1 算法都失去保证。已有的"带查询"公平分配工作 (Oh et al. 2021; Bu et al. 2024; Plaut–Roughgarden 2020) 默认查询无噪，且查的是捆绑而非单件；Li et al. 2025 引入了噪声但仍假设"重复查询 + 多数投票"就能恢复精确值（噪声为常概率翻转的离散噪声）。

核心矛盾：在加性高斯噪声下，无论查多少次都得不到精确效用，只能拿到带 \(1/\sqrt{q}\) 收敛的估计。要同时把所有物品估到足够准会让样本量指数级爆炸；而事实上 EF 只需要"分得对"而不需要"估得准"，这就需要新的算法 + 新的下界技术去刻画两者之间的差距。

本文目标：(1) 形式化"噪声查询下的 EF 分配"问题；(2) 给出在 \(m\)、\(\Delta\)、噪声方差 \(\sigma^2\) 下的紧样本复杂度；(3) 上界要可在多项式时间内实现，下界要对自适应+任意时间算法都成立。

切入角度：把"最优分配的负嫉妒缺口" \(\Delta=-\mathrm{OptEnvy}\) 作为问题难度的"间隙参数"，类似多臂老虎机里的 reward gap。\(\Delta\) 越大、最优分配越"宽裕"，找到 EF 越容易。这种以缺口为单位的视角让我们能像 bandit 一样写出 \(q\propto \mathrm{poly}(m)/\Delta^2\) 的标准样本复杂度形式。

核心 idea：不要为每件物品都估出 \(O(\Delta/m)\) 精度，而是按 \(cv_i^a - v_i^b\) 的单物品阈值规则直接分配，再通过精心选择阈值常数 \(c\) 让两侧嫉妒"自动平衡"——这能把朴素 \(\widetilde{O}(m^3/\Delta^2)\) 砍到 \(\widetilde{O}(m^{2.5}/\Delta^2)\)；下界则用 4 类物品 (两类"细微偏好" + 两类"双方共同偏好") 构造的硬实例，证明这个 \(m^{2.5}\) 不可改进。

方法详解¶

整体框架¶

两类对偶贡献：

问题形式化：\(m\) 件物品在两个智能体 \(a,b\) 之间分配，估值 \(u_i^\nu\in[0,1]\)；每次查询返回 \(y_{i,t}^\nu\sim\mathcal{N}(u_i^\nu,\sigma^2)\)；目标是用最少查询数 \(q\) 输出一个分配 \(\widehat{\mathcal{A}}\)，以高概率满足 \(\mathrm{Envy}(\widehat{\mathcal{A}})\le 0\)。问题难度由最优负嫉妒 \(\Delta>0\) 参数化，\(\mathrm{OptEnvy}\le -\Delta\)。
三段式技术：朴素基线 (§3) → 改进上界 (§4) → 匹配下界 (§5)。论文同时给出常数噪声方差和一般 \(\sigma\) 的版本 (§6)，并把结论平移到比例公平 (§7)。

关键设计¶

朴素重复采样基线 — 揭示瓶颈在哪 (\(q=\widetilde{O}(m^3/\Delta^2)\)):
- 功能：作为"对比组"说明天真做法的代价，并精确定位为什么会浪费 \(m\) 因子。
- 核心思路：把 \(q\) 次查询均匀摊到 \(m\) 件物品上，每件采样 \(\tau=q/m\) 次，平均得到 \(v_i^\nu=\tfrac{1}{\tau}\sum_t y_{i,t}^\nu\)；然后暴力枚举所有分配 \(\mathcal{A}\)，挑 \(\min\{v_{\mathcal{A}_a}^a-v_{\mathcal{A}_b}^a,\,v_{\mathcal{A}_b}^b-v_{\mathcal{A}_a}^b\}\) 最大者。用单物品置信区间累加得到捆绑置信宽度，要求宽度 \(\le \Delta\) 推出 \(\tau\gtrsim \sigma^2 m^2/\Delta^2\)，故 \(q=\widetilde{O}(m^3/\Delta^2)\)。
- 设计动机：暴露两个弱点——(i) 累加置信宽度按"最坏情况" \(O(m\cdot\sigma/\sqrt{\tau})\) 放大，浪费一阶 \(m\)；(ii) 暴力搜索分配指数复杂度。后续上界正是分别修这两点。
改进上界 — 单物品阈值 + 自适应阈值常数 \(c\) (\(q=\widetilde{O}(m^{2.5}/\Delta^2)\)):
- 功能：把样本复杂度从 \(m^3\) 砍到 \(m^{2.5}\)，同时把分配规则变成多项式时间。
- 核心思路：在 \(q\ge m\) 的"小 \(\Delta\)"区间，仍均匀采样估计 \(v_i^\nu\)，但分配改为按 \(cv_i^a - v_i^b\) 做单物品阈值 \((\mathrm{eq.4})\)：\(cv_i^a>v_i^b\) 给 \(a\)，否则给 \(b\)。利用 \(cv_i^a-v_i^b\) 是高斯，精确刻画每件物品的分配概率，把两侧嫉妒按合适权重加总，证明存在阈值 \(c\) 使 \(a\to b\) 与 \(b\to a\) 的真实嫉妒同时为负；该 \(c\) 只依赖估计值 \(v_i^\nu\)，所以算法可计算。再在 \(q<m\) 的"大 \(\Delta\)"区间里随机抽 \(q\) 件采一次、其余按 \(1/2\) 概率独立随机分配，并通过中心极限论证未采样部分的 \(\sqrt{m}\) 波动不会吞掉已采样部分的负嫉妒。
- 设计动机：把朴素分析里"按最坏方式累加误差"的 \(m\) 损失换成"阈值规则下分配概率的精确刻画"。通过对 \(c\) 做平衡而不是固定 \(c=1\)，避免了"一方估值整体高于另一方"时的失败模式，相当于用一个全局自由度抵消异质性。论文在 Remark 2 解释为何 \(\Delta\ge m^{1/4}\log^2 m\) 是"平滑性"控制的内在限制，不仅是技术 artifact。
匹配下界 — 4 类物品硬实例 + 多假设检验 (\(\Omega(m^{2.5}/\Delta^2)\)):
- 功能：证明 \(m^{2.5}/\Delta^2\) 是紧的，连任意自适应查询 + 任意计算时间的算法都做不到更少查询。
- 核心思路：Table 1 设计了 4 类物品：(i) \(i\le m/2\) 段每件以 \(1/2\) 概率被 \(a\) 微弱偏好 \(\tfrac{1}{2}\pm\varepsilon\)、被 \(b\) 反向偏好；(ii) \(i>m/2\) 段每件以 \(1/2\) 概率被双方共同偏好/嫌弃 \(\tfrac{1}{2}\pm\gamma\)。前一组贡献"识别个体类型的难度"，后一组贡献"未采样部分的随机波动 \(\Theta(\sqrt{m})\)"。再用 Le Cam / KL 风格的多假设检验，证明 \(q\le O(m^{2.5}/\Delta^2)\) 时算法以常数概率失败。常数噪声下，参数取 \(\gamma=1/2\) 当 \(\Delta\gg m^{3/4}\)、\(\gamma=\Theta(\varepsilon m^{1/4})\) 当 \(\Delta\ll m^{3/4}\)。
- 设计动机：原始"只放 \(\tfrac{1}{2}\pm\varepsilon\) 物品"的朴素硬实例只能撑到 \(m/\Delta^{1.5}\) 或 \(m^2/\Delta^2\)，比上界松；加入"共同偏好"物品把未采样部分的随机波动从 \(\Theta(\varepsilon\sqrt{m})\) 拉到 \(\Theta(\sqrt{m})\)，正好填补这一段差距，得到与上界仅差对数因子的紧界。

损失函数 / 训练策略¶

本文为算法分析型工作，无可微损失。算法层面的关键超参是阈值常数 \(c\)（由估计值自适应选取以平衡两侧嫉妒）和采样模式（\(q\ge m\) 时每件均匀重复采样、\(q<m\) 时随机子采样一次）。理论分析建立在加性高斯噪声的子高斯尾界、KL/Le Cam 多假设检验、以及"分配概率—嫉妒积分—中心极限"三段证明链上。

实验关键数据¶

主结果对比表¶

论文核心成果是样本复杂度上下界 (常数噪声方差)，下表汇总。

结果	适用条件	查询次数 \(q\)	备注
朴素重复采样上界 (Thm.1)	任意 \(\Delta>0\)	\(O(m^3\log(m/\delta)/\Delta^2)\)	暴力枚举分配，指数时间
本文主上界 (Thm.2)	\(m^{1/4}\log^2 m\le\Delta\le Cm\)	\(\widetilde{O}(m^{2.5}/\Delta^2)\)	多项式时间、非自适应查询
本文主下界 (Thm.3)	\(\Delta\in(1,m/2)\)	\(\widetilde{\Omega}(m^{2.5}/\Delta^2)\)	对自适应+任意时间算法成立
朴素硬实例下界 (§5 讨论)	—	\(\max\{m/\Delta^{1.5},m^2/\Delta^2\}\)	严格弱于本文下界，说明 4 类硬实例的必要性

最关键的结论是：在 \(\Delta\gg m^{1/4}\log^2 m\) 的"广阔区间"内，上下界匹配到对数因子，真实样本复杂度 \(= \widetilde{\Theta}(m^{2.5}/\Delta^2) = \widetilde{\Theta}\!\left(\sqrt{m}/(\Delta/m)^2\right)\)，把"归一化缺口" \(\Delta/m\) 显式分离了出来。

一般噪声水平下的精细界¶

区域	上界	下界	紧度
\(q\ge m\) (Thm.5, Appx.C.3)	\(q=m\lceil\sigma^2(15 m^{3/2}\log m/\Delta^2+\log^2 m)\rceil\)	\(O(\sigma^2 m^{2.5}/\Delta^2)\) (Δ=O(m^{3/4}))	第一项主导时 \(\log m\) 紧
\(q<m\) (Thm.102, Appx.C.4)	\(\max\{160^2 m^4\sigma^4\log^2 m/\Delta^4,\,160\sigma m^{5/2}\log^2 m/\Delta^2\}\)	\(O(\sigma m^{2.5}/\Delta^2)\) (Δ=ω(m^{3/4}))	第二项主导时 \((\log m)^2\) 紧

关键发现¶

\(\sqrt{m}\) 因子的来源：直观上 \(q\propto \sqrt{m}/(\Delta/m)^2\)，分母 \((\Delta/m)^2\) 是 bandit 风格的"归一化缺口的平方倒数"，分子 \(\sqrt{m}\) 反映把 \(m\) 件物品打包成一捆时误差的中心极限累积。
何时无需查每一件：\(\Delta\gg m^{3/4}\) 时算法只需查 \(q<m\) 件，未采样部分靠随机分配 + 中心极限消化，反而比"每件都查一次"更便宜。
下界对算法构造很有启发：朴素 \(\tfrac{1}{2}\pm\varepsilon\) 硬实例不够紧，必须再加入"双方共同偏好"项才能逼近 \(m^{2.5}\)，这提示设计算法时不能忽视"对两方都贵/便宜"的物品对随机波动的放大效应。
比例公平 = EF (n=2, 加性)：两个智能体加性效用下，\(r\) 嫉妒等价于"低于按比例份额 \(r/2\)"，所以本文所有结果可平移到比例公平。

亮点与洞察¶

把"算法博弈论中的 EF 问题"和"统计估计/多臂老虎机的样本复杂度框架"漂亮地缝合在一起：把 \(\Delta\) 当作 gap，让经济学语言里的"公平阈值"直接对应到统计语言里的"探索难度"。
单物品阈值 + 自适应阈值常数 \(c\) 是一个非常优雅的设计：不需要任何 bundle-level 估计，却能通过一个全局自由度抵消两个智能体的整体偏差，分析虽然技术却非常自然。
下界里"加入双方共同偏好物品放大随机波动"的 trick 非常巧妙，揭示了一种以前文献忽视的"不影响最优嫉妒方向、但影响算法决策方差"的辅助结构。如果未来要把结果推广到 \(n>2\) 智能体，这类构造很可能是下界证明的核心模板。
论文把上界完全用非自适应查询实现 (Thm.2)，下界却允许任意自适应算法，这种"上紧下松地匹配"在 bandit 文献里很有教学价值。

局限与展望¶

主要结果只覆盖 两个智能体。作者在 §7 指出 \(n>2\) 时阈值规则要从单比例扩展到 \(\binom{n}{2}\) 个比例，是否仍是正确的统计量都不清楚；这是最显著的开放问题。
仅考虑加性效用和加性高斯噪声。子高斯噪声的扩展应可走类似路线但需要重做集中不等式；非加性效用 (互补 / 替代) 几乎肯定需要新算法。
假设 \(\Delta\ge m^{1/4}\log^2 m\)：作者在 Remark 2 中说明这一限制看似技术性，但很可能反映了算法在小缺口下需要从"item-by-item 阈值"切到"bundle 级"决策的本质区别。
没有 EF1 / EFX 等放宽：本文专注严格 EF，未来把噪声查询样本复杂度扩展到 EF1/EFX 会更贴合实际，因为后两者总是存在解，可避免 \(\Delta\) 假设。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次形式化"噪声查询下的 EF 分配"，并给出与 bandit 思维完美对接的样本复杂度框架。
实验充分度: ⭐⭐⭐⭐ 纯理论工作，三段证明 (朴素上界 / 改进上界 / 匹配下界) 完备且配套一般噪声水平的精细界。
写作质量: ⭐⭐⭐⭐⭐ 主文给直觉、附录给细节、Remark 1-2 明确指出建模与技术假设的边界，可读性极高。
价值: ⭐⭐⭐⭐ 开辟了"噪声查询公平分配"这一新方向，对群体决策、众包分配、A/B 测试驱动的资源分配有直接启发；\(n>2\) 与 EF1 推广是天然后续。