Fair and Efficient Chore Allocation: Existence and Computation

Aniket Murhekar

Introduction

In the field of discrete fair division, the goal is to distribute a set of indivisible items among agents as equitably and efficiently as possible. While the allocation of "goods" (items with positive utility, such as jewelry or assets) is well-understood, the allocation of "chores" (items with negative utility, such as undesirable work shifts or household tasks) remains a significant challenge in social choice theory. This paper addresses the "existence and computation" gap for chores, providing the first non-trivial polynomial-time algorithms that guarantee both fairness and efficiency.

The Challenge of Negative Utility

The gold standard for a desirable allocation involves two properties:

  1. Envy-Free up to One item (EF1): No agent should envy another agent's bundle after "ignoring" one chore from their own set.
  2. Pareto-Optimal (PO): There is no alternative allocation that makes at least one agent better off without making another worse off.

For goods, maximizing the Nash Welfare (the product of utilities) automatically satisfies both EF1 and PO. However, for chores, no such universal welfare function has been identified. The mathematical asymmetry between goods and chores means that techniques used for positive utilities often fail when applied to costs. Consequently, whether an EF1 and PO allocation always exists for chores in the general case is currently a major open problem.

Methodology: The Competitive Equilibrium Framework

The researcher utilizes the Competitive Equilibrium (CE) framework to navigate the search space for fair allocations. In this economic model, agents "earn" a fictitious currency by performing chores. Each chore is assigned a price (payment), and agents only accept chores that offer them the best "disutility-to-payment" ratio.

The algorithm maintains the system in a state of Competitive Equilibrium to "lock in" efficiency. Because any CE allocation is fractionally Pareto-optimal (fPO)—a condition even stronger than standard PO—the algorithm can focus on reaching fairness (EF1) without risking the loss of Pareto-optimality. To achieve this, the algorithm performs:

  • Discrete Chore Transfers: Moving chores between agents to reduce envy.
  • Payment Updates: Simultaneously adjusting the prices of chores to maintain the equilibrium state during transfers.

Key Results and Insights

The paper proves that an EF1 and PO allocation not only exists but can be computed in polynomial time for several structured scenarios:

  • Bivalued Instances: Cases where every agent values every chore at one of only two possible cost levels (e.g., cost $a$ or cost $b$).
  • Small Agent Count ($n=3$): Instances involving exactly three agents, regardless of the complexity of their individual preferences.
  • Limited Agent/Chore Types: Instances where there are only three distinct types of agent preference profiles or only two distinct types of chores.

These results represent the first significant progress toward solving the general existence question. The work highlights that the difficulty in chore allocation stems from the specific structure of preferences rather than just the number of items.

Limitations and Future Directions

Despite these breakthroughs, the general case for $n \ge 4$ agents remains unsolved. The current algorithm for three agents relies on a property where at least one agent "only loses chores" throughout the process; it is currently unknown if this property holds for larger groups.

Future research will likely explore "2-ary" preferences (where each agent has their own specific pair of costs) and "weighted" EF1, where agents have different entitlements or shares of the total chore burden. These areas represent the next frontier in achieving universal fairness and efficiency in chore division.

Summary updated

Abstract

We investigate the existence and computation of fair and efficient allocations of indivisible chores to agents with additive preferences. We consider the popular envy-based fairness notions of envy-freeness up to one chore (EF1) and the efficiency notion of Pareto-optimality (PO). The existence of an allocation of chores that is simultaneously EF1 and PO is regarded a major open problem in discrete fair division. We show that an EF1 and PO allocation can be computed in polynomial time for certain structured instances. These results comprise the first non-trivial positive results for the problem and reveal insights towards settling the problem in its full generality.
BibTeX
@inproceedings{murhekar2024fair,
  author = {Aniket Murhekar},
  title = {{Fair and Efficient Chore Allocation: Existence and Computation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=n0aEB8NxNX},
}
Figure