L’algoritmo Gale-Shapley che aiuta i matematici… a cuccare!
Un accanito lettore de La Tigre di Carta che abbia scorso ogni tanto la colonna di matematica avrà oramai capito, lo spero bene, che questa temuta materia si nasconde in realtà placida un po’ dovunque, e anche quando meno ce lo si aspetta permette di ottenere una visione molto più profonda della verità. Ma cosa può essa rivelarci quando si parla di attrazione reciproca dei generi e di promesse di matrimonio?
Supponiamo di avere N uomini (Alceo, Bacco, Cleandro…) e N donne (Ancilla, Brunilde, Cleofe…), qualsiasi sia N, e di volere creare delle coppie uomo-donna (lo so, siamo nel 2018 e un po’ di apertura mentale non farebbe male, ma il problema è stato formulato così…). Immaginiamo che ciascuno abbia delle preferenze rispetto ai possibili partner del sesso opposto, cioè che abbia una lista di nomi che va da chi viene considerato più attraente, intelligente, ecc., fino al meno interessante. Ad esempio, la lista di Ancilla potrà essere: Bacco, Cleandro, Alceo…, mentre quella di Bacco potrà essere: Ancilla, Cleofe, Brunilde…
Ancilla Brunilde Cleofe + Alceo Bacco Cleandro. Illustrazione di Francesca Cavallero
Vogliamo fare in modo che non ci siano né scapoli, né zitelle, e inoltre che gli N matrimoni siano stabili, ovvero che non esistano un uomo e una donna che preferiscono entrambi essersi sposati l’uno con l’altra rispetto alle persone con cui sono sposati attualmente. Questo succederebbe se, quando qualcuno non è sposato con la sua prima scelta e dunque preferirebbe qualche altra persona, questa stessa persona a sua volta lo preferisca al suo partner attuale. Ad esempio, considerando le preferenze di Ancilla e Bacco proposte sopra, se Bacco fosse sposato con Cleofe e Ancilla con Alceo, questa scelta di matrimoni non sarebbe stabile, perché entrambi Ancilla e Bacco preferirebbero l’un l’altra ai loro partner proposti, che quindi lascerebbero per sposarsi insieme.
Il problema dei matrimoni stabili è dunque questo: per N uomini e N donne, che abbiano fornito una lista di preferenze tra i componenti dell’altro sesso, occorre trovare degli accoppiamenti in modo tale che tutti siano sposati e che i matrimoni siano stabili, ovvero non esistano una donna e un uomo che non sono sposati tra loro ma che preferirebbero esserlo rispetto ai loro partner attuali.
Non è per nulla chiaro se una soluzione al problema esista! Non sentiamo forse nella vita di tutti i giorni di storie d’amore complicatissime, anche tra un numero ridotto di ragazzi e ragazze? Se c’è qualcuno che possa venire a capo di questo millenario dilemma, non possono che essere i matematici, famosi per il loro carisma seducente e il loro savoir-faire in quanto a seduzione… o forse più per la loro innata capacità di risolvere problemi. Qualunque sia la ragione, i matematici David Gale and Lloyd Shapley[1] sono riusciti, nel 1962, a dimostrare che per qualsiasi N esiste sempre una soluzione al problema dei matrimoni stabili. Non solo: hanno fornito anche un algoritmo da impiegare per ottenere una configurazione stabile, fornendo quindi una dimostrazione costruttiva dell’esistenza di (almeno) una soluzione possibile: essa esiste, perché la trovo in questa maniera qui. L’algoritmo da loro proposto è il seguente.
Passo 1. Ciascun uomo si propone alla donna che compare come sua prima scelta. Se gli uomini hanno tutti proposto un matrimonio a donne diverse, abbiamo finito, altrimenti alcune donne avranno ottenuto più di una proposta, altre nessuna. Ogni donna a cui è stata fatta almeno una proposta risponde “forse” all’uomo che preferisce tra tutti quelli che si sono rivolti a lei, rigettando (se ce ne sono) gli altri, e si formano così delle coppie temporanee, mentre ci saranno degli uomini e delle donne ancora senza partner.
Passo 2. Ciascun uomo che ancora non ha una compagna si propone alla sua prossima scelta, indipendentemente dal fatto che lei abbia già un fiancé temporaneo o no. Ciascuna donna può ora scegliere fra tutte queste proposte (più eventualmente il suo compagno temporaneo del passo precedente, se ne aveva ottenuto uno) il candidato che le va più a genio, a cui dice “forse”, rigettando (sempre se ce ne sono) gli altri. A questo punto: o tutti gli uomini hanno trovato una compagna, e allora abbiamo finito, oppure no, e rimangono quindi ancora degli uomini e delle donne soli.
Passi successivi. Il passo precedente viene iterato finché tutti non abbiano trovato un partner temporaneo. Raggiunta questa situazione, le coppie ottenute possono finalmente sposarsi.
Ci sono due domande che sorgono immediatamente dopo aver letto la descrizione dell’algoritmo: siamo sicuri che esso effettivamente abbia una fine e non continui all’infinito? E, se sì, i matrimoni così ottenuti sono stabili, secondo la definizione data sopra? Possiamo rispondere “sì” a entrambe.
Innanzitutto, dopo al più N iterazioni, non può esserci neanche una donna che abbia ricevuto zero proposte e non abbia trovato almeno un partner temporaneo, perché altrimenti ci sarebbe un uomo anch’egli senza compagna, il quale, a un certo momento, dovrà pur essersi proposto a lei; d’altra parte, ogni donna riceve una proposta da ciascun uomo al massimo una volta sola, quindi non può succedere che delle donne si “rimbalzino” a vicenda degli uomini all’infinito. Quindi l’algoritmo deve terminare, e si raggiunge dunque una situazione in cui ogni donna è accoppiata a ogni uomo, e viceversa. D’altra parte, la soluzione che viene così trovata è effettivamente stabile. Infatti, se un uomo dovesse preferire un’altra donna alla sua sposa così trovata, egli necessariamente si sarebbe già rivolto a lei, e se lei non è diventata sua moglie è solo perché ha potuto scegliere un altro uomo che considerava migliore.
Sembrerebbe così che questo algoritmo favorisca le donne, dato che hanno il potere di scegliere fra tutti i contendenti. In realtà la soluzione stabile trovata, che, come vedremo, non è l’unica possibile in generale, favorisce sempre il gruppo che fa le proposte e sfavorisce quello che decide se accettarle o scartarle. Se sono gli uomini a proporsi, uno qualsiasi tra questi comincia “a provarci” sempre a partire dalle donne che considerava migliori, e una volta che ha ottenuto un “forse” da una di queste (ed è il matching più felice che poteva ottenere in ogni caso, dato che tutte le altre si sono già fidanzate con uomini che considerano migliori di lui), se viene poi rigettato da questa e deve accontentarsi di un’altra è solo perché altrimenti il loro matrimonio darebbe vita a una situazione instabile (ci sarebbe un secondo uomo che preferirebbe alla sua compagna la sposa del primo, e anche questa preferirebbe cambiare e sposarsi con questo secondo uomo). Banalmente, quando sono gli uomini a proporsi, ciascuno se la gioca sempre per le donne che preferisce. Invece, una donna rischia di non ricevere mai le proposte degli uomini che considera più interessanti, perché questi possono aver già ottenuto un “forse” da altre donne che consideravano migliori e questo “forse” potrà alla fine trasformarsi in un “sì”. Per fare un esempio concreto con N = 3, consideriamo ancora i nostri amici Alceo, Bacco e Cleandro, e le nostre amiche Ancilla, Brunilde e Cleofe. Per semplicità, indichiamo i tre uomini con α, β, γ, e le tre donne con A, B, C. Supponiamo che le preferenze di α siano in ordine A, C, B, quelle di β siano B, A, C, e quelle di γ siano C, B, A; inoltre supponiamo che le preferenze di A siano γ, β, α, quelle di B siano α, γ, β, e quelle di C siano β, α, γ. Ci sono tre possibili accoppiamenti (donna, uomo) che sono stabili: il primo è (A,α), (B,β), (C,γ), il secondo (A,β), (B,γ), (C,α), e il terzo (A,γ), (B,α), (C,β). Nel primo, gli uomini ottengono tutti quanti le loro prime scelte mentre le donne le loro terze scelte: questo è quello che succede se si applica l’algoritmo di Gale-Shapley con gli uomini che propongono; nel secondo uomini e donne ottengono tutti le loro seconde scelte, e non si può mai ottenere con un algoritmo tipo quello di Gale-Shapley; nel terzo sono le donne a ottenere le loro prime scelte, e vi si giungerebbe applicando Gale-Shapley, lasciando alle donne il compito di proporsi agli uomini.
Cosa impariamo dunque da questo algoritmo? Che in amore vale la pena lanciarci, proporci e, se ci va male, provarci di nuovo! È la matematica che ce lo dice.
Note
[1] Nel 2012 Shapley ha ricevuto insieme ad Alvin Roth il Premio Nobel per l’economia per il lavoro che i due hanno svolto nell’ambito della cosiddetta matching theory, che ha appunto molte applicazioni in economia.
