Maximally Diverse Stable Matchings: Optimizing Arbitrary Institutional Objectives

Stable matching theory underpins major centralized clearinghouses worldwide, from school choice programs to medical residency allocations. However, a persistent challenge has been incorporating distributional goals—such as multi-dimensional diversity quotas or sibling co-assignment guarantees—without compromising stability. The existing literature typically weakened stability to accommodate such constraints. A new preprint by Gergely Csáji and Zhaohong Sun turns this approach on its head: they restrict attention to stable matchings and ask how well distributional objectives can still be achieved.

Their key contribution is a general, polynomial-time algorithmic framework that can optimize arbitrary institutional (or even two-sided) objectives within the set of stable matchings. They prove that for any polynomial-time computable set function evaluating assigned students at institutions, a stable matching minimizing either the utilitarian sum or the egalitarian maximum can be found efficiently. The algorithm leverages structural properties of stable matchings to map arbitrary set functions to linear edge weights, enabling standard optimization techniques.

The framework directly addresses major open practical problems. It can find stable matchings that minimally violate overlapping diversity quotas under both total and maximum violation metrics. It can also maximize the number of sibling families assigned to the same institution—a notoriously difficult constraint. Additionally, even when distributional objectives are prioritized, the algorithm helps quantify the "price of stability"—the gap between the maximally diverse matching and the maximally diverse stable matching.

The implications are significant for any market using stable matching with fairness or diversity requirements. School districts can now pursue diversity goals without risking instability, and medical residency programs can better accommodate couples or family preferences. By showing that stability and diversity are not inherently at odds, this work provides a practical tool for institutional designers and opens new avenues for algorithmic fairness research.