Abstract
Finding fair and efficient allocations for indivisible chores is a fundamental challenge in discrete fair division, particularly when agents have asymmetric weights. This paper presents the first polynomial-time algorithms to achieve weighted envy-freeness up to one chore (wEF1) and fractional Pareto-optimality (fPO) for two significant cases: instances with three types of agents and instances with two types of chores. By leveraging competitive equilibrium frameworks and novel chore-transfer strategies, the authors bridge critical gaps in the state-of-the-art, moving closer to a general solution for additive chore division.
Introduction: The Chore Division Problem
In the field of discrete fair division, the goal is to allocate indivisible items among agents such that the outcome is both fair and efficient. While significant progress has been made for "goods" (items with positive utility), "chores" (tasks with negative utility, such as household tasks or industrial liabilities) present unique mathematical difficulties.
The complexity increases when agents are asymmetric, possessing different "weights" or entitlements—for instance, a senior employee versus a junior one. This research focuses on finding allocations that satisfy two primary criteria:
- Weighted Envy-Free up to One Chore (wEF1): No agent envies another's bundle more than their own, provided one chore can be ignored from their own bundle, adjusted for weights.
- Pareto-Optimality (PO): No alternative allocation exists that makes at least one agent better off without making another worse off.
Achieving both wEF1 and PO for chores has remained a major open problem. This work narrows the gap by solving it for specific structured instances.
Methodology: Competitive Equilibrium and Weighted Picking
The authors utilize the Competitive Equilibrium (CE) framework, specifically the Fisher market model adapted for chores. In this model, chores carry "payments," and agents aim to earn a specific amount by performing them. The core of the approach involves maintaining the allocation on the "Minimum Pain-per-Buck" (MPB) set to ensure efficiency.
Key algorithmic components include:
- Weighted Picking Sequence (WPS): A greedy-like subroutine that accounts for agent weights during chore selection.
- Chore Transfers and Price Adjustments: To maintain fairness, the algorithm strategically transfers chores between agents or adjusts chore payments to shift the equilibrium until wEF1 is achieved.
- Pivot Agent Strategy: For the two-chore-type scenario, a "pivot" agent initially holds all chores, which are then systematically redistributed to resolve envy while maintaining the necessary structure for efficiency.
Key Results: Filling the Fairness-Efficiency Gap
The paper successfully fills several "holes" in the current landscape of fair division results. Most notably, it proves that a wEF1 and fPO (fractional Pareto-optimal) allocation always exists and can be found in polynomial time for instances with three types of agents or two types of chores.
These results generalize previous findings that were restricted to symmetric agents or smaller agent counts. A key insight is that the Weighted Picking Sequence, typically used for goods, possesses properties that can be leveraged for chores when combined with price-adjustment mechanisms. By ensuring the allocation corresponds to a competitive equilibrium, the authors guarantee fractional Pareto-optimality (fPO), a stronger efficiency requirement than standard PO.
Discussion and Future Directions
While this work provides significant progress, the General Additive case—where every agent has unique preferences and there are many types of chores—remains an open challenge. The current techniques rely on the "few types" structure to ensure that chore-transfer cycles terminate in polynomial time. Future research will explore whether these competitive equilibrium techniques can scale to the general case or if fundamental barriers exist for achieving wEF1 and PO simultaneously in all chore instances.
Summary updated