@article{10.1145/3728367,
author = {Viswanathan, Vignesh and Zick, Yair},
title = {A General Framework for Fair Allocation under Matroid Rank Valuations},
year = {2025},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
issn = {2167-8375},
url = {https://doi.org/10.1145/3728367},
doi = {10.1145/3728367},
abstract = {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.},
note = {Just Accepted},
journal = {ACM Trans. Econ. Comput.},
month = apr
}