We study the problem of allocating a set of indivisible chores to three agents, among whom two have additive cost functions, in a fair manner. Two fairness notions under consideration are envy-freeness up to any chore (EFX) and a relaxed notion, namely envy-freeness up to transferring any chore (tEFX). In contrast to the case of goods, the case of chores remain relatively unexplored. In particular, our results constructively prove the existence of a tEFX allocation for three agents if two of them have additive cost functions and the ratio of their highest and lowest costs is bounded by two. In addition, if those two cost functions have identical ordering (IDO) on the costs of chores, then an EFX allocation exists even if the condition on the ratio bound is slightly relaxed. Throughout our entire framework, the third agent is unrestricted besides having a monotone cost function.
翻译:我们研究如何以公平的方式将一套不可分割的杂务分配给三个代理商,其中两个代理商具有累加成本功能;审议的两个公平概念是:不嫉妒,直到任何工作(EFX)和放松的概念,即不嫉妒,直到转移任何工作(tEFX);与货物的情况相反,杂务的情况仍然相对没有探讨;特别是,我们的结果建设性地证明,如果其中两个代理商具有累加成本功能,而其最高和最低成本的比例受两个约束,则三个代理商拥有tEFX的分配;此外,如果这两种成本功能对工作成本有相同的订单(IDO),那么即使受约束的比例条件略有放宽,EFX的分配也是存在的;在整个框架范围内,第三种代理商除了具有单一成本功能之外,是不受限制的。