# Problema del matrimonio stabile

In Matematica, Economia e Informatica, il problema del matrimonio stabile o problema dell'abbinamento stabile è il problema di trovare un abbinamento stabile tra gli elementi di due insiemi di cardinalità uguale, dato un certo ordine di preferenze per ogni elemento. Un abbinamento è stabile se non esistono coppie, in base all'ordinamento scelto, che sarebbero meglio assortite. In altre parole, l'abbinamento (a,b), con a elemento dell'insieme A e b elemento dell'insieme B, non è stabile se:
* a sarebbe meglio abbinato con un elemento di B diverso da b
* b sarebbe meglio abbinato con un elemento di A diverso da a.
Il nome deriva dalla possibilità di formularlo in termini di coppie uomo-donna come segue:
Dati n uomini e n donne, dove ogni persona ha classificato tutti i membri del sesso opposto in ordine di preferenza, far sposare tra loro gli uomini e le donne in modo tale che non ci siano due persone di sesso opposto che preferirebbero avere un altro partner, piuttosto che il loro attuale. Quando tutte le coppie soddisfano queste condizioni, l'insieme dei matrimoni è considerato stabile.

## Soluzione algoritmica

Nel 1962, David Gale e Lloyd Shapley dimostrarono che, a parità di numero di uomini e donne, è sempre possibile risolvere il problema della stabilità del matrimonio, rendendo stabili tutti i matrimoni. Ciò avviene mediante un algoritmo da essi scoperto.
L'algoritmo Gale-Shapley (noto anche come algoritmo di accettazione differita) prevede una serie di "iterazioni":
* Nel primo turno, ogni uomo non impegnato fa la proposta alla donna che preferisce di più, e poi ogni donna risponde "forse" al suo pretendente se lo preferisce di più degli altri, altrimenti "no". È quindi provvisoriamente "impegnata" con il corteggiatore che preferisce di più finora, e anche quel corteggiatore è provvisoriamente impegnato con lei.
* In ogni turno successivo, ogni uomo non impegnato fa la proposta alla donna che preferisce e alla quale non ha ancora chiesto di sposarlo (indipendentemente dal fatto che la donna sia già impegnata), e poi ogni donna risponde "forse" se lei non è attualmente impegnata o se preferisce quest'uomo al suo attuale partner provvisorio (in questo caso, rifiuta il suo attuale partner provvisorio che diventa non impegnato). La natura provvisoria degli impegni preserva il diritto di una donna già impegnata di poter cambiare partner.
* Questo processo viene ripetuto fino a quando tutti sono fidanzati.
Questo algoritmo garantisce che si realizzerà un matrimonio stabile per tutti i partecipanti nel tempo $O(n^{2})$, dove $n$ è il numero di uomini o donne.
Tra tutti i possibili abbinamenti stabili, si ottiene sempre quello che è migliore per tutti gli uomini tra tutti gli abbinamenti stabili, e peggiore per tutte le donne.
Dal punto di vista degli uomini (la parte proponente), si tratta di un cosiddetto meccanismo veritiero (per cui la strategia ottimale per ogni partecipante è essere onesto), vale a dire che nessun uomo può ottenere una corrispondenza migliore per sé, anche travisando le proprie preferenze. Non solo, anche creando una strategia di gruppo da parte degli uomini, vale a dire mettendosi d'accordo per una falsa rappresentazione delle proprie preferenze, non riuscirebbero a ottenere una soluzione migliore per sè. Tuttavia, alcune coalizioni potrebbero ottenere i partner ottimali, lasciando che altri non li ottengano. Al contrario, l'algoritmo non è veritiero per le donne (la parte che effettua la revisione): ogni donna potrebbe travisare le proprie preferenze e ottenere una corrispondenza migliore.