论文标题
不可分割的杂务的公平分配：超越添加成本
Fair Allocation of Indivisible Chores: Beyond Additive Costs
论文作者
论文摘要
我们研究了$ m $不可分割的家务的最大值份额（MMS）公平分配给$ n $ n $ n $的代理商，这些代理人为完成分配的琐事而成本。众所周知，无法保证确切的MMS公平性，到目前为止，添加成本功能的最著名的近似值是Huang和Segal-Halevi [EC，2023]的$ \ frac {13} {11} $。但是，除了添加性之外，知之甚少。在这项工作中，我们首先证明，没有算法可以确保比$ \ min \ {n，\ frac {\ log m} {\ log \ log \ log \ log m} \} $ - 如果成本函数subsodular。该结果还表明，如Barman和Krishnamurthy [TeaC，2020年]和Ghodsi等人所示，与存在恒定近似值的商品的分配形成了鲜明的对比。 [AIJ，2022]。然后，我们证明，对于亚基成本，总是存在$ \ min \ {n，\ lceil \ log m \ rceil \} $ - 近似值的分配，因此近似比渐近地很紧。除了乘法近似外，我们还考虑了序数松弛，即$ d $ mms的1级，这是Hosseini等人最近提出的。 [Jair和Aamas，2022年]。我们的不可能结果意味着，对于任何$ d \ ge 2 $，可能不存在1 $ d $ mms分配。由于这些一般亚收益成本的这些硬度结果，我们转向研究两个特定的亚收益成本，即垃圾箱包装和工作计划。对于这两种设置，我们都表明，对于MMS的乘法和序数松弛，存在恒定的近似分配。
We study the maximin share (MMS) fair allocation of $m$ indivisible chores to $n$ agents who have costs for completing the assigned chores. It is known that exact MMS fairness cannot be guaranteed, and so far the best-known approximation for additive cost functions is $\frac{13}{11}$ by Huang and Segal-Halevi [EC, 2023]; however, beyond additivity, very little is known. In this work, we first prove that no algorithm can ensure better than $\min\{n,\frac{\log m}{\log \log m}\}$-approximation if the cost functions are submodular. This result also shows a sharp contrast with the allocation of goods where constant approximations exist as shown by Barman and Krishnamurthy [TEAC, 2020] and Ghodsi et al. [AIJ, 2022]. We then prove that for subadditive costs, there always exists an allocation that is $\min\{n,\lceil\log m\rceil\}$-approximation, and thus the approximation ratio is asymptotically tight. Besides multiplicative approximation, we also consider the ordinal relaxation, 1-out-of-$d$ MMS, which was recently proposed by Hosseini et al. [JAIR and AAMAS, 2022]. Our impossibility result implies that for any $d\ge 2$, a 1-out-of-$d$ MMS allocation may not exist. Due to these hardness results for general subadditive costs, we turn to studying two specific subadditive costs, namely, bin packing and job scheduling. For both settings, we show that constant approximate allocations exist for both multiplicative and ordinal relaxations of MMS.
