This paper explores the boundaries of fair division for indivisible goods, focusing on a specific class of preferences called cost utilities. The authors prove that for three agents, or for any number of agents with hierarchical (laminar) preferences, a "maximin fair" allocation is guaranteed to exist—a significant result given that such guarantees fail in more general settings.
TL;DR
The authors demonstrate that "cost utilities"—where items have fixed costs and agents only value items they "approve"—provide a powerful framework for guaranteed fair division. They prove the existence of Maximin Fair Share (MMS) allocations for three agents and for any number of agents with hierarchical preferences, while also identifying the limits of strategyproof mechanisms in this space.
What Problem Does This Paper Address?
Fairly dividing indivisible items (like office equipment, tasks, or course slots) is a classic problem in computer science and economics. A gold standard for fairness is the Maximin Fair Share (MMS).
Imagine a "cut-and-choose" scenario: an agent partitions all items into $n$ bundles (where $n$ is the number of agents) and expects to receive at least the value of their least-preferred bundle. An allocation is "MMS-fair" if every agent receives at least this value.
The challenge is that for general additive valuations, MMS allocations are not guaranteed to exist for three or more agents. Furthermore, even when they do exist, computing them is NP-hard. This paper looks for a "sweet spot"—a class of valuations that is realistic enough for applications but restricted enough to provide theoretical fairness guarantees.
Methods
The authors focus on cost utilities. In this model:
- Each item $g$ has a public cost $c(g)$.
- Each agent $i$ has an approval set $A_i$.
- An agent's value for an item is $c(g)$ if they approve it, and $0$ otherwise.
The paper employs constructive and inductive proofs to establish existence:
- For $n=3$ agents: They provide a constructive method to find a Pareto efficient MMS allocation by partitioning items based on how many agents approve them.
- For Laminar Set Approvals: They use an inductive approach. Laminar approvals represent hierarchical preferences (e.g., one agent wants all vegetarian food, another wants only vegan food, which is a sub-category).
- Mechanism Design: They analyze Sequential Allocation (picking sequences) to see if agents can be incentivized to report their true preferences (strategyproofness) while still achieving fairness.
Datasets
Not discussed in the paper. This is a theoretical work based on mathematical proofs and algorithmic analysis.
Key Insights and Ideas
- The NP-Hard/Existence Paradox: This is the first known class of valuations (other than identical valuations) where calculating the MMS value itself is NP-hard, yet the existence of an MMS allocation is guaranteed for specific cases. Usually, existence results are found in simpler classes where computation is also easy.
- Laminarity as a Fairness Enabler: The hierarchical structure of laminar approvals allows for a recursive allocation strategy. If an MMS allocation exists when many agents approve everything, the authors prove it must also exist as those approval sets shrink into a hierarchy.
- Strategyproofness vs. Efficiency: The authors find a "tight" bound for strategyproofness. While they can guarantee a strategyproof, fair, and efficient allocation for $n$ agents and $n+2$ items, they prove this is impossible once you reach $n+3$ items.
Key Results
- Three-Agent Guarantee: Theorem 1 proves that for three agents with cost utilities, a Pareto efficient MMS allocation always exists. This contrasts with general additive utilities, where counterexamples exist for $n=3$.
- General Laminar Guarantee: Theorem 2 proves that for any number of agents, if approval sets are laminar, an MMS allocation always exists.
- Strategyproof Mechanism: For $n$ agents and $m = n+2$ items, the authors define a specific picking sequence for Sequential Allocation that is strategyproof, Pareto efficient, and MMS-fair.
- Impossibility Result: Proposition 3 shows that for 2 agents and 5 items ($n+3$), no mechanism can be simultaneously strategyproof, Pareto efficient, and MMS-fair.
Limitations and Future Work
- General $n$ for Cost Utilities: The biggest open question remains: does an MMS allocation always exist for $n > 3$ agents with cost utilities without the laminar restriction?
- Computational Complexity: While existence is proven, the paper notes that finding these allocations remains computationally difficult (NP-hard).
- Additional Constraints: The authors suggest extending this work to scenarios with cardinality constraints (e.g., an agent can only receive a maximum number of items) or budget constraints, which are common in real-world resource allocation.
Summary updated