Tractable Graph Structures in EFX Orientation

doi:10.1007/978-3-032-03639-1_10

Tractable Graph Structures in EFX Orientation

2026-01-01

0

PRE

AI

DOI：10.1007/978-3-032-03639-1_10

原文链接

原文求助

摘要

En 中文

自从引入以来，对任何物品的公平分配（EFX）已成为不可分物品公平分配领域的一个基本解决方案概念。然而，其存在性仍然难以捉摸——即使对于四个代理和加性效用函数的情况，EFX分配是否总是存在仍未知。毫不奇怪，研究人员已探索受限设置以区分可处理和不可处理的情况。Christadolou、Fiat等人[EC'23]引入了EFX方向的定义，其中代理构成图的顶点，物品对应边，且代理只对其关联的物品估价。目标是将物品分配给相邻的代理之一，同时满足EFX条件。这种基于图的设置已受到广泛关注，并催生了大量研究成果。基于Zeng和Mehta'24的工作，该工作基于底层图的结构建立了清晰的复杂度阈值——对于二分图可在多项式时间内求解，而对于色数至少为三的图则为NP难问题——我们进一步利用参数化图算法探索EFX方向的算法景观。具体而言，我们证明二分性是可处理性的一个惊人严格条件：即使估价是对称的、二元的，且图最多通过两次边移除即可变为二分图，EFX方向问题仍然是NP完全的。此外，引入单个非二元值会使问题变为NP难，即使图仅需一次边移除即可变为二分图。我们进一步进行参数化分析，考察使问题可处理的底层图结构。特别地，我们证明在树宽受常数限制的图上，问题可在线性时间内求解。此外，我们还证明实例的复杂性与图中单值边上的无环连通分量大小密切相关。

Keyword:

ASSIGNMENT

Tractable Graph Structures in EFX Orientation

摘要

期刊

机构

引用论文