# Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 17 Jun 2022.

## Builds on (most cited first, 13 of 13)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Weighted Envy-Freeness in Indivisible Item Allocation](https://mlsanity.com/paper/1909.10502/) (2019)
- [Faster Matroid Intersection](https://mlsanity.com/paper/1911.10765/) (2019)
- [On Maximum Weighted Nash Welfare for Binary Valuations](https://mlsanity.com/paper/2204.03803/) (2022)
- [Greedy Algorithms for Maximizing Nash Social Welfare](https://mlsanity.com/paper/1801.09046/) (2018)
- [Finding Fair and Efficient Allocations When Valuations Don't Add Up](https://mlsanity.com/paper/2003.07060/) (2020)
- [Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations](https://mlsanity.com/paper/2012.12710/) (2020)
- [Truthful and Fair Mechanisms for Matroid-Rank Valuations](https://mlsanity.com/paper/2109.05810/) (2021)
- [Strategyproof Multi-Item Exchange Under Single-Minded Dichotomous Preferences](https://mlsanity.com/paper/1905.10778/) (2019)
- [Multi-unit Assignment under Dichotomous Preferences](https://mlsanity.com/paper/1703.10897/) (2017)
- [Approximating Nash Social Welfare under Binary XOS and Binary Subadditive Valuations](https://mlsanity.com/paper/2106.02656/) (2021)

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

- [Multilevel Fair Allocation with Matroid-Rank Preferences](https://mlsanity.com/paper/2512.24105/) (2025)
- [Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations](https://mlsanity.com/paper/2302.03087/) (2023)
- [Distributed course allocation with asymmetric friendships](https://mlsanity.com/paper/2309.09684/) (2023)

## Abstract (arXiv)

We study fair allocation of indivisible goods when agents have matroid rank valuations. Our main contribution is a simple algorithm based on the colloquial Yankee Swap procedure that computes provably fair and efficient Lorenz dominating allocations. While there exist polynomial time algorithms to compute such allocations, our proposed method improves on them in two ways. (a) Our approach is easy to understand and does not use complex matroid optimization algorithms as subroutines. (b) Our approach is scalable; it is provably faster than all known algorithms to compute Lorenz dominating allocations. These two properties are key to the adoption of algorithms in any real fair allocation setting; our contribution brings us one step closer to this goal.