论文标题
不可分割的杂务的公平分配
Equitable Allocations of Indivisible Chores
论文作者
论文摘要
我们研究具有附加估值的代理商中不可分割的杂务（即具有非阳性价值的项目）的公平分配。如果分配是公平的，则认为分配是公平的，这意味着代理人的分配是（大约）相等的。我们的主要理论贡献是表明，始终存在一个同时公平的分配，该分配是公平的（EQ1）和Pareto Optimal（PO），并提供用于计算此类分配的伪综合时间算法。此外，我们观察到词汇溶液 - 已知可以满足商品环境中近似公平性的强烈形式---甚至无法满足杂务的EQ1。但是，它确实满足了一个新颖的公平概念，我们将公平性称为任何重复的琐事。我们从Spliddit网站获得的合成以及现实世界数据的实验表明，与当前在SplidDit上部署的算法相比，我们工作中考虑的算法近似公平和效率的频率要高得多。
We study fair allocation of indivisible chores (i.e., items with non-positive value) among agents with additive valuations. An allocation is deemed fair if it is (approximately) equitable, which means that the disutilities of the agents are (approximately) equal. Our main theoretical contribution is to show that there always exists an allocation that is simultaneously equitable up to one chore (EQ1) and Pareto optimal (PO), and to provide a pseudopolynomial-time algorithm for computing such an allocation. In addition, we observe that the Leximin solution---which is known to satisfy a strong form of approximate equitability in the goods setting---fails to satisfy even EQ1 for chores. It does, however, satisfy a novel fairness notion that we call equitability up to any duplicated chore. Our experiments on synthetic as well as real-world data obtained from the Spliddit website reveal that the algorithms considered in our work satisfy approximate fairness and efficiency properties significantly more often than the algorithm currently deployed on Spliddit.
