论文标题
关于不可分割的家务和混合资源的近似嫉妒
On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
论文作者
论文摘要
我们研究了不可分割的不可分割的项目或琐事的公平分配。尽管对理想的不可分割的物品（或商品）的情况进行了广泛的研究，但许多结果以不同的公平概念而闻名，但对琐事的公平分裂知之甚少。我们研究了嫉妒的杂务，并做出了三项贡献。首先，我们表明，即使在代理具有二进制添加剂估值的情况下，确定无嫉妒分配的存在也是NP的完整。其次，我们提供了一种多项式时间算法，用于计算满足嫉妒性最高可繁琐的分配（EF1），从而纠正了文献中的现有证明。我们算法的直接修改可用于计算双重单调实例的EF1分配（其中，每个代理都可以将一组项目划分为客观商品和客观杂货。我们的第三个结果适用于混合资源模型，该模型由不可分割的项目和可分裂的，不良的异质资源（即坏蛋）组成。我们表明，在这种情况下，总是存在一种分配，可以满足混合资源（EFM）的嫉妒性，并补充了Bei等人的最新结果。 （第2021年，第2021号），用于不可分割的商品和可分割的蛋糕。
We study the fair allocation of undesirable indivisible items, or chores. While the case of desirable indivisible items (or goods) is extensively studied, with many results known for different notions of fairness, less is known about the fair division of chores. We study the envy-free division of chores, and make three contributions. First, we show that determining the existence of an envy-free allocation is NP-complete, even in the simple case when agents have binary additive valuations. Second, we provide a polynomial-time algorithm for computing an allocation that satisfies envy-freeness up to one chore (EF1), correcting an existing proof in the literature. A straightforward modification of our algorithm can be used to compute an EF1 allocation for doubly monotone instances (wherein each agent can partition the set of items into objective goods and objective chores). Our third result applies to a mixed resources model consisting of indivisible items and a divisible, undesirable heterogeneous resource (i.e., a bad cake). We show that there always exists an allocation that satisfies envy-freeness for mixed resources (EFM) in this setting, complementing a recent result of Bei et al. (Art. Int. 2021) for indivisible goods and divisible cake.
