Matroids are Equitable by Hannaneh Akrami

Abstract: We show that if the ground set of a matroid can be partitioned into k≥2 bases, then for any given subset S of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with S may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó (Electron.~J.~Comb.~2011) in the affirmative. We also investigate equitable splittings of two disjoint sets S1 and S2, and show that there is a partition into k bases such that the sizes of the intersections with S1 may differ by at most one and the sizes of the intersections with S2 may differ by at most two; this is the best possible one can hope for arbitrary matroids.

We also derive applications of this result into matroid constrained fair division problems. We show that there exists a matroid-constrained fair division that is envy-free up to 1 item if the valuations are identical and tri-valued additive. We also show that for bi-valued additive valuations, there exists a matroid-constrained allocation that provides everyone their maximin share.

This is based on joint work with Siyue Liu, Roshan Raj, and László A. Végh.

Speaker Bio: Hannaneh Akrami is a postdoctoral fellow at the University of Bonn and a Minerva Fast-track fellow at MPI-Informatik. She obtained her PhD from the University of Saarlandes and MPI-Informatik in 2024 and completed a BSc from Sharif University of Technology in 2019. Her interests are in fair division, Algorithmic Game theory, Combinatorics, Graph theory and Approximation algorithms.