Fair and Efficient Chore Allocation: Existence and Computation

Aniket Murhekar, Yiguan Lin, Yinghao Li, Yang Gao

TL;DR

While we know how to fairly and efficiently divide "goods" (items people want), doing the same for "chores" (tasks people dislike) remains one of the biggest open problems in discrete fair division. This paper makes a significant breakthrough by providing the first polynomial-time algorithms that guarantee both fairness (EF1) and efficiency (Pareto-optimality) for several important classes of chore allocation problems.

What Problem Does This Paper Address?

In the field of multi-agent systems and social choice, "fair division" explores how to distribute items among agents with different preferences. When items are indivisible (like a single car or a specific shift at work), achieving perfect fairness is often impossible.

Researchers use two main benchmarks:

  1. EF1 (Envy-Freeness up to One item): A relaxation of fairness where an agent doesn't envy another's bundle after "ignoring" at most one item from their own bundle (in the case of chores).
  2. PO (Pareto-Optimality): An efficiency standard where you cannot make one person better off without making someone else worse off.

For goods, it is well-proven that an allocation that is both EF1 and PO always exists. However, chores (items with negative utility/disutility) are mathematically more stubborn. For years, it has been an open question whether an EF1 and PO allocation even exists for chores in the general case, let alone how to compute it efficiently. This paper tackles this "source of hardness" by focusing on structured instances to find a path toward a general solution.

Methods

The author utilizes the Competitive Equilibrium (CE) framework, a concept borrowed from economics.

In this model, chores are assigned "prices" (payments), and agents "earn" money by performing them. The core of the approach involves:

  • Fisher Market Analogy: Agents aim to earn a specific amount of money while minimizing their total disutility.
  • The Selection Rule: Agents are only assigned chores that provide the minimum "disutility-to-payment" ratio. This specific property ensures the allocation is fractionally Pareto-optimal (fPO), a condition even stronger than standard PO.
  • Algorithmic Adjustments: The algorithms start with a CE and then perform "chore transfers" between agents to resolve envy. To keep the system in equilibrium, the algorithm simultaneously performs "payment updates" (raising or dropping the price of chores).
  • Potential Functions: To prove these algorithms actually finish (terminate) in polynomial time, the author uses complex mathematical "potential functions" that track the progress of the allocation toward fairness.

Datasets

As a theoretical contribution to computer science and social choice, this paper does not use empirical datasets. Instead, it provides mathematical proofs of existence and algorithmic complexity. The "evaluation" is the rigorous proof that the proposed algorithms work for any valid input within the specified structured classes.

Key Insights and Ideas

  • Chores $\neq$ Negative Goods: A common misconception is that chores are just "goods with negative values." The paper highlights that the mathematical structures (like Nash Welfare) that guarantee fairness for goods do not behave the same way for chores.
  • The Power of fPO: By maintaining a Competitive Equilibrium, the algorithm stays within a "safe" space of efficiency (fPO). This allows the researcher to focus on fixing fairness (EF1) without worrying that the allocation will become inefficient.
  • Structure as a Stepping Stone: By solving the problem for "bivalued" instances (where chores only have two possible cost levels) or for a small number of agents ($n=3$), the author reveals the specific mechanics required to eventually solve the general $n$-agent problem.

Key Results

The paper presents the first non-trivial positive results for the chore allocation problem, proving that an EF1 and PO allocation can be computed in polynomial time for:

  1. Bivalued instances: Where every agent's disutility for any chore is one of two values $\{a, b\}$.
  2. Three-agent instances: Any instance involving exactly three agents, regardless of their preferences.
  3. Three types of agents: Instances where many agents exist, but they fall into only three distinct preference profiles.
  4. Two types of chores: Instances where there are only two categories of tasks.

Limitations and Future Work

Despite these breakthroughs, the "Main Question" remains: Does an EF1 and PO allocation exist for all chore instances?

The author points out several hurdles:

  • Scaling to $n=4$: The algorithm for three agents relies on a specific property (one agent only "loses" chores during the process) that is not yet proven to hold for four or more agents.
  • General Preferences: Moving beyond bivalued or "2-ary" instances to completely arbitrary disutility values is the ultimate goal.
  • Weighted Agents: The current work assumes all agents are equal. Future research needs to address "asymmetric" agents who might have different entitlements (e.g., one person is contracted to do more work than another).

Summary updated

BibTeX
@inproceedings{murhekar2024fair,
  author = {Aniket Murhekar and Yiguan Lin and Yinghao Li and Yang Gao},
  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