Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties

Motivated by a serious issue that hospitals in rural areas suffer from shortage of residents, we study the Hospitals/Residents model in which hospitals are associated with lower quotas and the goal is to satisfy them as much as possible. When preference lists are strict, the number of residents assigned to each hospital is the same in any stable matching due to the famous rural hospitals theorem, so there is no room for algorithmic interventions. However, when ties are introduced in preference lists, this is not the case since the number of residents may vary over stable matchings. The main focus of this paper is to investigate how much we can utilize this flexibility to aid rural hospitals, in the presence of ties. We first show that the exact optimization is NP-hard and incompatible with strategy-proofness for residents. We then propose a linear-time strategy-proof algorithm whose approximation ratio is substantially better than a naive algorithm that breaks ties arbitrarily and applies the Gale-Shapley algorithm.