Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

Crie um digrafo onde cada agente aponta para seu agente mais preferido entre os que ainda estão no mercado.

2

Encontre todos os ciclos no digrafo (sequências onde A aponta para B, B aponta para C, ..., de volta para A).

3

Para cada ciclo identificado, execute as trocas: cada agente recebe o dote do agente para o qual apontou.

4

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

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    Abrir referência DOI
    Copiado.
  2. 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 DOI
    Copiado.