# An Improved Approximation Algorithm for Maximin Shares

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2019.

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

- [Fair and Efficient Resource Allocation with Partial Information](https://mlsanity.com/paper/2105.10064/) (2021)
- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [Fair Shares: Feasibility, Domination and Incentives](https://mlsanity.com/paper/2205.07519/) (2022)
- [The Fairness Fair: Bringing Human Perception into Collective Decision-Making](https://mlsanity.com/paper/2312.14402/) (2023)
- [Guaranteeing Maximin Shares: Some Agents Left Behind](https://mlsanity.com/paper/2105.09383/) (2021)
- [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)
- [Improving the Bounds on Approximating Weighted Maximin Share for Chores](https://mlsanity.com/paper/2610.15520/) (2026)

## Abstract (arXiv)

Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a fair manner. We study the case where m indivisible items need to be divided among n agents with additive valuations using the popular fairness notion of maximin share (MMS). An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist, a series of work provided approximation algorithms for a 2/3-MMS allocation in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, Ghodsi et al. [EC'2018] showed the existence of a 3/4-MMS allocation and a PTAS to find a (3/4-ε)-MMS allocation for an ε > 0. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. In this paper, we develop a new approach that gives a simple algorithm for showing the existence of a 3/4-MMS allocation. Furthermore, our approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial-time algorithm to find a 3/4-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (3/4 + 1/(12n))-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 3/4 was the best factor known for n> 4.