Hospital-Residents (HR) problem is a very well-studied matching problem in the context of matching with preferences. In this problem, residents are to be assigned to hospitals in the presence of preferences of both residents and hospitals. Hospitals may also have demand, in addition to the capacity, for their smooth functioning. In literature, this is modeled as Hospital-Residents problem with Lower Quotas (HRLQ problem). Similarly, there may be a requirement that some residents must be matched in a particular round of assignments of residents to hospitals. We model this by allowing residents to specify its demand as a part of the input, and call it as a Hospital-Residents problem with two-sided Lower Quotas (HR2LQ problem).

The input to our problem is a bipartite graph G=(R U H,E), each vertex in R U H has a strict preference ordering over its neighbours. The set R and H denote the set of residents and hospitals respectively. Each hospital has a lower quota (demand) and an upper quota (capacity) denoting the minimum and maximum number of residents that can be assigned to it. Residents have upper quota equal to one and lower quota at most one. The goal is to assign hospitals to residents satisfying their demands and capacities and respecting the preferences submitted by the agents. Stability is one of the well-accepted notion of optimality. However, it is well-known that a stable matching satisfying the demands and capacities of every agent may not always exist. Hence, we study an alternate notion of optimality called popularity. We show that whenever the set of feasible matchings is non-empty, there always exists a matching that is popular among the set of feasible matching. We give a polynomial time algorithm to compute such a matching.

We discuss extensions of this work to compute maximum cardinality popular matchings in the HR2LQ setting.

This is joint work with Meghana Nasre, Prajakta Nimbhorkar and Ankita Sarkar.