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:
- Envy-Free up to One item (EF1): No agent should envy another agent's bundle after "ignoring" one chore from their own set.
- 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