Fair Chore Division under Binary Supermodular Costs

Siddharth Barman, Vishnu V. Narayan, Paritosh Verma

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:

  1. 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.
  2. 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

Abstract

We study the problem of dividing indivisible chores among agents whose costs (for the chores) are supermodular set functions with binary marginals. Such functions capture complementarity among chores, i.e., they constitute an expressive class wherein the marginal disutility of each chore is either one or zero, and the marginals increase with respect to supersets. In this setting, we study the broad landscape of finding fair and efficient chore allocations. In particular, we establish the existence of (i) EF1 and Pareto efficient chore allocations, (ii) MMS-fair and Pareto efficient allocations, and (iii) Lorenz dominating chore allocations. Furthermore, we develop polynomial-time algorithms—in the value oracle model—for computing the chore allocations for each of these fairness and efficiency criteria. Complementing these existential and algorithmic results, we show that in this chore division setting, the aforementioned fairness notions, namely EF1, MMS, and Lorenz domination are incom- parable: an allocation that satisfies any one of these notions does not necessarily satisfy the others. Additionally, we study EFX chore division. In contrast to the above-mentioned positive results, we show that, for binary supermodular costs, Pareto efficient allocations that are even approximately EFX do not exist, for any arbitrarily small approximation constant. Focusing on EFX fairness alone, when the cost functions are identical we present an algorithm (Add-and-Fix) that computes an EFX allocation. For binary marginals, we show that Add-and-Fix runs in polynomial time.
BibTeX
@misc{barman2023fair,
  author = {Siddharth Barman and Vishnu V. Narayan and Paritosh Verma},
  title = {{Fair Chore Division under Binary Supermodular Costs}},
  year = {2023},
  eprint = {2302.11530},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.11530},
}
Figure