Il problema dei matrimoni stabili

 

Come ben sanno gli informatici, gli algoritmi sono procedimenti che risolvono un problema attraverso lo svolgimento di un numero finito di passi elementari, in un tempo accettabile.

Gli algoritmi ci consentono di risolvere molti problemi e sono alla base dell'ordine matematico dell'universo. Le nostre vite sono toccate quotidianamente da algoritmi spesso invisibili e la maggior parte di noi non ne è consapevole. Ci sono algoritmi che controllano quello che si legge, che monitorano i prodotti che acquistiamo, che prevedono il tempo atmosferico, che guidano i pacchi nei binari motorizzati di un magazzino, che fissano l'ordine degli aerei nelle piste di partenza, che fanno le ricerche in Internet, che ordinano milioni di dati in un database... banalmente c'è un algoritmo anche quando seguiamo una ricetta per preparare un dolce!

 

In questa sede parliamo di uno dei più importanti algoritmi di Matching, ovvero algoritmi di accoppiamento tra gli elementi di due insiemi.

Nel 2012 il premio Nobel per l'Economia è andato al matematico statunitense Lloyd Shapley, per aver ideato molti anni prima, unitamente al defunto collega David Gale, un procedimento, divenuto famoso come “l'algoritmo di Gale-Shapley” o “algoritmo dei matrimoni stabili”.

 

Negli anni '60 i due matematici affrontarono e risolsero il problema dell'associazione tra studenti e facoltà universitarie, ogni studente doveva trovare una sistemazione presso una facoltà e doveva restare soddisfatto anche se era rimasto escluso dalla facoltà che costituiva la sua prima scelta. Utilizzando il linguaggio dell'insiemistica, se A = ”insieme degli studenti” e B = ”insieme delle facoltà”, l'insieme delle coppie del matching ottimale costituisce un sottoinsieme del prodotto cartesiano AxB, ovvero l'insieme delle coppie nelle quali il primo elemento di ogni coppia appartiene al primo insieme ed il secondo elemento di ogni coppia appartiene al secondo insieme.

 

Dato per scontato che non sia possibile garantire l'ottimo, ovvero che ogni elemento dei due insiemi sia abbinato alla rispettiva prima scelta, è fondamentale però evitare delle coppie instabili, ovvero evitare assegnazioni nelle quali un elemento x del primo insieme preferirebbe y al suo partner attuale e un elemento y del secondo insieme preferirebbe x al partner assegnato (questo sarebbe causa di separazione!).

 

L'algoritmo da premio Nobel di Gale-Shapley garantisce la creazione di coppie stabili attraverso l'iterazione di due semplici passaggi: consideriamo due insiemi di uguale numerosità, quello delle donne (D) e quello degli uomini (U), allora D = {d₁, d₂, …, d_n} e U = {u₁, u₂, …, u_n}, dando un taglio maschilistico all'applicazione dell'algoritmo, nella prima fase le varie donne (elementi del primo insieme) dichiarano qual è la loro prima preferenza in termini di uomini (elementi del secondo insieme) e si creano delle coppie provvisorie sulla base della scelta degli uomini che hanno ricevuto 'delle proposte', evidentemente gli uomini scelgono l'unica o la preferita tra le gentili signore disponibili. Nella fase successiva le donne respinte dichiarano la loro 'seconda scelta' e gli uomini continuano a scegliere la miglior proposta ricevuta. Una volta accettata una donna, l'uomo non diventa più libero e potrà solo migliorare, scambiando la partner con una ritenuta migliore... alla fine delle iterazioni, quando tutti hanno un partner, si ottengono le migliori coppie possibili.

 

A chi ha riscontrato della misoginia nei passi precedenti faccio notare che è possibile scambiare i due insiemi in modo che l'applicazione dell'algoritmo inverta il tipo di ottimalità (l'uomo-ottimalità diventa una donna-ottimalità).

 

L'algoritmo di Gale-Shapley è usato in tutto il mondo: in Danimarca per l'assegnazione di bambini agli asili, in Ungheria per l'iscrizione di bambini alle scuole, a New York per la scelta dei rabbini alle sinagoghe, in Cina, Germania e Spagna per gli studenti delle università, nel Regno Unito l'algoritmo è stato il punto di partenza per elaborare un metodo ottimale per associare organi a pazienti bisognosi di trapianti... non è un'esagerazione affermare che molte persone devono la vita a questo algoritmo!

 

 

* dvd “Gli algoritmi che hanno cambiato il mondo” - Le conquiste della matematica, formule e teorie per capire il mondo

 

________