Document Open Access Logo

Popular Matchings with Lower Quotas

Authors Meghana Nasre, Prajakta Nimbhorkar

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.44.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Meghana Nasre
Prajakta Nimbhorkar

Cite As Get BibTex

Meghana Nasre and Prajakta Nimbhorkar. Popular Matchings with Lower Quotas. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.44

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.

Subject Classification

Keywords
  • bipartite matchings
  • preferences
  • hospital residents
  • lower-quota
  • popular matchings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Péter Biró, Tamás Fleiner, Robert W. Irving, and David F. Manlove. The College Admissions Problem with Lower and Common Quotas. Theoretical Computer Science, 411(34-36):3136-3153, 2010. Google Scholar
  2. Péter Biró, Robert W. Irving, and David Manlove. Popular Matchings in the Marriage and Roommates Problems. In Proceedings of 7th International Conference on Algorithms anc Complexity, pages 97-108, 2010. Google Scholar
  3. Florian Brandl and Telikepalli Kavitha. Popular Matchings with Multiple Partners. CoRR, abs/1609.07531 (To appear in Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science), 2016. Google Scholar
  4. Ágnes Cseh and Telikepalli Kavitha. Popular Edges and Dominant Matchings. In Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization, pages 138-151, 2016. Google Scholar
  5. David Gale and Llyod Shapley. College Admissions and the Stability of Marriage. American Mathematical Monthly, 69:9-14, 1962. Google Scholar
  6. David Gale and Marilda Sotomayor. Some Remarks on the Stable Matching Problem. Discrete Applied Mathematics, 11(3):223-232, 1985. Google Scholar
  7. Peter Gärdenfors. Match making: Assignments based on bilateral preferences. Behavioral Science, 20(3):166-173, 1975. Google Scholar
  8. Koki Hamada, Kazuo Iwama, and Shuichi Miyazaki. The Hospitals/Residents Problem with Lower Quotas. Algorithmica, 74(1):440-465, 2016. Google Scholar
  9. M. Hirakawa, Y. Yamauchi, S. Kijima, and M. Yamashita. On The Structure of Popular Matchings in The Stable Marriage Problem - Who Can Join a Popular Matching? In Proceedings of the 3rd International Workshop on Matching Under Preferences, 2015. Google Scholar
  10. Chien-Chung Huang and Telikepalli Kavitha. Popular Matchings in the Stable Marriage Problem . Information and Computation, 222:180-194, 2013. Google Scholar
  11. Telikepalli Kavitha. A Size-Popularity Tradeoff in the Stable Marriage Problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  12. Telikepalli Kavitha. Popular Half-Integral Matchings. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, pages 22:1-22:13, 2016. Google Scholar
  13. Zoltán Király. Better and simpler approximation algorithms for the stable marriage problem. Algorithmica, 60(1):3-20, 2011. URL: http://dx.doi.org/10.1007/s00453-009-9371-7.
  14. Meghana Nasre and Prajakta Nimbhorkar. Popular Matching with Lower Quotas. CoRR, abs/1704.07546, 2017. URL: http://arxiv.org/abs/1704.07546.
  15. Meghana Nasre and Amit Rawat. Popularity in the Generalized Hospital Residents Setting. In Proceedings of the 12th International Computer Science Symposium in Russia, pages 245-259, 2017. Google Scholar
  16. Alvin E. Roth. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. Journal of Political Economy, 92(6):991-1016, 1984. Google Scholar
  17. Alvin E. Roth. On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets. Econometrica, 54(2):425-427, 1986. Google Scholar
  18. Yu Yokoi. Envy-Free Matchings with Lower Quotas. CoRR, abs/1704.04888 (To appear in Proceedings of the 28th International Symposium on Algorithms and Computation), 2017. URL: http://arxiv.org/abs/1704.04888.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact