Constant-Factor EFX Exists for Chores

We study the problem of fair allocation of chores among agents with additive preferences. In the discrete setting, envy-freeness up to any chore (EFX) has emerged as a compelling fairness criterion. However, establishing its (non-)existence or achieving a meaningful approximation remains a major open question in fair division. The current best guarantee is the existence of O ( n 2 )-EFX allocations, where n denotes the number of agents, obtained through a sophisticated algorithm. In this paper, we show the existence of 4-EFX allocations, providing the first constant-factor approximation of EFX. We further investigate the existence of allocations that are both fair and efficient , using Pareto optimality (PO) as our efficiency criterion. For the special case of bivalued instances, we establish the existence of allocations that are both 3-EFX and PO, thereby improving upon the current best factor of O ( n )-EFX without any efficiency guarantees. For general additive instances, the existence of allocations that are α-EF k and PO has remained open for any constant values of α and k , where EF k denotes envy-freeness up to k chores. We provide the first positive result in this direction by showing the existence of allocations that are 2-EF2 and PO. Our results are obtained via a novel economic framework called earning restricted (ER) competitive equilibrium for fractional allocations, which imposes limits on the earnings of agents from each chore. We show the existence of ER equilibria by carefully formulating a linear complementarity problem (LCP) that captures all ER equilibria, and then prove that the classic complementary pivot algorithm applied to this LCP terminates at an ER equilibrium. By carefully setting earning limits and leveraging the properties of ER equilibria, we design algorithms that involve rounding the fractional solutions and then performing swaps and merges of bundles to meet the desired fairness and efficiency criteria. We expect that the concept of ER equilibrium will play a crucial role in deriving further results on related problems.

Authors

• Jugal Garg
• Aniket Murhekar
• John Qin

Keywords

• EFX
• chores
• earning restricted equilibrium
• fair allocation