Dopo aver spiegato come la teoria dei giochi può aiutare i capovillaggi a sposare i giovani in età da matrimonio, erano rimaste in sospeso alcune questioni a cui è tempo di dare risposta.

Esistono altre soluzioni stabili?

Per il problema del matrimonio, in cui è necessario formare delle coppie tra due gruppi distinti (che possono essere uomini e donne da sposare, ma anche potenziali donatori di organi e pazienti che necessitano un trapianto o candidati e offerte di lavoro…) almeno una soluzione stabile esiste sempre.

Come abbiamo già scritto, la soluzione stabile si trova utilizzando un algoritmo in cui uno dei due gruppi si reca a visitare l’altro gruppo, che rimane in attesa e seleziona ad ogni passaggio, tra tutti i corteggiatori disponibili, quello che preferisce. Utilizzando l’algoritmo in cui le donne visitano gli uomini o quello in cui gli uomini visitano le donne, solitamente si trovano due soluzioni diverse. Tra tutte le soluzioni stabili, quella migliore per un gruppo è quella in cui quel gruppo si reca a far visita all’altro, questa al tempo stesso è la peggior soluzione possibile per il gruppo che rimane fermo in attesa di ricevere le visite. In alcuni casi possono esistere altre soluzioni stabili intermedie tra queste due estreme che favoriscono e penalizzano sempre uno dei due gruppi. Ad esempio, utilizziamo ancora tre ragazze Anna, Beatrice, Carlotta e i tre ragazzi Daniele, Ermanno e Francesco con queste preferenze:

A:D>E>F       D:C>B>A
B:D>F>E       E:B>A>C
C:F>D>E       F:A>B>C

Le due soluzioni stabili che si possono trovare utilizzando l’algoritmo di Gale e Shapley sono (A,E), (B,D), (C,F) (la migliore per le ragazze) e (A,F), (B,E), (C,D) (migliore dal punto di vista dei ragazzi).

Cercando un compromesso tra queste due soluzioni si può provare a rompere la coppia (A,F) e formare la coppia A,E per dare ad A un partner migliore; F, rimasto libero, può essere accoppiato a B che è la sua seconda preferenza. In questo modo si formano le coppie (A,E), (B,F), (C,D): anche questa è una soluzione stabile! E non è né la migliore né la peggiore per uno dei due gruppi di giocatori.

Per individuare le (altre) soluzioni stabili si può procedere a tentativi, verificando uno ad uno tutti i possibili accoppiamenti (che se ci sono n uomini e n donne sono n!) in cerca di quelli stabili. Oppure si può partire da una soluzione stabile, cercando di rompere una ad una le coppie, migliorando la situazione di un gruppo e peggiorando quella dell’altro in cerca di altre soluzioni stabili. Purtroppo si tratta comunque di procedere per forza bruta, controllando ad ogni passaggio se ci sono coppie che obiettano e preferiscono stare insieme tradendo i loro partner, fino alla determinazione di una soluzione stabile.

Sposarsi non è obbligatorio

Quando il numero di ragazzi e ragazze è diverso, è inevitabile che rimarranno dei single nel gruppo più numeroso. Se ad esempio ci fosse una sola ragazza Anna e due ragazzi, è immediato trovare come soluzione la coppia tra Anna e il ragazzo che lei preferisce, mentre il secondo ragazzo rimarrebbe da solo.

Ma se non tutti fossero disposti a sposarsi per forza? Ovviamente possiamo aggiungere la possibilità di rimanere single tra le preferenze dei giocatori:  l’opzione “single” è equivalente ad un giocatore fantasma che ha come preferenza al primo posto tutti i giocatori. In questo modo ognuno rimarrà senza partner, solo quando ha ricevuto proposte da partner a cui preferisce rimanere single o quando è stato scartato da tutti i partner che preferisce alla possibilità di rimanere da solo.

Immaginiamo che nell’esempio precedente, Beatrice proprio non ne voglia sapere di stare con Ermanno, cambiamo così la sua preferenza: D>F>single>E. Nel caso in cui gli uomini corteggino le donne, la soluzione stabile diventa (A,E), (B,F), (C,D). Se aggiungiamo che Ermanno desidera stare con Beatrice o con nessun’altra, allora una soluzione stabile è (A,D), (C,F) Ermanno e Beatrice da soli. Potete proseguire con tutte le variazioni che preferite nelle preferenze dei giocatori per vedere quali siano gli esiti sulla formazione di coppie stabili.

E per il matrimonio omosessuale?

Il problema di creare delle coppie all’interno dello stesso gruppo (come ad esempio cercare un partner tra persone dello stesso sesso) è discusso solitamente come il problema dei compagni di stanza, che possiamo raccontare così:

Durante una gita scolastica, i professori devono dividere le ragazze in stanze doppie. Ogni ragazza ha ovviamente delle preferenze sulle sue compagne, esiste un modo per formare le camere assicurandosi che non ci siano discussioni e le ragazze non si spostino nel corso della notte cambiando compagna di stanza?

In questo caso le differenze con l’esempio iniziale sono maggiori, perché non esistono più due gruppi distinti ma un unico gruppo di giocatori N in cui ogni elemento esprime preferenze sugli altri.

Immaginiamo ad esempio di avere quattro compagne: Anna, Barbara, Cecilia e Denise e che queste siano le loro preferenze:

A: B>C>D
B: C>A>D
C: A>B>D
D: A>B>C

In questo caso tutte le possibili coppie sono solo tre, quindi possiamo anche procedere a tentativi alla ricerca di una soluzione stabile: (A,B) (C,D) non è una soluzione stabile perché C e B preferiscono stare insieme piuttosto che con le compagne assegnate dai prof. Potremmo provare ad accontentare queste due ragazze formand le camere (B,C) (A,D) ma in questo caso A e C si lamenterebbero e cercherebbero di stare insieme. La possibilità rimasta è quindi formare le coppie (A,C) (B,D), ma anche in questo caso A e B si lamenterebbero preferendo stare insieme che con le loro attuali compagne. Purtroppo il problema dei coinquilini può non avere soluzioni stabili, ma a seconda delle preferenze dei giocatori possono crearsi dei “cicli” di questo tipo in cui si trova sempre una coppia disposta a rompere la soluzione proposta per ottenere di meglio.

Matrimoni poligami e liste d’attesa

Come abbiamo già raccontato, l’articolo originale di Shapley e Gale era intitolato “College admission and the stability of marriage”. La prima parte del titolo fa riferimento al problema di come associare gli studenti alle varie università cercando di soddisfare sia le preferenze degli studenti che delle università, immaginando che ogni college abbia un numero limitato di posti a disposizione.

Utilizzando ancora la metafora della ricerca del partner ideale, questo problema è quello di trovare matrimoni stabili nella situazione di poligamia: i college rappresentano gli uomini (o le donne) che possono essere sposati con più di un partner (visto che più di uno studente si recherà nella stessa università). Anche in questo caso, esiste almeno una soluzione stabile per cui le università non si vedranno gli studenti scappare in cerca di offerte migliori, dopo averli immatricolati e, viceversa, gli studenti non verranno scartati per candidati migliori, dopo essere stati accettati. L’algoritmo per individuare la soluzione è simile a quello del matching semplice, bisogna solo aggiungere la maggiore “disponibilità” di alcuni elementi ad accogliere potenziali partner introducendo delle copie dei giocatori che possono avere più di un partner.

Ad esempio, immaginiamo ci siano tre studenti Alice, Barbara e Carlo che vogliono iscriversi a Harvard dove ci sono due posti disponibili e Yale che ha un solo posto disponibile. Queste sono le preferenze degli studenti

A:Y> H     B:Y> H     C:H> Y  

Le università invece valutano così i candidati

H:C>A>B    Y:B>C>A

Possiamo ritrasformarlo in un gioco con tre università sdoppiando il ruolo di Harvard:

 A:Y> H1> H2      B:Y>H1> H2      C:H1> H2> Y

H1:C>A> B     H2:C> A> B      Y:B> C> A

Se utilizziamo l’algoritmo con gli studenti che “visitano” le università Alice e Barbara si iscriveranno a Yale, mentre Carlo andrà ad Harvard; d’altra parte se invece favoriamo le università, Carlo e Alice andranno ad Harvard, mentre Barbara verrà ammessa da Yale.

Proprio grazie al lavoro in questo settore, nel 2012 il premio Nobel per l’economia è stato assegnato a Shapley, l’autore dell’algoritmo per risolvere il problema, e Roth, che si è occupato di mettere in pratica questi algoritmi in casi concreti come la distribuzione degli studenti nei college di New York e l’assegnazione degli specializzandi in medicina negli ospedali. Risolvendo questi problemi, ne è saltato fuori un altro altrettanto interessante: spesso gli specializzandi di medicina sono sposati con altri specializzandi medici, quindi diventava necessario non solo accoppiare uno specializzando con un ospedale, ma anche il suo partner con lo stesso ospedale o un ospedale sufficientemente vicino. Purtroppo però il problema di accoppiare “coppie” con “ospedali” non ha una soluzione così immediata e elegante anzi, i calcoli necessari per trovare una soluzione crescono velocemente in funzione del numero dei giocatori, è addirittura un problema NP completo!

La matematica e la teoria dei giochi possono aiutare, ma ancora non sono riusciti a risolvere tutti i possibili problemi di coppia!

Per saperne di più (in inglese)…

Un video di Numberphile: https://www.youtube.com/watch?v=Qcv1IqHWAzg
L’articolo di Gale e Shapley: College admission and the stability of marriage

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.