A General Framework for Fair Allocation under Matroid Rank Valuations

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 present a simple algorithmic 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, this 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. We also extend this framework to the setting of binary chores—items with marginal values -1 or 0—and similarly show that it can be used to maximize any justice criteria satisfying some mild assumptions.