1/2 Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations

Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni, Ruta Mehta

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:

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

Abstract

We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation within the context of additive valuations. We explore these notions for valuations that extend beyond additivity. First, we study approximate MMS under the separable (piecewise-linear) concave (SPLC) valuations, an important class generalizing additive, where the best known factor was 1/3-MMS. We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We note that SPLC valuations introduce an elevated level of intricacy in contrast to additive. For instance, the MMS value of an agent can be as high as her value for the entire set of items. Further, the equilibrium computation problem, which is polynomial-time for additive valuations, becomes intractable for SPLC. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. Our result extends to give (symmetric) 1/2-APS, a stronger guarantee than MMS. APS is a stronger notion that generalizes MMS by allowing agents with arbitrary entitlements. We study the approximation of APS under submodular valuation functions. We design and analyze a simple greedy algorithm using concave extensions of submodular functions. We prove that the algorithm gives a 1/3-APS allocation which matches the current best-known factor. Concave extensions are hard to compute in polynomial time and are, therefore, generally not used in approximation algorithms. Our approach shows a way to utilize it within analysis (while bypassing its computation), and might be of independent interest.
BibTeX
@inproceedings{chekuri2024approximate,
  author = {Chandra Chekuri and Pooja Kulkarni and Rucha Kulkarni and Ruta Mehta},
  title = {{1/2 Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=Fzzl7OqXWU},
}
Figure