Blog divulgativo sulla matematica applicata

Teoria dei giochi: il problema delle coppie

corbis_42-21306094-630x360Come esser sicuri di star sposando la persona giusta? La teoria dei giochi può aiutarvi nella scelta di un partner che... non vi tradirà!

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 capo-villaggio è 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?

Il modello sottostante a questa storia è quello di un problema di matching: ci sono due insiemi, quello degli uomini \mathcal{M} e quello delle donne \mathcal{W}, ogni elemento di un insieme ha delle preferenze su tutti gli elementi del secondo insieme e una soluzione consiste nel creare delle coppie associando un elemento di \mathcal{M} con un elemento di \mathcal{W}. Se ognuno di questi due insiemi fosse composto da un solo elemento, si potrebbe formare una sola coppia e il problema sarebbe facilmente risolto. Ma già con due uomini e due donne, ci sono due diverse soluzioni: come individuare la migliore? E per numero qualsiasi di uomini e di donne, cosa si può fare? Per agevolare il discorso immaginiamo di avere solo tre ragazze Anna, Beatrice e Carlotta, d'ora in poi semplicemente A,B,C e tre ragazzi Daniele, Ermanno e Francesco, d'ora in poi D,E,F.

Ovviamente la soluzione dipende dalle preferenze dei giocatori. Iniziamo con un caso semplice in cui ogni ragazza preferisce un ragazzo diverso, ad esempio:

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

e dall'altra parte anche le preferenze dei ragazzi sono tutte diverse tra loro:

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

Proviamo a prendere una soluzione qualsiasi: (A,F),(B,E),(C,D). E' una soluzione stabile, ovvero in cui non ci saranno dei tradimenti?
Osserviamo la coppia (A,F): ognuno dei due trova il suo partner il peggior partner possibile. Ad esempio F preferirebbe stare con B, ma B si trova già con E che è la sua migliore scelta quindi non ha intenzione di tradirlo! Invece C, che F preferisce comunque ad A, si trova con D ma preferirebbe stare con F: si individua così la coppia (C,F) che è disposta a tradire i propri partner per stare insieme! Questa soluzione è instabile! Una soluzione stabile è invece una proposta di coppie in cui non c'è nessuna coppia di giocatori che può migliorare la sua situazione tradendo il proprio partner attuale e formando una nuova coppia insieme.

boy-1300250_640

Nell'esempio che stiamo osservando una soluzione stabile è quella che lega ogni donna alla sua prima preferenza, si formano così le coppie (A,D),(B,E),(C,F). Anche se gli uomini non sono completamente soddisfatti questa soluzione è stabile: le donne si trovano tutte con la loro prima preferenza e nessuna di loro è disposta a tradire il proprio partner, quindi non si trova una coppia (composta da un uomo e da una donna) che obietta a questa proposta e in cui entrambi potrebbero migliorare la loro situazione. Analogamente, una soluzione stabile è data da abbinare gli uomini con la loro prima preferenza (D,C),(E,A)(F,B).

Cosa fare quando le preferenze non sono così semplici e distinte?
In un articolo del 1962 dal titolo "On college admission and the stability of marriage'', due matematici ed economisti americani, Gale e Shapley hanno introdotto un algoritmo per determinare una soluzione stabile (che quindi esiste sempre!).

Per individuare le coppie da sposare il capo-villaggio deve avere la pazienza di aspettare alcuni giorni e organizzare così il corteggiamento:

  1. Giorno 1: Ogni uomo si reca a visitare la donna in cima al suo elenco di preferenze.
    1.  Se tutte le donne ricevono la visita di un solo uomo, la fase di corteggiamento è finita. Ogni uomo e ogni donna si possono fidanzare e abbiamo trovato una soluzione stabile (siamo nel caso semplice di cui abbiamo già visto un esempio).boy-1300249_1280
    2. Se invece alcune donne hanno ricevuto più di un uomo in visita, allora
      ognuna di loro sceglie l'uomo che preferisce tra i suoi attuali pretendenti.
    3. Gli uomini che sono stati rifiutati tornano a casa e le donne che non hanno ricevuto nessuna visita aspettano.
  2. Giorno 2: Gli uomini che si trovano senza una compagna si recano a visitare la loro seconda preferenza.
    1.  Se tutte le donne hanno un solo pretendente, la fase di corteggiamento
      è finita.
    2.  Tutte le donne che hanno più di un pretendente (incluso quello eventualmente accettato il primo giorno) scelgono l'uomo che  preferiscono e mandano via tutti gli altri.
  3.  Giorno 3: Gli uomini che si trovano senza una compagna si recano a visitare la donna successiva nelle loro preferenze...

Dopo certo numero (finito!) di notti ogni uomo e ogni donna si troveranno con un solo partner ponendo la fine alla fase di corteggiamento: il capovillaggio può sposare le coppie che si sono formate! La soluzione così trovata è infatti stabile: ogni uomo non può scappare con una donna che preferisce alla sua partner attuale, perché ha visitato le donne in ordine di preferenza ed è stato scartato da tutte le donne migliori rispetto alla sua partner finale perché le altre hanno preferito altri uomini (che quindi non sono disposte a tradire!). Dall'altra parte, ogni donna ha avuto l'opportunità di scegliere sempre il migliore tra gli uomini che erano interessati a lei, quindi neanche le donne hanno l'opportunità di tradire il proprio partner e ottenere una sistemazione migliore.

Ovviamente la situazione è simmetrica, potremmo immaginare che siano le donne a far visita agli uomini seguendo le loro preferenze. E' possibile boy-1300251_1280dimostrare che tra tutte le soluzioni stabili, quella in cui gli uomini visitano le donne è la migliore per tutti gli uomini e contemporaneamente la peggiore per tutte le donne. Quindi è meglio... farsi avanti per primi!

Ad esempio,  se le preferenze delle donne e degli uomini sono:

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

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

la soluzione ottenuta con le donne a visitare gli uomini è (A,D),(B,E),(C,F), mentre quando sono gli uomini a visitare si arriva a (B,D),(A,E),(C,F). Esistono altre soluzioni stabili? Se sì, come si possono individuare?

E se il numero di uomini e di donne non fosse lo stesso? O se qualcuno preferisse rimanere single piuttosto che sposarsi ad ogni costo? Se prendessimo in considerazione il matrimonio tra persone dello stesso sesso, cambierebbe qualcosa? E perché l'articolo in cui è stato introdotto l'algoritmo che abbiamo descritto parlava della stabilità del matrimonio e anche dell'ammissione al college?

I "problemi di coppia'' non si sono esauriti! Ci sono ancora delle questioni che lasciamo in sospeso fino al prossimo intervento...

 

Per continuare a leggere di questo argomento...
Un articolo da Matematica e Cultura 2006: http://virgo.unive.it/licalzi/GiocoCoppie.pdf

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

Similar posts

2 commenti

  1. Raffaele Quatraro's Gravatar Raffaele Quatraro
    dicembre 6, 2016    

    Molto bello questo articolo :-)

  2. Osvaldo P.'s Gravatar Osvaldo P.
    luglio 29, 2017    

    Articolo veramente interessante!
    Tuttavia, benché la situazione sia speculare (uomini che vanno a trovare donne = donne che vanno a trovare uomini), forse quella presentata è la più "cavalleresca". Del resto può succedere che un uomo scelto il primo giorno, il terzo giorno si ritrovi di nuovo single, perché il secondo giorno la donna ha ricevuto la visita di un uomo (single) più attraente per lei.
    Ma per fortuna è solo un gioco matematico..... o no?

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination