公平分配不可分割的物品和杂务的组合 (Fair allocation of combinations of indivisible goods and chores)

from arxiv, This article is a complete version of a conference paper, which appeared in IJCAI 2019. The conference version contains an error in the proof of Theorem 2 regarding EF1 existence for arbitrary utility functions

We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are `goods' i.e., they yield positive utility for the agents. There is also some work where the items are `chores' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.

翻译：我们考虑的是公平划分一组物品的问题。许多公平分工文献认为,物品是`货物',即对代理人有积极效用。还有一些工作是,物品是`工作',对代理人有消极效用。在本文件中,我们考虑的是代理人对每一物品可能有消极或正面效用的比较一般的设想,例如,公平任务分配,代理人可以对每项任务有正面和负面的效用。我们表明,虽然一些积极的不言而喻和计算结果延伸到这一更为普遍的背景,但另一些则没有。我们提出了几项新的和有效率的算法,以便在这一总体背景中找到公平的分配。我们还指出了文献中存在的一些差距,即分配是否符合某些公平和效率特性,并进一步研究了这种分配的复杂程度。