# On Approximate MMS Allocations on Restricted Graph Classes

arXiv: https://arxiv.org/abs/2508.06343 · HTML: https://mlsanity.com/paper/2508.06343/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 8 Aug 2025.

## Builds on (most cited first, 16 of 16)

- [Fair Allocation of Indivisible Goods: Improvement and Generalization](https://mlsanity.com/paper/1704.00222/) (2017)
- [Approximation Algorithms for Computing Maximin Share Allocations](https://mlsanity.com/paper/1503.00941/) (2015)
- [An Improved Approximation Algorithm for Maximin Shares](https://mlsanity.com/paper/1903.00029/) (2019)
- [Approximation Algorithms for Maximin Fair Division](https://mlsanity.com/paper/1703.01851/) (2017)
- [Breaking the 3/4 Barrier for Approximate Maximin Share](https://mlsanity.com/paper/2307.07304/) (2023)
- [A tight negative example for MMS fair allocations](https://mlsanity.com/paper/2104.04977/) (2021)
- [Fair Division of a Graph](https://mlsanity.com/paper/1705.10239/) (2017)
- [Almost Envy-Free Allocations with Connected Bundles](https://mlsanity.com/paper/1808.09406/) (2018)
- [Fairly Allocating Contiguous Blocks of Indivisible Items](https://mlsanity.com/paper/1707.00345/) (2017)
- [Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints](https://mlsanity.com/paper/1811.04872/) (2018)
- [Simplification and Improvement of MMS Approximation](https://mlsanity.com/paper/2303.16788/) (2023)
- [The Price of Connectivity in Fair Division](https://mlsanity.com/paper/1908.05433/) (2019)
- [Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division](https://mlsanity.com/paper/2401.14825/) (2024)
- [Chore division on a graph](https://mlsanity.com/paper/1812.01856/) (2018)
- [Maximin share allocations on cycles](https://mlsanity.com/paper/1905.03038/) (2019)
- [MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results](https://mlsanity.com/paper/2302.13224/) (2023)

## Abstract (arXiv)

We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i.e., if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and d-claw-free graphs for any fixed d, such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.