2025-11-13T10:19:14.372822

Polynomial-Time Algorithms for Fair Orientations of Chores

Hsu, King
This paper addresses the problem of finding fair orientations of graphs of chores, in which each vertex corresponds to an agent, each edge corresponds to a chore, and a chore has zero marginal utility to an agent if its corresponding edge is not incident to the vertex corresponding to the agent. Recently, Zhou et al. (IJCAI, 2024) analyzed the complexity of deciding whether graphs containing a mixture of goods and chores have EFX orientations, and conjectured that deciding whether graphs containing only chores have EFX orientations is NP-complete. We resolve this conjecture by giving polynomial-time algorithms that find EF1 and EFX orientations of graphs containing only chores if they exist, even if there are self-loops. Remarkably, our result demonstrates a surprising separation between the case of goods and the case of chores, because deciding whether graphs containing only goods have EFX orientations was shown to be NP-complete by Christodoulou et al. (EC, 2023). In addition, we show the EF1 and EFX orientation problems for multigraphs to be NP-complete.
academic

Polynomial-Time Algorithms for Fair Orientations of Chores

基本信息

  • 论文ID: 2501.13481
  • 标题: Polynomial-Time Algorithms for Fair Orientations of Chores
  • 作者: Kevin Hsu, Valerie King (University of Victoria)
  • 分类: cs.GT (Game Theory), cs.AI (Artificial Intelligence), cs.DM (Discrete Mathematics)
  • 发表时间: arXiv预印本，2025年1月
  • 论文链接: https://arxiv.org/abs/2501.13481

摘要

本文研究图上chore（负效用任务）的公平分配问题，其中每个顶点代表一个智能体，每条边代表一个chore。当边与顶点不相邻时，该chore对相应智能体的边际效用为零。Zhou等人（IJCAI 2024）猜想纯chore图的EFX orientation判定问题是NP完全的。本文通过给出多项式时间算法解决了这一猜想，能够找到纯chore图的EF1和EFX orientation（如果存在）。值得注意的是，这与纯goods图的EFX orientation判定问题是NP完全的形成鲜明对比，展现了goods和chores之间的惊人分离。同时证明了多重图上的EF1和EFX orientation问题是NP完全的。

研究背景与动机

问题定义

本文研究的核心问题是图上chore的公平分配：

  1. 图模型：图G中每个顶点对应一个智能体，每条边对应一个chore
  2. 效用约束：当边e不与顶点i相邻时，e对i的边际效用为0
  3. 分配目标：找到满足公平性条件（EF1或EFX）的orientation

研究重要性

  1. 实际应用：模拟多种现实场景，如员工办公室分配、教室调度、离婚财产分割等
  2. 理论价值：公平分配被称为"公平分配中最神秘的问题"
  3. 复杂性理论：揭示goods和chores在计算复杂性上的根本差异

现有方法局限性

  1. EFX存在性：一般情况下EFX分配的存在性仍是开放问题
  2. 图限制：已有结果主要针对goods，chores的研究相对缺乏
  3. 复杂性差异：Zhou等人猜想chores情况下的复杂性与goods相同

研究动机

  1. 解决重要猜想：直接回应Zhou等人的NP完全性猜想
  2. 揭示本质差异：探索goods和chores在计算复杂性上的分离
  3. 算法设计：提供实用的多项式时间算法

核心贡献

  1. 解决重要猜想：证明了Zhou等人关于chore图EFX0 orientation的NP完全性猜想是错误的，给出了O(|V(G)|⁴)时间的多项式算法
  2. EF1算法：提供了O(|V(G)|²)时间的EF1 orientation判定和构造算法
  3. 复杂性分离：首次证明了goods和chores在EFX orientation问题上的计算复杂性分离
  4. 多重图硬度：证明了多重图上EF1和EFX orientation问题的NP完全性
  5. 理论框架：建立了从EFX0-ORIENTATION到2SAT的完整归约链

方法详解

任务定义

输入：图G=(V(G), E(G))和效用函数集合u 输出：满足EF1或EFX0条件的orientation，或判定不存在 约束：

  • 效用函数单调递减：ui(S) ≤ ui(T) when T ⊆ S
  • 边际效用约束：不相邻边的效用为0

核心定义

EF1定义：分配π是EF1的，当且仅当对每对智能体i≠j，存在边e∈πi使得ui(πi{e}) ≥ ui(πj)

EFX0定义：分配π是EFX0的，当且仅当没有智能体强烈嫉妒另一个智能体

算法架构

本文提出了三层嵌套的算法架构：

EFX0-ORIENTATION → EFX0-ORIENTATION-OBJECTIVE → PD-VERTEX-COVER → 2SAT

1. EF1 Orientation算法

核心洞察（命题1）：图G的orientation π是EF1的当且仅当每个顶点i最多接收一条对其有负效用的边。

算法流程：

  1. 使用命题2将所有零效用边转化为负效用边
  2. 检查每个连通分量K是否满足|E(K)| ≤ |V(K)|
  3. 如果满足，使用观察3构造入度至多为1的orientation
  4. 时间复杂度：O(|V(G)|²)

2. EFX0 Orientation算法

FINDEFXORIENTATION (Algorithm 3)：

  • 输入：EFX0-ORIENTATION实例(G,u)
  • 输出：EFX0 orientation或false

关键步骤：

  1. 边细分：将非客观边eij替换为新顶点k和两条新边eik, ejk
  2. 客观实例构造：转化为EFX0-ORIENTATION-OBJECTIVE实例
  3. 调用子算法：使用FINDEFXORIENTOBJ求解

FINDEFXORIENTOBJ (Algorithm 2)：

  • 核心洞察（命题5）：客观实例的orientation是EFX0的当且仅当每个顶点要么接收唯一一条边，要么接收的所有边都是dummy边

算法流程：

  1. 找到所有负连通分量K
  2. 检查每个K是否包含≤|V(K)|条负边
  3. 构造PD-VERTEX-COVER实例(H,P,D)
  4. 调用FINDPDVERTEXCOVER求解

FINDPDVERTEXCOVER (Algorithm 1)：

  • 归约目标：将PD-VERTEX-COVER归约到2SAT
  • 构造方式：
    • 变量：每个顶点i对应布尔变量xi
    • 约束：三种类型的子句确保顶点覆盖和约束条件

技术创新点

  1. 复杂性分离发现：首次证明goods和chores的本质差异
  2. 多层归约设计：巧妙的三层嵌套归约结构
  3. 图论洞察：将公平性条件转化为纯图论性质
  4. 边细分技术：通过边细分统一处理客观和非客观边

实验设置

理论分析框架

本文主要是理论工作，通过数学证明验证算法的正确性和复杂度：

  1. 正确性证明：每个算法都有完整的正确性证明
  2. 复杂度分析：详细的时间复杂度分析
  3. 归约验证：证明各层归约的等价性

复杂性对比

  • EF1 orientation：O(|V(G)|²) vs 之前无已知算法
  • EFX0 orientation：O(|V(G)|⁴) vs Zhou等人猜想的NP完全
  • 多重图：证明NP完全性，与简单图形成对比

实验结果

主要理论结果

  1. 定理9：存在O(|V(G)|⁴)时间算法判定chore图是否有EFX0 orientation并构造
  2. 命题1：EF1 orientation的图论刻画
  3. 命题5：客观实例EFX0 orientation的图论刻画
  4. 定理10：多重图EF1/EFX0 orientation的NP完全性
  5. 定理12：无自环多重图EF1 orientation的NP完全性

复杂性分离证明

goods vs chores对比：

  • Goods：EFX orientation判定是NP完全的（Christodoulou等，EC 2023）
  • Chores：EFX0 orientation判定是多项式时间可解的（本文）

简单图 vs 多重图对比：

  • 简单图：EF1和EFX0都是多项式时间可解
  • 多重图：EF1和EFX0都是NP完全的

算法效率分析

  1. EF1算法：O(|V(G)|²)，主要开销在BFS和orientation构造
  2. EFX0算法：O(|V(G)|⁴)，瓶颈在边细分后的图规模
  3. 2SAT求解：利用Aspvall等人的线性时间算法

相关工作

公平分配理论

  1. EFX存在性：Procaccia称为"最神秘问题"
  2. 限制性结果：相同效用函数、字典序偏好、3个智能体等特殊情况
  3. 图实例：Christodoulou等人引入的图模型

复杂性理论

  1. goods情况：EFX orientation的NP完全性
  2. 混合情况：Zhou等人的混合goods/chores结果
  3. 多重图：各种正面和负面结果

算法设计

  1. 归约技术：从图问题到SAT的归约
  2. 图论工具：顶点覆盖、连通性分析
  3. orientation算法：基于BFS的构造方法

结论与讨论

主要结论

  1. 猜想否定：Zhou等人的NP完全性猜想是错误的
  2. 算法贡献：提供了实用的多项式时间算法
  3. 理论洞察：揭示了goods和chores的本质差异
  4. 完整图景：给出了简单图上chore分配问题的完整复杂性刻画

局限性

  1. 多重图硬度：多重图情况仍然是NP完全的
  2. 常数因子：O(|V(G)|⁴)的复杂度可能在实践中较高
  3. 效用函数限制：需要满足单调性假设
  4. 自环处理：虽然支持自环，但增加了算法复杂性

未来方向

  1. 算法优化：降低EFX0算法的时间复杂度
  2. 多重图算法：寻找多重图的特殊可解情况
  3. 近似算法：当精确算法不可行时的近似方案
  4. 实际应用：将理论结果应用到实际分配场景

深度评价

优点

  1. 理论突破：
    • 解决了重要的开放问题和猜想
    • 发现了goods和chores之间的根本性差异
    • 提供了完整的复杂性刻画
  2. 技术创新：
    • 巧妙的多层归约设计
    • 将公平性条件转化为纯图论性质
    • 边细分技术的创新应用
  3. 算法质量：
    • 提供了实际可用的多项式时间算法
    • 算法具有良好的理论保证
    • 复杂度分析详细准确
  4. 写作质量：
    • 论文结构清晰，逻辑严密
    • 证明完整详细
    • 相关工作梳理全面

不足

  1. 实践效率：
    • O(|V(G)|⁴)的复杂度在大规模图上可能较慢
    • 缺乏实际运行时间的实验验证
  2. 适用范围：
    • 多重图情况仍然困难
    • 效用函数需要满足特定假设
    • 未考虑在线或动态场景
  3. 算法常数：
    • 理论复杂度分析未考虑常数因子
    • 实际实现可能存在较大开销

影响力

  1. 理论贡献：
    • 为公平分配理论提供了重要洞察
    • 推动了计算复杂性理论的发展
    • 为后续研究奠定了基础
  2. 实用价值：
    • 算法可应用于实际的任务分配问题
    • 为系统设计提供了理论指导
    • 有助于公平性机制的设计
  3. 可复现性：
    • 算法描述详细清晰
    • 理论证明完整
    • 易于实现和验证

适用场景

  1. 任务分配：食品配送、清洁任务等负效用工作的分配
  2. 资源调度：在约束条件下的公平调度问题
  3. 机制设计：需要考虑公平性的自动化系统
  4. 理论研究：作为其他公平分配问题的基础工具

参考文献

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

  • Zhou et al. (IJCAI 2024)：混合goods/chores的EFX分配
  • Christodoulou et al. (EC 2023)：goods图的EFX orientation复杂性
  • Procaccia (2020)：EFX问题的重要性评述
  • 以及计算复杂性理论的经典结果

总体评价：这是一篇高质量的理论计算机科学论文，解决了重要的开放问题，提供了有价值的算法和理论洞察。论文的主要贡献在于揭示了goods和chores在计算复杂性上的根本差异，并提供了实用的多项式时间算法。虽然在实践效率和适用范围上还有改进空间，但其理论价值和学术影响力是显著的。