Introduction
Fair division is a cornerstone of computational social choice, traditionally focusing on the allocation of desirable "goods." However, many practical resource allocation problems involve "chores"—tasks with negative utility, such as household labor, hospital shifts, or the processing of hazardous waste. In these scenarios, agents seek to minimize their total cost rather than maximize gain.
This paper investigates the fair division of chores under a specific and expressive cost structure: binary supermodular costs. This setting captures two critical real-world phenomena. First, binary marginals imply that adding a single chore to an agent's bundle increases their cost by either 0 or 1. Second, supermodularity models the "multitasking burden," where the marginal cost of a task increases as an agent is assigned more work. While the fair division of goods is well-documented, the chores setting presents unique challenges; many existence and efficiency results for goods do not translate directly to chores.
The Matroid Connection
The primary technical contribution of this research is the establishment of a bridge between fair division and Matroid Theory. The authors demonstrate a fundamental bijection: a set function $c(S)$ is binary supermodular if and only if its complementary function, defined as $g(S) = |S| - c(S)$, is a matroid rank function.
By reframing chore costs through the lens of matroid rank, the authors transform complex fairness questions into well-understood combinatorial optimization problems. This connection allows the application of powerful tools such as Matroid Union Algorithms. Specifically, the authors utilize these tools to identify "social-cost-minimizing" partial allocations—where agents incur zero cost—and then extend these into complete, fair allocations.
Algorithmic Framework
The paper introduces several key algorithms to navigate the landscape of fairness and efficiency:
- CostMinPartAlloc: A foundational subroutine that computes a basis of a union matroid. This algorithm is essential for identifying the minimum possible social cost for any given instance, serving as a starting point for efficient allocations.
- Add-and-Fix Algorithm: Developed specifically for the identical-cost setting, this approach incrementally assigns chores while "fixing" potential fairness violations to maintain Envy-Freeness up to any item (EFX).
Fairness, Efficiency, and Incompatibility
A central theme of the paper is the relationship between various fairness notions and Pareto Efficiency (PE). In the context of goods, certain fairness criteria often imply others. However, the authors prove that for chores under binary supermodular costs, EF1 (Envy-Freeness up to one item), MMS (Maximin Share), and Lorenz Domination are incomparable. An allocation satisfying one may fail the others, and in certain instances, they may even be mutually exclusive.
Key Positive Results
Despite these complexities, the authors provide several existence proofs and polynomial-time algorithms:
- EF1 + PE and MMS + PE: The authors prove that allocations satisfying these combinations always exist and can be found in polynomial time.
- Lorenz Domination: Allocations that are Lorenz-optimal (a strong form of equity) are also shown to be computable in polynomial time.
- EFX for Identical Costs: When all agents share the same binary marginal cost function, the Add-and-Fix algorithm successfully finds an EFX allocation.
The EFX "Hard Wall"
The research reveals a significant divergence between EF1 and the more stringent EFX (Envy-Freeness up to any item). While EF1 is compatible with Pareto efficiency, the authors prove a "hard wall" for EFX: even approximate EFX is fundamentally incompatible with Pareto efficiency in the chores setting, even when agents have identical cost functions. Furthermore, while finding EFX allocations for goods is often achieved via "leximax" allocations, the authors prove that computing a leximax-optimal allocation for chores is NP-hard.
Conclusion and Future Directions
This work provides a comprehensive map of the feasibility of fair chore division under binary supermodular costs. By leveraging matroid theory, the authors provide polynomial-time solutions for EF1 and MMS in conjunction with Pareto efficiency.
However, several questions remain open. While EFX is achievable for identical costs, its existence for general (non-identical) binary supermodular costs is not yet settled. Additionally, the current framework relies on the binary nature of marginal costs (0 or 1). Future research may explore whether these results can be generalized to broader supermodular functions or identify the best possible approximations of EFX that can still maintain economic efficiency.
Summary updated