Epistemic Pairwise Maximin Share¶

会议: NeurIPS 2026
arXiv: 2606.18921
OpenReview: https://openreview.net/forum?id=6pVA0fm67W
领域: 学习理论
关键词: 不可分物品公平分配, 配对最大最小份额, 认知松弛, 嫉妒消除循环算法, 词典序极大极小

一句话总结¶

本文首次形式化引入认知配对最大最小份额（EPMMS）与认知群组最大最小份额（EGMMS），打破了 EEFX 现有技术（消圈与孤立划分者）无法直接迁移的理论壁垒，证明了加性效用下多项式时间可求 4/5-EPMMS 分配，双值效用下多项式时间存在精确 EGMMS 分配，并在 MMS 普遍不存在的 3 智能体与双类型智能体设定下证明了精确 EPMMS 的必然存在性。

研究背景与动机¶

不可分物品的公平分配问题在众多现实机制设计中至关重要，如高校选课席位分配、学术会议审稿人分配等。在双人分配场景中，“切蛋糕者切、选择者选”（cut-and-choose）机制天然构成了规范解；然而当推广到 $n \ge 3$ 个智能体时，不存在直接平移的典范机制。为此，学界提出了两类核心松弛概念：基于比较的至多差一件无嫉妒（EFX）与配对最大最小份额（PMMS）。PMMS 要求任意智能体 $i$ 在与另一智能体 $j$ 的联合打包集合 $X_i \cup X_j$ 上，其效用至少达到由自己作为二分切割者时所能保证的最大最小份额 $\mu_i(2, X_i \cup X_j)$。在非退化条件下，PMMS 严格强于 EFX，然而无论 EFX 还是 PMMS 在一般加性效用下的存在性均是长期悬而未决的公开难题。

近期在 EFX 研究上的突破得益于“认知”（Epistemic）视角的引入——即 EEFX 允许每个智能体站在自身主观效用视角，将其他智能体手中的物品重新虚拟划分为满足 EFX 的束，从而使智能体仅凭自身分得的物品集合即可验证公平性，而无需关心他人之间真实的微观切分。这一认知松弛在加性乃至一般单调效用下均取得了严格存在性保证。很自然的核心矛盾随之浮现：这一强大的认知视角能否攻克条件更强、结论更罕见的 PMMS 难题？

深入考察表明，EEFX 依赖的两大支柱方法在 PMMS 面前全面失效：其一，传统用于消除嫉妒环的 Envy Cycle Elimination 算法沿环轮换物品束时能严格保持 EFX，但在 PMMS 下即使从精确 PMMS 出发，单次消圈也会将保证暴跌至 $\frac{2\alpha}{2+\alpha} \le \frac{2}{3}$；其二，单调效用下依赖的 Lone Divider 树状匹配依赖于“子集可行可单调回溯至全集可行”的性质，而这一单调性在 EPMMS 下被显式反例完全摧毁；此外，MMS 并不蕴含 EPMMS。核心 idea：本文构建了从任意偏好到相同排序实例的保持规约框架，在排序实例上证明了非退化加性效用下 Envy Cycle Elimination 能够维系 4/5-PMMS 下界，并借助词典序极大极小（Leximin）解的结构性质在双值、3 智能体及双类型智能体中确立了精确 EPMMS/EGMMS 的存在性。

方法详解¶

整体框架¶

本文针对加性效用、双值效用（Bivalued）、3 智能体与双类型智能体展开系统分析。整体处理流水线分为两个核心阶段：首先是通用规约层，将任意偏好排序的实例通过物品位次定义与 Picking Sequence 机制规约为所有智能体对物品价值降序完全一致的“相同排序实例（Identical-Ranking Instance）”；随后在排序实例上，分别设计消圈流水线与基于词典序极大极小（Leximin）的递归构造算法，最后通过保序双射将虚拟分配映射回原始真实实例。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：任意加性/双值效用实例"] --> B["相同排序规约机制<br/>按位次构建有序实例并用 Pick 序列保持比例下界"]
    B --> C{"判定估值类型与智能体设定"}
    C -->|一般加性效用| D["非退化微扰消圈分配<br/>扰动破除退化 + 贪心无嫉妒赋权 + 环轮转"]
    C -->|双值效用 a,b| E["递归 Leximin 前缀剥离机制<br/>按高估值前缀长度递减排序 + 最小基数束划分"]
    C -->|3 智能体 / 双类型| F["结构化分区与优先级选择<br/>基于首选者 Leximin + 剩余物品次级 Leximin 组合"]
    D --> G["输出：4/5-EPMMS 且 EEFX 分配"]
    E --> H["输出：精确 EGMMS 分配（强于 MMS 与 EPMMS）"]
    F --> I["输出：精确 EPMMS 分配（3 人下兼得 IMMP）"]

关键设计¶

1. 相同排序规约机制：将多代理异质排序严格保真投影至有序空间 在经典公正划分中，智能体对物品排序的差异会导致复杂的组合爆炸。为解决 EPMMS 下任意成对重组的复杂偏差，本文建立了面向 EPMMS 与更强群组 GMMS 的排序规约框架。设智能体 $i$ 对物品按自身估值降序排列的位次为 $r_i(g)$，构建统一有序实例 $\hat{\mathcal{I}}$，其中有序估值函数为 $\hat{v}_i(T) = v_i(\{ \ell_t \mid t \in T \})$。在有序实例获得分配 $\hat{X}$ 后，算法定义抓取序列 $L = (a_1, \ldots, a_m)$，其中 $a_k = i$ 表示在 $\hat{X}$ 中第 $k$ 件物品分给智能体 $i$。随后在真实实例中运行贪心抓取算法 $\text{Pick}(\mathcal{I}, L)$，每个智能体轮到时挑选当前剩余中真实估值最高的物品。该机制的关键保证由结构双射引理提供：存在双射 $\pi_i: [m] \to M$，使得智能体 $i$ 分得的物品在位次上只增不减（$r_i(\pi_i(j)) \le j$），而未分得物品的位次只降不增（$r_i(\pi_i(j)) \ge j$）。利用加性效用与 $(1-\alpha) \ge 0$ 的代数放缩： $$\hat{v}_i(\hat{X}_i \setminus \hat{R}) + (1-\alpha) v_i(R) \ge \alpha \hat{v}_i(\hat{P}_1 \setminus \hat{R})$$ 从而将有序实例中的任意 $\alpha$-EPMMS（及 $\alpha$-EGMMS）证书直接拉回为原实例中的合法认知证书。

2. 非退化微扰消圈分配：突破消圈破坏成对份额的 2/3 瓶颈 直接在普通加性实例上运行 Lipton 等人的消圈算法，可能在退化点（不同物品束价值相等）遭遇死锁或由于成对效用跨越导致 PMMS 比率退化至 2/3 甚至更低。本文首先证明了非退化性（任意两不同子集效用不相等）是维系高近似比的本质条件，并通过对物品注入指数级微扰 $\varepsilon \cdot 2^j$（其中 $\varepsilon \cdot 2^{m+1} < \delta$）实现全多项式时间无损扰动规约。在有序非退化实例上，算法维护贪心无嫉妒分配与嫉妒有向图。当待分配物品 $g$ 加入到被指向的智能体束 $X_j \setminus \{g\}$ 时，若 $v_i(g) \le \frac{1}{2} v_i(X_i)$，则直接由均值不等式导出： $$\mu_i(2, X_i \cup X_j) \le \frac{1}{2}(v_i(X_i) + v_i(X_j \setminus \{g\}) + v_i(g)) \le \frac{5}{4} v_i(X_i) \implies v_i(X_i) \ge \frac{4}{5} \mu_i(2, X_i \cup X_j)$$ 而若 $v_i(g) > \frac{1}{2} v_i(X_i)$，有序性与非退化性强力约束了束的结构：$X_j$ 恰好只有两件物品 $\{g', g\}$ 且之前持有 $X_i$ 前缀的智能体必持有单件更大物品 $h$，满足 $v_i(h) > v_i(g') > v_i(g)$，通过剔除引理再次证明 $v_i(X_i) \ge \mu_i(2, X_i \cup X_j)$。两者结合严格闭合了 4/5 边界。

3. 递归 Leximin 前缀剥离机制：利用词典序优势实现精确 EGMMS 针对双值效用 $v_i(g) \in \{a, b\}$（$0 \le a < b$），各智能体在有序设定下的偏好差异完全退化为各自高估值前缀 $p_b(i)$ 的长度不同。本文拓展了 Feige 针对 MMS 的选择框架，其本质革新在于：Feige 任意选取 MMS 分区会导致 EPMMS 证明显式失效，本文强制要求在剩余物品集 $M^{(i)}$ 上计算关于 $v_i$ 的词典序极大极小（Leximin）分区 $(B_i^i, \ldots, B_n^i)$。算法挑选基数最小的束赋给智能体 $i$ 并让其包含最高索引的可用 $b$ 值物品。在构建认知证书 $Y^i = (X_1, \ldots, X_i, B_{i+1}^i, \ldots, B_n^i)$ 后，本文通过对子集 $J \subseteq [n]$ 最小索引 $j_1 = \min(J)$ 的倒退归纳法（Backward Induction）证明 GMMS 成立：若 $j_1$ 占有 $i$ 的高值物品，利用 Leximin 替换引理（若去掉一部分最优点，剩余子束仍是剩余集上的最优 Leximin），证明整个证书后缀构成等价估值下的全局 Leximin，因而天然满足 GMMS；若 $j_1$ 仅含低值物品 $a$，则依据其束基数是否超过平均水平，分别利用 MMS 单调性引理（剔除低于平均规模的最小值子集不降低 MMS）或在补集中寻找更大基数束进行对换，全面确立精确 EGMMS。

4. 结构化分区与优先级选择：在 3 智能体与双类型场景突破 MMS 存在性限制 已知即使在 3 个加性智能体或两种类型智能体下，经典 MMS 分配也可能根本不存在。本文针对此两类困难结构构造了显式的多项式证书机制： - 对于 3 智能体：先求智能体 1 的全局 Leximin 分区 $(X_1, X_2, X_3)$，不妨设智能体 2 认为 $X_1$ 最劣，再由智能体 2 对 $X_2 \cup X_3$ 做二等分 Leximin 分区 $(X_2', X_3')$。随后让智能体 3 在候选束集 $\{X_1, X_2', X_3'\}$ 中首选其最偏好的束。若智能体 3 未选 $X_1$，智能体 1 拿走 $X_1$，智能体 2 拿走剩余束；若智能体 3 挑走 $X_1$，则智能体 2 在原始 $(X_2, X_3)$ 中挑选其最偏好的束，智能体 1 拿走剩余。此机制不仅保证每人均具备合法 EPMMS 证书，且保证全员满足 IMMP（即每个人要么得到自身 MMS 份额，要么在真实分配中对他人无 PMMS 嫉妒）。 - 对于两类型智能体（类型 $\alpha$ 与 $\beta$）：首先对全体物品按 $v_\alpha$ 求解全局 $n$ 束 Leximin 分区，将其中被 $v_\beta$ 认为价值最小的 $|N_\alpha|$ 个束分给类型 $\alpha$ 的全体智能体；剩余的全部物品再按 $v_\beta$ 重新求解 $|N_\beta|$ 束的内部 Leximin 分区并分给类型 $\beta$ 的智能体。由于类型 $\beta$ 分到的每一束均弱优于分给类型 $\alpha$ 的最大束，且自身内部为 Leximin，故天然无 PMMS 嫉妒；类型 $\alpha$ 则直接以原始全局 Leximin 分区作为全员 EPMMS 证书。

损失函数 / 训练策略¶

本理论工作为纯离散算法与组合极值分析，无连续优化损失函数。其核心计算复杂度与算法终止保证源自以下两点： 1. 非退化消圈的步数界：在 Algorithm 1 中，每次主循环要么消耗一件未分配物品（至多 $m$ 步），要么在产生有向环时进行束轮换消除嫉妒环。由于每次轮换使参与智能体的效用单调严格增加且束的物理组合有限，在非退化性保证下消圈过程在多项式步内必达拓扑无环态，算法总时间复杂度为 $O(m \cdot n^3)$。 2. 双值 Leximin 分区的动态规划算法：利用相同估值下双值物品仅由 $a$ 值与 $b$ 值物品数量决定的性质，设计状态为 $\text{DP}[k][n_a][n_b]$ 的动态规划（其中 $k \le n, n_a \le N_a, n_b \le N_b$ 为剩余智能体数及物品数）。每一状态转移枚举分配给单人的 $(i, j)$ 组合，总时间复杂度为 $O(n \cdot N_a^2 N_b^2)$，确保了 Algorithm 2 的强多项式可解性。

实验关键数据¶

主实验¶

本文的核心实验/定理分析给出了不同设定下 EPMMS 与相关公平性概念的最优保证比率与计算复杂度，明确区分了基线方法与本文提出的认知松弛保证：

估值设定与智能体规模	公平性保证类型	本文保证（Ours）	现有最优基线（Prev. SOTA）	相对提升与优势
一般加性效用 ($n$ 智能体)	乘性近似保证	4/5-EPMMS (多项式时间)	0.781-PMMS (Kurokawa [42]) / 1/2-PMMS (EF1 蕴含)	突破长期停滞的 0.781 上界，首提认知配对份额且兼具 EEFX
双值估值 ($v_i(g) \in \{a,b\}$)	精确公平性判定	精确 EGMMS (包含 EPMMS)	精确 MMS (Feige [30]) / 精确 EFX [8]	从单一全局份额（MMS）强化至任意子群认知份额（EGMMS）
3 智能体加性估值	复合公平性满足	精确 EPMMS + IMMP	精确 EFX (Chaudhury [25]) / 2/3-PMMS	首度证实 3 人加性下 EPMMS 必存（而一般 MMS 可能不存在）
双类型加性智能体	精确公平性判定	精确 EPMMS	精确 EFX (Mahara [47]) / 一般 MMS 不存在 [29]	绕过 Feige-Sapir-Tauber 的 MMS 负反例，多项式构造成功
相同排序加性实例	局域消圈下界	4/5-PMMS 严格紧确界	2/3-PMMS (未考虑非退化时崩溃)	修正前人证明漏洞，提供非退化下严格紧确 0.8 因子

消融实验¶

针对消圈过程与机制构造中的核心技术假设，本文构造了多项精确的反例实例，严格证明了各设计机制的必要性与紧确性：

算法机制 / 假设配置	剥离或退化状态	测得极限公平性指标	机制失效与理论说明
消圈单步保持性	允许任意单次消圈	$\le \frac{2\alpha}{2+\alpha}$ (精确为 2/3)	命题 A.1 构造 3 智能体 6 物品实例，单次轮换直接将 1-PMMS 击穿至 2/3
非退化性假设	允许零价值物品（退化）	$\le 2/3$-PMMS	观测 F.1 构造 3 智能体 7 物品实例，退化使消圈停滞于 2/3
非退化性假设	严格正价值物品（退化）	$\le 3/4$-PMMS	观测 F.2 构造 7 物品全正值实例，退化估值在消圈后最高仅达 3/4
Algorithm 1 整体分析	采用完整非退化加性微扰	严格等于 4/5-PMMS	命题 D.1 给出 3 人 9 物品微扰实例，算法输出比率严格收敛至 4/5，证实分析紧确
双值估值分区策略	采用任意 MMS 代替 Leximin	EGMMS 完全失效	观测 A.7 证实普通 MMS 划分不包含 EPMMS 证书，必须采用 Leximin
估值结构假设	纯单调非负效用（2 智能体）	EPMMS 不存在	2 人下 EPMMS 等价于 PMMS，继承 Byrka 等人的非存在性，与 EEFX 形成鲜明分离

关键发现¶

消圈保持性的维度断裂：EFX 在消圈操作下天然闭合，而 PMMS 在消圈下会发生灾难性衰减（单步直接掉至 2/3）。本文的突破在于发现：只要引入非退化性扰动并在相同排序下运行贪心分配，消圈步骤所引发的偏离能够被全局几何约束严格限制在 4/5 以内。
MMS 与 EPMMS 的双向独立性：MMS 虽为更宏观的份额，但在本质上与局部成对认知并不等价。观测 A.7 明确给出了“满足 MMS 却不满足 EPMMS”以及“满足 EPMMS 却不满足 MMS”的完全双向不可比反例，打破了前人关于“宏观大份额必然蕴含局部份额”的直觉猜想。
双值效用下的层级跃迁：对于双值效用，前人仅证明了全局 MMS 与 EFX 的存在；本文直接将保证提升至群组最大最小份额（EGMMS），由于 EGMMS 严格强于 MMS，本结论构成了对 Feige [30] 经典结论的严格加强。

亮点与洞察¶

认知视角的独立理论版图：以往学者认为认知松弛是 EFX 的专属工具，本文通过反例（证明 Lone Divider 失效与消圈崩溃）与新构造，系统奠定了认知配对最大最小份额（EPMMS）的理论基础，揭示了比较公平与份额公平在认知松弛下的深层交织。
非退化微扰的杠杆作用：通过在离散估值上叠加指数微扰 $\varepsilon \cdot 2^j$ 消除所有子集平局，迫使消圈算法在状态空间中走出单向严格递增路径，以极为极简的纯代数手法修复了前人文献（Dai et al. [28]）中遗漏退化讨论的关键漏洞。
Leximin 替换引理的代数威力：引理 5.2 证明了最优 Leximin 分区在剥离单个束后，剩余子束依然保持等价的 Leximin 极值性，这为后续在多智能体交互中构造递归不变的认知证书提供了高度通用的数学工具。

局限与展望¶

一般加性效用下精确 EPMMS 的未解状态：虽然本文给出了 4/5-EPMMS 多项式算法，但对于一般加性效用下是否存在精确（1-因子）EPMMS 分配（即便在 4 个智能体时）依然是一个重大的未决公开问题。
计算复杂度对特定类别的依赖：在双值效用下利用动态规划可在多项式时间求解 Leximin，但一般加性效用下的 Leximin 计算本身是 NP-hard 的，限制了 Leximin 结构在一般高效算法设计中的直接应用。
向次模与一般互补估值的推广阻力：由于 2 智能体单调估值下 PMMS 已被证明必然不存在，EPMMS 在超越 GMMS-feasible 估值类别后将迅速遭遇坚硬的理论不可能性天花板。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出 EPMMS 与 EGMMS，开辟了配对份额认知松弛的全新研究方向，技术反例深刻。
实验充分度: ⭐⭐⭐⭐⭐ 纯理论组合极值论文，数学证明严谨完整，所有紧确界与下界均配有完备的反例分析。
写作质量: ⭐⭐⭐⭐⭐ 结构清晰，反例动机阐述极其透彻，引理递进关系自洽优美。
价值: ⭐⭐⭐⭐⭐ 为离散公平分配中长期停滞的 PMMS 难题提供了极具希望的突破路径，理论奠基意义显著。

估值设定与智能体规模	公平性保证类型	本文保证（Ours）	现有最优基线（Prev. SOTA）	相对提升与优势
一般加性效用 (\(n\) 智能体)	乘性近似保证	4/5-EPMMS (多项式时间)	0.781-PMMS (Kurokawa [42]) / 1/2-PMMS (EF1 蕴含)	突破长期停滞的 0.781 上界，首提认知配对份额且兼具 EEFX
双值估值 (\(v_i(g) \in \{a,b\}\))	精确公平性判定	精确 EGMMS (包含 EPMMS)	精确 MMS (Feige [30]) / 精确 EFX [8]	从单一全局份额（MMS）强化至任意子群认知份额（EGMMS）
3 智能体加性估值	复合公平性满足	精确 EPMMS + IMMP	精确 EFX (Chaudhury [25]) / 2/3-PMMS	首度证实 3 人加性下 EPMMS 必存（而一般 MMS 可能不存在）
双类型加性智能体	精确公平性判定	精确 EPMMS	精确 EFX (Mahara [47]) / 一般 MMS 不存在 [29]	绕过 Feige-Sapir-Tauber 的 MMS 负反例，多项式构造成功
相同排序加性实例	局域消圈下界	4/5-PMMS 严格紧确界	2/3-PMMS (未考虑非退化时崩溃)	修正前人证明漏洞，提供非退化下严格紧确 0.8 因子

算法机制 / 假设配置	剥离或退化状态	测得极限公平性指标	机制失效与理论说明
消圈单步保持性	允许任意单次消圈	\(\le \frac{2\alpha}{2+\alpha}\) (精确为 2/3)	命题 A.1 构造 3 智能体 6 物品实例，单次轮换直接将 1-PMMS 击穿至 2/3
非退化性假设	允许零价值物品（退化）	\(\le 2/3\)-PMMS	观测 F.1 构造 3 智能体 7 物品实例，退化使消圈停滞于 2/3
非退化性假设	严格正价值物品（退化）	\(\le 3/4\)-PMMS	观测 F.2 构造 7 物品全正值实例，退化估值在消圈后最高仅达 3/4
Algorithm 1 整体分析	采用完整非退化加性微扰	严格等于 4/5-PMMS	命题 D.1 给出 3 人 9 物品微扰实例，算法输出比率严格收敛至 4/5，证实分析紧确
双值估值分区策略	采用任意 MMS 代替 Leximin	EGMMS 完全失效	观测 A.7 证实普通 MMS 划分不包含 EPMMS 证书，必须采用 Leximin
估值结构假设	纯单调非负效用（2 智能体）	EPMMS 不存在	2 人下 EPMMS 等价于 PMMS，继承 Byrka 等人的非存在性，与 EEFX 形成鲜明分离