Il problema degli abbinamenti stabili è un classico problema informatico la cui soluzione è un algoritmo interessante. Supponiamo di avere $N$ studenti e $N$ professori e vogliamo abbinare ogni studente con esattamente un professore (magari per fare la tesi). Ogni studente compila una lista dei professori in ordine di preferenza e ogni professore fa lo stesso per gli studenti.
In linea di massima vorremmo trovare l’abbinamento “migliore”, ma che significa “migliore”? Se avessimo una funzione che, dato un possibile abbinamento di ogni studente con un professore, gli assegna un punteggio, potremmo provare a massimizzare questa funzione. Tuttavia non c’è nessuna scelta “naturale” per assegnare un punteggio del genere. Allora scegliamo un criterio diverso, ovvero che tutti gli abbinamenti siano stabili. Diciamo che un abbinamento è stabile se non esiste nessuna coppia studente/professore non abbinati che preferisce l’un l’altro rispetto al proprio tesista/relatore. In altri termini, nessuno ha un incentivo a cambiare abbinamento, perché non c’è nessuno preferito che sia disposto a cambiare.
La dimostrazione dell’esistenza di accoppiamenti stabili è data direttamente dall’algoritmo che si usa per trovarne uno. Come procede l’algoritmo? Iniziamo ciclando su tutti gli studenti ordinati a caso. Il primo studente si propone al suo professore preferito, che per il momento accetta la proposta. Poi anche il secondo studente si propone al suo professore preferito, che per il momento accetta, e via dicendo. Ad un certo punto può succedere che uno studente si proponga ad un professore già scelto; a quel punto tocca al professore scegliere chi dei due preferisce: il preferito dal professore viene (per il momento) accettato, e l’altro rimane senza abbinamento. In questa maniera continuiamo a ciclare tra gli studenti non abbinati; per la sua seconda proposta, lo studente si proporrà al secondo professore preferito con lo stesso meccanismo, per la terza proposta al terzo preferito, e via dicendo finché tutti gli studenti sono abbinati.
Nel caso peggiore, ognuno degli $N$ studenti si propone ad ognuno degli $N$ professori al massimo una volta, e quindi in totale abbiamo $N^2$ proposte. Ciò vuol dire inoltre che l’algoritmo necessariamente terminerà con un abbinamento tra studenti e professori. L’abbinamento è stabile? Supponiamo che abbiamo abbinato lo studente $A$ con il professore $X$, e lo studente $B$ con il professore $Y$, ma $A$ preferisca $Y$ a $X$ e $Y$ preferisca $A$ a $B$. In tal caso, $A$ si sarebbe proposto ad $Y$ prima che a $X$ (perché ogni studente si propone in ordine delle sue preferenze); se $Y$ è libero, avrebbe accettato $A$ temporaneamente; altrimenti se fosse già stato accoppiato a qualcuno che preferisce ad $A$, avrebbe rifiutato $A$. Perciò quando arriva il turno di $B$ e $B$ si propone a $Y$ (ciò dev’essere successo, perché sappiamo che $B$ e $Y$ sono abbinati) $Y$ è necessariamente già abbinato o con $A$ o con $C$, che $Y$ preferisce ad $A$ (e quindi anche a $B$, perché la lista è ordinata). Perciò $Y$ rifiuterebbe $B$, il che è contraddittorio col fatto che $B$ ed $Y$ sono accoppiati.
Poiché esistono $N!$ possibili accoppiamenti (fissati i professori, abbiamo $N!$ possibili permutazioni di studenti) se cercassimo le coppie con forza bruta avremmo bisogno di un tempo potenzialmente fattoriale. Invece l’algoritmo sopra ci garantisce una tempistica dell’ordine di $N^2$, che è molto più favorevole.
Notiamo comunque che l’abbinamento stabile non è unico, anzi esistono moltissimi abbinamenti stabili. In particolare ciclando sugli studenti in ordine diverso, oppure scambiando il ruolo di studenti e professori, l’algoritmo può dare risultati diversi.
Esistono anche molte varianti dello stesso problema: se ad esempio vogliamo abbinare $2N$ studenti a coppie per un progetto, ad esempio, e di nuovo gli studenti hanno una lista di altri studenti preferiti, l’abbinamento stabile potrebbe anche non esistere. Oppure possiamo avere lo stesso problema sopra con studenti e professori, ma avere più studenti che professori (un professore può avere più tesisti). In entrambi i casi esistono appositi algoritmi per risolvere i problemi.