The Good, the Bad and the Submodular: Fairly Allocating Mixed Manna Under Order-Neutral Submodular Preferences

Cyrus Cousins, Vignesh Viswanathan, Yair Zick

Introduction

Fair allocation is the study of how to divide a set of indivisible items among agents with heterogeneous preferences. While the division of "goods" (items with positive utility) is well-documented, real-world scenarios often involve "mixed manna"—collections containing both goods and chores (items with negative utility, such as cleaning shifts or maintenance tasks).

This paper addresses the fair allocation of mixed manna under a broad class of submodular preferences. The authors tackle two primary hurdles: the failure of the "Gold Standard" objective (Nash Social Welfare) when utilities are zero or negative, and the computational complexity of the leximin objective. Leximin optimization—which maximizes the utility of the worst-off agent, then the second worst-off, and so on—is a natural egalitarian choice but is notoriously difficult to compute for indivisible items and non-additive preferences.

Preference Model: Order-Neutral Submodularity

The research focuses on Order-Neutral Submodular (ONSUB) valuations. In this setting, the marginal gain of an item decreases as an agent acquires more items (submodularity), and the marginal values are restricted to the set $\{-1, 0, c\}$ for some positive integer $c$.

A critical insight of the paper is the property of order-neutrality. This means that while the total value of a bundle is independent of the order in which items are received, the set of marginal values encountered during the construction of that bundle is also independent of the order. This property allows the complex allocation problem to be decomposed into manageable components.

The Algorithmic Framework

The authors introduce the first polynomial-time algorithm to compute leximin allocations for ONSUB preferences. The algorithm operates in three distinct phases:

  1. Initial Utility Maximization: The algorithm utilizes a modified "Yankee Swap" approach to allocate non-negative items, maximizing the total social welfare as a baseline.
  2. Leximin Refinement via Weighted Path Augmentation: This phase is the technical core of the work. To balance utilities without disrupting existing gains, the authors introduce Weighted Exchange Graphs. These graphs assign specific weights to item transfers, ensuring that balancing "good" items ($c$-valued) does not inadvertently destroy the balance of "neutral" items ($0$-valued).
  3. Greedy Chore Allocation: Once the goods are balanced, the remaining chores (marginal value of $-1$) are distributed greedily. Chores are assigned to agents currently holding the highest utility, maintaining the egalitarian distribution established in the previous phases.

Key Theoretical Insights

  • Decomposition Theorem: The authors prove that any allocation under ONSUB preferences can be decomposed into three virtual allocations: one for goods ($c$), one for neutral items ($0$), and one for chores ($-1$).
  • The "Integer $c$" Constraint: The algorithm’s success relies on $c$ being a positive integer. The authors demonstrate that if $c$ is allowed to be a non-integer rational number (e.g., $1.5$), the problem of finding a leximin allocation becomes NP-hard.
  • Lorenz Dominance: The paper proves that in this setting, a leximin allocation is "Lorenz dominating." This implies it provides the most equitable distribution of utility possible across the entire population of agents.

Results and Fairness Guarantees

The proposed algorithm is not only efficient—running in polynomial time relative to the number of agents and items—but also provides robust fairness guarantees:

  • PROP1: The allocations satisfy "proportionality up to one item," a standard fairness relaxation for indivisible items.
  • EF1 & MMS: In cases where preferences are restricted to be additive, the algorithm also guarantees "envy-freeness up to one item" and ensures every agent receives their "maxmin share."
  • Hardness Bounds: The authors provide a lower bound proof showing that computing leximin allocations is NP-hard for $\{ -p, q \}$-additive valuations for any co-prime integers where $p \geq 3$.

Conclusion and Future Work

This work provides a significant advancement in the fair division of mixed manna by identifying ONSUB preferences as a tractable yet expressive class for leximin optimization. While the current algorithm is tuned for the $\{-1, 0, c\}$ value set, it lays the groundwork for future explorations into broader submodular functions, chores with varying weights, and other complex valuation classes like Rado valuations.

Summary updated

Abstract

We study the problem of fairly allocating indivisible goods (positively valued items) and chores (negatively valued items) among agents with decreasing marginal utilities over items. Our focus is on instances where all the agents have simple preferences; specifically, we assume the marginal value of an item can be either \(-1\), 0 or some positive integer c. Under this assumption, we present an efficient algorithm to compute leximin allocations for a broad class of valuation functions we call order-neutral submodular valuations. Order-neutral submodular valuations strictly contain the well-studied class of additive valuations but are a strict subset of the class of submodular valuations. We show that these leximin allocations are Lorenz dominating and approximately proportional. We also show that, under further restriction to additive valuations, these leximin allocations are approximately envy-free and guarantee each agent their maximin share. We complement this algorithmic result with a lower bound showing that the problem of computing leximin allocations is NP-hard when c is a rational number.
BibTeX
@inproceedings{cousins2023good,
  author = {Cyrus Cousins and Vignesh Viswanathan and Yair Zick},
  title = {{The Good, the Bad and the Submodular: Fairly Allocating Mixed Manna Under Order-Neutral Submodular Preferences}},
  booktitle = {WINE},
  year = {2023},
  doi = {10.1007/978-3-031-48974-7\_12},
}
Figure