# Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2020.

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

- [Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations](https://mlsanity.com/paper/2206.08495/) (2022)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)
- [Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations](https://mlsanity.com/paper/2302.03087/) (2023)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)

## Abstract (arXiv)

We study fair and economically efficient allocation of indivisible goods among agents whose valuations are rank functions of matroids. Such valuations constitute a well-studied class of submodular functions (i.e., they exhibit a diminishing returns property) and model preferences in several resource-allocation settings. We prove that, for matroid-rank valuations, a social welfare-maximizing allocation that gives each agent her maximin share always exists. Furthermore, such an allocation can be computed in polynomial time. We establish similar existential and algorithmic results for the pairwise maximin share guarantee as well. To complement these results, we show that if the agents have binary XOS valuations or weighted-rank valuations, then maximin fair allocations are not guaranteed to exist. Both of these valuation classes are immediate generalizations of matroid-rank functions.