License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.44
URN: urn:nbn:de:0030-drops-83937
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8393/
Go to the corresponding LIPIcs Volume Portal

Nasre, Meghana ; Nimbhorkar, Prajakta

Popular Matchings with Lower Quotas

pdf-format:
LIPIcs-FSTTCS-2017-44.pdf (0.6 MB)

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 residents
and 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 M' gets more votes than M when vertices vote between M and M'. 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.

BibTeX - Entry

@InProceedings{nasre_et_al:LIPIcs:2018:8393,
  author =	{Meghana Nasre and Prajakta Nimbhorkar},
  title =	{{Popular Matchings with Lower Quotas}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8393},
  URN =		{urn:nbn:de:0030-drops-83937},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.44},
  annote =	{Keywords: bipartite matchings, preferences, hospital residents, lower-quota, popular matchings}
}

Keywords: bipartite matchings, preferences, hospital residents, lower-quota, popular matchings
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI