Document Open Access Logo

Popular Matchings with Multiple Partners

Authors Florian Brandl, Telikepalli Kavitha

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2017.19.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Bipartite graphs
  • Linear programming duality
  • Gale-Shapley algorithm

Metrics

Abstract

Our input is a bipartite graph G=(A\cup B,E) where each vertex in A\cup B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to cap(a)\geq 1 many courses while each course b seeks cap(b)\geq 1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G - a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.

Cite As Get BibTex

Florian Brandl and Telikepalli Kavitha. Popular Matchings with Multiple Partners. 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. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.19

Author Details

Florian Brandl
Telikepalli Kavitha

References

  1. D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030-1045, 2007. Google Scholar
  2. G. Askalidis, N. Immorlica, A. Kwanashie, D. Manlove, and E. Pountourakis. Socially stable matchings in the hospitals/residents problem. In the 13th International Symposium on Algorithms and Data Structures (WADS), pages 85-96, 2013. Google Scholar
  3. P. Biró, R. W. Irving, and D. F. Manlove. Popular matchings in the marriage and roommates problems. In the 7th International Conference on Algorithms and Complexity (CIAC), pages 97-108, 2010. Google Scholar
  4. C. Blair. The lattice structure of the set of stable matchings with multiple partners. Mathematics of Operations Research, 13:619-628, 1988. Google Scholar
  5. Marquis de Condorcet. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie Royale, 1785. Facsimile published in 1972 by Chelsea Publishing Company, New York. Google Scholar
  6. Á. Cseh, C.-C. Huang, and T. Kavitha. Popular matchings with two-sided preferences and one-sided ties. In the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 367-379, 2015. Google Scholar
  7. Á. Cseh and T. Kavitha. Popular edges and dominant matchings. In the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 138-151, 2016. Google Scholar
  8. D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962. Google Scholar
  9. D. Gale and M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11(3):223-232, 1985. Google Scholar
  10. P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Sciences, 20(3):166-173, 1975. Google Scholar
  11. D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Boston, MA, 1989. Google Scholar
  12. K. Hamada, K. Iwama, and Shuichi Miyazaki. The hospitals/residents problem with lower quotas. Algorithmica, 74(1):440-465, 2016. Google Scholar
  13. 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 the 3rd International Workshop on Matching Under Preferences (MATCH-UP), 2015. Google Scholar
  14. C.-C. Huang. Classified stable matching. In the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1235-1253, 2010. Google Scholar
  15. C.-C. Huang and T. Kavitha. Popular matchings in the stable marriage problem. Information and Computation, 222:180-194, 2013. Google Scholar
  16. C.-C. Huang and T. Kavitha. Popularity, self-duality, and mixed matchings. In the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2294-2310, 2017. Google Scholar
  17. R. W. Irving, D. F. Manlove, and S. Scott. The hospitals/residents problem with ties. In the 7th Scandinavian Workshop on Algorithm Theory (SWAT), pages 259-271, 2000. Google Scholar
  18. R. W. Irving, D. F. Manlove, and S. Scott. Strong stability in the hospitals/residents problem. In the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 439-450, 2003. Google Scholar
  19. T. Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  20. T. Kavitha. Popular half-integral matchings. In the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 22.1-22.13, 2016. Google Scholar
  21. T. Kavitha, J. Mestre, and M. Nasre. Popular mixed matchings. Theoretical Computer Science, 412(24):2679-2690, 2011. Google Scholar
  22. D. F. Manlove. Algorithmics of Matching Under Preferences. World Scientific Publishing Company, 2013. Google Scholar
  23. M. Nasre and A. Rawat. Popularity in the generalized hospital residents setting. In the 12th International Computer Science Symposium in Russia (CSR), pages 245-259, 2017. Google Scholar
  24. National Resident Matching Program. Why the match? Web document available at URL: http://www.nrmp.org/whythematch.pdf.
  25. A. E. Roth. The evolution of the labor market for medical interns and resident: a case study in game theory. The Journal of Political Economy, 92(6):991-1016, 1984. Google Scholar
  26. A. E. Roth. Stability and polarization of interests in job matching. Econometrica, 52:47-57, 1984. Google Scholar
  27. A. 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
  28. Canadian Resident Matching Service. How the matching algorithm works. Web document available at URL: http://carms.ca/algorithm.htm.
  29. M. Sotomayor. Three remarks on the many-to-many stable matching problem. Mathematical Social Sciences, 38:55-70, 1999. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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