Constrained Fair Allocations via Partition Matroid Reductions
2026-08-31 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study fair ways to divide indivisible items among people when certain complex rules (called matroid constraints) apply. They focus on whether it is always possible to find an allocation where no one envies another's share too much (envy-free up to one good, EF1). They extend previous results that worked for simpler rule sets to more complex ones called laminar matroids, proving it for three people and partially for four. They also show fair divisions exist under some other matroid types, like transversal matroids, under certain conditions.
indivisible goodsadditive valuationsmatroid constraintsenvy-free up to one good (EF1)partition matroidslaminar matroidstransversal matroidsgraphic matroidsgammoidsfair allocation
Authors
Benjamin Cookson, Nisarg Shah
Abstract
We study fair allocation of indivisible goods under additive valuations and matroid constraints. A challenging open question is whether a complete and feasible envy-free up to one good (EF1) allocation exists under every matroid that admits a complete and feasible allocation. The state-of-the-art result by Biswas and Barman [2018] positively resolves this question for partition matroids. Our first result positively resolves it for laminar matroids, which generalize partition matroids, when there are three agents. Our technique reduces this general existence question to finding an EF1 allocation satisfying a mild additional condition under a single finite-sized key laminar matroid, and we establish the required allocation by case analysis. We show that our technique somewhat extends to four agents, reducing the analogous problem to finding EF1 allocations under two finite-sized laminar matroids, although we are unable to establish their existence. We also use recent matroid decomposition results to establish EF1 existence under broader classes of matroids. Specifically, we show that EF1 allocations always exist under transversal matroids whenever a complete allocation is feasible, and obtain existence results for graphic matroids and gammoids under stronger assumptions.