# Exact and approximate maximin share allocations in multi-graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2025.

## Built on by (most cited first, 2 of 2)

- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [EFX Allocation In (Multi)Hypergraphs](https://mlsanity.com/paper/2608.03171/) (2026)

## Abstract (arXiv)

We study the problem of (approximate) maximin share (MMS) allocation of indivisible items among a set of agents. We focus on the graphical valuation model, previously studied by Christodolou, Fiat, Koutsoupias, and Sgouritsa ("Fair allocation in graphs", EC 2023), where the input is given by a graph where edges correspond to items, and vertices correspond to agents. An edge may have non-zero marginal value only for its incident vertices. We study additive, XOS and subadditive valuations and we present positive and negative results for (approximate) MMS fairness, and also for (approximate) pair-wise maximin share (PMMS) fairness.