New Algorithms for the Fair and Efficient Allocation of Indivisible Chores

Abstract

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.

43 pages. Accepted to IJCAI 2023. This version corrects a typo in Theorem 2

References in corpus (4)

• Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods
• Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions
• Fair Allocation of Two Types of Chores
• EFX Allocations: Simplifications and Improvements

Cited by in corpus (1)

• Mixed Fair Division: A Survey