Matching Hospitals with Inseparable Couples Proven NP-Hard

In a new paper, computer scientists Zeyuan Hu and C. Gregory Plaxton tackle a long-standing open problem in game theory: the complexity of finding a coalition-stable assignment in the Hospitals/Residents with Inseparable Couples (HRIC) model. The HRIC problem models real-world scenarios where couples must be matched together to the same hospital (or course), creating constraints that classical stable matching algorithms cannot handle. Building on earlier NP-hardness results by McDermid and Manlove, the authors prove that even when every hospital has capacity at most two and every resident belongs to a couple of size two, finding an assignment that is stable under coalitional deviations is NP-hard. This means there is no efficient algorithm that guarantees to find such an assignment, and the problem is likely computationally intractable at scale.

The result directly addresses an open question posed by Rodríguez and Manlove in recent work on course allocation. Rodríguez and Manlove had shown NP-hardness for three of four stability notions but left coalition stability unresolved. Hu and Plaxton close that gap, showing coalition stability is also NP-hard. Additionally, they introduce a new notion called unitwise-coalition stability and prove that intractability extends to that variant as well. For practitioners in hospital residency matching, university course allocation, and other two-sided markets with inseparable pairs, this means that optimal stable assignments may be infeasible to compute, forcing reliance on approximation or heuristic methods.