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
modifica
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.[1][2]
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 , dove è il numero di uomini o donne.[3]
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.[4]
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è.[5] Tuttavia, alcune coalizioni potrebbero ottenere i partner ottimali, lasciando che altri non li ottengano.[6] 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.
Note
modifica- ^ D. Gale e L. S. Shapley, College Admissions and the Stability of Marriage, in The American Mathematical Monthly, vol. 69, n. 1, 1º gennaio 1962, pp. 9-15, DOI:10.1080/00029890.1962.11989827. URL consultato il 12 febbraio 2025.
- ^ Harry Mairson, The Stable Marriage Problem, su www1.cs.columbia.edu, vol. 12, The Brandeis Review, 1992. URL consultato il 12 febbraio 2025.
- ^ Kazuo Iwama e Shuichi Miyazaki, A Survey of the Stable Marriage Problem and Its Variants, in International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008), 2008-01, pp. 131-136, DOI:10.1109/ICKS.2008.7. URL consultato il 12 febbraio 2025.
- ^ Jeff Erickson, Greedy Algorithms (PDF), in Algorithms, Università dell'Illinois, Giugno 2019, pp. 170-176.
- ^ L. E. Dubins e D. A. Freedman, Machiavelli and the Gale-Shapley Algorithm, in The American Mathematical Monthly, vol. 88, n. 7, 1º agosto 1981, pp. 485-494, DOI:10.1080/00029890.1981.11995301. URL consultato il 12 febbraio 2025.
- ^ (EN) Chien-Chung Huang, Cheating by Men in the Gale-Shapley Stable Matching Algorithm, in Yossi Azar, Thomas Erlebach (a cura di), Algorithms – ESA 2006, Springer, 2006, pp. 418-431, DOI:10.1007/11841036_39. URL consultato il 12 febbraio 2025.
Bibliografia
modifica- Kleinberg, J. e Tardos, E. (2005) Algorithm Design, capitolo 1, pp 1-12. Vedere il sito Web di accompagnamento per il testo [1] Archiviato il 14 maggio 2011 in Internet Archive.
- Vedere Sezione 10.6.4; scaricabile gratuitamente online.
Voci correlate
modifica- Corrispondenza (teoria dei grafi) : corrispondenza tra diversi vertici del grafo; solitamente non correlato all'ordinamento delle preferenze.
Collegamenti esterni
modifica- Beatrice Bernardini - Il problema del matrimonio stabile - Uniroma3 (PDF), su ricerca.mat.uniroma3.it.
| Controllo di autorità | LCCN (EN) sh85081518 · BNF (FR) cb12372391v (data) · J9U (EN, HE) 987007553378805171 |
|---|
