论文标题
公平有效分配不可分割的琐事的新算法
New Algorithms for the Fair and Efficient Allocation of Indivisible Chores
论文作者
论文摘要
我们研究了具有添加剂功能功能的代理商中公平有效地分配不可分割的家务的问题。我们考虑了EF1和EFX的广泛基于嫉妒的公平特性，以及分数帕累托（FPO）的效率。同时ef1/efx和FPO的分配的存在（和计算）都在挑战开放问题，我们在这两个方面都取得了进展。我们表明存在分配的存在 -EF1+FPO，当有三个代理时， -EF1+fpo，当最多有两个脱离功能时， -EFX+FPO，适用于三个无数偶然的药物。这些结果是基于强烈多项式时间算法的建设性。我们还研究了不存在的，并表明即使对于两种代理，也不必存在EFX+FPO的分配。
We study the problem of fairly and efficiently allocating indivisible chores among agents with additive disutility functions. We consider the widely-used envy-based fairness properties of EF1 and EFX, in conjunction with the efficiency property of fractional Pareto-optimality (fPO). Existence (and computation) of an allocation that is simultaneously EF1/EFX and fPO are challenging open problems, and we make progress on both of them. We show existence of an allocation that is - EF1+fPO, when there are three agents, - EF1+fPO, when there are at most two disutility functions, - EFX+fPO, for three agents with bivalued disutilities. These results are constructive, based on strongly polynomial-time algorithms. We also investigate non-existence and show that an allocation that is EFX+fPO need not exist, even for two agents.
