JOGOS DE SALÃO E O CASAMENTO ESTÁVEL

Authors

  • Jeferson Lesbão de Siqueira
  • Nei Yoshihiro Soma

DOI:

https://doi.org/10.69609/1516-2893.2024.v30.n1.a3842

Keywords:

Algorithm, Data Structures, Parlor Games, Stable Marriage, Gale-Shapley

Abstract

The problem known as SM (Stable Marriage) consists of solving the problem of marriage between an even number of people, forming couples, so that no one can unilaterally dissolve their marriage whose applicability includes the assignment of newly graduated doctors to hospitals, students to schools and human organs available for transplantation to recipients. This article aims to present an introduction to Von Neumann's ‘Parlour Games’, while focusing on the Stable Marriage problem. The text gives a brief introduction to the problem's history and relevance, presenting its description, an example case, and the implementation of its most common resolution algorithm, along with a stability check algorithm implementation.

References

GALE, D.; SHAPLEY, E. L. S. College admissions and the Stability of Marriage, The American Mathematical Monthly, v. 69, n. 1, p. 9-15, 1962.

GUSFIELD, D.; IRVING, R. algorithms. [S.l.]: MIT press, 1989. W. The stable marriage problem: structure and KNUTH, D. E. Marriage stables et leurs relations avec d’autres probl`emes combinatoires. Les Presses de l’Universit´e de Montréal, 1976.

NOBEL, The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012. Site Nobel Prize. Disponível em: https://www.nobelprize.org/prizes/economic-sciences/2012/summary/. Acesso em: 03 de Outubro de 2023.

ROBERTSON, J.; WEBB, W. Cake-cutting algorithms: be fair if you can, AK Peters, Natick, 1998.

STEINHAUS, H., The problem of fair division, Econometrica, v. 16, p. 101-104, 1948.

STROMQUIST, W. How to Cut a Cake Fairly. American Mathematical, Monthly 18, no. 8 (October), p. 640-644, 1980

VON NEUMANN, J. From Parlor Games to Social Science: von Neumann, Morgenstern and the Creation of Game Theory, 1928 – 1944 J. von Neumann, 1928, Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 1928, 100, pp. 295- 320; traduzido por S. Bargmann como “On the Theory of Games of Strategy,” em capítulo de Contributions to the theory of games. Vol. 4. Eds.: Albert Tucker and T. Duncan Luce. Princeton: Princeton U. Press, 1959, pp. 13-42.

Downloads

Published

2024-06-06

Issue

Vol. 30 No. 1 (2024)

Section

Articles

License

Creative Commons License

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

A submissão de originais para este periódico implica na transferência, pelos autores, dos direitos de publicação impressa e digital. Os direitos autorais para os artigos publicados são do autor, com direitos do periódico sobre a primeira publicação. Os autores somente poderão utilizar os mesmos resultados em outras publicações indicando claramente este periódico como o meio da publicação original.