Fair Allocation of Indivisible Chores

232 concepts123 papers1 proposal

In the study of fair division, researchers have long focused on "goods"—items like jewelry, land, or computing resources that agents desire. However, many real-world problems involve the distribution of "chores," or items with negative utility, such as household tasks, hospital shifts, or social burdens. While it is tempting to assume that chores are simply "negative goods" that can be handled by inverting existing algorithms, Aziz et al. and Ebadian et al. argue that chore allocation is fundamentally more complex, requiring distinct algorithmic frameworks to ensure fairness.

The Inversion Fallacy and Mathematical Asymmetry

The core difficulty in chore allocation stems from a mathematical asymmetry between positive and negative utility. In goods allocation, adding an item to a bundle always increases (or at least maintains) an agent's welfare. This monotonicity allows for well-behaved, convex optimization landscapes.

In contrast, Ray Chaudhury et al. demonstrate that chore markets result in non-convex and potentially disconnected equilibrium landscapes. Standard "interior-point" methods, which work well for goods, fail here because the gradient of the disutility function can increase infinitely as an agent's workload approaches zero. This traps algorithms in unfair local minima. To overcome this, Ray Chaudhury et al. introduced a novel exterior-point method to navigate these jagged landscapes, providing the first approximation schemes for competitive equilibrium in chore markets.

Redefining Fairness for Burdens

Fairness in indivisible allocation is often measured by "Envy-Freeness up to one item" (EF1) or the stricter "Envy-Freeness up to any item" (EFX). The transition from goods to chores changes the very definition of these terms:

  • For Goods: An allocation is EF1 if agent $A$ stops envying agent $B$ after removing one item from $B$’s bundle.
  • For Chores: An allocation is EF1 if agent $A$ stops envying agent $B$ after removing one chore from $A$’s own bundle.

This shift creates significant hurdles. Zhou et al. point out that because adding a high-cost chore causes unpredictable jumps in envy, approximating EFX for chores is much harder than for goods. In fact, Christoforidis et al. recently proved that for general cost functions, an EFX allocation for chores may not even exist, constructing a counterexample with just three agents and six chores.

Finding Tractable Solutions

Despite these theoretical barriers, researchers have identified specific scenarios where fair chore allocation is achievable:

  1. Bivalued Utilities: When agents categorize chores simply as "easy" or "difficult," Ebadian et al. and Murhekar et al. show that it is possible to find allocations that are both fair (EF1) and efficient (Pareto optimal) in polynomial time.
  2. Ordinal Preferences: If we only know how agents rank chores rather than their exact numerical costs, Aziz et al. and Hosseini et al. demonstrate that strategyproof mechanisms—where agents cannot benefit by lying—can achieve strong fairness guarantees through sequential picking sequences.
  3. The Safety Gap in Large Populations: In a surprising result, Manurangsi et al. argue that chores may actually be "easier" than goods in large-scale settings. They identify a "safety gap": because agents with low current costs can accept additional chores without immediately envying others, the number of chores needed to guarantee envy-freeness grows only linearly with the number of agents, whereas goods require a superlinear number of items.

Strategic and Information Hurdles

The problem of chores also extends to how information is handled. Li et al. explored Maximin-Aware (MMA) fairness, which considers agents who are unaware of what others received. They found that while perfect fairness is hard to guarantee when agents have different "obligations" or weights, approximations are possible as the number of agents grows.

Furthermore, Hosseini et al. introduced the concept of "dubious chores"—tasks that seem costly to an observer but are actually effortless for the performer. By leveraging this information asymmetry, they showed that envy-free and efficient allocations can be found even in cases that are traditionally difficult.

As the field of Computational Social Choice matures, the shift from maximizing utility (goods) to minimizing disutility (chores) remains a frontier that requires moving beyond simple symmetry to address the unique geometric and strategic properties of sharing burdens.

Key Foundational Work

Computational Social Choice: Some Current and New Directions (2016) — contributed 3 concept elements to this direction.
Approximation Algorithms for Max-Min Share Allocations of Indivisible Chores and Goods (2016) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 132 papers
  2. Version 1 · 2026-10-04 · 174 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_negative_utility_allocation_bcaaeb5b,
  title = {negative utility allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/negative-utility-allocation/rdr_bcaaeb5b9d774dc48f4b4dbc64858526},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_negative_utility_allocation_bcaaeb5b_v2,
  title = {negative utility allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/negative-utility-allocation/rdr_bcaaeb5b9d774dc48f4b4dbc64858526/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake