New Algorithms for the Fair and Efficient Allocation of Indivisible Chores

Jugal Garg, Aniket Murhekar, John Qin

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.

Introduction

In algorithmic game theory, "fair division" traditionally focuses on allocating goods. However, many real-world scenarios involve "chores"—tasks with negative utility, such as household work or waste disposal. The goal is to find an allocation that is both fair and efficient. Fairness is often defined by Envy-Free up to one item (EF1) or the stricter Envy-Free up to any item (EFX). Efficiency is defined by fractional Pareto-optimality (fPO), ensuring no reallocation can improve one agent's utility without harming another's.

While maximizing Nash Welfare often solves this for goods, chores lack an equivalent global welfare function, making the simultaneous achievement of fairness and efficiency a difficult open problem. This paper addresses this "Nash Welfare vacuum" by providing the first constructive, polynomial-time algorithms for several key chore allocation scenarios.

Methodology

The authors utilize the Fisher Market framework, where agents "earn" a salary by performing chores. Key techniques include:

  • Competitive Equilibrium (CE): Maintaining a state where agents perform chores with the "minimum pain per buck" (MPB), which guarantees fPO.
  • Payment Envy-Freeness (pEF1): A new strengthening of EF1 based on payments. By adjusting chore payments and transferring chores in equilibrium, the system is driven toward a fair state.
  • Round-Robin Procedures: Used for "two-type" agent scenarios (where agents fall into one of two preference groups) to maintain fairness within groups.
  • Chore Balancing: For bivalued chores (where every chore costs either $a$ or $b$), algorithms focus on balancing the chore count to achieve EFX.

Key Results

The paper's contributions significantly expand the known boundaries of fair and efficient chore allocation. The authors provide strongly polynomial-time algorithms for EF1+fPO in cases of 3 agents or two-type preference functions, and EFX+fPO for 3 agents with bivalued disutilities.

Summary of existence and non-existence results for fair and efficient allocations. Blue cells indicate the contributions of this work.

A critical insight is the "non-existence wall": the paper proves that EFX and fPO can be mutually exclusive. They provide a counterexample with two agents and "2-ary" disutilities where no allocation can satisfy both properties, setting a clear boundary on what is mathematically possible.

Conclusion and Future Work

While this work successfully addresses the 3-agent case and specific preference structures, the existence of EF1+fPO for a general number of agents ($n > 3$) remains a major open problem. Future research may also explore extending EFX+fPO to more general preference structures beyond bivalued instances, or identifying further cases where such allocations are impossible.

Summary updated

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.
BibTeX
@inproceedings{garg2023new,
  author = {Jugal Garg and Aniket Murhekar and John Qin},
  title = {{New Algorithms for the Fair and Efficient Allocation of Indivisible Chores}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/302},
}
Figure