📈 economics

Fair Allocation with Optional Selling

本文研究了不可分物品的公平分配问题，其中代理人可以选择按市场价格出售物品，通过将标准公平性概念（如 MMS 和 EFX）应用于这种混合设定，并为平衡物品分配与收益的分配方案建立了存在性保证和近似界限。

原作者： Uriel Feige, Yotam Gafni

发布于 2026-08-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Uriel Feige, Yotam Gafni

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

公平分配是一个致力于解决一个如同人类合作一样古老的数学与经济学问题的领域：如何分割资源，使每个人都觉得自己获得了一份公平的份额。几十年来，研究人员一直在研究如何分配那些无法切割的物品，例如房子、汽车或珍稀书籍收藏。在这些场景中，目标是找到一种安排，使得没有人会对他人收到的东西感到嫉妒，或者确保每个人都能根据其个人偏好获得最低水平的满意度。然而，这些经典模型假设所涉及的物品是固定不变的。它们忽略了一个非常普遍的现实世界选项：将物品出售换取现金的能力。例如，在离婚时，一对夫妇可能会认为，卖掉家里的房子并平分所得款项，比由一个人保留房子而另一方一无所获的方案更好。这种出售物品的简单选项改变了可能性的整个格局，但也引入了以往理论未曾处理的新复杂性。

来自魏茨曼科学研究所的 Uriel Feige 和 Yotam Gafni 填补了这一空白，探索了当代理人可以选择按市场价格出售商品，然后再分配剩余物品和所得现金时会发生什么。他们的研究提出了一个基本问题：如果人们可以出售物品，那么保证公平结果是变得更容易了还是更难了？他们发现，虽然出售扩大了可能性，但与禁止出售的传统设定相比，要保证某些类型的公平实际上变得更难了。研究人员开发了新的衡量公平的方法，同时兼顾人们保留物品的价值和他们收到的现金。他们证明，对于两个人，总能找到一种满足最强公平标准的分配方式，确保即使在考虑了出售选项后，也没有人会对另一方的组合产生嫉妒。然而，随着人数的增加，保证程度会略微下降。对于三个人，他们表明不可能保证每个人都获得其绝对最大的可能公平份额；在某些情况下，人们所能期望的最佳结果仅是理想份额的一个特定比例。

研究人员还调查了对于更大规模的群体，他们能在多大程度上近似这些公平份额。他们证明，对于任何人数，总有一种方法可以分配商品和金钱，使得每个人至少获得其保证最低份额的三分之二。这是一个显著的结果，因为它表明即使在增加了出售的复杂性之后，仍然可以实现极高水平的公平。此外，他们发现可以将这种基于份额的公平与强烈的“无嫉妒性”相结合，这意味着没有人会更倾向于用自己的整套物品和现金去交换另一人的组合。他们通过改进一种被称为“孤立除法器”（Lone Divider）的方法实现了这一点，该方法涉及由一个人提出拆分方案，然后由其他人选择他们偏好的部分。在有出售选项的新设定下，他们必须仔细修改这种方法，确保明智地选择提出拆分的人，并且以特定的方式构建组合，以防止出售物品不公平地损害剩余参与者的利益。

论文中最引人注 el 发现之一是带有出售选项的设定与不带出售选项的设定之间的差异。作者构建了一个涉及三个人和八件物品的具体案例，在该案例中，如果允许出售，则无法保证每个人都能获得其理想份额的十一十二。在不允许出售物品的传统设定中，针对同一场景的最佳已知限制要高得多，这意味着出售的能力实际上在“理论上可能”与“实践中可保证”之间创造了更大的差距。这一反直觉的结果表明，虽然出售提供了灵活性，但它也引入了一种新的风险，即高价值物品可能以低价售出，导致剩余的物品不足以满足所有人的需求。研究人员还探讨了一个相关的场景，即关于“家务”或任务（即人们不喜欢的工作），其中外包工作以支付费用的方式扮演了与出售商品相同的角色。他们发现了类似的模式，表明支付费用请他人完成任务会使保证剩余工作的完美公平分配变得更加困难。

论文还讨论了这些数学证明的实际应用问题，即这些公平分配是否可以由计算机高效地计算出来。作者表明，在两个人的特定情况下，可以在合理的时间内找到公平分配。对于更大的群体，他们开发的算法可以无限接近理想的公平份额，这意味着只要有足够的计算能力，就可以找到一个几乎达到理论最佳值的解。他们还证明，一种基于“截断比例份额”（truncated proportional share）的特定公平保证是可以快速计算的，并且可以与无嫉妒条件相结合。这项工作为理解市场与个人偏好在公平分配问题中的相互作用提供了一个稳健的框架，为从离婚财产分割到遗产继承等各种情况提供了新的工具。通过严格定义在出售成为选项时什么是可能的，研究人员阐明了在资源可以转化为金钱的世界中公平的界限，确保我们明确知道在利益攸关时可以依赖哪些保证。

技术摘要：带有可选出售选项的公平分配

问题定义

本文研究了在代理人对物品拥有主观估值函数，但物品同时具有外生市场价格的情况下，不可分物品公平分配的问题。在这种设定中，代理人拥有“外部选项”：他们可以选择按市场价格出售物品。这些销售所得的收益是可分的，且对所有代理人具有统一的加性价值。

核心挑战在于设计一种分配机制，该机制需同时决定：

哪些物品集合应当被出售。
如何分配剩余未售出的物品。
如何分配从出售物品中获得的货币收益。

目标是满足能够将标准的基于份额（share-based）和基于嫉妒（envy-based）的保证适配到这种混合环境中的公平性概念。作者假设对于物品和金钱均采用加性估值。

公平性概念

本文改编了两类公平性定义：

基于份额的概念：
- 最大最小份额 (Maximin Share, MMS)： 定义为代理人通过优化决定出售哪些物品，然后将剩余物品和收益划分为 $n$ 个捆绑包，并获得其中价值最低的一个，从而能保证自己获得的最高价值。与标准 MMS 不同，代理人需要同时优化出售决策和划分方案。
- 截断比例份额 (Truncated Proportional Share, TPS)： 这是不可分设定中 TPS 概念的扩展，定义为最大的价值 $t$ ，使得所有物品的 $\max\{p(g), \min\{v(g), t\}\}$ 之和除以 $n$ 等于 $t$ 。
基于嫉妒的概念：
- SEF1 和 SEFX (强/可售无嫉妒)： 这些是 EF1 和 EFX 的适配版本。如果对于任何代理人 $i$ 和任何其他代理人 $j$ ， $i$ 在 $j$ 选择出售其一个物品（并获得市场价格）而非保留该物品时，都不会嫉妒 $j$ 的捆绑包，则称分配是 SEFX 的。形式化地，对于每个物品 $g \in A_j$ ， $\bar{v}_i(A_i) + P_i \ge \bar{v}_i(A_j \setminus \{g\}) + p(g)$ ，其中 $\bar{v}_i(g) = \max\{v_i(g), p(g)\}$ 。

方法论与算法

作者采用了多种算法技术，包括“切割与选择”（Cut & Choose）、“装袋”（Bag-Filling）以及“孤立分割者”（Lone Divider）范式的变体，并针对引入可选出售所带来的复杂性进行了修改。

切割与给予 (n=2)： 对于两个代理人，作者引入了一种“切割与给予”协议。一名“切割者”（Cutter）根据其 MMS 提出一个划分方案。如果另一名“给予者”（Giver）认为该捆绑包是可以接受的，则接受它。如果不可接受，给予者通过出售自己的预期物品并取消切割者的销售行为来修改划分，从而创建一个同时满足 MMS 和 SEFX 的新捆绑包。
带虚拟物品的装袋法 (TPS)： 为了实现 $n/(2n-1)$ -TPS，算法使用了一种“移动切刀”方法。市场价格较高的物品会被立即出售，以满足代理人的最低份额要求。剩余收益被视为“虚拟物品”。随后通过一个装袋程序分配捆绑包，直到代理人的价值达到要求的阈值。
规范划分 (用于 MMS 的孤立分割者)： 对于一般情况下的 $n$ ，作者改编了孤立分割者方法。其关键创新在于构建由具有最高 MMS 的代理人提出的“规范划分”。这些划分由“纯捆绑包”（不含金钱）、“单件捆绑包”（一个物品加上至多一个其他已售物品的收益）以及一个单一的“剩余物”捆绑包组成。这种结构限制了如果代理人拒绝的捆绑包被分配给他人时所遭受的潜在损失，特别是限制了因强制销售导致的损失。
处理高价值物品： 算法包含初步阶段，用于处理价值显著超过 MMS 阈值的物品，例如通过出售这些物品来满足特定代理人，或直接分配这些物品，从而确保剩余问题符合近似框架。

关键结果

1. 结合份额与嫉妒的保证

两个代理人 ( $n=2$ )： 始终存在一个同时满足 MMS 和 SEFX 的分配方案。这是一个很强的结果，因为在标准设定下实现完全 MMS 通常对于 $n \ge 3$ 是不可能的，而在这里，它是在实现强无嫉妒概念的同时实现的。
一般代理人 ( $n \ge 2$ )： 存在一个同时满足 $n/(2n-1)$ -TPS 和 SEFX 的分配方案。即使在没有 SEFX 要求的情况下，该比例 $n/(2n-1)$ 也被证明是 TPS 的最佳近似值。

2. MMS 近似界限

三个代理人 ( $n=3$ )： 本文确立了有出售与无出售设定之间的定量差距。虽然在标准不可分设定下（无出售），对于 $n=3, m=8$ 个物品，完全 MMS 是保证存在的（而已知最佳界限为 $39/40$ ），但在出售设定中，存在某些实例使得没有任何分配能保证超过 $11/12$ -MMS。
一般代理人 ( $n \ge 4$ )： 作者提供了一个 $2/3$ -MMS 分配方案。这与标准不可分设定（不含某些先前工作中发现的 $O(1/n)$ 加性项）中已知的最佳近似比相匹配。
特殊情况 ( $n=3$ )： 通过结合一般 $n$ 的方法与 $n=2$ 的全 MMS 算法，作者为三个代理人实现了 $3/4$ -MMS 分配。

3. 计算复杂度

MMS 计算： 计算精确的 MMS 值对于 $n=2$ $n = 2$ 是弱 NP-困难，对于一般 $n$ $n$ 是强 NP-困难。然而，本文提供了：
- 对于固定 $n$ 的伪多项式时间算法。
- 用于计算 MMS 值和划分的多项式时间近似方案 (PTAS)。
TPS 计算： TPS 可以高效地在多项式时间内计算。
结合保证： 对于同时满足 $n/(2n-1)$ -TPS 和 $\epsilon$ -SEFX 的分配，存在 FPTAS。

4. 扩展

等额收益： 本文分析了一个受限设定，即销售收益必须在所有代理人之间平等分配。在这种情况下，近似保证降至 $1/n$ -TPS，且 MMS 保证可能比不受限情况显著更弱。
带有外包任务的琐事 (Chores)： 该模型被扩展到琐事（负估值）场景，其中代理人可以以市场成本“外包”任务。其结果与物品设定类似：可以实现 2-MMS 近似，但近似差距比标准不可分琐事设定更宽。

重要性与主张

本文声称为当市场选项可用时，提供了一个“两全其美”的框架。其主要贡献包括：

理论差距识别： 它表明，引入出售选项虽然扩大了可行结果集，但却可能反直觉地使得近似某些公平性保证（特别是 MMS， $n=3$ 时）变得更加困难（相比于纯不可分设定）。
鲁棒算法： 它开发了新的算法技术（规范划分、改进的孤立分割者），尽管在优化出售决策方面增加了复杂性，但仍成功恢复了在存在出售情况下的最佳已知 MMS 近似比。
统一公平性： 它成功地将基于份额的保证（MMS/TPS）与强无嫉妒概念（SEFX）整合到单一分配中，表明高质量的份额近似并不一定会排除在此设定下的强无嫉妒性。

作者强调，其结果在若干情况下是紧致的（例如 TPS 的 $n/(2n-1)$ 界限），并且这些关于负面结果（ $n=3$ 时的 $11/12$ 差距）的结论是该模型的可证明限制，而非仅仅是当前算法局限性的产物。