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
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
Creare un grafo diretto in cui ogni agente punta all'agente preferito tra quelli ancora nel mercato.
Trovare tutti i cicli nel grafo (sequenze in cui A punta a B, B punta a C, ..., di nuovo ad A).
Per ogni ciclo identificato, eseguire gli scambi: ogni agente riceve il patrimonio dell'agente a cui ha puntato.
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
Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.
Apri il riferimento DOICopiato.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 DOICopiato.