# Fair Division Under Cardinality Constraints

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2018.

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

- [Fair Ranking as Fair Division: Impact-Based Individual Fairness in Ranking](https://mlsanity.com/paper/2206.07247/) (2022)
- [Towards Fair Recommendation in Two-Sided Platforms](https://mlsanity.com/paper/2201.01180/) (2021)
- [Two-Sided Matching Meets Fair Division](https://mlsanity.com/paper/2107.07404/) (2021)
- [A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization](https://mlsanity.com/paper/2109.07882/) (2021)
- [Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks](https://mlsanity.com/paper/2303.00799/) (2023)
- [Fair Division with Market Values](https://mlsanity.com/paper/2410.23137/) (2024)
- [A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization](https://mlsanity.com/paper/2203.05618/) (2022)
- [A 2-opt Algorithm for Locally Optimal Set Partition Optimization](https://mlsanity.com/paper/2303.08219/) (2023)
- [First-Choice Maximality Meets Ex-ante and Ex-post Fairness](https://mlsanity.com/paper/2305.04589/) (2023)
- [Maximin Share Guarantees via Limited Cost-Sensitive Sharing](https://mlsanity.com/paper/2602.20541/) (2026)
- [Exact Cut Complexity of Equal-Length Proportional Cake Cutting](https://mlsanity.com/paper/2610.19733/) (2026)

## Abstract (arXiv)

We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i.e., the goods are categorized---and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied (unconstrained) fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Specifically, we develop efficient algorithms which compute EF1 and approximately MMS allocations in the constrained setting. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist and can be computed efficiently even under laminar matroid constraints.