In the classic "fair division" problem, we usually imagine a set of desirable items—like jewelry or cake—that must be split among agents with different preferences. But in the real world, we often need to divide "chores": undesirable tasks like cleaning, debt, or pollution quotas.
While these problems might seem like opposites, a growing body of research shows they are actually two sides of the same mathematical coin. By establishing formal dualities and symmetries, researchers have found that the algorithms we use to share wealth can be mirrored to fairly distribute burdens.
The Exemption Trick: Turning Chores into Goods
The most intuitive way to bridge the gap between goods and chores is to reframe the absence of a chore as a benefit. This "chore-good duality" was formalized by Yotam Gafni, Xin Huang, and Ron Lavi in Unified Fair Allocation of Goods and Chores via Copies.
Imagine a group of roommates who must complete 10 cleaning tasks. Instead of allocating the tasks directly, we can think of each roommate as having a "capacity" to do all 10 tasks. If a roommate is assigned only 2 tasks, they have effectively received 8 "exemptions." These exemptions act exactly like goods: the more you have, the happier you are.
By treating the total capacity minus the assigned chores as a set of desirable "copies," Gafni et al. proved that fairness guarantees for goods (like $EFX$, or Envy-Free up to Any item) can be translated directly into the chores domain.
Valuation Negation and Symmetry
A second approach to this duality is valuation negation symmetry. This principle suggests that if we simply flip the signs of an agent's preferences—turning a $+5$ utility for a diamond into a $-5$ disutility for a dishwashing shift—the underlying fairness of the allocation should remain intact.
Aditi Sethia, Jatin Yadav, and Vishwa Prakash HV explored this in The Landscape of Almost Equitable Allocations. They found that for certain fairness notions, like Equitability up to one item (EQ1)—where everyone feels they received roughly the same value—the math is perfectly symmetrical. If an algorithm can find an equitable way to share a treasure chest, it can find an equitable way to share a pile of bills by simply negating the values.
Similarly, Ayumi Igarashi and Hirotaka Yoneda demonstrated in Dividing Conflicting Items Fairly that existence results for Envy-Free up to one item (EF1) can be mapped from goods to chores even when items have complex "conflicts" (e.g., two chores that cannot be done by the same person).
Reciprocal Bounds and Weighted Entitlements
The relationship between goods and chores becomes even more precise when agents have different "entitlements"—for example, a larger city having a greater right to resources (or a greater responsibility for waste) than a smaller one.
Max Springer, MohammadTaghi Hajiaghayi, and Hadi Yami discovered a reciprocal relationship in these weighted settings. In their work Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements, they showed that the mathematical bounds used to approximate fairness for goods are the inverse of the bounds for chores. This symmetry allows researchers to take a polynomial-time algorithm designed for resource distribution and mathematically transform it into a robust solution for chore division.
The Complexity Wall
Despite these elegant symmetries, the problem of fair division hits a "complexity wall" as it scales. While many fair allocations are guaranteed to exist for two agents, the math often breaks down when a third agent is added.
For instance, Igarashi et al. proved that while an EF1 allocation always exists for two agents with conflicting items, finding one for three agents is NP-hard. Similarly, Yu Zhou and colleagues found that in "Mixed Manna" settings (where an item might be a good to one person but a chore to another), the existence of fair allocations depends heavily on the underlying structure of how agents are connected, as detailed in A Complete Landscape of EFX Allocations of Mixed Manna on Graphs.
Why Duality Matters
Understanding the duality between goods and chores is more than a theoretical exercise. It provides a unified framework for fairness. If we can prove that a fairness guarantee like Epistemic EFX exists for monotone valuations of goods—as Hannaneh Akrami and Nidhi Rathi did in Epistemic EFX Allocations Exist for Monotone Valuations—the symmetry principles allow us to immediately extend those guarantees to chores, debts, and other negative-utility items. This ensures that our systems for sharing burdens are just as rigorous and fair as our systems for sharing wealth.