A Simple, General Framework for Fair Allocation Under Matroid Rank Valuations


Friday, October 14, 2022, 1:00pm to 2:30pm


SEC 1.413, and streamed via Zoom: https://harvard.zoom.us/j/95184948637?pwd=bXBIc2U5MEZ0QmRUb01WQ0o0SXRCdz09


We study the problem of fairly allocating a set of indivisible goods among agents with matroid rank valuations. We present a simple framework that efficiently computes any fairness objective that satisfies some mild assumptions. Along with maximizing a fairness objective, the framework is guaranteed to run in polynomial time, maximize utilitarian social welfare and ensure strategyproofness. Our framework can be used to achieve four different fairness objectives: (a) Prioritized Lorenz dominance, (b) Maxmin fairness, (c) Weighted leximin, and (d) Max weighted Nash welfare. In particular, our framework provides the first polynomial time algorithms to compute weighted leximin and max. weighted Nash welfare allocations for matroid rank valuations.


As always, the talk will be 1pm-2pm Eastern Time in SEC 1.413, and streamed via Zoom at the usual link: