Abstract
This paper investigates the fair distribution of $m$ indivisible goods among $n$ agents under the principles of Maximin Share (MMS) and Any Price Share (APS). While these notions are well-studied for additive valuations, we extend the analysis to more complex valuation functions. Specifically, we focus on Separable Piecewise-Linear Concave (SPLC) valuations, where we improve the best-known approximation factor from 1/3 to 1/2. Our approach utilizes a relax-and-round paradigm involving competitive equilibrium and linear programming (LP) relaxations. Additionally, we address submodular valuations, providing a 1/3-APS allocation via a greedy algorithm analyzed through concave extensions. These results significantly advance the state-of-the-art in polynomial-time fair division.
Introduction
Fair division is a fundamental problem in computational social choice, concerning the allocation of items among agents with diverse preferences. A central fairness criterion is the Maximin Share (MMS), which represents the maximum utility an agent can guarantee themselves if they were to partition the items into $n$ bundles and receive the least preferred one. While MMS is a robust standard for divisible goods, its existence is not guaranteed for indivisible items. Consequently, research has shifted toward finding approximate MMS allocations.
Most existing literature focuses on additive valuations, where the value of a bundle is simply the sum of the values of its constituent items. However, real-world scenarios often exhibit diminishing returns. This paper addresses two broader classes: Separable Piecewise-Linear Concave (SPLC) valuations and submodular valuations.
The Complexity of SPLC Valuations
SPLC valuations generalize additive ones by allowing the marginal utility of a good to decrease as an agent receives more units of that "type" of good. This introduces significant complexity compared to the additive model:
- High MMS Values: In the additive case, an agent's MMS is bounded by their average value. In SPLC, an agent's MMS can be as high as their total value for the entire set of items.
- Computational Intractability: Finding market equilibria, which is polynomial-time for additive valuations, becomes intractable for SPLC.
Improving SPLC Allocations: The Relax-and-Round Paradigm
The authors introduce a polynomial-time algorithm that achieves a 1/2-MMS guarantee for SPLC valuations, a substantial improvement over the previous 1/3-MMS bound. The method follows a "relax-and-round" strategy:
1. Linear Relaxation and Market Equilibrium
The algorithm first treats goods as divisible. By leveraging Fisher market theory, the authors prove that a fractional competitive equilibrium exists where every agent receives at least their full MMS. This fractional allocation serves as a baseline for the final distribution.
2. Cycle Elimination
The fractional allocation is modeled as a bipartite graph between agents and goods. To simplify the structure, the authors perform "cycle elimination," removing dependencies until the graph becomes a forest (a collection of trees).
3. Strategic Rounding
In a forest structure, each agent is connected to at most one fractional item. By carefully rounding these fractional assignments, the authors ensure that each agent loses at most one "segment" of a piecewise-linear utility function. Mathematically, this ensures that every agent retains at least 1/2 of their MMS value in the final integer allocation.
Submodular Valuations and Concave Extensions
Beyond SPLC, the paper examines submodular valuations, where the marginal value of any item decreases as the agent's bundle grows. The authors analyze a simple greedy algorithm for this class.
The primary innovation lies in the analysis rather than the algorithm itself. The authors use concave extensions—continuous functions that interpolate discrete submodular functions—to upper-bound the Any Price Share (APS). APS is a more stringent fairness notion than MMS that accounts for agents with different entitlements. Although computing concave extensions is NP-hard, the authors use them as a theoretical tool to prove that the greedy approach yields a 1/3-APS allocation, matching the current best-known factor.
Key Results and Future Directions
The paper establishes two major benchmarks:
- 1/2-MMS for SPLC: A new state-of-the-art for a complex valuation class, which also extends to 1/2-APS for symmetric agents.
- 1/3-APS for Submodular: A simplified analysis of greedy algorithms using concave extensions.
Despite these advances, a gap remains. For submodular valuations, the theoretical upper bound for MMS existence is 2/3, yet current algorithms only reach approximately 1/3. Future work will likely focus on closing this gap and exploring whether the relax-and-round paradigm can be adapted for even broader classes of valuation functions.
Summary updated