Gergely Csáji

Gergely Csáji, David Manlove, Iain McBride et al.

In this paper, we study the Hospitals / Residents problem with Couples (HRC), where a solution is a stable matching or a report that none exists. We present a novel polynomial-time algorithm that can find a near-feasible stable matching (adjusting the hospitals' capacities by at most 1) in an HRC instance where the couples' preferences are sub-responsive (i.e., if one member switches to a better hospital, then the couple also improves) and sub-complete (i.e., each pair of hospitals that are individually acceptable to both members are jointly acceptable for the couple) by reducing it to an instance of the Stable Fixtures problem. We also present a polynomial-time algorithm for HRC in a sub-responsive, sub-complete instance that is a Dual Market, or where all couples are one of several possible types. We show that our algorithm also implies the polynomial-time solvability of a stable b-matching problem, where the underlying graph is a multigraph with loops. We complement our algorithms with several hardness results. We show that HRC with sub-responsive and sub-complete couples is NP-hard, even with other strong restrictions. We also show that HRC with a Dual Market is NP-hard under several simultaneous restrictions. Finally, we show that the problem of finding a matching with the minimum number of blocking pairs in HRC is not approximable within $m^{1-\varepsilon}$, for any $\varepsilon>0$, where $m$ is the total length of the hospitals' preference lists, unless P=NP, even if each couple applies to only one pair of hospitals. Our polynomial-time solvability results greatly expand the class of known tractable instances of HRC and provide a useful tool for designing better and more efficient mechanisms in the future.

Gergely Csáji, Zhaohong Sun

Stable matching theory is the foundation of centralized clearinghouses worldwide, from school choice programs to medical residency allocations. However, incorporating complex distributional goals-such as multi-dimensional diversity quotas or sibling co-assignment guarantees-often compromises stability or renders the problem computationally intractable. The existing literature typically addresses this tension by weakening stability to accommodate distributional constraints. In contrast, the reverse question remains largely unexplored: if we restrict attention to stable matchings, to what extent can such distributional objectives be achieved? In this paper, we resolve this tension by introducing a general, polynomial-time algorithmic framework to optimize arbitrary institutional (or even two-sided) objectives within the set of stable matchings. We prove that for any polynomial-time computable set functions $g_i$ evaluating the assigned students at institutions $i \in I$, a stable matching minimizing either the utilitarian objective $\sum_{i\in I} g_i$ or the egalitarian objective $\max_{i\in I} g_i$ can be found efficiently. Our approach leverages the structural properties of stable matchings, mapping arbitrary set functions to linear edge weights. We apply this theorem to efficiently solve major open practical problems: finding stable matchings that minimally violate overlapping diversity quotas (under both total and maximum violations) and maximizing the number of sibling families assigned to the same institution. Even when the distributional objective is prioritized, our algorithm helps to quantify the ``price of stability'', i.e., the gap between the maximally diverse matching and the maximally diverse stable matching.