# A General Framework for Fair Allocation under Matroid Rank Valuations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2022.

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

- [Multilevel Fair Allocation with Matroid-Rank Preferences](https://mlsanity.com/paper/2512.24105/) (2025)
- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [To Pool or Not To Pool: Analyzing the Regularizing Effects of Group-Fair Training on Shared Models](https://mlsanity.com/paper/2402.18803/) (2024)
- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)

## Abstract (arXiv)

We study the problem of fairly allocating a set of indivisible goods among agents with matroid rank valuations -- every good provides a marginal value of 0 or 1 when added to a bundle and valuations are submodular. We generalize the Yankee Swap algorithm to create a simple framework, called General Yankee Swap, that can efficiently compute allocations that maximize any justice criterion (or fairness objective) satisfying some mild assumptions. Along with maximizing a justice criterion, General Yankee Swap is guaranteed to maximize utilitarian social welfare, ensure strategyproofness and use at most a quadratic number of valuation queries. We show how General Yankee Swap can be used to compute allocations for five different well-studied justice criteria: (a) Prioritized Lorenz dominance, (b) Maximin fairness, (c) Weighted leximin, (d) Max weighted Nash welfare, and (e) Max weighted p-mean welfare. In particular, our framework provides the first polynomial time algorithms to compute weighted leximin, max weighted Nash welfare and max weighted p-mean welfare allocations for agents with matroid rank valuations.