Abstract
The fair division of chores—tasks with associated costs—is a central problem in computational social choice. This paper investigates the existence and computation of allocations that are both Envy-Free up to any item (EFX) and Pareto Optimal (PO). Focusing on bi-valued chore costs {1, k}, the authors provide a new algorithm that achieves a (2 - 1/k)-approximation for EFX while maintaining PO. For the specific case of {1, 2} costs, they prove that a perfectly EFX and PO allocation always exists and can be found in polynomial time.
Introduction
In fair division, the "holy grail" is finding allocations that are both fair and efficient. While well-studied for "goods," the problem is significantly harder for "chores" (items with negative utility). The gold standard for fairness is Envy-Freeness up to any item (EFX): an agent does not envy another even after any single chore is removed from their own bundle. Combined with Pareto Optimality (PO), which ensures no agent can be made better off without making another worse off, EFX represents a robust fairness-efficiency guarantee.
The existence of EFX allocations for chores remains an open question for more than two agents. Previous work achieved a 3-approximation for bi-valued chores (where costs are either 1 or k). This research aims to tighten this bound and resolve existence for specific cost structures.
Methodology: Market Equilibria and Discrete Swaps
The authors leverage the Fisher Market framework, treating chores as items for which agents are paid to perform. The process begins with a pEF1 equilibrium—a state that is already PO and Envy-Free up to one item (EF1).
Instead of traditional rounding of fractional solutions, the paper introduces a discrete swap algorithm. Agents are categorized into groups based on their total earnings (payments received). For general {1, k} instances, the algorithm iteratively moves items from agents with high-payment chores to those with low-payment chores until the (2 - 1/k) threshold is satisfied.
Key Insights: The Power of Reallocation
A core contribution is the shift from continuous rounding to direct discrete reallocation. By focusing on the payments agents receive in equilibrium, the authors maintain PO as an invariant while iteratively improving fairness.
The algorithm identifies agents who are not (2 - 1/k)-EFX and performs a specific swap: a high-payment item is moved to an agent with lower earnings, and the bundles are updated to rebalance the "load." This process is visualized in the transition between earning states.
For {1, 2} instances, a more refined grouping strategy (z, z+1, z+2 earning levels) allows the algorithm to reach perfect EFX without violating PO. This suggests that smaller disparities in chore costs lead to more manageable mathematical structures.
Results and Discussion
The paper establishes two primary results:
- Improved Approximation: For {1, k} chores, a (2 - 1/k)-EFX and PO allocation is computable in polynomial time, improving upon the previous 3-approximation.
- Existence for {1, 2}: The authors prove that exact EFX and PO allocations always exist for {1, 2} costs and provide an efficient algorithm for their computation.
Limitations and Future Work
The current results rely on the bi-valued cost assumption. Future research should explore whether EFX exists for chores with arbitrary costs for n > 2 agents, or if these techniques can extend to ternary values (e.g., {0, 1, 2}). This work provides a robust framework for using market dynamics to solve complex fairness problems through iterative reallocation.
Summary updated