# Simplification and Improvement of MMS Approximation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2023.

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

- [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)
- [Improving the Bounds on Approximating Weighted Maximin Share for Chores](https://mlsanity.com/paper/2610.15520/) (2026)

## Abstract (arXiv)

We consider the problem of fairly allocating a set of indivisible goods among n agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. The Garg-Taki algorithm gives the current best approximation factor of (frac34 + frac112n). Most of these results are based on complicated analyses, especially those providing better than 2/3 factor. Moreover, since no tight example is known of the Garg-Taki algorithm, it is unclear if this is the best factor of this approach. In this paper, we significantly simplify the analysis of this algorithm and also improve the existence guarantee to a factor of (frac34 + min(frac136, frac316n-4)). For small n, this provides a noticeable improvement. Furthermore, we present a tight example of this algorithm, showing that this may be the best factor one can hope for with the current techniques.