2025-11-18T20:31:13.847843

Fair Assignment of Indivisible Chores to Asymmetric Agents

Seddighin, Seddighin
We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (\MMS) context. While constant-\MMS\ allocations/assignments are guaranteed to exist for both goods and chores in the symmetric setting, the situation becomes much more complex when agents have different entitlements. For the allocation of indivisible goods, it has been proven that an $n$-\WMMS\ (weighted \MMS) guarantee is the best one can hope for. For indivisible chores, however, it was recently discovered that an $O(\log n)$-\WMMS\ assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-\WMMS\ guarantee.\footnote{We prove the existence of a 20-\WMMS\ assignment, but we did not attempt to optimize the constant factor. We believe our methods already yield a slightly better bound with a tighter analysis.}
academic

Fair Assignment of Indivisible Chores to Asymmetric Agents

基本信息

  • 论文ID: 2510.10698
  • 标题: Fair Assignment of Indivisible Chores to Asymmetric Agents
  • 作者: Masoud Seddighin, Saeed Seddighin
  • 分类: cs.GT (Computer Science - Game Theory)
  • 发表时间: 2025年10月12日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.10698v1

摘要

本文研究在最大最小份额值(MMS)框架下，将不可分割任务分配给具有不同权利的智能体的公平分配问题。虽然在对称设置下，物品和任务的常数-MMS分配/分派是有保证存在的，但当智能体具有不同权利时，情况变得更加复杂。对于不可分割物品的分配，已被证明n-WMMS(加权MMS)保证是最优的。然而，对于不可分割任务，最近发现O(log n)-WMMS分派保证存在。本文将这一上界改进为常数-WMMS保证，具体证明了20-WMMS分派的存在性。

研究背景与动机

  1. 核心问题: 本文研究的是非对称智能体间不可分割任务的公平分配问题。与经典的"分蛋糕"问题不同，这里处理的是离散的、不可分割的任务(chores)，且智能体具有不同的权利(entitlements)。
  2. 问题重要性:
    • 在现实世界中，不平等权利的情况频繁出现，如各种文化和宗教中的继承法通常规定不平等分配
    • 自然资源(如石油、渔业)的分配通常基于地理、经济或政治考虑
    • 这些实际需求凸显了研究不平等权利下公平分配的重要性
  3. 现有方法局限性:
    • 对称设置下的常数近似保证方法直接适用，但非对称情况更具挑战性
    • 对于物品分配，已证明n-WMMS是最优保证
    • 对于任务分配，之前最好的结果是O(log n)-WMMS保证
  4. 研究动机: 将任务分配的近似比从对数级别改进到常数级别，这在理论上是重大突破。

核心贡献

  1. 主要理论贡献: 证明了非对称任务分配问题存在20-WMMS分派，这是首个常数-WMMS保证
  2. 算法创新: 提出了新颖的分层移动刀算法(Layered Moving Knife Algorithm)，将移动刀方法扩展到非对称设置
  3. 小规模情况优化: 针对n=3和n=4的情况，提供了比log n+1更好的上界
  4. 任务无关分析: 开发了任务无关分析技术，改进了小规模智能体数量下的界限

方法详解

任务定义

输入:

  • N = {a₁, a₂, ..., aₙ}: n个智能体
  • M = {b₁, b₂, ..., bₘ}: m个任务
  • Vᵢ: 智能体aᵢ的加性成本函数
  • wᵢ: 智能体aᵢ的权利，满足∑wᵢ = 1

输出: 任务到智能体的分配，使得每个智能体aᵢ获得的任务包Sᵢ满足Vᵢ(Sᵢ) ≤ α·WMMSᵢ

关键定义:

  • 加权最大最小份额值: WMMSᵢ = min⟨A₁,...,Aₙ⟩∈Π(M) maxⱼ∈N Vᵢ(Aⱼ)·(wᵢ/wⱼ)
  • α-WMMS分派: 所有智能体的成本都不超过其WMMS值的α倍

模型架构

1. 预处理阶段

引理4.1 (排序任务设置归约): 如果在排序任务设置下保证存在α-WMMS分派，则一般情况下也存在α-WMMS分派。

引理4.2 (权利可整除性归约): 如果在权利可整除设置下保证存在α-WMMS分派，则一般情况下存在2α-WMMS分派。

2. 分层移动刀算法

算法维护三个智能体集合:

  • 死亡智能体(D): 已完成分配的智能体
  • 进行中智能体(P): 当前轮次参与分配的智能体
  • 队列智能体(Q): 等待分配的智能体

安全措施:

  • ∑aᵢ∈P wᵢ ≥ ∑aᵢ∈D wᵢ
  • m - s ≥ ∑ᵢ>minp wᵢ/wminp (其中minp是P中最小索引智能体)

核心流程:

  1. 从bₘ到b₁逐个分配任务
  2. 为P中每个智能体aᵢ创建2wᵢ/wminp个副本构成P'
  3. 使用刀区间(ℓ,r)，尽可能扩展区间直到没有智能体的成本≤5wminp
  4. 将区间内所有任务分配给一个满足条件的智能体副本
  5. 当P'为空时，更新D、P、Q集合

技术创新点

  1. 分层结构: 通过维护三层智能体结构，确保算法的安全性和有效性
  2. 副本机制: 为每个智能体创建多个副本，平衡不同权利下的分配
  3. 移动刀扩展: 将经典移动刀方法从对称扩展到非对称设置
  4. 渐进式分配: 通过多轮分配逐步处理所有智能体

实验设置

理论分析设置

本文主要进行理论分析，实验部分集中在:

  1. 小规模情况分析: 针对n=3,4的精确界限分析
  2. 经验验证: 对3≤n≤10的情况，随机采样10亿组权利设置进行验证
  3. 对比基准: 与之前的log n+1上界进行比较

评价指标

  • 近似比: WMMS保证的倍数因子
  • 适用范围: 算法适用的智能体数量范围
  • 理论保证: 最坏情况下的性能保证

实验结果

主要结果

设置之前工作本文结果
一般nlog n+120
n=2(√3+1)/2-
n=3-≈2.1122
n=4-≈2.5404

关键定理

定理4.5: 非对称任务分配问题存在20-WMMS分派。

定理5.4: 对于3个智能体，总是存在约2.1122-WMMS分派。

定理5.5: 对于4个智能体，总是存在约2.5404-WMMS分派。

实验发现

  1. 理论突破: 首次将上界从O(log n)改进到常数
  2. 小规模优化: 对于n≤10的情况，任务无关技术提供了更好的界限
  3. 实际阈值: 常数界限仅在n>2¹⁹=524288时优于对数界限

相关工作

主要研究方向

  1. 经典公平分割: 始于1948年Steinhaus的分蛋糕问题
  2. 不可分割物品分配: 从连续资源转向离散物品的分配
  3. MMS概念: Budish提出的最大最小份额作为公平性度量

本文与相关工作的关系

  • Aziz等4: 首次研究不平等权利下的任务分配
  • Wang等27: 建立了O(log n)-WMMS上界
  • Huang等21: 提供了小规模情况下的具体界限

技术优势

相比现有工作，本文的优势在于:

  1. 首次达到常数近似比
  2. 提供了统一的算法框架
  3. 对小规模情况给出了更精确的分析

结论与讨论

主要结论

  1. 理论贡献: 证明了非对称任务分配存在常数-WMMS保证
  2. 算法创新: 分层移动刀算法有效解决了非对称设置下的技术挑战
  3. 实用价值: 为现实中的不平等权利分配问题提供了理论基础

局限性

  1. 常数因子: 20这个常数相对较大，实际应用中可能不够紧
  2. 适用阈值: 仅在智能体数量极大时优于之前的对数界限
  3. 算法复杂度: 分层结构增加了实现复杂度

未来方向

  1. 常数优化: 通过更精细的分析改进常数因子
  2. 下界研究: 探索问题的理论下界
  3. 算法简化: 寻找更简单的达到常数保证的算法

深度评价

优点

  1. 理论突破: 从对数到常数的改进是重大理论进展
  2. 方法创新: 分层移动刀算法设计巧妙，理论分析严谨
  3. 完整性: 同时处理了一般情况和小规模特殊情况
  4. 写作清晰: 论文结构清晰，证明详细完整

不足

  1. 实用性限制: 常数20相对较大，实际改进有限
  2. 适用范围: 仅在极大规模时有优势
  3. 算法复杂性: 实现相对复杂，可能影响实际应用

影响力

  1. 理论意义: 为公平分配理论做出重要贡献
  2. 方法价值: 分层移动刀技术可能适用于其他问题
  3. 研究推动: 为后续研究提供了新的技术工具

适用场景

  1. 大规模资源分配: 适用于智能体数量极大的场景
  2. 理论研究: 为相关理论研究提供基础
  3. 算法设计: 分层技术可推广到其他分配问题

参考文献

论文引用了该领域的重要工作，包括：

  1. Budish (2011): MMS概念的提出
  2. Aziz et al. (2019): 非对称任务分配的开创性工作
  3. Wang et al. (2024): 之前最好的O(log n)结果
  4. Huang et al. (2023): 小规模情况的界限分析

总体评价: 这是一篇高质量的理论计算机科学论文，在公平分配领域取得了重要的理论突破。虽然实际应用价值有限，但其理论贡献和方法创新为该领域的发展奠定了重要基础。分层移动刀算法的设计体现了作者深厚的理论功底和创新能力。