# A tight negative example for MMS fair allocations

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2021.

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

- [Fair Shares: Feasibility, Domination and Incentives](https://mlsanity.com/paper/2205.07519/) (2022)
- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [On Approximate MMS Allocations on Restricted Graph Classes](https://mlsanity.com/paper/2508.06343/) (2025)
- [Maximin Share Guarantees via Limited Cost-Sensitive Sharing](https://mlsanity.com/paper/2602.20541/) (2026)

## Abstract (arXiv)

We consider the problem of allocating indivisible goods to agents with additive valuation functions. Kurokawa, Procaccia and Wang [JACM, 2018] present instances for which every allocation gives some agent less than her maximin share. We present such examples with larger gaps. For three agents and nine items, we design an instance in which at least one agent does not get more than a frac3940 fraction of her maximin share. Moreover, we show that there is no negative example in which the difference between the number of items and the number of agents is smaller than six, and that the gap (of frac140) of our example is worst possible among all instances with nine items. For n ≥ 4 agents, we show examples in which at least one agent does not get more than a 1 - frac1n4 fraction of her maximin share. In the instances designed by Kurokawa, Procaccia and Wang, the gap is exponentially small in n. Our proof techniques extend to allocation of chores (items of negative value), though the quantitative bounds for chores are different from those for goods. For three agents and nine chores, we design an instance in which the MMS gap is frac143.