Solucionador do Problema do Casamento Estável

Solucionador do Problema do Casamento Estável

O Solucionador do Problema do Casamento Estável é uma implementação interativa do algoritmo de aceitação adiada de Gale-Shapley, o algoritmo de emparelhamento de 1962 que David Gale e Lloyd Shapley provaram que sempre produz um emparelhamento estável entre dois grupos de tamanhos iguais, dadas as classificações completas de cada membro em relação ao outro lado. Esta ferramenta recebe suas listas de preferências, executa o algoritmo passo a passo e mostra o resultado como um casamento estável, uma visualização bipartida animada, mapas de calor de preferência e uma prova verificada de que não existe nenhum par de bloqueio.

O Que é o Problema do Casamento Estável?

Dados dois conjuntos disjuntos de tamanho igual — por exemplo, n homens e n mulheres, ou n candidatos e n cargos — e uma lista de preferências completa de cada membro classificando cada membro do outro lado, um emparelhamento é uma correspondência um-para-um entre os dois conjuntos. O emparelhamento é chamado de estável se nenhum par (a, b) fora do emparelhamento preferisse estar junto a ficar com seus parceiros atribuídos.

Formalmente, um emparelhamento M é estável se não houver um par de bloqueio — um par (a, b) com a emparelhado com b' e b emparelhado com a' de modo que:

Se ambas as condições forem verdadeiras, tanto a quanto b abandonariam seus parceiros atuais, o que desestabilizaria o emparelhamento. Um casamento estável é aquele onde nenhum par desse tipo existe.

O Algoritmo de Gale-Shapley

Gale e Shapley provaram — construtivamente — que um casamento estável sempre existe para qualquer conjunto de preferências e forneceram um algoritmo eficiente para encontrá-lo. O algoritmo funciona em rodadas:

1. Cada propositor solteiro propõe ao receptor de maior ranking em sua lista que ainda não o rejeitou.
2. Cada receptor que recebeu uma ou mais propostas escolhe aquela que mais prefere (comparada com qualquer noivo tentador atual) e aceita tentativamente; todos os outros são rejeitados.
3. Os propositores rejeitados tornam-se livres novamente e passam para sua próxima escolha na rodada seguinte.
4. O algoritmo termina quando cada propositor está noivo — o que é garantido que aconteça em no máximo n² propostas.

Principais Propriedades Teóricas

Existência e Unicidade

Um casamento estável sempre existe (Gale & Shapley, 1962), mas não é necessariamente único. Para um determinado conjunto de preferências, pode haver múltiplos casamentos estáveis, e eles formam uma rede ordenada por preferência conjunta.

Otimização para o Propositor

Quando um lado propõe, o Gale-Shapley produz o casamento estável ótimo para o propositor: cada propositor recebe o melhor parceiro com quem poderia ser emparelhado em qualquer casamento estável. Por um argumento simétrico, este é também o casamento péssimo para o receptor — o lado que recebe obtém o seu pior parceiro estável. Mudar o lado que propõe nesta calculadora muitas vezes altera o resultado.

À Prova de Estratégia para os Propositores

Sob o Gale-Shapley, os propositores não têm incentivo para omitir ou falsificar suas preferências: dizer a verdade é uma estratégia dominante para eles. Os receptores, no entanto, às vezes podem se beneficiar de informações estratégicas falsas — uma das razões pelas quais o mercado de hospitais e residentes nos EUA é projetado com os estudantes como o lado que propõe.

Teorema dos Hospitais Rurais

O conjunto de agentes não emparelhados é idêntico em todos os casamentos estáveis. Portanto, se sua instância tiver tamanhos desequilibrados (além do escopo desta ferramenta clássica), as mesmas pessoas ficarão sem par em cada solução estável.

Formato de Entrada

Esta calculadora espera uma linha por membro, com o nome seguido por dois pontos e uma lista de preferências completa classificada separada por vírgulas:

Requisitos:

• Ambos os grupos devem ter exatamente o mesmo número de membros.
• Cada membro deve classificar todos os membros do outro grupo — nada de listas parciais.
• Os nomes podem usar letras, dígitos, sublinhados, hifens, espaços e letras Unicode comuns.
• Suporte para até 15 membros por lado para uma animação interativa rápida.

Como Usar Esta Calculadora

1. Insira as preferências para o Grupo A na área de texto à esquerda — uma linha por membro, lista completa classificada.
2. Insira as preferências para o Grupo B na área de texto à direita — uma linha por membro, mesmo formato.
3. Escolha o lado que propõe. Escolha Grupo A ou Grupo B. Tente ambos para comparar os resultados A-ótimo vs B-ótimo.
4. Clique em "Resolver Casamento Estável." A calculadora executa o Gale-Shapley e produz os pares estáveis, estatísticas, animação e prova de estabilidade.
5. Controle a animação com os botões play / passo / reiniciar para ver cada proposta, aceitação, troca e rejeição em ordem.
6. Inspecione o mapa de calor. Cada célula mostra o ranking; as células com contorno amarelo formam o emparelhamento final — observe quão alto ou baixo essas células estão para ver quão "feliz" cada lado está.

Exemplo Prático — O Clássico 3×3

Homens: Alex, Bryan, Chris. Mulheres: Bea, Claire, Diana. Preferências:

Executar o Gale-Shapley com os homens propondo resulta em Alex–Bea, Bryan–Claire, Chris–Diana em uma única rodada (a primeira escolha de cada homem corresponde a uma mulher cuja primeira escolha é outra pessoa — sem conflito). O emparelhamento é estável: nenhum par homem-mulher estaria melhor trocando de parceiro, portanto, não há par de bloqueio.

Aplicações no Mundo Real

Por Que Lloyd Shapley Ganhou um Prêmio Nobel

Em 2012, a Real Academia de Ciências da Suécia concedeu o Prêmio Nobel de Economia a Lloyd Shapley (pela teoria, junto com David Gale que já havia falecido) e Alvin Roth (por aplicar a teoria a mercados reais, incluindo a reformulação da correspondência de residência médica nos EUA e redes de troca de rins). A premiação citou "a teoria das alocações estáveis e a prática do design de mercado".

Perguntas Frequentes

O que é o problema do casamento estável?

O problema do casamento estável pergunta: dados dois grupos de tamanhos iguais onde cada membro classifica todos os membros do outro grupo do mais para o menos preferido, podemos emparelhar todos de modo que não existam duas pessoas que prefiram deixar seus parceiros atuais um pelo outro? Tal emparelhamento é chamado de casamento estável. O algoritmo de Gale-Shapley resolve este problema em tempo O(n²) e sempre encontra um casamento estável.

Como funciona o algoritmo de Gale-Shapley?

O algoritmo de aceitação adiada de Gale-Shapley procede em rodadas. Em cada rodada, cada propositor atualmente solteiro propõe ao receptor de maior ranking em sua lista que ainda não o rejeitou. Cada receptor aceita tentativamente a melhor proposta recebida até agora e rejeita as demais; qualquer propositor deslocado fica livre novamente. O algoritmo termina quando nenhum propositor está livre, o que acontece em no máximo n² propostas.

O casamento estável é único?

Não. Uma instância do problema do casamento estável pode ter muitos casamentos estáveis. No entanto, quando um lado propõe, Gale-Shapley sempre produz o casamento estável ótimo para o propositor: cada propositor obtém o melhor parceiro que poderia obter em qualquer casamento estável. Por simetria, este é também o casamento péssimo para o receptor para o outro lado. Mudar o lado propositor muitas vezes resulta em um casamento estável diferente.

O que é um par de bloqueio?

Um par de bloqueio é um par (a, b) que não está emparelhado atualmente, onde a prefere b ao seu parceiro atual E b também prefere a ao seu parceiro atual. Se existir qualquer par de bloqueio, o emparelhamento é instável porque esses dois prefeririam se unir um ao outro. Um casamento estável não possui pares de bloqueio, o que esta calculadora verifica automaticamente após cada resolução.

Quais são as aplicações reais do casamento estável?

O algoritmo de Gale-Shapley impulsiona o Programa Nacional de Correspondência de Residências (NRMP) que designa estudantes de medicina para residências nos Estados Unidos, sistemas de escolha de escolas em Boston e Nova York, admissões em faculdades em vários países, cadeias de troca de rins de doadores de órgãos e sistemas de atribuição de colegas de quarto. Lloyd Shapley e Alvin Roth ganharam o Prêmio Nobel de Economia de 2012 em parte por este trabalho.

Ambos os grupos precisam ter o mesmo tamanho?

Na formulação clássica do casamento estável, sim. Ambos os lados devem ter o mesmo número de membros e cada um deve fornecer um ranking completo do outro lado. Variantes desequilibradas (como o casamento estável com listas incompletas ou o problema dos hospitais e residentes) existem, mas requerem algoritmos modificados. Esta calculadora impõe tamanhos iguais e listas de preferência completas.

Leitura Adicional

• Problema do casamento estável — Wikipedia (Inglês)
• Algoritmo de Gale-Shapley — Wikipedia (Inglês)
• National Resident Matching Program — Wikipedia (Inglês)
• Prêmio Nobel de Ciências Econômicas de 2012 — Shapley & Roth (Inglês)