JOGOS DE SALÃO E O CASAMENTO ESTÁVEL

Autores

  • Jeferson Lesbão de Siqueira
  • Nei Yoshihiro Soma

DOI:

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

Palavras-chave:

Algoritmo, Estrutura de Dados, Jogos de Salão, Casamento Estável, Gale-Shapley

Resumo

O problema do casamento estável, também conhecido como SM (Stable Marriage) consiste em resolver o problema do casamento entre um número par de pessoas, formando casais, de forma que ninguém possa unilateralmente dissolver seu casamento cuja aplicabilidade inclui a atribuição de médicos recém-formados a hospitais, estudantes a escolas e órgãos humanos disponíveis para transplante a receptores. Este artigo visa apresentar uma introdução aos jogos de salão de Von Neumann, com enforque no problema do casamento estável. O texto faz uma introdução ao histórico do problema e sua relevância, a apresenta a descrição e um caso de exemplo do principal algoritmo para resolução, junto de um algoritmo para verificação de estabilidade.

Referências

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

Publicado

2024-06-06

Edição

Seção

Artigos