2026/07/21 by Zeyuan Hu, C. Gregory Plaxton
#cs.GT
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.