Introduction
Fair division of indivisible items is a cornerstone of computational social choice. While the allocation of "goods" (items with positive utility) has seen significant progress, the division of "chores"—tasks with negative utility that agents wish to avoid—presents unique challenges. This research addresses the simultaneous achievement of fairness and efficiency in chore allocation.
The paper focuses on three primary criteria:
- EF1 (Envy-Free up to one item): An agent does not envy another after the removal of at most one chore from the other's bundle.
- EFX (Envy-Free up to any item): A stricter fairness notion where removing any chore from a bundle eliminates envy.
- fPO (Fractional Pareto-Optimality): An efficiency standard ensuring no redistribution (even fractional) can improve one agent's utility without harming another.
Algorithmic Framework: Competitive Equilibrium
The authors leverage the concept of Competitive Equilibrium (CE) from Fisher markets. In this setting, chores are assigned "payments," and agents seek to minimize their "pain" by selecting chores with the minimum-pain-per-buck (MPB).
A key innovation is the introduction of pEF1 (payment Envy-Free up to one item). The authors demonstrate that an allocation satisfying pEF1 within a competitive equilibrium is guaranteed to be both EF1 and fPO.
The "Big Earner" Algorithm
For the specific case of three agents ($n=3$), the authors propose a "Big Earner" algorithm. This procedure begins by assigning all chores to a single agent and iteratively rebalancing the allocation through payment adjustments and chore transfers, maintaining the MPB property throughout.
Key Results and Contributions
The study provides several breakthrough results, summarized in the table below. Notably, it offers the first polynomial-time algorithms for EF1+fPO in the three-agent and two-type agent scenarios.
Major Findings:
- Three-Agent EF1+fPO: Established existence and provided a strongly polynomial-time algorithm.
- Two-Type EF1+fPO: Developed a polynomial-time algorithm for any number of agents, provided they belong to one of two preference groups.
- EFX Boundaries: While EFX+fPO is achievable for three agents with bivalued preferences, the authors proved it is mathematically impossible for just two agents with "2-ary" preferences, identifying a sharp limit to combining these properties.
Conclusion and Future Directions
This work significantly advances the understanding of chore allocation by bridging the gap between fairness and efficiency. The most prominent remaining challenge is the existence of EF1+fPO for an arbitrary number of agents ($n$) with general additive preferences. The authors suggest that their market-based framework, potentially combined with envy-resolving techniques like Round-Robin, provides a promising path toward solving this general case.
Summary updated