Paper Info
Title
Popular Matching with Lower Quotas.
Abstract
We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph G = (R U H, E) where R and 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 has an associated upper-quota and a lower-quota. A matching M in G is an assignment of residents to hospitals, and M is said to be feasible if every resident is assigned to at most one hospital and a hospital is assigned at least its lower-quota many residentsand at most its upper-quota many 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 M is popular if no other matching Mu0027 gets more votes than M when vertices vote between M and Mu0027. 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.
Year
DOI
Venue
2017
10.4230/LIPIcs.FSTTCS.2017.44
FSTTCS
DocType
Volume
Citations 
Conference
abs/1704.07546
1
PageRank 
References 
Authors
0.38
2
2
Name
Order
Citations
PageRank
Meghana Nasre19812.80
Prajakta Nimbhorkar217015.04