La teoria dei giochi studia e analizza il modo in cui si comportano i singoli individui quando interagiscono con altri in situazioni che possono portare alla vincita o alla spartizione di qualcosa. Queste interazioni, che possono essere cooperative o conflittuali, sono finalizzate al massimo guadagno per ciascun soggetto. La teoria dei giochi trova ampio utilizzo anche in economia; un contributo molto importante in questo ambito è stato dato da John Nash nel Novecento.
IN BREVE
Indice
TEORIA DEI GIOCHI: STORIA
Le prime testimonianze della teoria dei giochi risalgono a un carteggio del 1654 sul gioco di azzardo e sul calcolo delle probabilità di Blaise Pascal e Pierre de Fermat; tuttavia l’espressione “teoria dei giochi” venne utilizzata per la prima volta negli anni ’20 da Emil Borel che, nella Theorie des jeux, si occupò dei giochi a somma zero con due giocatori. La teoria dei giochi moderna iniziò con l’idea degli equilibri di strategia mista nei giochi a somma zero per due persone e la sua dimostrazione del matematico John Von Neumann che portò alla pubblicazione dell’articolo Sulla teoria dei giochi di strategia nel 1928. Questo articolo fu seguito dalla pubblicazione del libro Theory of Games and Economic Behavior di John Von Neumann e Oskar Morgenstern nel 1944. Successivamente Von Neumann concentrò i suoi studi principalmente sui giochi cooperativi. La teoria dei giochi è stata ampiamente sviluppata negli anni ’50 da molti studiosi, infatti risale a questo periodo la prima discussione matematica sul famoso dilemma del prigioniero. Nello stesso periodo John Nash, uno dei più famosi studiosi ad essersi occupato della teoria dei giochi, si occupò dei giochi non cooperativi dimostrando che ogni gioco con un numero finito di giocatori ha almeno un punto di equilibrio, noto come equilibrio di Nash, quando si applicano strategie miste. Questo risultato può essere visto come un’estensione dei “giochi a somma zero” studiati da Neumann. Successivamente la teoria dei giochi venne applicata anche in altri ambiti, tra cui le scienze politiche, l’economia (in particolare in microeconomia) e la biologia. La teoria dei giochi ha svolto un ruolo fondamentale nel corso della Guerra Fredda, in cui è stata applicata per determinare le risposte che avrebbero dovuto attuare gli Stati Uniti in caso di attacco dell’URSS.
DESCRIZIONE DEI GIOCHI
La teoria dei giochi ha come premessa fondamentale che l’obiettivo è vincere, quindi ci sono alcuni presupposti necessari per potere applicare la teoria dei giochi:
- gli individui giocano con lo scopo di vincere, quindi cercano di massimizzare il loro risultato;
- ogni individuo è a conoscenza delle regole del gioco e dei risultati ottenibili (cioè il payoff) in ogni singola mossa;
- ogni partecipante può prendere un numero finito di decisioni, anche se è contemplata una versione più astratta con numero infinito di decisioni, insieme delle mosse che un giocatore intende fare è chiamato strategia;
- ogni decisione presa ha delle conseguenze, che può essere positiva, una vincita, o negativa, una penalità;
- il gioco può essere cooperativo, se più individui sono d’accordo con le decisioni assunte, oppure non cooperativo se ci si scontra con le scelte degli altri individui.
Uno strumento utile per rappresentare le interazioni tra due giocatori può essere una tabella delle decisioni o matrice o anche attraverso alberi decisionali.
TIPOLOGIE DI GIOCHI
I giochi possono essere classificati in vari modi: nei giochi a informazione perfetta si conosce in ogni momento la storia delle giocate precedenti, rientrano in questa categoria gli scacchi, Hex, la dama; nei giochi a informazione completa ogni giocatore è a conoscenza del contesto ma non delle azioni degli altri giocatori, come nel dilemma del prigioniero; nei giochi finiti invece per esempio, il numero delle situazioni di gioco possibili è finito, ma il numero delle situazioni può essere molto grande, rientrano in questa categoria tris, Othello, morra cinese, scacchi e dama. Un’altra classificazione può essere quella dei giochi a somma zero che modellizzano una contrapposizione totale tra i giocatori, ovvero la vittoria di uno coincide perfettamente alla sconfitta dell’avversario e la somma delle vincite in funzione delle strategie adottate è sempre zero. Un esempio di gioco a somma zero a informazione perfetta sono gli scacchi, in cui i tre risultati possibili sono tre: 1, -1 se vince il bianco; -1, 1, se vince il nero e 0,0 in caso di pareggio; non esiste il caso in cui vincono o perdono entrambi. Il poker e la briscola sono esempi di giochi a somma zero a informazione imperfetta. Un’altra importante suddivisione è quella tra giochi cooperativi o non cooperativi.
Giochi Cooperativi/Giochi non cooperativi
Si parla di giochi cooperativi quando vi sono degli interessi comuni tra i giocatori, quindi i giocatori perseguono un fine comune e, mediante accordi vincolanti, alcuni cercano di associarsi per migliorare il proprio payoff e ottenere un risultato migliore. Se si considera \( N \) l’insieme dei giocatori, ogni sottoinsieme \(S \) di \( N \) è detto coalizione, se \( S=N \) si ha una grande coalizione, possono esistere \( 2^n – 1 \) arbitrarie coalizioni. Il valore di ogni singola coalizione è dato dalla funzione caratteristica \( v: P(N) \rightarrow \mathbb{R} \) che associa ad ogni coalizione un numero, inoltre \( v(\emptyset) = 0 \), in quanto è nullo il pagamento per la coalizione vuota. In questo modo si assegna a ogni coalizione la massima vincita possibile, indipendentemente dal comportamento degli altri giocatori. Ovviamente questa è una rappresentazione molto semplificativa perché non permette di definire la vincita di ogni singolo giocatore della coalizione, ma solo la vincita complessiva. I giochi cooperativi sono divisi in due sottoclassi: NTU (giochi a utilità non trasferibile), detti anche senza pagamenti laterali e TU (giochi a utilità trasferibile), detti anche a pagamenti laterali. La distinzione sta nel fatto che nei giochi TU si assume che i costi siano espressi in maniera monetaria. Nei giochi non cooperativi, detti anche giochi competitivi, invece, le parti non possono stipulare nessun accordo tra loro e sono in concorrenza; in questa situazione ogni individuo ha l’obiettivo di perseguire la strategia che risulta più vantaggiosa per lui. Nel caso in cui dovesse esistere una strategia che massimizzi anche i guadagni di tutti gli individui, allora si parla di equilibrio di Nash che esprime un comportamento razionale socialmente utile, dal momento che tutti i giocatori ottengono un pagamento che presenta la convergenza degli interessi di tutti gli individui; in questo “stato stazionario” nessun partecipante intende modificare la propria strategia. John Nash, nella sua tesi di dottorato, ha dimostrato che ogni gioco finito ad \( n \) giocatori ammette almeno un punto di equilibrio in strategie miste, ovvero una distribuzione di probabilità sulle strategie a disposizione del giocatore. Tuttavia, non è detto che la situazione di equilibrio sia la soluzione migliore per tutti, infatti se un giocatore decidesse di allontanarsi dal punto di equilibrio potrebbe massimizzare il suo guadagno. Un esempio di questa situazione è il dilemma del prigioniero.
Dilemma del prigioniero
Uno degli esempi più semplici per capire l’equilibrio di Nash è il dilemma del prigioniero, gioco ad “informazione completa”, ovvero ogni giocatore conosce tutte le regole del gioco, studiato da Merrill Flood e Melvin Dresher nel 1950 e successivamente formalizzato da Albert W. Tucker. Il dilemma afferma quanto segue: due criminali, A e B, vengono accusati di aver commesso un reato e vengono rinchiusi in carcere in due celle diverse, senza la possibilità di comunicare. Viene spiegato loro che:
- se solo uno dei due collabora accusando l’altro, evita la pena, mentre l’altro viene condannato a 7 anni di carcere;
- se si accusano a vicenda, vengono entrambi condannati a 6 anni;
- se nessuno dei due accusa l’altro, entrambi vengono comunque condannati a 1 anno, perché colpevoli di porto abusivo di armi.
Questo gioco può essere descritto con la seguente matrice:
Non potendosi confrontare sulla strategia da adottare, i due prigionieri partecipano a un gioco non cooperativo. La strada meno rischiosa, quindi la migliore strategia non sapendo cosa farà l’altro è (collabora, collabora). Infatti lo scopo, per ognuno, è quello di minimizzare la condanna e per ogni prigioniero collaborare significa avere o 0 o 6 anni, non collaborare significa avere o 1 o 7 anni. Ovviamente non parlare è la scelta più conveniente, ma senza la garanzia che sia seguita anche dall’altro. Accusarsi a vicenda corrisponde all’equilibrio di Nash, infatti entrambi i prigionieri ottengono qualcosa nell’interesse di entrambi, una riduzione di pena.
Equilibrio di Nash
Un gioco è caratterizzato da:
- Un insieme di giocatori, \( N \).
- Per ogni giocatore un vettore di strategie che il giocatore ha a disposizione, ovvero le mosse che può compiere: \( S_i =(s_{i,1}, s_{i,2}, …, s_{i,j}, …, s_{i,n}) \), con \( s_i \) si indica la strategia del giocatore \( i \).
- Per ogni giocatore la funzione \( U_i =(s_1, s_2, …, s_i, …, s_N) \), associa al giocatore \( i \) il guadagno, payoff, derivante da una combinazione di strategie, comprese quelle dei suoi avversari. Un equilibrio di Nash è una combinazione di strategie \( s^e_1, s^e_2, …, s^e_N \) tale che per ogni \( i \) e per ogni \( s_i \) si ha \( U_i =(s^e_1, s^e _2, …, s^e _i, …, s^e _N) \geq U_i =(s^e_1, s^e _2, …, s^e _i, …, s^e _N) \), ovvero, se un gioco ammette un equilibrio di Nash, il giocatore \( i \) non ha alcun vantaggio in termini di guadagno a cambiare la sua strategia \( s^e_i \) mentre gli altri hanno giocato la loro strategia \( s^e_j \), perché può solo peggiorare il suo guadagno o lasciarlo invariato.
Quindi se i giocatori raggiungono un equilibrio di Nash, nessuno può modificare la propria posizione cambiando solamente la propria strategia, ma è vincolato dalle scelte degli altri e, poiché questo vale per tutti i giocatori, tale equilibrio è unico.
Il contributo più importante di Nash alla teoria dei giochi è la dimostrazione matematica dell’esistenza di questo equilibrio, infatti ha dimostrato che ogni gioco finito, gioco con qualunque numero di giocatori e strategie purché in numero finito, ha almeno un equilibrio di Nash, eventualmente in strategie miste, ovvero una strategia non predefinita (comportamento non noto). Quindi la teoria dei giochi di Nash ha dimostrato che se i comportamenti di un singolo individuo cambiano in maniera probabilistica e non in maniera predefinita, allora sta realizzando una strategia mista che vince contro qualsiasi strategia pura. A livello matematico, il teorema presenta il seguente enunciato: Sia \( G(S_i,U_i) \) un gioco non cooperativo ad \( N \) giocatori. Si supponga che valgano le seguenti:
- \( S_i \in \mathbb{R}^{n_i}\) sono sottoinsiemi convessi e compatti di \(\mathbb{R}^{n_i}\), per ogni \( i=1,2,…N\);
- \(U_i : S:=S_1 \times \cdots \times S_N \rightarrow \mathbb{R} \) sono funzioni continue, per ogni \( i=1,2,…N\);
- \(U_i : S_i \rightarrow \mathbb{R} \), tale che \( s_i \mapsto U_i(s_i,S_i) \) indica la stringa di lunghezza \( N-1 \) in cui è stata eliminata la componente \(i\)-esima, sia quasi concava, per ogni \( i=1,2,…N\).
Allora il gioco ammette almeno un equilibrio di Nash. Le teorie di Nash sono state in parte illustrate nel film “A Beautiful Mind” del 2001.
Giochi a somma zero/Giochi a somma non zero
I giochi a somma zero sono un caso particolare dei giochi a somma costante, dove questa costante è zero; tuttavia le conclusioni teoriche sono le medesime. Von Neumann descrive i giochi di strategia come giochi con un numero finito di scelte, ognuna delle quali determina un numero finito di risultati diversi. Ogni individuo non è in grado di influenzare gli eventi e le scelte dei giocatori vengono prese simultaneamente. Se \(l=1,2, \ldots, m \) sono gli eventi che dipendono dal caso, considerando \( M_l\) il numero di esiti possibili per ciascun evento, la probabilità associata a ciascun evento casuale è \( \alpha_{l,1}, \alpha_{l,2}, \ldots, \alpha_{l,M_l} \) con \(l=1,2, \ldots, m \) e \( \alpha_{l,1}+ \alpha_{l,2}+ \ldots+ \alpha_{l,M_l} =1 \) con \( \alpha_{l,k} \ge 0 \) per \(k=1,2, \ldots, M_l \). I risultati che possono verificarsi sono:
$$ M = \prod_{l=1}^m M_l $$
Von Neumann semplifica la descrizione dei giochi e riconduce l’azione degli \( M \) eventi casuali e separati ad un singolo evento \( y \) combinando gli eventi in accordo con il calcolo delle probabilità. Quindi se i giocatori sono \( n>1\) e ciascuno dispone di \( 1,2,\ldots, N_i\) scelte, con \( i=1, 2, \ldots, n\) e indicato con \( s_1, s_2, \ldots, s_n\) le scelta di ogni giocatore, si ottiene la funzione pagamento del giocatore \( i\)-esimo, \( f_i(y, s_1, s_2, \ldots, s_n)\). Se si considerano tutti gli \( n \) giocatori essi percepiscono:
$$ f_1(y, s_1, s_2, \ldots, s_n) + f_2(y, s_1, s_2, \ldots, s_n) + \ldots + f_n(y, s_1, s_2, \ldots, s_n) \equiv 0$$
Quindi l’equazione dei giochi a somma zero, che vale per qualsiasi \( y, s_1, s_2, \ldots, s_n \), risulta:
$$ f_1 + f_2 + \ldots + f_n \equiv 0$$
Ciò che avviene è una ridistribuzione della ricchezza tra i giocatori a seguito delle loro scelte e di un’azione casuale \( y \) che determinano il pagamento che fa un giocatore all’altro. Inoltre ogni giocatore effettua la sua scelta senza essere influenzato dagli altri. Von Neumann ricorre al concetto probabilistico di valore atteso per una definizione che non tenga conto della nozione di evento aleatorio: se \( M \) eventi casuali \( y_1, y_2, \ldots, y_M \) accadono con probabilità \( \alpha_1, \alpha_2, \ldots, \alpha_M\) e vi sono \( s_1, s_2, \ldots, s_n \) scelte, allora il valore atteso del risultato per un giocatore risulta essere:
$$g_i(s_1, s_2, \ldots, s_n) = \alpha_1 \cdot f_i(y_1, s_1, s_2, \ldots, s_n) + \ldots + \alpha_M \cdot f_i(y_n, s_1, s_2, \ldots, s_n)$$
Dato che \(f_1 + f_2 + \ldots + f_n \equiv 0 \) implica che \( g_1 + g_2 + \ldots + g_n \equiv 0 \), restringersi a considerare solo le scelte non altera la struttura del gioco che rimane a somma zero. Se la somma non è zero, si parla di giochi a somma non zero. Ne è un esempio il dilemma del viaggiatore.
Giochi a due persone
Per definizione il gioco a somma zero è \( g_1(s_1,s_2)+g_2(s_1,s_2) \equiv 0 \) con \( s_1, s_2 \) scelte del giocatore 1 e 2 rispettivamente. Il giocatore 1 ha a disposizione \( i=1,2,\ldots,m\) strategie e il giocatore 2 invece \( j=1,2,\ldots,n\). Se si indica con $$ g(i,j) \equiv g_1(i,j) $$ la funzione pagamenti del giocatori 1, allora per il giocatore 2 risulta essere $$ g_2(i,j) \equiv -g(i,j) $$ ovvero, il guadagno di uno dei due corrisponde esattamente alla perdita dell’altro. Von Neumann immagina che entrambi i giocatori abbiano come obiettivo quello di massimizzare il proprio guadagno, ovvero il giocatore 1 cerca di massimizzare \( g_1(i,j) \) e il giocatore 2 \( g_2(i,j) \). Poiché \( \max_j g_2(i,j) = \max_j [-g(i,j)] = \min_j g(i,j) \), il giocatore 2 cerca di minimizzare \( g(i,j) \) in riferimento ai pagamenti del giocatore 1. Quindi il giocatore 1 effettua una scelta \(i^*\) e la sua perdita o la sua vincita dipenderà dalla scelta \(j\) del giocatore 2: \( g(i^*,j) \geq \min_j g(i^*,j) \), per ogni scelta \( j \) del giocatore 2. Il giocatore 1, se sceglie opportunamente \( i \), può avere la certezza che $$ \max_i g(i,j)=g(i^*,j) \geq max_i\min_j g(i,j) $$ Il giocatore 2, secondo un ragionamento analogo ha la certezza che $$ \min_jg(i,j)=g(i,j^*) \leq \min_j\max_ig(i,j) $$ a prescindere dalla decisone del giocatore 1. Dalla definizione di minimo (\( \min_jg(i,j) \leq g(i,j) \) per ogni \( i,j\)) si deduce che \(\max_i\min_jg(i,j) \leq \max_i g(i,j) \). Se si sceglie \( i=i^* \) tale che \( \max_i g(i,j)=g(i^*,j) \) si può scrivere $$ \max_i\min_j g(i,j) =\min_j g(i^*,j) \leq g(i^*,j) $$ per qualunque \( j \), se si sceglie \( j=j^* \) si ha $$ \max_i\min_j g(i,j) =\leq g(i^*,j^*) $$ Analogamente dalla definizione di massimo (\( \max_ig(i,j) \geq g(i,j) \) per ogni \( i,j\)) si deduce che \( \min_j\max_i g(i,j) \geq \min_j g(i,j) \). Se si sceglie \( j=j^* \) tale che \( \min_j g(i,j)=g(i,j^*) \) si può scrivere $$ \min_j\max_i g(i,j) =\max_i g(i,j^*) \geq g(i,j^*) $$ per qualunque \( i \), se si sceglie \( i=i^* \) si ha $$ \min_j\max_ig(i,j) \geq g(i^*,j^*) $$ Per confronto si ottiene:
$$ \max_i\min_j g(i,j) \leq g(i^*,j^*) \leq \min_j\max_i g(i,j) $$
Se questa disuguaglianza è valida, i giocatori non sono certi di conseguire il miglior risultato per sé stessi, Von Neumann conclude che per un giocatore sia impossibile agire in modo più intelligente dell’altro poiché l’esito risulta imprevedibile.
Nei giochi invece in cui \( \max_i\min_j g(i,j) = \min_j\max_i g(i,j) \), i giocatori adottano la scelta ritenuta più razionale e fanno in modo che l’esito del gioco sia determinato poiché il criterio del massimo del giocatore 1 e il criterio del minimo del giocatore 2 portano ad un risultato comune e considerato razionale da entrambi i partecipanti al gioco: se si ripetesse il gioco molte volte il risultato sarebbe sempre lo stesso; tuttavia, se il gioco si ripete, l’avversario potrebbe trarre vantaggio dalle mosse di un giocatore che effettua sempre la stessa scelta e quindi potrebbe compiere diverse scelte con una certa probabilità (strategia mista). Il giocatore 1 quindi associa a ciascuna scelta una probabilità \( p_1,p_2, \ldots, p_m \) e anche il giocatore 2 \( q_1,q_2, \ldots, q_n\). Il valore atteso per il giocatore 1 risulta essere:
$$ h_1(p,q)=\sum_{i=1}^m\sum_{j=1}^n g_1(i,j)p_i \cdot q_j $$
e per il giocatore 2 \( -h_1(p,q) \). Questa scrittura contempla anche una specifica strategia \( k \) da parte di un giocatore. In questo caso si porrà la probabilità di tale scelta \( p_k=1 \) e la strategia \( s_k=(0, \ldots, 1, \ldots,0) \) è chiamata strategia pura; quindi ogni giocatore può scegliere se prendere una decisione specifica o affidarsi al caso. Il teorema del minimax assicura l’esistenza di un punto di equilibrio per \( h(p,q) \), costituito da strategie miste per i giochi a due persone:
$$ \displaystyle \max_p \min_q h(p,q) = \min_q \max_p h(p,q). $$
Nei giochi a più di due giocatori può emergere la cooperazione tra i partecipanti, infatti la scelta di un giocatore potrebbe non essere svantaggiosa per tutti i suoi avversari presenti.
Dilemma del viaggiatore
Questo problema della teoria dei giochi venne posto nel 1994 da Kaushik Basu. Si immagini che due passeggeri di un aereo tornino da un viaggio nello stesso paese, durante il quale abbiano fatto le medesime cose, visitato gli stessi posti ed effettuato gli stessi acquisti. I bagagli dei due sono identici. Dopo l’atterraggio i bagagli vengono perduti e la compagnia area decide di rimborsare i passeggeri, ma non è in grado di accertare il valore del contenuto dei bagagli e per questo si rivolge direttamente ai passeggeri. Per evitare che i due se ne approfittino, la compagnia propone il seguente patto: ciascun passeggero separatamente dovrà scrivere su un foglio il valore in dollari per cui vorrebbe essere rimborsato (valore compreso tra un massimo e un minimo, ad esempio tra 50 e 300 dollari). Nel caso in cui le due cifre siano identiche, la compagnia procederà al rimborso, altrimenti darà a ciascuno la cifra più bassa tra quelle scritte e, in più, chi ha scritto la cifra più bassa riceverà come premio per l’onestà i dollari (ad esempio 50) che verranno tolti, come punizione, a chi ha scritto la cifra più alta. Analizzando la situazione, l’equilibrio di Nash è raggiunto quando entrambi scrivono la risposta più bassa possibile (nell’esempio, 50 dollari). Infatti la soluzione (50,50) è l’unica dalla quale nessun giocatore ha interesse a deviare. Quindi 300 non è la migliore risposta perché, anche se il secondo giocatore scrivesse la stessa cosa, si può ottenere di più scrivendo 299 (299+50); quindi non conviene rispondere 300 per qualunque altra risposta del secondo passeggero che, arrivato alla medesima conclusione, non considererà vantaggiosa nemmeno la risposta 299, e così avanti fino ad arrivare al minimo possibile. Studi empirici dimostrano che giocatori reali, posti in questa situazione, tendono ad avvicinarsi all’equilibrio di Nash quando la penalità è percepita alta rispetto ai valori in gioco.
Fonte
- Dilemma del prigioniero
Prisoner’s dilemma - Comments on the Interpretation of Game Theory
Econometrica - The Work of John Nash in Game Theory
Journal of Economy Theory - Nash Equilibrium and the History of Economic Theory
American Economic Association - A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature
National Academy of Sciences - The Collaboration Between Oskar Morgenstern and John von Neumann on the Theory of Games
American Economic Association