Altro

    Il problema delle coppie perfette: dal matrimonio all’università dei sogni

    Il problema delle coppie perfette: dal matrimonio all’università dei sogni

    Il tema dell’amore, o più in generale delle relazioni interpersonali, è diventato oggetto di studio in varie branche della Matematica nel corso del XX secolo. Sergio Rinaldi, docente di matematica del Politecnico di Milano, è stato il primo a studiare seriamente le relazioni amorose da un punto di vista matematico, partendo dall’analisi di una delle opere poetiche più romantiche che siano mai state scritte: il Canzoniere di Petrarca. La sua opera è raccolta nel testo “Modeling Love Dynamics”, pubblicato nel 2016 da World Scientific.

    Cambiando punto di vista, Gale e Shapley nel 1962, hanno introdotto il cosiddetto Problema del matching che ricade nell’ambito della Teoria dei Giochi. In questo articolo andremo ad analizzare quest’ultimo problema, ma prima consideriamo alcuni esempi:

    • In un villaggio, isolato dal resto del mondo, si trova un gruppo di donne e di uomini che, avendo raggiunto la maggiore età, si devono sposare entro la fine dell’anno. Il capovillaggio è incaricato di celebrare i matrimoni e deve decidere quali siano le coppie da formare in modo che tutti i giovani siano felicemente sposati, senza divorzi e tradimenti. Come può fare?
    • Un gruppo di studenti, terminati gli anni delle scuole superiori, si trova di fronte ad una delle scelte più importanti della propria vita: la scelta dell’università. Stilano pertanto una lista in base alle loro preferenze. D’altro canto, però, le università non possono accogliere tutte le domande e quindi dovranno redigere un ranking sugli studenti. Come è possibile far sì che nessuno studente sia scontento e pertanto invogliato a cambiare facoltà?
    • Il primario di un ospedale si trova di fronte il nuovo gruppo di specializzandi. Ognuno ha ambizioni e interessi diversi e quindi è necessario che a ciascuno di essi venga assegnata una specializzazione in linea con le aspettative. Come può fare il primario per evitare scontenti all’interno del suo staff?

    Questi problemi, sebbene apparentemente molto diversi, possono essere messi a fattor comune sotto un’unica teoria e trattazione, che andremo a scoprire passo per passo. Prendiamo in esame il caso di matching tra uomini e donne, ma tutti i ragionamenti possono essere ripetuti sostituendo i ruoli con gli altri attori presentati.

    Problema del matching Coppie perfette

    Il problema

    La formulazione del problema prevede due insiemi (mathcal{M}) e (mathcal{W}) con la stessa cardinalità (i.e. con lo stesso numero di elementi). Ogni elemento di (mathcal{W}(mathcal{M})) ha un ranking, indicato con (>_m) e (>_W) rispettivamente, sugli tutti gli elementi di (mathcal{M}(mathcal{W})).  L’obiettivo è formare coppie stabili. Per esempio se

    $$ begin{aligned}
    mathcal{W}&={text{Anna,Giulia,Maria}}\
    mathcal{M}&={text{Marco,Luca,Giovanni}}
    end{aligned}$$

    un possibile matching è dato da

    $$ Lambda=[(text{Anna,Marco}),(text{Giulia,Luca}),(text{Maria,Giovanni})]$$

    Non abbiamo ancora specificato però cosa si intende con coppie stabili. Definiamo un matching stabile se nessuna coppia obietta. Una coppia obietta qualora sia l’uomo che la donna si preferiscano a vicenda rispetto alla persona con cui sono stati accoppiati. Ad esempio, se nel matching precedente

    $$ text{Marco}>_{text{Giulia}}text{Luca}quadtext{Giulia}>_text{Marco}text{Anna}$$

    allora non sarà stabile.

    Un algoritmo per la soluzione

    Fortunatamente, ogni problema di matching ammette una soluzione stabile. Vediamo allora come fare a trovare le coppie, assumendo che tutti preferiscano essere accoppiati piuttosto che rimanere soli. Per semplicità di notazione, indichiamo gli uomini con lettere minuscole e le donne con lettere maiuscole. Le preferenze sono le seguenti

    $$ begin{aligned}
    & A>_aB>_aCquad &B>_bA>_bC quad&A>_cB>_cC\
    & a>_Ab>_Acquad &b>_Ba>_Bcquad&a>_C b >_C c
    end{aligned} $$

    Per trovare un matching stabile ricorriamo all’algoritmo di visita:

    1. Il primo giorno ogni donna si reca dalla sua prima scelta. Se ogni uomo si trova con una sola donna l’algoritmo termina. Altrimenti, l’uomo (o gli uomini) che si trova con più di una scelta sceglie in base al suo ranking.
    2. Il secondo giorno le donne rifiutate si recano dalla loro seconda scelta. Analogamente al giorno 1, gli uomini possono accettare o scegliere in base al loro ranking.
    3. L’algoritmo termina quando tutte le donne hanno trovato una compagna.

    Con i profili riportati sopra otteniamo il seguente matching stabile:

    $$ {(a,A),(c,B),(b,C)}$$

    Algoritmo di visita

    La soluzione è unica?

    In generale la risposta è negativa. Infatti, non vi è ragione per affermare che, invertendo i ruoli di uomini e donne nell’algoritmo, si giunga alla stessa soluzione. Per il problema precedente, invertendo i ruoli, si giunge ad un secondo matching:

    $$ {(a,A),(b,B),(c,C)}$$

    Articolo a cura di Mirko Baroni.


    Il problema delle coppie perfette: dal matrimonio all’università dei sogni

    Share

    NEL MONDO
    62,053,970
    Casi totali confermati
    Updated on 28 November 2020 10:37
    All countries
    1,450,271
    Morti totali
    Updated on 28 November 2020 10:37

    GUARDA TUTTI I DATI

    ITALIA

    Italy
    1,538,217
    Casi totali confermati
    Updated on 28 November 2020 10:37
    Italy
    696,647
    Guariti totali
    Updated on 28 November 2020 10:37
    Italy
    787,893
    Attuali positivi totali
    Updated on 28 November 2020 10:37
    Italy
    53,677
    Morti totali
    Updated on 28 November 2020 10:37

    Ultimi articoli

    Alghe stampate in 3D come generatori di ossigeno per i tessuti umani

    A partire dall’uomo nel suo complesso alla più piccola cellula che lo compone, la vita è possibile solo in presenza di un’adeguata quantità di...

    Scoperto un inibitore che potrebbe bloccare la replicazione di SARS-CoV-2

    Quante volte in questi mesi abbiamo sentito che aziende e gruppi di ricerca stavano lavorando ad un antivirale specifico contro il SARS-CoV-2? Ovviamente e,...

    Alla ricerca del moto perpetuo: il Santo Graal per molti studiosi

    La realizzazione della macchina a moto perpetuo ha attirato la curiosità di molti studiosi, diventando un vero e proprio rompicapo. La tenacia e la...

    Cure e vaccini

    Alghe stampate in 3D come generatori di ossigeno per i tessuti umani

    A partire dall’uomo nel suo complesso alla più piccola cellula che lo compone, la vita è possibile solo in presenza di un’adeguata quantità di...

    Alla ricerca del moto perpetuo: il Santo Graal per molti studiosi

    La realizzazione della macchina a moto perpetuo ha attirato la curiosità di molti studiosi, diventando un vero e proprio rompicapo. La tenacia e la...

    Alzheimer e Sindrome di Down, una triste relazione

    La presenza di un cromosoma in più comporta spesso rischi e limitazioni a livello corporeo per tutti i soggetti con Sindrome di Down. Tra...

    Morto Maradona: ad ucciderlo un arresto cardiorespiratorio

    Una notizia che non avremmo mai voluto ricevere quella di questo pomeriggio: Diego Armando Maradona è morto all’età di 60 anni in seguito ad...

    Pompei: ritrovati due corpi intatti, di chi si tratta?

    Come abbiamo letto sui libri e molto probabilmente studiato a scuola, nel 79 d.C. l’eruzione del Vesuvio provocò la completa distruzione delle città di...

    Aggressione con acido: come soccorrere la vittima?

    In una società all’avanguardia, che si evolve velocemente, facendosi portavoce di valori come l’uguaglianza dei diritti degli esseri umani, e che si serve di...

    Articoli correlati

    Alghe stampate in 3D come generatori di ossigeno per i tessuti umani

    A partire dall’uomo nel suo complesso alla più piccola cellula che lo compone, la...

    Scoperto un inibitore che potrebbe bloccare la replicazione di SARS-CoV-2

    Quante volte in questi mesi abbiamo sentito che aziende e gruppi di ricerca stavano...

    Alla ricerca del moto perpetuo: il Santo Graal per molti studiosi

    La realizzazione della macchina a moto perpetuo ha attirato la curiosità di molti studiosi,...

    Alzheimer e Sindrome di Down, una triste relazione

    La presenza di un cromosoma in più comporta spesso rischi e limitazioni a livello...