Skip to content
Torna ai risultati

Algoritmo di Gale-Shapley

Introdotto da
David Gale, Lloyd Shapley
Anno
1962
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?

L'algoritmo di Gale-Shapley risolve il problema del matrimonio stabile: come accoppiare due gruppi (ad esempio, specializzandi medici con ospedali, studenti con scuole) in modo tale che nessuna coppia preferisca l'altro al proprio partner assegnato.

Introdotto da David Gale e Lloyd Shapley nel 1962, l'algoritmo garantisce un accoppiamento stabile in tempo polinomiale attraverso un processo di accettazione differita in cui un lato propone sequenzialmente e l'altro lato risponde, rivedendo le scelte man mano che arrivano opzioni migliori.

L’intuizione alla base del metodo

Immaginiamo di accoppiare medici con ospedali. L'algoritmo funziona come un gioco di sedie musicali: ogni medico propone all'ospedale preferito; ogni ospedale accetta provvisoriamente il miglior medico disponibile. Man mano che gli ospedali ricevono proposte migliori, rivedono le loro scelte, potenzialmente rifiutando le accettazioni precedenti. I medici che vengono rifiutati propongono al loro ospedale successivo in ordine di preferenza. Il processo continua finché nessun medico vuole proporre ulteriormente e nessun ospedale vuole scambiare il proprio partner attuale. Il risultato è stabile: nessuna coppia medico-ospedale preferirebbe essere accoppiata tra loro piuttosto che ai propri partner assegnati.

Storia

David Gale e Lloyd Shapley pubblicarono la loro soluzione al problema del matrimonio stabile nel 1962, dimostrando che gli accoppiamenti stabili esistono sempre per i mercati a due lati. Il loro algoritmo ha dato origine a una vasta letteratura sulla teoria degli accoppiamenti con applicazioni che spaziano dalla medicina, all'istruzione e ai mercati del lavoro. Nel 2012, Alvin Roth ha vinto il Premio Nobel per l'Economia per il suo lavoro sperimentale e teorico sull'applicazione della teoria degli accoppiamenti alla progettazione di mercati reali, convalidando l'importanza pratica del quadro di Gale-Shapley.

Quando usarlo

Applicare l'algoritmo di Gale-Shapley quando si accoppiano mercati a due lati in cui la stabilità è cruciale: collocamento di specializzandi medici, assegnazione di studenti a scuole, scambio di reni, accoppiamento sul mercato del lavoro o mercati di incontri online. Usare quando c'è il rischio di instabilità nell'accoppiamento (coppie bloccanti) che potrebbero disfare un accoppiamento dopo l'assegnazione. L'algoritmo è ideale quando un lato può muoversi per primo con un vantaggio strategico.

Limiti e considerazioni

  • Non Pareto ottimale: l'accoppiamento potrebbe non massimizzare il benessere totale; potrebbero esistere coppie bloccanti che potrebbero tutte beneficiare dello scambio di partner
  • Vulnerabilità strategica: il lato proponente può guadagnare travisando le preferenze, mentre il lato rispondente è veritiero
  • Asimmetria: gli esiti dipendono fortemente da quale lato propone per primo
  • Non gestisce vincoli: difficile incorporare preferenze complesse (ad esempio, coppie, preferenze regionali) senza modifiche algoritmiche

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

Punti di forza

  • Stabilità garantita: non esistono coppie bloccanti nell'accoppiamento finale
  • Tempo polinomiale: complessità O(n^2), che lo rende efficiente per grandi popolazioni
  • Implementazione semplice: facile da eseguire in pratica con una raccolta trasparente delle preferenze
  • Incentivi strategici: il lato proponente ha un vantaggio strategico, preferendo proposte anticipate a quelle successive
  • Applicabilità universale: funziona per qualsiasi profilo di preferenze senza presupporre convessità o transitività

Applicazioni

  • Accoppiamento di specializzandi medici: accoppiamento di laureati in medicina con programmi di specializzazione ospedaliera tramite NRMP
  • Scelta della scuola: assegnazione di studenti a scuole pubbliche in base alle preferenze e ai vincoli di capacità
  • Scambio di reni: accoppiamento di donatori e riceventi di organi per massimizzare i trapianti compatibili
  • Accoppiamento sul mercato del lavoro: collegamento tra persone in cerca di lavoro e datori di lavoro in mercati del lavoro a due lati
  • Incontri online: accoppiamento di utenti su piattaforme di incontri per migliorare la stabilità degli accoppiamenti e la soddisfazione degli utenti

Come funziona

Come funziona

1

Creare liste di preferenze per tutti gli individui in entrambi i gruppi, che rappresentino il loro ordinamento dell'altro lato.

2

In ogni round, ogni persona non accoppiata dal lato proponente propone alla persona più in alto in classifica dall'altro lato a cui non ha ancora proposto.

3

Ogni persona dal lato ricevente accetta provvisoriamente la proposta se non è accoppiata, o se il proponente è classificato più in alto del proprio partner attuale, nel qual caso revoca l'impegno precedente.

4

L'algoritmo si arresta quando ogni persona è accoppiata e non avvengono ulteriori proposte, producendo un accoppiamento stabile.

Errori comuni

  • Presupporre che la stabilità da sola sia sufficiente per l'equità o il benessere; gli accoppiamenti stabili possono essere fortemente sbilanciati verso un lato
  • Confondere stabilità con ottimalità; un accoppiamento stabile non è necessariamente massimizzante del benessere
  • Trascurare il vantaggio strategico del lato proponente: i membri del lato proponente tendono ad accoppiarsi con partner di rango superiore
  • Dimenticare che l'algoritmo presuppone liste di preferenze complete; le preferenze incomplete richiedono modifiche

Domande frequenti

Perché la stabilità è importante negli accoppiamenti?

Senza stabilità, le coppie accoppiate potrebbero in seguito scoprire di preferirsi a vicenda rispetto ai propri partner assegnati, creando un incentivo a rompere l'accoppiamento. Gli accoppiamenti stabili prevengono tali coppie bloccanti, garantendo che l'accoppiamento persista senza rinegoziazioni.

L'algoritmo di Gale-Shapley produce sempre lo stesso accoppiamento?

No. Diverse liste di preferenze o ordini di proposta possono produrre diversi accoppiamenti stabili. Tuttavia, esiste sempre un accoppiamento stabile 'ottimale per l'uomo' (il migliore per tutti i proponenti) e un accoppiamento stabile 'ottimale per la donna' (il migliore per tutti i rispondenti).

Come gestisce Gale-Shapley le preferenze sui gruppi (ad esempio, coppie)?

L'algoritmo standard non gestisce direttamente coppie o altri vincoli. Esistono estensioni come l'algoritmo per coppie, ma sono più complesse e potrebbero non garantire la stabilità per tutti i profili di preferenze.

Metodi correlati

Fonti

  1. Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.

    Apri il riferimento DOI
    Copiato.
  2. Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.

    Apri il riferimento DOI
    Copiato.