Skip to content
Torna ai risultati

Cicli di Scambio Principali

Introdotto da
Lloyd Shapley, Herbert Scarf
Anno
1974
Tipo
algorithm
Famiglia
Game-theoretic

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

I Cicli di Scambio Principali (TTC) sono un algoritmo per l'allocazione di beni indivisibili ad agenti, tale che l'allocazione sia Pareto efficiente e individualmente razionale.

Sviluppato da Lloyd Shapley e Herbert Scarf nel 1974, l'algoritmo identifica cicli di scambi in un digrafo delle preferenze, esegue tali scambi e si ripete iterativamente finché nessuno scambio ulteriore è vantaggioso. Il TTC è ampiamente utilizzato negli scambi di reni e nell'allocazione di alloggi grazie alla sua efficienza e semplicità di implementazione.

L’intuizione alla base del metodo

Immagina un gruppo di persone, ognuna proprietaria di una casa, e ognuno che classifica tutte le case per preferenza. L'algoritmo TTC chiede: chi è il mio preferito? Puntalo. Ora guarda chi ha puntato te. Se si forma un ciclo (A punta a B, B punta a C, C punta ad A), esegui questi scambi: A ottiene la casa di B, B ottiene la casa di C, C ottiene la casa di A. Tutti nel ciclo sono felici perché hanno ottenuto la casa di qualcuno che preferiscono alla loro attuale. Rimuovi il ciclo e ripeti finché non esistono più cicli. Il risultato è efficiente perché tutti gli scambi vantaggiosi vengono effettuati.

Storia

Lloyd Shapley e Herbert Scarf introdussero l'algoritmo dei Cicli di Scambio Principali nel 1974 come soluzione al problema del mercato immobiliare, dimostrando che produce allocazioni Pareto-efficienti uniche. L'algoritmo acquisì importanza pratica attraverso il lavoro di Alvin Roth sugli scambi di reni, dove divenne centrale per l'abbinamento di donatori e riceventi. Il Premio Nobel del 2012 a Roth convalidò l'importanza del TTC per la progettazione di mercati reali, in particolare nel trapianto di organi.

Quando usarlo

Applicare il TTC nell'allocazione di beni indivisibili (case, organi, posti a scuola) tra agenti con preferenze strette sui pacchetti. Utilizzare quando l'efficienza di Pareto è essenziale e non sono disponibili o desiderabili trasferimenti monetari. Il TTC è ideale per mercati decentralizzati in cui gli agenti possono identificare scambi vantaggiosi localmente. Funziona meglio quando gli agenti hanno informazioni complete e acicliche sulle preferenze.

Limiti e considerazioni

  • Richiede ordini di preferenza stretti senza indifferenza; le estensioni a preferenze deboli sono complesse
  • Non a prova di coalizione: le coalizioni di agenti possono falsificare le preferenze per migliorare il risultato collettivo
  • Sensibilità ai cicli di preferenza: la non esistenza di cicli può lasciare alcuni agenti non scambiati
  • Limitato al matching senza trasferimenti monetari; inefficiente per valutazioni eterogenee

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Pareto efficiente: non esistono miglioramenti senza scambi; tutti gli scambi reciprocamente vantaggiosi vengono eseguiti
  • Individualmente razionale: ogni agente preferisce debolmente l'allocazione finale al suo patrimonio iniziale
  • Strategicamente robusto in determinati contesti: gli agenti non possono migliorare la propria situazione falsificando le preferenze
  • Computazionalmente efficiente: tempo polinomiale con implementazione semplice
  • Trasparente: gli agenti comprendono come la loro scelta puntata porti all'allocazione

Applicazioni

  • Scambio di reni: abbinamento di donatori e riceventi di organi per aumentare la compatibilità dei trapianti attraverso scambi multipartitici
  • Allocazione di alloggi: assegnazione efficiente di stanze di dormitori universitari o unità abitative pubbliche
  • Scelta scolastica: assegnazione di studenti a scuole con vincoli di capacità e diversità di preferenze
  • Scambio di lobi epatici: facilitazione di scambi di donazione appaiata per il trapianto di fegato da donatore vivente
  • Scambio di mobili e beni: organizzazione di scambi di baratto efficienti su piattaforme di condivisione comunitaria

Come funziona

Come funziona

1

Creare un grafo diretto in cui ogni agente punta all'agente preferito tra quelli ancora nel mercato.

2

Trovare tutti i cicli nel grafo (sequenze in cui A punta a B, B punta a C, ..., di nuovo ad A).

3

Per ogni ciclo identificato, eseguire gli scambi: ogni agente riceve il patrimonio dell'agente a cui ha puntato.

4

Rimuovere gli agenti scambiati e i loro patrimoni dal mercato. Ricostruire il grafo delle preferenze tra gli agenti rimanenti e ripetere finché non esistono più cicli.

Errori comuni

  • Confusione tra efficienza di Pareto e equità o giustizia; il TTC massimizza l'efficienza ma non l'uguaglianza dei risultati
  • Presupponendo la robustezza strategica in tutti i contesti; il TTC è veritiero solo in determinati contesti (es. mercati immobiliari, non scambi di reni con prioritizzazione)
  • Trascurando che l'algoritmo termina quando non esistono più cicli profittevoli, potenzialmente lasciando agenti non abbinati
  • Dimenticando che il TTC richiede preferenze strette senza indifferenza; applicarlo con preferenze deboli richiede un'estensione

Domande frequenti

Perché l'efficienza di Pareto è importante nell'allocazione delle risorse?

L'efficienza di Pareto garantisce che nessun agente possa essere migliorato senza peggiorare un altro. È un requisito minimo per un'allocazione 'buona'; violarla significa che le risorse vengono sprecate e potrebbero essere riallocate a beneficio di qualcuno.

Il TTC può produrre molteplici allocazioni diverse?

No. L'algoritmo TTC, con il suo digrafo di preferenze unico, produce un'allocazione Pareto-efficiente unica. Il percorso verso tale allocazione (ordine di identificazione e esecuzione degli scambi dei cicli) può variare, ma il risultato finale è sempre lo stesso.

Come viene modificato il TTC per lo scambio di reni quando non tutte le coppie donatore-ricevente sono compatibili?

Nello scambio di reni, il digrafo delle preferenze viene costruito solo su coppie compatibili. L'algoritmo identifica quindi cicli e catene di scambi tra agenti compatibili, estendendo il TTC originale per tenere conto dei vincoli biologici.

Metodi correlati

Fonti

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

    Apri il riferimento DOI
    Copiato.
  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.

    Apri il riferimento DOI
    Copiato.