2025-11-17T18:43:12.758371

Fair and Efficient Allocation of Indivisible Mixed Manna

Barman, HV, Sethia et al.
We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness -- in terms of a relaxation of envy-freeness -- and Pareto efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to $k$ reallocations (EFR-$k$): An allocation $A$ of the indivisible items is said to be EFR-$k$ if there exists a subset $R$ of at most $k$ items such that, for each agent $i$, we can reassign items from within $R$ (in $A$) and obtain an allocation, $A^i$, which is envy-free for $i$. We establish that, when allocating mixed manna among $n$ agents with additive valuations, an EFR-$(n-1)$ and Pareto optimal (PO) allocation $A$ always exists. Further, the individual envy-free allocations $A^i$, induced by reassignments, are also PO. In addition, we prove that such fair and efficient allocations are efficiently computable when the number of agents, $n$, is fixed. We also obtain positive results focusing on EFR by itself (and without the PO desideratum). Specifically, we show that an EFR-$(n-1)$ allocation of mixed manna can be computed in polynomial time. In addition, we prove that when all the items are goods, an EFR-${\lfloor n/2 \rfloor}$ allocation exists and can be computed efficiently. Here, the $(n-1)$ bound is tight for chores and $\lfloor n/2 \rfloor$ is tight for goods. Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.
academic

Fair and Efficient Allocation of Indivisible Mixed Manna

基本信息

  • 论文ID: 2507.03946
  • 标题: Fair and Efficient Allocation of Indivisible Mixed Manna
  • 作者: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
  • 分类: cs.GT (Computer Science - Game Theory)
  • 发表时间: 2025年10月15日 (arXiv预印本第二版)
  • 论文链接: https://arxiv.org/abs/2507.03946v2

摘要

本文研究具有加性估值的智能体之间不可分割混合甘露(mixed manna)的公平分配问题。混合甘露是指价值可能为正、负或零的物品。论文建立了公平性(基于无嫉妒性的放松)和帕累托效率可以同时实现的理论保证。具体而言，公平性保证基于"k次重新分配的无嫉妒性"(EFR-k)概念：如果存在至多k个物品的子集R，使得对每个智能体i，可以通过重新分配R中的物品获得对i无嫉妒的分配A^i，则分配A是EFR-k的。

研究背景与动机

问题定义

公平分配是一个在房产分割、任务分配、边界争端和债务分配等现实场景中频繁出现的问题。当参与的智能体具有个人偏好时，"谁得到什么"的问题既具有实际紧迫性又具有理论丰富性。

研究挑战

  1. 混合甘露的复杂性: 与纯粹的商品(goods)或家务(chores)不同，混合甘露中物品的价值符号可能因智能体而异，这使得分配更加复杂。
  2. 公平性与效率的权衡: 在不可分割物品的设置下，传统的无嫉妒性(envy-freeness)不能保证存在，需要寻找合适的放松条件。
  3. 现有方法的局限性:
    • 对于家务分配，即使是四个智能体的情况下，EF1和帕累托最优分配的存在性仍未解决
    • 对于混合甘露，这个问题甚至在三个智能体的情况下仍然开放
    • 现有的基于市场的方法在估值为负时不能直接推广

研究动机

论文旨在通过引入EFR-k概念，为混合甘露的公平高效分配提供理论保证，并开发有效的计算算法。

核心贡献

  1. 理论存在性保证: 证明了对于具有加性估值的n个智能体的混合甘露分配，总是存在EFR-(n-1)且帕累托最优的分配。
  2. 算法可计算性: 当智能体数量n固定时，可以在多项式时间内计算出EFR-(n-1)且帕累托最优的分配。
  3. 独立的EFR结果:
    • EFR-(n-1)的混合甘露分配可以在多项式时间内计算
    • 当所有物品都是商品时，EFR-⌊n/2⌋分配存在且可高效计算
  4. 紧致性结果:
    • 对于家务，(n-1)界是紧的
    • 对于商品，⌊n/2⌋界是紧的
  5. 技术创新: 首次在离散公平分配中应用Knaster-Kuratowski-Mazurkiewicz (KKM)定理。

方法详解

任务定义

输入:

  • n个智能体，记为n = {1,...,n}
  • m个不可分割物品，记为m = {1,...,m}
  • 加性估值函数{vi}i∈n，其中vi(t) ∈ ℝ表示智能体i对物品t的估值

输出: 分配A = (A1,...,An)，其中Ai ⊆ m是分配给智能体i的物品集合

目标: 找到同时满足EFR-k和帕累托最优的分配

核心概念

EFR-k定义

分配A是EFR-k的，当且仅当存在大小至多为k的子集R ⊆ m，使得对每个智能体i，可以通过重新分配R中的物品获得对i无嫉妒的分配A^i。

关键技术组件

  1. 估值扰动: 为了获得非退化条件，对给定估值添加足够小的加性扰动：
    v̄i(t) = vi(t) - εi,t

    其中εi,t从(0,ε)均匀随机抽取。
  2. 权重偏移: 对每个权重向量w ∈ Δn-1，将每个分量偏移参数η > 0：
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. KKM覆盖: 对每个智能体i，定义集合
    Ci := {w ∈ Δn-1 : 存在分配Xi ∈ Oη(w)使得i在Xi下无嫉妒}

主要算法框架

定理3.1的证明思路

  1. 构造扰动估值: 确保非退化性质
  2. 定义KKM覆盖: 构造满足KKM条件的闭集合族{Ci}
  3. 应用KKM定理: 获得交集w* ∈ ∩i Ci
  4. 计数论证: 证明重新分配集合R的大小至多为n-1

算法1: 商品的冲突感知选择序列

对于纯商品情况，设计了基于轮询的算法：

  • 冲突解决阶段: 识别多个智能体最偏好的相同商品，将其加入重新分配集合R
  • 选择阶段: 活跃智能体按字典序选择最偏好的商品

技术创新点

  1. KKM定理的新应用: 首次将经典的KKM定理应用于离散公平分配问题，提供了与现有基于市场的方法完全不同的技术路径。
  2. 扰动技术: 通过精心设计的估值扰动确保非退化性，使得加权社会福利最大化问题具有良好的性质。
  3. 计数论证: 利用二部图的无环性质证明重新分配集合的大小界限。

实验设置

理论分析框架

由于这是一篇理论论文，主要通过数学证明而非实证实验来验证结果。论文采用以下分析框架：

  1. 存在性证明: 使用KKM定理证明EFR-(n-1)和PO分配的存在性
  2. 紧致性分析: 构造反例证明界限的紧致性
  3. 算法复杂性: 分析算法的时间复杂度

复杂性分析

  • 固定智能体数: EFR-(n-1)和PO分配可在m^poly(n)时间内计算
  • 一般情况: EFR-(n-1)分配可在多项式时间内计算
  • 商品情况: EFR-⌊n/2⌋分配可在多项式时间内计算

实验结果

主要理论结果

定理3.1 (主要存在性结果)

每个具有不可分割混合甘露和加性估值的公平分配实例都存在EFR-(n-1)且帕累托最优的分配。

定理4.1 (可计算性结果)

对于固定数量智能体的混合甘露分配实例，可以在多项式时间内计算EFR-(n-1)且帕累托最优的分配。

定理5.1 (EFR独立结果)

对于混合甘露和加性估值的公平分配实例，总存在既是EFR-(n-1)又是EF1的分配，且可在多项式时间内计算。

定理5.4 (商品的改进界限)

对于纯商品的公平分配实例，算法1在多项式时间内计算出EFR-⌊n/2⌋分配。

紧致性结果

定理5.2 (家务的紧致性)

存在家务分配实例不存在EFR-(n-2)分配，证明(n-1)界是紧的。

定理5.5 (商品的紧致性)

存在商品分配实例不存在EFR-(⌊n/2⌋-1)分配，证明⌊n/2⌋界是紧的。

计算复杂性结果

定理A.1 (判定问题的复杂性)

给定分配A和正整数k < n-2，判定A是否为EFR-k是NP完全的。

相关工作

公平分配的经典理论

  • 可分割情况: Varian和Weller的经典结果表明无嫉妒性和PO可以同时实现
  • 不可分割商品: EF1和PO的同时实现已有成熟理论(Nash社会福利最大化)

家务和混合甘露的挑战

  • 家务分配: 即使四个智能体的EF1+PO存在性仍未解决
  • 混合甘露: 三个智能体的EF1+PO存在性仍是开放问题
  • 方法论差异: 不存在类似Nash社会福利的函数保证家务的EF1

相关放松概念

  • EF1: 通过移除一个物品消除嫉妒
  • EFX: 通过移除任意物品消除嫉妒
  • 分数分配: 至多(n-1)个物品分数分配的无嫉妒性

结论与讨论

主要结论

  1. 理论突破: 首次为一般混合甘露设置提供了公平性和效率的同时保证
  2. 技术创新: KKM定理在离散公平分配中的新应用开辟了新的研究方向
  3. 实用价值: 算法结果为实际应用提供了计算基础

局限性

  1. 界限: EFR-(n-1)的界限相对较大，平均每个智能体需要重新分配约2个物品
  2. 固定智能体假设: 多项式时间算法需要智能体数量固定
  3. 加性估值限制: 结果仅适用于加性估值函数

未来方向

  1. 改进界限: 寻找更小的重新分配集合R
  2. 扩展估值类型: 考虑非加性估值函数
  3. 实际应用: 将理论结果应用于具体的分配场景

深度评价

优点

  1. 理论贡献重大: 解决了混合甘露公平高效分配的基本问题
  2. 技术手段新颖: KKM定理的应用展现了深刻的数学洞察
  3. 结果全面: 既有存在性又有算法，既有上界又有下界
  4. 证明严谨: 数学推导完整，技术细节处理得当

不足

  1. 实用性有限: EFR-(n-1)的界限在实际应用中可能过大
  2. 缺乏实证评估: 作为理论论文，缺少在真实数据上的性能评估
  3. 算法效率: 固定智能体数时的m^poly(n)复杂度在实践中可能较高

影响力

  1. 学术影响: 为公平分配理论做出重要贡献，预期被广泛引用
  2. 方法论价值: KKM定理的应用可能启发更多相关研究
  3. 实用前景: 为实际分配系统的设计提供理论基础

适用场景

  1. 遗产分割: 包含资产和债务的复杂分割场景
  2. 任务分配: 同时包含有吸引力和无吸引力任务的分配
  3. 资源管理: 需要同时考虑收益和成本的资源分配问题

参考文献

论文引用了公平分配领域的重要文献，包括：

  • Budish (2011): EF1概念的引入
  • Caragiannis et al. (2019): Nash社会福利与EF1+PO的关系
  • Aziz et al. (2022): 混合甘露的EF1存在性
  • Sandomirskiy & Segal-Halevi (2022): 分数分配的相关结果

总评: 这是一篇高质量的理论论文，通过引入EFR概念和应用KKM定理，为混合甘露的公平高效分配提供了重要的理论保证。尽管在实用性方面存在一定局限，但其理论贡献和技术创新使其成为公平分配领域的重要进展。