Popular matchings with lower quotas

DOI10.4230/LIPICS.FSTTCS.2017.44zbMATH Open1493.91094arXiv1704.07546OpenAlexW2964264698MaRDI QIDQ5136336FDOQ5136336

Authors: Meghana Nasre, Prajakta Nimbhorkar 

Publication date: 25 November 2020

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=(mathcalRcupmathcalH,E)$ where $mathcalR$ and $mathcalH$ 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, and $M$ is said to be feasible if every resident is assigned to at most one hospital and a hospital $h$ is assigned at least $q^{-}(h)$ and at most $q^{+}(h)$ 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^{\prime }$ gets more votes than $M$ when vertices vote between $M$ and $M^{\prime }$. 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.

Full work available at URL: https://arxiv.org/abs/1704.07546

Recommendations

• How Good Are Popular Matchings
• Popularity in the generalized hospital residents setting
• The hospitals/residents problem with lower quotas
• The Hospitals/Residents Problem with Quota Lower Bounds
• scientific article; zbMATH DE number 7278072

zbMATH Keywords

preferencesbipartite matchingspopular matchingshospital residentslower-quota

Mathematics Subject Classification ID

Matching models (91B68)

Cites Work

• Some remarks on the stable matching problem
• The hospitals/residents problem with lower quotas
• College Admissions and the Stability of Marriage
• The college admissions problem with lower and common quotas
• Popular matchings in the marriage and roommates problems
• Better and simpler approximation algorithms for the stable marriage problem
• Popular matchings in the stable marriage problem
• Popular edges and dominant matchings
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• Popular Half-Integral Matchings.
• Popularity in the generalized hospital residents setting
• Title not available (Why is that?)

Cited In (11)

• Envy-free matchings with lower quotas
• The hospitals/residents problem with lower quotas
• Maintaining Near-Popular Matchings
• Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
• Popular matchings of desired size
• How Good Are Popular Matchings
• Envy-freeness and relaxed stability: hardness and approximation algorithms
• Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas
• Refined computational complexities of hospitals/residents problem with regional caps
• Critical Relaxed Stable Matchings with Two-Sided Ties
• Popularity in the generalized hospital residents setting

This page was built for publication: Popular matchings with lower quotas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136336)