Risolutore del Problema del Matrimonio Stabile

Risolutore del Problema del Matrimonio Stabile

Il Risolutore del Problema del Matrimonio Stabile è un'implementazione interattiva dell'algoritmo di accettazione differita di Gale-Shapley, l'algoritmo di abbinamento del 1962 che David Gale e Lloyd Shapley dimostrarono produrre sempre un accoppiamento stabile tra due gruppi di uguali dimensioni, data la classifica completa di ogni membro dell'altra parte. Questo strumento prende le tue liste di preferenze, esegue l'algoritmo passo dopo passo e mostra il risultato come abbinamento stabile, visualizzazione bipartita animata, mappe di calore delle preferenze e una prova verificata che non esistono coppie bloccanti.

Cos'è il Problema del Matrimonio Stabile?

Dati due insiemi disgiunti di uguale dimensione — ad esempio n uomini e n donne, o n candidati e n posizioni — e una lista completa di preferenze da parte di ogni membro che classifica ogni membro dell'altra parte, un abbinamento è un accoppiamento uno-a-uno tra i due insiemi. L'abbinamento è definito stabile se non esiste alcuna coppia (a, b) esterna all'abbinamento che preferirebbe stare insieme piuttosto che restare con i partner assegnati.

Formalmente, un abbinamento M è stabile se non esiste una coppia bloccante — una coppia (a, b) con a abbinato a b' e b abbinato a a' tale che:

Se entrambe le condizioni sono soddisfatte, sia a che b abbandonerebbero i loro attuali partner, destabilizzando l'abbinamento. Un abbinamento stabile è quello in cui non esiste una coppia del genere.

L'algoritmo di Gale-Shapley

Gale e Shapley hanno dimostrato — costruttivamente — che esiste sempre un abbinamento stabile per qualsiasi insieme di preferenze e hanno fornito un algoritmo efficiente per trovarne uno. L'algoritmo procede a round:

1. Ogni proponente non impegnato propone al ricevente con il rango più alto nella sua lista che non lo ha ancora rifiutato.
2. Ogni ricevente che ha ricevuto una o più proposte sceglie quella che preferisce di più (confrontandola con l'eventuale partner provvisorio attuale) e accetta provvisoriamente; tutti gli altri vengono rifiutati.
3. I proponenti rifiutati tornano liberi e passano alla loro scelta successiva nel round seguente.
4. L'algoritmo termina quando ogni proponente è impegnato — il che è garantito accadere in massimo n² proposte.

Proprietà Teoriche Chiave

Esistenza e Unicità

Esiste sempre un abbinamento stabile (Gale e Shapley, 1962), ma non è necessariamente unico. Per un dato insieme di preferenze possono esserci più abbinamenti stabili, che formano un reticolo ordinato per preferenza congiunta.

Ottimalità per il Proponente

Quando una parte propone, Gale-Shapley produce l'abbinamento stabile ottimale per il proponente: ogni proponente riceve il miglior partner con cui potrebbe mai essere abbinato in qualsiasi abbinamento stabile. Per un argomento simmetrico, questo è anche l'abbinamento pessimale per il ricevente — la parte ricevente ottiene il suo peggior partner stabile. Cambiare il lato proponente in questo calcolatore spesso cambia il risultato.

Resistenza alle Strategie per i Proponenti

Sotto Gale-Shapley, i proponenti non hanno alcun incentivo a dichiarare il falso sulle proprie preferenze: dire la verità è una strategia dominante per loro. I riceventi, tuttavia, possono a volte trarre vantaggio da una dichiarazione strategica errata — uno dei motivi per cui il mercato ospedali-residenti negli Stati Uniti è progettato con gli studenti come parte proponente.

Teorema degli Ospedali Rurali

L'insieme degli agenti non abbinati è identico in tutti gli abbinamenti stabili. Quindi, se la tua istanza ha dimensioni sbilanciate (oltre lo scopo di questo strumento classico), le stesse persone rimarranno non abbinate in ogni soluzione stabile.

Formato di Input

Questo calcolatore si aspetta una riga per membro, con il nome seguito da due punti e una lista completa di preferenze classificate separate da virgole:

Requisiti:

• Entrambi i gruppi devono avere esattamente lo stesso numero di membri.
• Ogni membro deve classificare ogni membro dell'altro gruppo — non sono ammesse liste parziali.
• I nomi possono contenere lettere, cifre, underscore, trattini, spazi e lettere Unicode comuni.
• Sono supportati fino a 15 membri per lato per un'animazione interattiva veloce.

Come utilizzare questo calcolatore

1. Inserisci le preferenze per il Gruppo A nell'area di testo a sinistra — una riga per membro, lista completa.
2. Inserisci le preferenze per il Gruppo B nell'area di testo a destra — una riga per membro, stesso formato.
3. Scegli il lato proponente. Scegli Gruppo A o Gruppo B. Provali entrambi per confrontare i risultati A-ottimale e B-ottimale.
4. Clicca su "Risolvi Abbinamento Stabile". Il calcolatore esegue Gale-Shapley e produce le coppie stabili, le statistiche, l'animazione e la prova di stabilità.
5. Scorri l'animazione con i controlli play / passo / reset per vedere ogni proposta, accettazione, scambio e rifiuto in ordine.
6. Ispeziona la mappa di calore. Ogni cella mostra il rango; le celle con il bordo giallo formano l'abbinamento finale — osserva quanto in alto o in basso si trovano per vedere quanto è "felice" ogni parte.

Esempio Pratico — Il Classico 3×3

Uomini: Alex, Bryan, Chris. Donne: Bea, Claire, Diana. Preferenze:

Eseguendo Gale-Shapley con gli uomini che propongono si ottiene Alex–Bea, Bryan–Claire, Chris–Diana in un unico round (la prima scelta di ogni uomo corrisponde a una donna la cui prima scelta è qualcun altro — nessun conflitto). L'abbinamento è stabile: nessuna coppia uomo-donna starebbe meglio scambiando i partner, quindi non esiste alcuna coppia bloccante.

Applicazioni nel Mondo Reale

Perché Lloyd Shapley ha vinto il Premio Nobel

Nel 2012 l'Accademia Reale Svedese delle Scienze ha assegnato il Premio Nobel per l'Economia a Lloyd Shapley (per la teoria, insieme a David Gale che era deceduto) e Alvin Roth (per aver applicato la teoria ai mercati reali, inclusa la riprogettazione dell'abbinamento dei tirocini medici negli USA e delle reti di scambio di reni). Il premio è stato assegnato per "la teoria delle allocazioni stabili e la pratica del market design".

Domande Frequenti

Cos'è il problema del matrimonio stabile?

Il problema del matrimonio stabile chiede: dati due gruppi di uguali dimensioni in cui ogni membro classifica tutti i membri dell'altro gruppo dal più al meno preferito, possiamo accoppiare tutti in modo che non ci siano due persone che preferirebbero lasciarsi per stare insieme? Tale accoppiamento è chiamato abbinamento stabile. L'algoritmo Gale-Shapley risolve questo problema in tempo O(n²) e trova sempre un abbinamento stabile.

Come funziona l'algoritmo di Gale-Shapley?

L'algoritmo di accettazione differita Gale-Shapley procede a round. In ogni round, ogni proponente attualmente non impegnato propone al ricevente con il rango più alto nella sua lista che non lo ha ancora rifiutato. Ogni ricevente accetta provvisoriamente la migliore proposta ricevuta finora e rifiuta le altre; ogni proponente rimpiazzato torna libero. L'algoritmo termina quando nessun proponente è libero, il che accade in massimo n² proposte.

L'abbinamento stabile è unico?

No. Un'istanza del problema del matrimonio stabile può avere molti abbinamenti stabili. Tuttavia, quando una parte propone, Gale-Shapley produce sempre l'abbinamento stabile ottimale per il proponente: ogni proponente ottiene il miglior partner che potrebbe mai ottenere in qualsiasi abbinamento stabile. Per simmetria, questo è anche l'abbinamento pessimo per l'altro lato. Cambiare il lato proponente spesso produce un abbinamento stabile diverso.

Cos'è una coppia bloccante?

Una coppia bloccante è una coppia (a, b) che non è attualmente abbinata dove a preferisce b al suo attuale partner E b preferisce anche a al suo attuale partner. Se esiste una coppia bloccante, l'abbinamento è instabile perché quei due preferirebbero accoppiarsi tra loro. Un abbinamento stabile non ha coppie bloccanti, cosa che questo calcolatore verifica automaticamente dopo ogni risoluzione.

Quali sono le applicazioni reali dell'abbinamento stabile?

L'algoritmo Gale-Shapley alimenta il National Resident Matching Program che assegna gli studenti di medicina ai tirocini negli Stati Uniti, i sistemi di scelta scolastica a Boston e New York, le ammissioni universitarie in diversi paesi, le catene di scambio di reni da donatori e i sistemi di assegnazione dei coinquilini. Lloyd Shapley e Alvin Roth hanno vinto il Premio Nobel per l'Economia nel 2012 in parte per questo lavoro.

Entrambi i gruppi devono avere la stessa dimensione?

Nella formulazione classica del matrimonio stabile, sì. Entrambe le parti devono avere lo stesso numero di membri e ognuna deve fornire una classifica completa dell'altra parte. Esistono varianti sbilanciate (come l'abbinamento stabile con liste incomplete o il problema ospedali-residenti) ma richiedono algoritmi modificati. Questo calcolatore impone dimensioni uguali e liste di preferenze complete.

Ulteriori letture

• Problema del matrimonio stabile — Wikipedia
• Algoritmo Gale-Shapley — Wikipedia (Inglese)
• National Resident Matching Program — Wikipedia (Inglese)
• Premio Nobel per le Scienze Economiche 2012 — Shapley & Roth