# Multilevel Fair Allocation with Matroid-Rank Preferences

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 21 references that are in the map.
- First posted on arXiv 30 Dec 2025.

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

- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [Envy-freeness up to any item with high Nash welfare: The virtue of donating items](https://mlsanity.com/paper/1902.04319/) (2019)
- [Almost Envy-Freeness in Group Resource Allocation](https://mlsanity.com/paper/1901.08463/) (2019)
- [Weighted Envy-Freeness in Indivisible Item Allocation](https://mlsanity.com/paper/1909.10502/) (2019)
- [Fair Division with Allocator's Preference](https://mlsanity.com/paper/2310.03475/) (2023)
- [Faster Matroid Intersection](https://mlsanity.com/paper/1911.10765/) (2019)
- [Fair Division via Social Comparison](https://mlsanity.com/paper/1611.06589/) (2016)
- [Almost Group Envy-free Allocation of Indivisible Goods and Chores](https://mlsanity.com/paper/1907.09279/) (2019)
- [Finding Fair and Efficient Allocations When Valuations Don't Add Up](https://mlsanity.com/paper/2003.07060/) (2020)
- [For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods](https://mlsanity.com/paper/2302.06958/) (2023)
- [Group Envy Freeness and Group Pareto Efficiency in Fair Division with Indivisible Items](https://mlsanity.com/paper/2006.15893/) (2020)
- [A General Framework for Fair Allocation under Matroid Rank Valuations](https://mlsanity.com/paper/2208.07311/) (2022)
- [Envy-Free Allocations Respecting Social Networks](https://mlsanity.com/paper/2011.11596/) (2020)
- [Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations](https://mlsanity.com/paper/2206.08495/) (2022)
- [Faster Matroid Partition Algorithms](https://mlsanity.com/paper/2303.05920/) (2023)

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

- [Multilevel Fair Allocation under Additive Preferences](https://mlsanity.com/paper/2608.24400/) (2026)

## Abstract (arXiv)

We introduce the concept of multilevel fair allocation of resources with tree-structured hierarchical relations among agents. While at each level it is possible to consider the problem locally as an allocation of an agent to its children, the multilevel allocation can be seen as a trace capturing the fact that the process is iterated until the leaves of the tree. In principle, each intermediary node may have its own local allocation mechanism. The main challenge is then to design algorithms which can retain good fairness and efficiency properties. In this paper we propose two original algorithms under the assumption that leaves of the tree have matroid-rank utility functions and the utility of any internal node is the sum of the utilities of its children. The first one is a generic polynomial-time sequential algorithm that comes with theoretical guarantees in terms of efficiency and fairness. It operates in a top-down fashion -- as commonly observed in real-world applications -- and is compatible with various local algorithms. The second one extends the recently proposed General Yankee Swap to the multilevel setting. This extension comes with efficiency guarantees only, but we show that it preserves excellent fairness properties in practice.