Improving Fairness and Efficiency Guarantees for Allocating 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

Fair division research traditionally focuses on "goods"—items that agents desire. However, many real-world scenarios involve "chores"—tasks that agents wish to avoid. Dividing chores is mathematically more complex than dividing goods because the standard tools, such as competitive equilibrium and potential functions, behave differently when dealing with disutilities. This paper addresses the challenge of finding allocations that are both fair (EF1 or EFX) and efficient (fractional Pareto-optimal, or fPO).

Fairness and Efficiency Criteria

In this work, fairness is defined through envy-based notions:

  • Envy-Free up to one item (EF1): An agent does not envy another after removing at most one chore from their own bundle.
  • Envy-Free up to any item (EFX): A stricter condition where envy vanishes after removing any chore from the agent's bundle.
  • Fractional Pareto-optimality (fPO): An efficiency guarantee ensuring no other allocation (even fractional) can make someone better off without making someone else worse off.

Summary of Contributions

The paper provides several new constructive algorithms and impossibility results, filling critical gaps in the literature. The following table summarizes the state of the art and the specific contributions of this work (highlighted in blue).

Table 1: Summary of existence and non-existence results for EF1/EFX + fPO allocations.

Methodology: Fisher Markets for Chores

The authors leverage the framework of Fisher Markets, where chores are assigned "payments" instead of prices. Agents act as workers seeking to earn a fixed "salary" by performing chores that minimize their "pain-per-buck" (Minimum Pain-per-Buck, or MPB).

A key innovation is the introduction of payment EF1 (pEF1). The authors prove that if an allocation satisfies pEF1 within a competitive market, it is guaranteed to be both EF1 and fPO. This allows the search for fair and efficient allocations to be conducted within the more structured space of market payments.

Key Results

  1. Three-Agent EF1 + fPO: The authors prove that an EF1 + fPO allocation always exists for three agents and can be computed in strongly polynomial time. This settles a significant open question for the three-agent case.
  2. Two-Type Agents: For any number of agents, if there are only two unique disutility functions across the population, an EF1 + fPO allocation is guaranteed to exist.
  3. Bivalued EFX + fPO: In cases where chores have only two possible disutility values (bivalued), the authors show that EFX + fPO exists for three agents.
  4. Impossibility of EFX + fPO: The paper establishes a sharp boundary for EFX. They prove that an EFX + fPO allocation may not exist even for two agents with "2-ary" disutilities (where each agent has two possible costs, but these costs differ between agents).

Discussion and Future Work

While this work makes substantial progress, the general existence of EF1 + fPO for $n > 3$ agents remains an open problem. The complexity of envy relationships in larger groups makes the "big earner" transfer logic difficult to scale. Furthermore, the existence of EFX (without the fPO requirement) for general additive chores remains one of the most prominent unsolved problems in fair division.

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{garg2023improving,
  author = {Jugal Garg and Aniket Murhekar and John Qin},
  title = {{Improving Fairness and Efficiency Guarantees for Allocating Indivisible Chores}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/302},
}
Figure