Algoritmo de Gale-Shapley
- Proposto por
- David Gale, Lloyd Shapley
- Ano
- 1962
- Tipo
- algorithm
- Família
- Game-theoretic
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
O algoritmo de Gale-Shapley resolve o problema do casamento estável: como parear dois grupos (por exemplo, residentes médicos a hospitais, alunos a escolas) de forma que nenhum par prefira um ao outro em vez de seus parceiros designados.
Introduzido por David Gale e Lloyd Shapley em 1962, o algoritmo garante um pareamento estável em tempo polinomial através de um processo de aceitação diferida, onde um lado propõe sequencialmente e o outro lado responde, revisando escolhas à medida que chegam opções melhores.
A intuição por trás do método
Imagine parear médicos a hospitais. O algoritmo funciona como um jogo de cadeiras musicais: cada médico propõe ao hospital de sua preferência; cada hospital aceita provisoriamente o melhor médico disponível. À medida que os hospitais recebem propostas melhores, eles revisam suas escolhas, potencialmente rejeitando aceitações anteriores. Médicos rejeitados propõem ao próximo hospital de sua preferência. O processo continua até que nenhum médico queira propor mais e nenhum hospital queira trocar seu par atual. O resultado é estável: nenhum par médico-hospital preferiria ser pareado um com o outro em vez de seus parceiros designados.
História
David Gale e Lloyd Shapley publicaram sua solução para o problema do casamento estável em 1962, provando que pareamentos estáveis sempre existem para mercados de dois lados. Seu algoritmo gerou uma vasta literatura sobre teoria de pareamento com aplicações abrangendo medicina, educação e mercados de trabalho. Em 2012, Alvin Roth ganhou o Prêmio Nobel de Economia por seu trabalho experimental e teórico aplicando a teoria de pareamento ao design de mercado real, validando a importância prática do framework de Gale-Shapley.
Quando usar
Aplique o algoritmo de Gale-Shapley ao parear mercados de dois lados onde a estabilidade é crucial: alocação de residentes médicos, designação de alunos a escolas, intercâmbio de rins, pareamento no mercado de trabalho ou mercados de namoro online. Use quando houver risco de instabilidade no pareamento (pares bloqueadores) que possa desmantelar um pareamento após a designação. O algoritmo é ideal quando um lado pode agir primeiro com uma vantagem estratégica.
Limitações e considerações
- Não é Pareto ótimo: o pareamento pode não maximizar o bem-estar total; podem existir pares bloqueadores que poderiam se beneficiar da troca de parceiros
- Vulnerabilidade estratégica: o lado proponente pode ganhar ao representar mal suas preferências, enquanto o lado receptor é verdadeiro
- Assimetria: os resultados dependem fortemente de qual lado propõe primeiro
- Não lida com restrições: difícil incorporar preferências complexas (por exemplo, casais, preferências regionais) sem modificação algorítmica
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Estabilidade garantida: não existem pares bloqueadores no pareamento final
- Tempo polinomial: complexidade O(n^2), tornando-o eficiente para grandes populações
- Implementação simples: fácil de executar na prática com coleta transparente de preferências
- Incentivos estratégicos: o lado proponente tem uma vantagem estratégica, preferindo propostas iniciais a posteriores
- Aplicabilidade universal: funciona para quaisquer perfis de preferência sem assumir convexidade ou transitividade
Aplicações
- Pareamento de residência médica: pareando graduados de escolas de medicina a programas de residência hospitalar via NRMP
- Escolha de escolas: designando alunos a escolas públicas com base em preferências e restrições de capacidade
- Troca de rins: pareando doadores e receptores de órgãos para maximizar transplantes compatíveis
- Pareamento no mercado de trabalho: conectando candidatos a empregos com empregadores em mercados de trabalho de dois lados
- Namoro online: pareando usuários em plataformas de namoro para melhorar a estabilidade do pareamento e a satisfação do usuário
Como funciona
Como funciona
Crie listas de preferências para todos os indivíduos em ambos os grupos, representando sua classificação do outro lado.
Em cada rodada, cada pessoa desemparelhada do lado proponente propõe à pessoa de maior classificação do outro lado à qual ainda não propôs.
Cada pessoa do lado receptor aceita provisoriamente a proposta se estiver desemparelhada, ou se o proponente tiver uma classificação superior à de seu parceiro atual, caso em que revoga o engajamento anterior.
O algoritmo para quando todas as pessoas estão pareadas e não ocorrem mais propostas, resultando em um pareamento estável.
Erros comuns
- Assumir que a estabilidade sozinha é suficiente para justiça ou bem-estar; pareamentos estáveis podem ser altamente enviesados para um lado
- Confundir estabilidade com otimalidade; um pareamento estável não é necessariamente maximizador de bem-estar
- Ignorar a vantagem estratégica do lado proponente: os membros do lado proponente tendem a ser pareados com parceiros de maior classificação
- Esquecer que o algoritmo assume listas de preferências completas; preferências incompletas requerem modificação
Perguntas frequentes
Por que a estabilidade é importante no pareamento?
Sem estabilidade, pares pareados podem descobrir posteriormente que se preferem um ao outro em vez de seus parceiros designados, criando um incentivo para quebrar o pareamento. Pareamentos estáveis evitam tais pares bloqueadores, garantindo que o pareamento persista sem renegociação.
O algoritmo de Gale-Shapley sempre produz o mesmo pareamento?
Não. Listas de preferências diferentes ou ordens de propostas podem gerar pareamentos estáveis diferentes. No entanto, sempre existe um pareamento estável 'ótimo para o homem' (melhor para todos os proponentes) e um pareamento estável 'ótimo para a mulher' (melhor para todos os respondedores).
Como Gale-Shapley lida com preferências sobre grupos (por exemplo, casais)?
O algoritmo padrão não lida diretamente com casais ou outras restrições. Extensões como o algoritmo de casais existem, mas são mais complexas e podem não garantir estabilidade para todos os perfis de preferência.
Métodos relacionados
Fontes
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Abrir referência DOICopiado.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
Abrir referência DOICopiado.