Title: Envy-free Matchings with Lower Quotas,
Abstract: While every instance of the Hospitals/Residents problem admits a stable
matching, the problem with lower quotas (HR-LQ) has instances with no stable
matching. For such an instance, we expect the existence of an envy-free
matching, which is a relaxation of a stable matching preserving a kind of
fairness property. In this paper, we investigate the existence of an envy-free
matching in several settings, in which hospitals have lower quotas and not all
doctor-hospital pairs are acceptable. We first show that, for an HR-LQ
instance, we can efficiently decide the existence of an envy-free matching.
Then, we consider envy-freeness in the Classified Stable Matching model due to
Huang (2010), i.e., each hospital has lower and upper quotas on subsets of
doctors. We show that, for this model, deciding the existence of an envy-free
matching is NP-hard in general, but solvable in polynomial time if quotas are
paramodular.