The Hospital/Residents (HR) problem is an extensively studied many-one matching with preferences problem. It is known for its application in the National Resident Matching Program, which allocates medical interns (or residents) to hospitals. The celebrated Gale–Shapley algorithm guarantees that a stable matching always exists and can be efficiently computed.
We study the Hospital/Residents problem with Sizes (HRS), a generalisation where each agent a is a group of residents of size s(a). Feasibility and stability of the matching are defined accordingly. Unlike the classical HR problem, an instance of HRS may not admit a stable matching. It is known that deciding whether an instance admits a stable matching is NP-hard.
In this talk, we provide an efficient algorithm for computing a stable matching in all instances of a restricted version of HRS. In this talk, we discuss a variation of the classical stability notion called occupancy-stable and a polynomial-time algorithm to compute the same. Moreover, computing a maximum-size occupancy-stable matching is NP-hard. We complement our hardness result by providing an approximation algorithm.
