We study the problem of allocating indivisible chores among agents with additive cost functions in a fair and efficient manner. A major open question in this area is whether there always exists an allocation that is envy-free up to one chore (EF1) and Pareto optimal (PO). Our main contribution is to provide a positive answer to this question by proving the existence of such an allocation for indivisible chores under additive cost functions. This is achieved by a novel combination of a fixed point argument and a discrete algorithm, providing a significant methodological advance in this area. Our additional key contributions are as follows. We show that there always exists an allocation that is EF1 and fractional Pareto optimal (fPO), where fPO is a stronger efficiency concept than PO. We also show that an EF1 and PO allocation can be computed in polynomial time when the number of agents is constant. Finally, we extend all of these results to the more general setting of weighted EF1 (wEF1), which accounts for the entitlements of agents.

翻译：我们研究了在具有可加成本函数的智能体之间公平且高效地分配不可分割杂务的问题。该领域一个主要的开放性问题在于：是否存在一种分配方案，既能满足至多一个杂务的无嫉妒性（EF1），又能实现帕累托最优（PO）。我们的主要贡献是通过证明在可加成本函数下，不可分割杂务的此类分配方案确实存在，从而对该问题给出了肯定的回答。这一结论是通过结合不动点论证与离散算法的新颖方法实现的，为该领域提供了重要的方法论进展。我们的其他关键贡献如下：我们证明了始终存在一种分配方案，既满足EF1又满足分数帕累托最优（fPO），其中fPO是比PO更强的效率概念。我们还证明了当智能体数量为常数时，EF1且PO的分配方案可在多项式时间内计算得出。最后，我们将所有这些结果推广到更一般的加权EF1（wEF1）设定中，该设定考虑了智能体的权益权重。