Hospitals/Residents with Inseparable Couples: Finding a Coalition-Stable Assignment Is NP-Hard

In recent work on course allocation, Rodríguez and Manlove consider the complexity of finding a stable assignment under four notions of stability, including two coalitional notions. In one case, which they call pair-size stability, they show that a stable assignment always exists and they provide a polynomial-time algorithm to find one. In a second case, called pair stability, they observe that an earlier NP-hardness result of McDermid and Manlove holds for a special case of course allocation called Hospitals/Residents with Sizes ($HRS$). In a third case, called first-coalition stability, they use a reduction from $HRS$ to show it is NP-hard to find a stable assignment. They leave open the complexity of finding a stable assignment under so-called coalition stability. Building on ideas from McDermid and Manlove, we resolve the open problem of Rodríguez and Manlove by showing that it is NP-hard to find a coalition-stable assignment for $HRS$. Indeed, our proof shows that the problem remains NP-hard when the hospital capacities and resident sizes are at most two. Accordingly, our NP-hardness result applies to the special case of $HRS$ known as Hospitals/Residents with Inseparable Couples ($HRIC$). Finally, we introduce a novel and natural notion of coalitional stability for both $HRS$ and course allocation, and we show that our NP-hardness result extends to this notion, which we call unitwise-coalition stability.