An efficient implementation of the Gale and Shapley "propose-and-reject" algorithm

Nasia Zacharia, Evi Papaioannou, Christos Kaklamanis

Abstract


We consider a version of the Hospitals/Residents problem which was first defined in 1962 by Gale and Shapley [9] under the name "College Admissions Problem". In particular, we consider the Firms/Candidates problem, where each Firm wishes to hire at least one Candidate and each Candidate can be finally assigned to a single Firm. We present an efficient implementation of the Gale and Shapley "propose-and-reject" algorithm when applied to the case of the Firms/Candidates problem.

Keywords


Stable matching; Gale and Shapley algorithm; the Firms/Candidates problem; efficient implementation; "propose-and-reject" algorithm

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.4

References

D. J. Abraham, R. W. Irving and D. F. Manlove, The student-project allocation problem, In Proceedings of the 14th International Symposium on Algorithms and Computation (ISAAC 2003) (2003), LNCS Springer 2906, 474-484.

H. Assiyatun, B. Rahadjeng, E. T. Baskoro, The connected size Ramsey number for matchings versus small disconnected graphs, Electronic Journal of Graph Theory and Applications 7(1) (2019), 113–119.

Canadian Resident Matching Service, How the matching algorithm works. Web document available at https://www.carms.ca/the-match/how-it-works/.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, 3rd ed. MIT press, 2009.

P.-T. Do, N.-K. Le, V.-T. Vu, Efficient maximum matching algorithms for trapezoid graphs,

Electronic Journal of Graph Theory and Applications 5(1) (2017), 7–20.

P. Golle, A Private Stable Matching Algorithm, In Proceedings of the 2006 International Conference on Financial Cryptography and Data Security (FC 2006) (2006), LNCS Springer 4107, 65–80.

D. Gusfield and R.W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.

D. Gale and L. S. Shapley, College admissions and the stability of marriage, Office of Naval Research, 1960-1961.

D. Gale, L. S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly 69(1) (1962), 9-15.

D. Gale and M. Sotomayor, Some remarks on the stable matching problem, Discrete Applied Mathematics 11 (1985), 223-232.

R. W. Irving, Matching medical students to pairs of hospitals: a new variation on an old theme, In Proceedings of the 6th European Symposium on Algorithms (ESA 1998) (1998), LNCS Springer 1461, 381-392.

R. W. Irving, Man-exchange stable marriage, University of Glasgow, Computing Science Department Research Report, TR-2004-177, 2004.

R. W. Irving, The cycle roommates problem: a hard case of kidney exchange, Information Processing Letters 103(1) (2007), 1-4.

R. W. Irving, D. F. Manlove, S. Scott, The Hospitals/Residents Problem with Ties, In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT2000) (2000), 259–271.

K. Iwama, S. Miyazaki, A Survey of the Stable Marriage Problem and Its Variants, In Proceedings of the 2008 IEEE International Conference on Informatics Education and Research for Knowledge-Circulating Society (2008), 131–136.

J. Kleinberg, E. Tardos, Algorithm Design. Pearson, 2006.

D. E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, In CRM Proceedings and Lecture Notes, volume 10, American Mathematical Society (1997).

E. Kujansuu, T. Lindberg, and E. M¨akinen, The stable roommates problem and chess tournament pairings, Divulgaciones Matem´aticas, 7(1) (1999), 19-28.

Laszlo Lovasz and M. D. Plummer, Matching Theory, Annals of Discrete Mathematics 121 (1986).

B. M. Maggs, R. K. Sitaraman, Algorithmic Nuggets in Content Delivery, ACM SIGCOMM Computer Communication Review, 45(3), 2015, 52–66.

V. S. Malhotra, On the stability of multiple partner stable marriages with ties, In Proceedings of the 12th Annual European Symposiumon Algorithms (ESA 2004) (2004), LNCS Springer 3221, 508-519.

D. Manlove, Hospitals/Residents Problem, Encyclopedia of Algorithms, Chapter 180 (2008), 390–394.

D. F. Manlove, Algorithms of Matching under preferences, World Scientific Publishing (2013), p. 524.

D. F. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, and Y. Morita, (2002) Hard variants of stable marriage, Theoretical Computer Science 276(1-2) (2002), 261–279.

I. McBride and D. F. Manlove, The Hospitals / Residents Problem with Couples: Complexity and Integer Programming models. Technical report, Computing Research Repository, Cornell University Library (2013).

National Kidney Foundation, Organ Donation and Transplantation Statistics https://www.kidney.org/news/newsroom/factsheets/Organ-Donation-and-Transplantation-

Stats), Accessed November 7, 2018.

Stable allocations and the practice of market redesign, Scientific Background on the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012 compiled by the Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences (2012).

National Resident Matching Program, http://www.nrmp.org/

A. 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) (1984), 991-1016.

A. E. Roth, On the allocation of residents to rural hospitals: a general property of two-sided matching markets, Econometrica, 54 (1986), 425-427.

A. E. Roth, Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions, International Journal of Game Theory, Special Issue in Honor of David Gale on his 85th birthday, 36 (2008), 537–569.

A. E. Roth and M. A. O. Sotomayor, Two-sided matching: a study in game-theoretic modeling and analysis, Econometric Society Monographs 18 (1990), Cambridge University Press.

A. E. Roth, T. Sonmez, and M. U. Unver, Pairwise kidney exchange, Journal of Economic Theory 125(2) (2005), 151-188.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats