Teoria dei giochi – Introduzione, equilibrio di Nash e primi esempi

Che cos’è un gioco? Un gioco, in termini matematici, non è niente di diverso da un gioco come siamo abitualmente soliti definirli. Tuttavia i giochi matematici racchiudono una classe di situazioni molto più ampie dei comuni giochi cooperativi e non, a cui abbiamo giocato tutti qualche volta.

Teoria dei giochi

Prima di passare alla definizione più teorica, preferisco che tu abbia in testa almeno un esempio di gioco, così da riportare ciò che scriverò al tuo caso. Alcuni giochi sono il pari e dispari, una partita di scacchi, una decisione tra andare al teatro o allo stadio (magari tra marito e moglie), la scelta del gusto del gelato e tutte situazioni ad esse simili.

Si può andare anche più nel complesso come nel caso delle strategie applicate in guerra, ci sono molte trattazioni a riguardo, ma molto più avanzate rispetto alle basi che vedremo qui di seguito.

Si definisce gioco qualsiasi interazione tra due o più oggetti/partecipanti le cui sorti dipendono dalle scelte di questi.

E’ quindi un gioco una qualsiasi situazione in cui va effettuata una decisione, va eseguita un’azione e ciò che accade al termine dell’interazione tra i partecipanti dipende dalle scelte fatte da essi.

Per incuriosirti un po’ ecco uno spezzone di un film che secondo me tutti devono vedere almeno una volta:

Possiamo categorizzare i giochi in funzione delle loro proprietà e modalità di sviluppo. Intanto partiamo con una prima distinzione: giochi in forma normale e giochi in forma estesa.

Non voglio appesantire fin da subito questo articolo, quindi direi che è il momento di un esempio, così da inquadrare un po’ ciò di cui stiamo parlando.

Pari e dispari

Il pari e dispari è un gioco a cui tutti, almeno una volta, hanno giocato. Vediamo come sia possibile descrivere questo gioco:

  1. I partecipanti sono 2
  2. Ogni giocatore ha 6 possibili mosse. Deve scegliere uno tra i seguenti numeri: 0,1,2,3,4,5.
  3. Ogni giocatore, prima di iniziare a giocare, ha deciso se “preferisce” Pari o Dispari e le due scelte devono essere l’una diversa dall’altra (se io scelgo pari, tu per forza avrai dispari) .

L’esito della partita dipende dal risultato della somma dei numeri scelti, in contemporanea, dai due giocatori. Supponiamo per comodità, che il Giocatore 1 vince in caso esca Pari e il 2 in caso esca Dispari.

Una volta determinate queste caratteristiche, seguono immediatamente alcune conseguenze. Per esempio, questo è un gioco in cui non esiste il pareggio. Infatti non esistono altre possibilità, ogni numero naturale è Pari o Dispari, per cui uno dei due partecipanti necessariamente vince.

Hanno entrambi la stessa probabilità di vittoria, infatti ciascuno vince in 2 casi su 4 (indicando con P e D la scelta pari e dispari, le coppie ordinate di possibili esiti sono infatti queste 4 PP,PD,DD,DP).

Bene, per ora non approfondiamo oltre l’esempio. Lo riprenderemo più avanti parlando di Equilibrio di Nash. Detto ciò, notiamo come in questo gioco particolare, i giocatori muovono contemporaneamente, è quindi un gioco in forma NORMALE.

Altra caratteristica di questi giochi, è che i giocatori non possono stringere accordi vincolanti nel corso della partita. Possono però comunicare prima che essa inizi.

Per vincolanti intendo che non si può condizionare la scelta dell’avversario con accordi più o meno vantaggiosi, facendo sì che se l’avversario non seguisse l’accordo verrebbe punito per questo. Ogni tipo di comunicazione deve precedere la partita, come se si telefonassero i giocatori prima di iniziare a giocare per decidere le regole e le modalità con cui il gioco si svilupperà.

Giochi in forma normale e giochi in forma estesa

Queste due categorie di giochi, fanno parte della classe dei giochi non cooperativi. Ossia giochi durante i quali non è possibile dialogare e contrattare. Tutto ciò che regola il gioco viene modellizzato prima che esso inizi (regole, turni e quant’altro).

Nei giochi in forma normale, i giocatori muovono simultaneamente, lo stesso numero di volte. I giochi in forma estesa, invece, si sviluppano nel tempo. In essi non tutti i giocatori muovono necessariamente insieme e lo stesso numero di volte.

Nei giochi in forma normale, quindi, i giocatori non possono muovere conoscendo ciò che gli altri hanno fatto, diversamente dai giochi in forma estesa, come gli scacchi.

Come abbiamo visto con l’esempio precedente, ogni giocatore ha alcune preferenze. Esse possono essere precisate con dei Payoff, dei premi che variano in valore in funzione delle preferenze dei giocatori stessi.

Nell’esempio del pari e dispari, se io scelgo Pari si può supporre che lo faccia perchè ha la possibilità di vincere più soldi in caso di vittoria. Diciamo quindi Payoff il premio che io vinco in caso si verifichi una data sequenza di scelte da parte dei giocatori.

Segue che ogni gioco in forma normale/estesa può essere descritto definendo i partecipanti, le mosse che hanno a disposizione (le modalità in cui esse vanno fatte, nel caso dei giochi in forma estesa) e i Payoff.

Per rappresentare un gioco in forma normale si utilizzano solitamente le tabelle a doppia entrata, mentre per rappresentare i giochi estesi si è soliti utilizzare degli alberi.

Si potrebbe dire molto di più riguardo a queste due branche di giochi, ma per il momento preferisco lasciare solo due immagini in cui penso vengano chiariti molti dettagli. Magari in separata sede, dedicherò un articolo più dettagliato a questa parte.

Gioco in forma estesa

Gioco in forma estesa (albero)

Dilemma del prigioniero

Gioco in forma normale (tabella doppia entrata)

Cos’è un equilibrio di Nash

La teoria dei giochi deve moltissimo a John Nash, grande matematico a cui è stato anche dedicato un film negli ultimi anni (‘A beautiful mind’). Se ti interessano i film sulla matematica ecco qui un articolo che fa per te: I 5 migliori film sulla matematica

A lui è dovuto il concetto di equilibrio all’interno di un gioco. In parole povere, per equilibrio si intende una situazione in cui nessuno dei giocatori ha interesse a cambiare la scelta fatta.

Se hai osservato con attenzione le immagini qui sopra, avrai senz’altro notato che per giungere ad ogni payoff, è necessaria una specifica sequenza di mosse, di scelte dei giocatori. Bene, se quando si è giunti ad un payoff, tutti i giocatori non hanno motivi per pentirsi della sequenza di scelte fatte, allora siamo in un equilibrio.

In quali situazioni un giocatore potrebbe ‘pentirsi’ delle scelte fatte e volerle cambiare? Quando è consapevole che ha ‘vinto’ meno di ciò che potenzialmente avrebbe potuto vincere.

Supponiamo quindi di arrivare ad un punto in cui il gioco si conclude, io ho effettuato due mosse che chiamo M1 e M2. Il mio avversario ha fatto L1 e L2. Mi rendo conto che in tali circostanze vincerei 10€. Supponiamo per un momento che il mio avversario faccia le stesse esatte mosse, ora mi chiedo: avrei potuto vincere di più di 10 se avessi fatto mosse diverse da M1 e M2?

In caso di risposta affermativa, allora non sono in una situazione di equilibrio, altrimenti dovrei fare la stessa verifica anche nella direzione opposta, così da verificare se esso sarebbe solo un equilibrio per me o anche per il mio avversario.

Prima di proseguire alla ricerca di un equilibrio in un esempio molto famoso, vorrei tornare un attimo sul pari e dispari. Esso è infatti un gioco senza equilibri di Nash se si gioca solo con strategie pure.

Specifichiamo quindi due cose: cosa si intende per strategie pure e perchè in quel caso non ci sono equilibri?

Per strategie pure si intende che le scelte vengono effettuate sulle possibilità a disposizione, non vengono lasciate al caso. Si parla invece di strategie miste in situazioni dove per esempio si lancia un dado che ha probabilità P che esca la faccia ‘6’, se uscisse un 6 allora sceglierei pari, altrimenti dispari.

In tal caso si può dimostrare che se P=1/2, ed entrambi i giocatori scegliessero tra Pari e Dispari con lo stesso metodo, allora saremmo in un equilibrio. Comunque ho già programmato di scrivere un articolo interamente dedicato all’interazione dei questi giochi con la probabilità, così da avanzare nella conoscenza della teoria dei giochi con casistiche più interessanti.

Perchè non ci sono quindi equilibri puri nel pari e dispari? Beh, è molto intuitivo, infatti in ogni possibile Payoff in cui mi posso trovare al termine del gioco, supponendo che ogni giocatore giochi per vincere, uno dei due giocatori avrà sempre interesse a cambiare la scelta perchè solo in tal caso potrebbe vincere. Non ci troveremmo quindi mai in una situazione di equilibrio.

Vediamo qui sotto un gioco molto famoso, lo utilizzeremo per comprendere meglio il concetto di equilibrio.

Il dilemma dei prigionieri

Il dilemma del prigioniero è un gioco proposto negli anni cinquanta del XX secolo da Albert Tucker come problema di teoria dei giochi. Oltre ad essere stato approfonditamente studiato in questo contesto, il “dilemma” è anche piuttosto noto al pubblico non tecnico come esempio di paradosso.

Il dilemma in sé, anche se usa l’esempio dei due prigionieri per spiegare il fenomeno, può descrivere altrettanto bene la corsa agli armamenti, proprio degli anni cinquanta, da parte di USA e URSS (i due prigionieri) durante la guerra fredda.

Ecco qui la tabella a doppia entrata in cui può essere sintetizzato il gioco.

 

Dilemma del prigioniero

 

In breve, la situazione è questa:

Ci sono due prigionieri a cui viene data la possibilità di confessare. Se entrambi lo fanno, trascorreranno 5 anni a testa in prigione. Se solo uno dei due lo farà, l’altro ne trascorrerà 10 in prigione. Se nessuno dei due confessasse, trascorrerebbero solamente 2 anni a testa in prigione. (gli anni possono variare, l’importante è il concetto dietro a questa trattazione)

E’ chiaro che se mettessero il proprio interesse prima di tutto, senza valutare bene la situazione, finirebbero entrambi a farsi 5 anni in prigione. Confessando infatti avrebbero la possibilità di essere liberati. Peccato che ciò accadrebbe solo se non lo facessero entrambi.

Qual è quindi secondo te l’equilibrio di Nash di questo gioco?

Apparentemente quindi converrebbe ad entrambi non confessare, dato che il totale degli anni trascorsi in prigione sarebbero soltanto 4. Tuttavia se analizzi il tutto dal punto di vista del singolo giocatore, confessare risulta senz’altro la scelta da essi preferita.

Infatti se il giocatore 1 confessa, allora anche al 2 conviene confessarlo dato che altrimenti si beccherebbe 10 anni di prigione.

Se invece il giocatore 1 non confessasse, comunque al giocatore 2 converrebbe confessare dato che, in tali circostanze, uscirebbe indenne dalla prigione.

Lo stesso ragionamento può essere ripetuto supponendo fissata la scelta del giocatore 2 e verificando come, in qualsiasi caso convenga scegliere di confessare anche al giocatore 1.

Infatti si può notare come confessare è strategia dominante per entrambi, è la scelta preferita da entrambi i giocatori indipendentemente da ciò che accade nel gioco stesso.

L’equilibrio è quindi (confessa,confessa) ed è qui che nasce un paradosso, infatti nelle loro migliori scelte vanno a trascorrere in galera più anni di quanti ne avrebbero potuti trascorrere se avessero potuto accordarsi.

Se infatti fossero entrambi certi che l’altro giocatore avesse scelto di non confessare, avrebbero potuto trascorrere solo 2 anni in prigione a testa. Ora invece ne trascorreranno 5 a testa, ma saranno comunque “contenti” delle loro scelte in quanto esse, indipendentemente dalle scelte dell’altro giocatore, garantivano il miglior risultato.

Conclusione di questa introduzione alla teoria dei giochi

Per questa introduzione è tutto, spero di essere riuscito a descrivere i fondamenti della teoria dei giochi in maniera abbastanza chiara. Se non altro, spero di averti incuriosito e di averti fatto venir voglia di cercare altre informazioni online a riguardo.

Infatti ci sono interi corsi, video online gratuiti, ti rimane solo da trovarli ed imparare, detto ciò ho già anticipato che questo non sarà l’ultimo articolo relativo a questa tematica. Infatti la teoria dei giochi mi interessa parecchio e quando ho del tempo ne approfitto per continuare ad esplorarla. Quindi aspettati nuovi articoli in futuro 😉

Al prossimo articolo

Davide

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *