How Good Are Popular Matchings?

Authors Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, Amit Rawat



PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.9.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Krishnapriya A M
  • Citrix Research and Development India
Meghana Nasre
  • Indian Institute of Technology Madras India
Prajakta Nimbhorkar
  • Chennai Mathematical Institute India and UMI ReLaX
Amit Rawat
  • University of Massachusetts Amherst USA

Cite As Get BibTex

Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat. How Good Are Popular Matchings?. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SEA.2018.9

Abstract

In this paper, we consider the Hospital Residents problem (HR) and the Hospital Residents problem with Lower Quotas (HRLQ). In this model with two sided preferences, stability is a well accepted notion of optimality. However, in the presence of lower quotas, a stable and feasible matching need not exist. For the HRLQ problem, our goal therefore is to output a good feasible matching assuming that a feasible matching exists. Computing matchings with minimum number of blocking pairs (Min-BP) and minimum number of blocking residents (Min-BR) are known to be NP-Complete. The only approximation algorithms for these problems work under severe restrictions on the preference lists. We present an algorithm which circumvents this restriction and computes a popular matching in the HRLQ instance. We show that on data-sets generated using various generators, our algorithm performs very well in terms of blocking pairs and blocking residents. Yokoi [Yokoi, 2017] recently studied envy-free matchings for the HRLQ problem. We propose a simple modification to Yokoi's algorithm to output a maximal envy-free matching. We observe that popular matchings outperform envy-free matchings on several parameters of practical importance, like size, number of blocking pairs, number of blocking residents.
In the absence of lower quotas, that is, in the Hospital Residents (HR) problem, stable matchings are guaranteed to exist. Even in this case, we show that popularity is a practical alternative to stability. For instance, on synthetic data-sets generated using a particular model, as well as on real world data-sets, a popular matching is on an average 8-10% larger in size, matches more number of residents to their top-choice, and more residents prefer the popular matching as compared to a stable matching. Our comprehensive study reveals the practical appeal of popular matchings for the HR and HRLQ problems. To the best of our knowledge, this is the first study on the empirical evaluation of popular matchings in this setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • bipartite graphs
  • hospital residents
  • lower-quotas
  • popular matchings

Metrics

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

References

  1. Data sets. URL: http://www.cse.iitm.ac.in/~meghana/projects/datasets/popular.zip.
  2. HR with couples data-set. URL: http://researchdata.gla.ac.uk/303/.
  3. National Residency Matching Program. URL: http://www.nrmp.org.
  4. Scottish Foundation Association Scheme. URL: http://www.matching-in-practice.eu/the-scottish-foundation-allocation-scheme-sfas.
  5. Source code repository. URL: https://github.com/rawatamit/GraphMatching.
  6. David J. Abraham, Robert W. Irving, Telikepalli Kavitha, and Kurt Mehlhorn. Popular Matchings. SIAM Journal on Computing, 37(4):1030-1045, 2007. Google Scholar
  7. Péter Biró, David F. Manlove, and Shubham Mittal. Size versus stability in the marriage problem. Theoretical Computer Science, 411(16):1828-1841, 2010. Google Scholar
  8. Péter Biró, Robert W. Irving, and David Manlove. Popular matchings in the marriage and roommates problems. In 7th International Conference on Algorithms and Complexity CIAC, pages 97-108, 2010. Google Scholar
  9. Florian Brandl and Telikepalli Kavitha. Popular matchings with multiple partners. In Proceedings of 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 19:1-19:15, 2017. Google Scholar
  10. Ágnes Cseh. Popular matchings. In U. Endriss, editor, Trends in Computational Social Choice, pages 105-122. COST (European Cooperation in Science and Technology), 2017. Google Scholar
  11. Ágnes Cseh and Telikepalli Kavitha. Popular Edges and Dominant Matchings. In Proceedings of the Eighteenth Conference on Integer Programming and Combinatorial Optimization, pages 138-151, 2016. Google Scholar
  12. David Gale and Lloyd Shapley. College Admissions and the Stability of Marriage. American Mathematical Monthly, 69:9-14, 1962. Google Scholar
  13. Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989. Google Scholar
  14. Koki Hamada, Kazuo Iwama, and Shuichi Miyazaki. The Hospitals/Residents Problem with Lower Quotas. Algorithmica, 74(1):440-465, 2016. Google Scholar
  15. Nicole Immorlica and Mohammad Mahdian. Marriage, honesty, and stability. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 53-62, 2005. Google Scholar
  16. Telikepalli Kavitha. A Size-Popularity Tradeoff in the Stable Marriage Problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  17. David F. Manlove, Iain McBride, and James Trimble. "Almost-stable" matchings in the Hospitals / Residents problem with Couples. Constraints, 22(1):50-72, 2017. Google Scholar
  18. Meghana Nasre and Prajakta Nimbhorkar. Popular matchings with lower quotas. In Proceedings of 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 44:1-44:15, 2017. Google Scholar
  19. 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
  20. Yu Yokoi. Envy-free matchings with lower quotas. In Proceedings of the 28th International Symposium on Algorithms and Computation, ISAAC, pages 67:1-67:12, 2017. Google Scholar
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