Ciclos de Troca Máxima
- Proposto por
- Lloyd Shapley, Herbert Scarf
- Ano
- 1974
- 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?
Ciclos de Troca Máxima (TTC) é um algoritmo para alocar bens indivisíveis a agentes de forma que a alocação seja Pareto eficiente e individualmente racional. Desenvolvido por Lloyd Shapley e Herbert Scarf em 1974, o algoritmo identifica ciclos de trocas em um digrafo de preferências, executa essas trocas e repete iterativamente até que nenhuma troca adicional seja benéfica.
O TTC é amplamente utilizado em intercâmbio de rins e alocação de moradias devido à sua eficiência e simplicidade de implementação.
A intuição por trás do método
Imagine um grupo de pessoas, cada uma possuindo uma casa, e cada pessoa classificando todas as casas por preferência. O algoritmo TTC pergunta: quem é meu favorito? Aponte para ele. Agora olhe para quem apontou para você. Se for um ciclo (A aponta para B, B aponta para C, C aponta para A), execute essas trocas — A fica com a casa de B, B fica com a casa de C, C fica com a casa de A. Todos no ciclo ficam felizes porque receberam a casa de alguém que preferem à sua atual. Remova o ciclo e repita até que não existam mais ciclos. O resultado é eficiente porque todas as trocas benéficas são realizadas.
História
Lloyd Shapley e Herbert Scarf introduziram o algoritmo Top Trading Cycles em 1974 como uma solução para o problema do mercado imobiliário, provando que ele gera alocações Pareto eficientes únicas. O algoritmo ganhou importância prática através do trabalho de Alvin Roth em intercâmbio de rins, onde se tornou central para o emparelhamento de doadores e receptores. O Prêmio Nobel de 2012 para Roth validou a importância do TTC para o design de mercado no mundo real, particularmente em transplante de órgãos.
Quando usar
Aplique o TTC ao alocar bens indivisíveis (casas, órgãos, vagas escolares) entre agentes com preferências estritas sobre pacotes. Use quando a eficiência de Pareto for essencial e não houver transferências monetárias disponíveis ou desejáveis. O TTC é ideal para mercados descentralizados onde os agentes podem identificar trocas benéficas localmente. Funciona melhor quando os agentes possuem informações de preferência completas e acíclicas.
Limitações e considerações
- Requer ordens de preferência estritas sem indiferença; extensões para preferências fracas são complexas
- Não à prova de coalizão: coalizões de agentes podem deturpar preferências para melhorar o resultado coletivo
- Sensibilidade a ciclos de preferência: a inexistência de ciclos pode deixar alguns agentes sem negociação
- Limitado a emparelhamentos sem transferências monetárias; ineficiente para avaliações heterogêneas
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
- Eficiente em termos de Pareto: não existem melhorias sem troca; todas as trocas mutuamente benéficas são executadas
- Individualmente racional: cada agente prefere fracamente a alocação final ao seu dote inicial
- Estratégico-prova em certos cenários: agentes não podem melhorar ao relatar preferências incorretamente
- Computacionalmente eficiente: tempo polinomial com implementação simples
- Transparente: agentes entendem como sua escolha apontada leva à alocação
Aplicações
- Intercâmbio de rins: emparelhamento de doadores de órgãos e receptores para aumentar a compatibilidade de transplantes através de trocas multipartidárias
- Alocação de moradias: atribuição eficiente de quartos de dormitórios universitários ou unidades de habitação pública
- Escolha de escolas: atribuição de alunos a escolas com restrições de capacidade e diversidade de preferências
- Troca de lobos hepáticos: facilitação de trocas de doação pareada para transplante de fígado com doador vivo
- Trocas de móveis e bens: organização de trocas de escambo eficientes em plataformas de compartilhamento comunitário
Como funciona
Como funciona
Crie um digrafo onde cada agente aponta para seu agente mais preferido entre os que ainda estão no mercado.
Encontre todos os ciclos no digrafo (sequências onde A aponta para B, B aponta para C, ..., de volta para A).
Para cada ciclo identificado, execute as trocas: cada agente recebe o dote do agente para o qual apontou.
Remova os agentes trocados e seus dotes do mercado. Reconstrúa o digrafo de preferências entre os agentes restantes e repita até que nenhum ciclo adicional exista.
Erros comuns
- Confundir eficiência de Pareto com justiça ou equidade; o TTC maximiza a eficiência, mas não a igualdade de resultados
- Assumir prova de estratégia em todos os cenários; o TTC é verdadeiro apenas em certos contextos (por exemplo, mercados imobiliários, não intercâmbio de rins com priorização)
- Ignorar que o algoritmo termina quando não há mais ciclos lucrativos, potencialmente deixando agentes sem emparelhamento
- Esquecer que o TTC requer preferências estritas sem indiferença; aplicá-lo com preferências fracas requer extensão
Perguntas frequentes
Por que a eficiência de Pareto é importante na alocação de recursos?
A eficiência de Pareto garante que nenhum agente possa ser melhorado sem piorar outro. É um requisito mínimo para uma alocação 'boa'; violá-la significa que os recursos estão sendo desperdiçados e poderiam ser realocados para beneficiar alguém.
O TTC pode produzir múltiplas alocações diferentes?
Não. O algoritmo TTC, com seu digrafo de preferências único, produz uma alocação Pareto eficiente única. O caminho para essa alocação (ordem de identificação de ciclos e execução de trocas) pode variar, mas o resultado final é sempre o mesmo.
Como o TTC é modificado para intercâmbio de rins quando nem todos os pares doador-receptor são compatíveis?
No intercâmbio de rins, o digrafo de preferências é construído apenas sobre pares compatíveis. O algoritmo então identifica ciclos e cadeias de trocas entre agentes compatíveis, estendendo o TTC original para levar em conta as restrições biológicas.
Métodos relacionados
Fontes
Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.
Abrir referência DOICopiado.Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.
Abrir referência DOICopiado.