On the Pursuit of EFX for Chores: Non-existence and Approximations

Vasilis Christoforidis, Christodoulos SantorinaiosIJCAI 2024

Introduction

Fair division is a cornerstone of computational social choice, seeking equitable ways to distribute resources among agents. While the division of "goods" (items with positive utility) has been extensively studied, the division of "chores" (items with negative utility or cost) presents unique challenges. The gold standard for fairness in indivisible item allocation is Envy-Freeness up to any item (EFX). For chores, an allocation is EFX if no agent envies another after removing any single chore from the envier's own bundle.

Despite its importance, the existence of EFX allocations for chores remained one of the most enigmatic open questions in the field. This paper provides a definitive answer, proving that EFX allocations do not always exist for chores under general cost functions and exploring the boundaries of existence and approximation.

The Non-Existence of EFX

The primary contribution of this work is the construction of a counterexample demonstrating that EFX allocations can be non-existent. Specifically, the authors identify an instance involving three agents and six chores where no EFX allocation is possible. This result hinges on the use of superadditive cost functions, where the cost of performing a set of chores together exceeds the sum of their individual costs—a realistic model for tasks that induce cumulative fatigue or require complex scheduling.

Cost function construction for a 3-agent, 6-chore instance where EFX fails.

Beyond mere non-existence, the paper shows that the approximation ratio for EFX can be unbounded. In certain scenarios, the "gap" between a feasible allocation and one that satisfies the EFX criteria can grow infinitely large, highlighting a fundamental divergence between the fair division of goods and chores.

Complexity and Algorithmic Bounds

The paper further investigates the computational difficulty of finding EFX allocations. By reducing from the Partition Problem, the authors prove that deciding whether an EFX allocation exists for a given instance is NP-complete.

However, the research also identifies "safe zones" where existence is guaranteed. A key finding is the $n+2$ threshold: if the number of chores $m$ is at most the number of agents $n$ plus two ($m \leq n+2$), an EFX allocation is guaranteed to exist for any monotone cost function.

General cost matrix structure used in establishing existence and hardness bounds.

For the specific case of three agents with additive costs, the authors improve the state-of-the-art approximation. By adapting the Top Trading Envy Cycle Elimination (TTECE) algorithm, they reduced the best-known approximation ratio from approximately 4.45 down to 2.

Key Insights

  • Separation of Goods and Chores: This work establishes the first formal proof that EFX for chores is fundamentally harder to guarantee than EFX for goods, particularly for three agents.
  • The Role of Superadditivity: The failure of EFX is closely tied to superadditive preferences, which model synergies and cumulative costs in task allocation.
  • Existence Thresholds: The $m \leq n+2$ result provides a practical bound for small-scale chore division problems.

Conclusion and Future Directions

While this paper settles the question for general cost functions, the "additive case" remains a significant open mystery. It is still unknown whether EFX allocations always exist when agents have purely additive disutilities. Future work will likely focus on closing this gap and investigating whether similar non-existence results can be extended to the goods setting, potentially resolving the other half of fair division's most famous open problem.

Summary updated

BibTeX
@inproceedings{christoforidis2024pursuit,
  author = {Vasilis Christoforidis and Christodoulos Santorinaios},
  title = {{On the Pursuit of EFX for Chores: Non-existence and Approximations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure