Matroids are Equitable

Prelegent(ci)

Hannaneh Akrami

Afiliacja

Max Planck Institute for Informatics and University of Bonn, Germany

Język referatu

angielski

Termin

7 maja 2026 12:15

Pokój

p. 4060

Seminarium

Seminarium „Ekonomia algorytmiczna”

---

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 a joint work with Siyue Liu, Roshan Raj, and László A. Végh.

Please find the paper here: https://arxiv.org/abs/2507.12100

---