# Approximation Algorithms for Computing Maximin Share Allocations

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

## Key facts

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

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

- [Towards Fair Recommendation in Two-Sided Platforms](https://mlsanity.com/paper/2201.01180/) (2021)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [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)
- [Guaranteeing Maximin Shares: Some Agents Left Behind](https://mlsanity.com/paper/2105.09383/) (2021)
- [Learning Fair and Preferable Allocations through Neural Network](https://mlsanity.com/paper/2410.17500/) (2024)
- [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 study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a 2/3-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a 2/3-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of 3 agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of 2 agents). We provide a 7/8-approximation algorithm, improving the previously known result of 3/4. The second case is when all item values belong to 0, 1, 2, extending the 0, 1 setting studied in Bouveret and Lemaitre. We obtain an exact algorithm for any number of agents in this case.