Algorithms for Max-Min Share Fair Allocation of Indivisible Chores
Algorithms for Max-Min Share Fair Allocation of Indivisible Chores
复制标题
不可分割家务的最大-最小份额公平分配算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. Walsh
中科院分区：
文献类型：
--
作者：
H. Aziz;Gerhard Rauchecker;G. Schryen;T. Walsh
我们考虑对不可分割的杂务（具有负效用的项目）进行最大-最小份额（MmS）公平分配。我们表明，家务分配和商品（具有正效用的物品）的经典分配具有一些基本联系，但也存在差异，这阻碍了在家务设置中直接应用商品算法，反之亦然。我们证明，对于杂务来说，MmS 分配不需要存在，并且计算 MmS 分配（如果存在）是强 NP 困难的。鉴于这些不存在且复杂的结果，我们提出了一种用于家务的 MmS 公平性的多项式时间 2 近似算法。然后，我们引入了一种新的公平性概念，称为最优 MmS，它代表了保证存在的 MmS 的最佳可能分配。我们使用与并行机器调度的连接来给出（1）用于在代理数量固定时计算最佳 MmS 分配的多项式时间近似方案，以及（2）具有事后最坏情况分析的有效且高效的启发式方法。
We consider Max-min Share (MmS) fair allocations of indivisible chores (items with negative utilities). We show that allocation of chores and classical allocation of goods (items with positive utilities) have some fundamental connections but also differences which prevent a straightforward application of algorithms for goods in the chores setting and vice-versa. We prove that an MmS allocation does not need to exist for chores and computing an MmS allocation - if it exists - is strongly NP-hard. In view of these non-existence and complexity results, we present a polynomial-time 2-approximation algorithm for MmS fairness for chores. We then introduce a new fairness concept called optimal MmS that represents the best possible allocation in terms of MmS that is guaranteed to exist. We use connections to parallel machine scheduling to give (1) a polynomial-time approximation scheme for computing an optimal MmS allocation when the number of agents is fixed and (2) an effective and efficient heuristic with an ex-post worst-case analysis.