It’s a (stable) match!

It’s a (stable) match!
Figura 1: [Fonte:Pixabay.com]

Quante volte avete sentito dire che l’amore è una questione di chimica?

Molecole che vengono scambiate, recettori che si attivano, tutti i sensi vengono coinvolti…

Oggi, però, voglio parlarvi dell’amore dal punto di vista… matematico.

Cosa?

Ah, ho capito, ci parli dell’amore per la matematica, dell’armonia delle leggi che governano l’Universo e tutte queste cose lette e rilette cento volte.

E invece no!

Oggi vi parlerò proprio dell’amore tra due persone da un punto di vista matematico e vi darò qualche suggerimento su come ottimizzare i vostri approcci (non sono proprio la persona più indicata per questo, ma ho un po’ di Matematica a supportarmi).

Secondo voi, in una app di incontri, è più conveniente proporsi, o aspettare che arrivino le proposte?

Siete curiosi, eh?

Iniziamo con una classica suddivisione in due insiemi: gli uomini costituiranno il nostro insieme U e le donne andranno a formare l’insieme D.

Supponiamo di avere nella nostra app di incontri N uomini e N donne, che vogliamo unire a formare delle coppie stabili.

Cosa intendiamo con coppia stabile?

Ve lo spiego con un esempio.

Supponiamo di avere due coppie, una formata da Anna e Andrea e l’altra formata da Marco e Martina.

Nelle coppie sorgerà un’instabilità, ad esempio, qualora ad Anna piaccia Marco più di Andrea e, viceversa, a Marco piaccia Anna più di Martina.

In questo caso le due coppie si scioglieranno, e Marco e Anna si metteranno insieme.

Ecco, noi vogliamo evitare questa situazione.

Quindi, formalizzando un attimo il tutto e sintetizzando, diremo che un insieme di coppie è instabile qualora ci siano un uomo e una donna non sposati tra loro, che però preferiscono l’un l’altro ai rispettivi compagni attuali.

Notate che qualora a Marco piacesse più Anna di Martina, ma ad Anna piacesse comunque più Andrea di Marco, non avremmo un’instabilità (per accoppiarsi serve il consenso di entrambi, vero?).

Riprendiamo ora i nostri insiemi di N donne e N uomini e supponiamo che sia gli uomini che le donne abbiano stilato una classifica dei loro partner ideali in ordine di preferenza.

A questo punto, ricordiamo che vogliamo formare solamente coppie stabili.

Quindi, ci chiediamo: è sempre possibile formare un insieme di coppie stabili?

La risposta è… SI.

Applicando l’algoritmo di Gale – Shapley, si dimostra 

 Teorema: Esiste sempre un insieme di matrimoni stabili.

Dimostriamolo applicando l’algoritmo.

Supponiamo che siano gli uomini a proporsi alle donne.

GIORNO 1: tutti i ragazzi si propongono alla prima ragazza nella loro lista. Una ragazza potrà allora ricevere una o più proposte, o nessuna.

Se una ragazza ha ricevuto più proposte, tiene la persona che si è proposta che si trova più in alto nella sua classifica di gradimento, scartando gli altri.

GIORNO 2: i ragazzi scartati passano a proporsi alla seconda ragazza nelle loro liste, e si ripete quanto avvenuto al giorno precedente.

Notate che se il giorno precedente una ragazza aveva già un partner, e il giorno successivo riceve una proposta migliore per lei, questa può scartare il precedente partner per tenere quello nuovo.

L’algoritmo termina quando ogni ragazza ha ricevuto almeno una proposta e si sono formate delle coppie.

Ma queste coppie sono stabili?

Torniamo al nostro esempio precedente con le coppie (Anna, Andrea) e (Marco, Martina).

Supponiamo che a Marco piaccia di più Anna. Ma allora vuol dire che Marco si è proposto prima ad Anna, la quale lo ha rifiutato in favore di Andrea.

Quindi, a Marco piace di più Anna, ma ad Anna piace di più Andrea, e i matrimoni sono stabili (non per forza devono essere felici).

Abbiamo quindi dimostrato che è sempre possibile formare delle coppie stabili.

[Figura 2: Ora che le coppie sono formate, potete felicemente convolare a nozze (Fonte: Pixabay.com)]

Vediamo ora se è più conveniente fare la prima mossa, aspettare le proposte, o se è indifferente.

Siete pronti con la vostra app di dating a fare swipe right?

Abbiamo visto che gli uomini che si proponevano potevano essere accettati, ma poi anche velocemente scartati. 

Poveri uomini, eh?

Ma siamo proprio sicuri che ci vada così male?

Diamo prima qualche definizione per chiarire la situazione e capire cosa intendiamo con ottimalità di un partner.

Nel caso del ragazzo che si propone alla ragazza, diremo che la partner ottimale per un uomo è la donna che si trova più in alto nella sua lista, con la quale può formare una coppia stabile.

In pratica, è il miglior matrimonio che l’uomo possa sperare.

E ora, signori e signore, ATTENZIONE:

Teorema: L’algoritmo in cui l’uomo si propone è ottimale per l’uomo. 

Ehm…ragazzi, ci siete ancora o avete già chiuso tutto per tuffarvi nel mondo del dating?

Se ci siete, ora lo dimostreremo.

Supponiamo per assurdo che il nostro algoritmo non sia ottimale per l’uomo.

Supponiamo che per Andrea la donna ottimale sia Anna.

Ora, supponiamo che al giorno k  avvenga il primo rifiuto di un uomo da parte della sua donna ottimale. 

In quel giorno Andrea viene rifiutato da Anna, a cui piace Marco, che le si è proposto.

Abbiamo però supposto che Anna sia la donna ottimale per Andrea, quindi la donna più in alto nella sua lista, con la quale possa formare una coppia stabile.

Allora, per definizione di ottimalità, possiamo affermare che esisterà un set di coppie stabili T = {…, (Anna, Andrea), …, (Marco, Martina),…}.

Dimostriamo allora che la coppia (Anna, Marco) può destabilizzare i matrimoni.

E’ evidente che ad Anna piaccia di più Marco rispetto ad Andrea, in quanto ha scartato Andrea in favore di Marco.

Ora, poiché il giorno k è il primo giorno in cui un uomo è rifiutato dalla sua donna ottimale, possiamo concludere che al giorno k Marco non era ancora stato rifiutato dalla sua donna ottimale.

Poiché Marco si è proposto ad Anna al giorno k, possiamo concludere che a Marco piaccia Anna almeno quanto la sua donna ottimale (Martina).

Ma, allora, la coppia (Marco, Anna) costituirà un elemento di instabilità nel nostro set di coppie T. 

Dunque T non è stabile.

CONTRADDIZIONE!

Quindi la nostra assunzione di partenza, ossia che l’algoritmo non sia ottimale per l’uomo, è errata.

In modo simile si potrebbe dimostrare che, se nell’algoritmo l’uomo si propone, il partner finale risulta essere pessimo per la donna.

Questo vorrà dire che, tra tutte le possibilità di partner stabili che una determinata donna avrebbe potuto avere, ha scelto il peggiore (il meno preferito, dai, non siamo troppo cattivi).

Concludo brevemente accennando che questo algoritmo può essere applicato anche al problema di assegnazione degli studenti a diverse università (trovate la spiegazione completa al link nelle fonti).

Ok, potete tornare ai vostri approcci.

Buona fortuna!

*L’autore tiene a precisare che i nomi utilizzati sono a puro scopo didattico e non sottintendono relazioni realmente esistenti ☺

Andrea Marangoni

Laurea Magistrale in Fisica con una tesi sui dischi circumstellari presso l’Università degli Studi di Padova.

Appassionato di scienza fin da bambino, tifoso della Juventus, nel tempo libero mi piace dedicarmi all’attività fisica. 

“I’m just a mad man in a box”.

Fonti:

Tag: