quotas (LQ). The input instance consists of a bipartite graph $ G=(\mathcal {R}\cup\mathcal {H}, E) $ where $\mathcal {R} $ and $\mathcal {H} $ denote sets of residents and hospitals respectively. Every vertex has a preference list that imposes a strict ordering on its neighbors. In addition, each hospital $ h $ has an associated upper-quota $ q^+(h) $ and lower-quota $ q^-(h) $. A matching $ M $ in $ G $ is an assignment of residents to hospitals …
We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph where and denote sets of residents and hospitals respectively. Every vertex has a preference list that imposes a strict ordering on its neighbors. In addition, each hospital has an associated upper-quota and lower-quota . A matching in is an assignment of residents to hospitals, and is said to be feasible if every resident is assigned to at most one hospital and a hospital is assigned at least and at most residents. Stability is a de-facto notion of optimality in a model where both sets of vertices have preferences. A matching is stable if no unassigned pair has an incentive to deviate from it. It is well-known that an instance of the HRLQ problem need not admit a feasible stable matching. In this paper, we consider the notion of popularity for the HRLQ problem. A matching is popular if no other matching gets more votes than when vertices vote between and . When there are no lower quotas, there always exists a stable matching and it is known that every stable matching is popular. We show that in an HRLQ instance, although a feasible stable matching need not exist, there is always a matching that is popular in the set of feasible matchings. We give an efficient algorithm to compute a maximum cardinality matching that is popular amongst all the feasible matchings in an HRLQ instance.