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.ISAAC.2017.67
URN: urn:nbn:de:0030-drops-82205
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8220/
Go to the corresponding LIPIcs Volume Portal

Yokoi, Yu

Envy-free Matchings with Lower Quotas

pdf-format:
LIPIcs-ISAAC-2017-67.pdf (0.5 MB)

Abstract

While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property.
In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas. We first provide an algorithm that decides whether a given HR-LQ instance has an envy-free matching or not. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (2010), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.

BibTeX - Entry

@InProceedings{yokoi:LIPIcs:2017:8220,
  author =	{Yu Yokoi},
  title =	{{Envy-free Matchings with Lower Quotas}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{67:1--67:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8220},
  URN =		{urn:nbn:de:0030-drops-82205},
  doi =		{10.4230/LIPIcs.ISAAC.2017.67},
  annote =	{Keywords: stable matchings, envy-free matchings, lower quotas, polynomial time algorithm, paramodular functions}
}

Keywords: stable matchings, envy-free matchings, lower quotas, polynomial time algorithm, paramodular functions
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

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