Category Archives: Game Theory

2.3 – Introduzione alla teoria dei giochi – Strumenti di soluzione: equilibrio strategico o equilibrio di Nash

In questo post introdurremo invece lo strumento di soluzione più noto al grande pubblico della teoria dei giochi: l’equilibrio di Nash. Premio Nobel per l’economia nel 1994, questo importante pensatore è conosciuto universalmente per la vasta applicazione che ha trovato il concetto di equilibrio strategico in tutti i campi, dalle discipline prettamente scientifiche a quelle umanistiche, ma forse ancor più per il proliferare di versioni romanzate della sua vicenda umana dopo il ritiro del prestigioso riconoscimento a Stoccolma. Proviamo ora a mettere da parte  l’approccio da cronaca rosa o da sussidiario con cui viene solitamente approcciato il suo contributo, ma proviamo a illustrarlo in maniera chiara e corretta.

L’equilibrio strategico è un insieme di strategie, una per giocatore, tale che ogni giocatore giochi una risposta ottima alle strategie adottate dagli altri giocatori. La risposta ottima (BR) per un certo giocatore è una strategia che massimizza la sua utilità attesa data la strategia adottata dagli altri giocatori.

Prendendo in esame il celeberrimo esempio del Dilemma del prigioniero, si avrà la seguente matrice di pay-off:

La classica rappresentazione della matrice di payoff del dilemma del prigioniero
La classica rappresentazione della matrice di payoff del dilemma del prigioniero

Si noti che se la risposta ottima per il giocatore I qualora il giocatore due giochi c è BRI(c)= C. Analogamene, BRI(nc)= C, BRII(C)= c e BRII(NC)= c. Pertanto la coppia (C,c) individua un equilibrio di Nash in strategie pure.

Si consideri ora un particolare equilibrio di Nash basato sul tipo, detto equilibrio Bayesiano. Di seguito è raffigurato il gioco Matching Pennies con informazione incompleta:

Matching Pennies con informazione incompleta
Matching Pennies con informazione incompleta

Si ipotizzi che sia conoscenza comune che θ1 assume il valore θ ̅ > 0 con una probabilità uguale a 0,5 e il valore -θ ̅ < 0 con una probabilità uguale a 0,5. In modo assolutamente simmetrico, si ipotizzi che sia conoscenza comune che θ2 assume il valore θ ̅ > 0 con una probabilità uguale a 0,5 e il valore –θ ̅ < 0 con una probabilità uguale a 0,5. In base alla rappresentazione in forma strategica ex ante di questo gioco, esistono quattro tipi di giocatori a cui si associa il seguente insieme di strategie: θ1=θ ̅ gioca come scelta ottima T, θ1= -θ ̅ gioca C, θ2= θ ̅ gioca t, θ2= -θ ̅ gioca c .

Infatti, dal momento che le strategie dei θ2 sono equiprobabili, se θ1 = θ ̅ gioca T avrà un’utilità attesa pari a 0,5(1+θ ̅ ̅) – 0,5 = 0,5θ ̅ ̅, mentre se decidesse di giocare C avrebbe un’utilità attesa pari a -0,5+0,5 = 0. Analogamente, se θ1 = -θ ̅ giocasse T avrebbe un’utilità attesa 0,5(1- θ ̅) – 0,5 = -0,5θ ̅ <0, mentre giocando C l’utilità sarebbe 0. Poiché anche le strategie dei θ1 sono equiprobabili, se θ2=θ ̅  gioca t avrà un’utilità attesa pari a 0,5(-1+ ̅) + 0,5 = 0,5θ ̅ >0, mentre se decidesse di giocare c avrebbe un’utilità attesa pari a 0,5-0,5 = 0.
Se, infine, se θ2=-θ ̅  giocasse t avrebbe un’utilità attesa 0,5(-1- θ ̅)+0,5 =-0,5θ ̅ <0, mentre giocando c l’utilità sarebbe 0.

Riconsiderando, ora, il gioco Matching Pennies nella forma classica:

Matching Pennies in forma classica
Matching Pennies in forma classica

Si nota immediatamente l’impossibilità di individuare un equilibrio strategico in strategie pure. Ricercandone uno in strategie miste, si ipotizzi che I giochi T con probabilità p e C con probabilità 1-p, mentre II giochi t con probabilità q, mentre c con probabilità 1-q. Se I gioca T la sua utilità attesa sarà uguale a q – (1-q) = 2q-1, mentre se gioca C sarà –q +1(1-q) = 1-2q. Pertanto:

mp_pq

Se II gioca t la sua utilità attesa sarà –p + (1-p) = 1-2p, se invece gioca c p – (1-p)= 2p -1. Di conseguenza si avrà:

mp_qp

Una volta rappresentate graficamente le curve di reazione p(q) e q(p), gli equilibri di Nash in strategie pure e in strategie miste saranno tutti e soli i punti di intersezione delle curve stesse. Il procedimento rimane invariato anche qualora si inserisca una perturbazione di Harsanyi legata al tipo θ. Ancorché piccolo, il valore di θ ≈ 0 elimina l’incertezza legata al fatto di giocare una strategia con probabilità 0,5. Pertanto la scelta non è più casuale, ma è
basata sul tipo θ.

Equilibrio di Nash come intersezione delle curve di reazione
Equilibrio di Nash come intersezione delle curve di reazione
Advertisements

2.2 – Introduzione alla teoria dei giochi – Strumenti di soluzione: strategie razionalizzabili

Nel post precedente abbiamo introdotto gli strumenti di soluzione di un gioco presentando il procedimento dell’eliminazione iterata. Al fine di illustrare il significato delle strategie razionalizzabili, si consideri ora il gioco a tre giocatori in forma strategica tratto da Brandeburger (1992):

Il gioco proposto in Bradeburger (1992)
Il gioco proposto in Brandeburger (1992)

La strategia ottimale per il giocatore III può essere individuata a partire dalle credenze adottate sulle strategie degli altri giocatori. Dopo aver mostrato che non esistono strategie strettamente dominate né per il giocatore I né per il giocatore II, siano le credenze di III r1, r2, r3, r4 ≥ 0 e r1+r2+r3+r4 = 1.

prob

L’utilità attesa per il giocatore III è 1 r1 +1 r2 + 0 r3 + 0 r4 = r1 + r2 se gioca A, 0,7 r1 + 0 r2 + 0 r3 + 0,7 r4 = 0,7 (r1+r4) se gioca B e 0 r1 + 0 r2 + 1 r3 + 1 r4 = r3+r4 se gioca C. Si ipotizzi di essere in presenza di un gioco del tipo Battaglia dei sessi tra giocatore I e II. Dal momento che r1= r4= 0,5 e r2=r3= 0, per il giocatore III B rappresenta la scelta ottima in quanto 0,7(r1+r4) > r1+r2 e 0,7(r1+r4) > r3+r4.

Si noti che la distribuzione delle credenze del giocatore III è stocasticamente dipendente, pertanto, osservando un altro giocatore giocare la sua prima mossa, egli potrebbe modificare le sue aspettative sul comportamento dell’altro giocatore. In questo caso la letteratura parla di strategia correlata.

Una variante di questo gioco può prevedere che le strategie dei giocatori I e II siano tra di loro stocasticamente indipendenti. In tal caso III assegnerà una probabilità p al fatto che I giochi U e una probabilità q al fatto che II giochi l. Avremo così:

prob2L’utilità attesa soggettiva associata alle sue tre strategie è uguale a 1 pq + 1 p(1-q) + 0 (1-p)q + 0(1-p)(1-q)= p in A, 0,7 pq + 0p (1-q) + 0 (1-p)q + 0,7(1-p)(1-q) = 0,7 (1-p-q+2pq) in B e 0 pq+ 0 p(1-q) + 1 (1-p)q +1 (1-p)(1-q) = 1-p in C.

Il lettore attento noterà che, ∀(p,q), A≻B aut C≻B siccome non può verificarsi contemporaneamente che 0,7(1-p-q+2pq) > p e 0,7 (1-pq+2pq)>1-p. Si dirà pertanto che B non è una strategia razionalizzabile, altrimenti dovrebbe sopravvivere all’eliminazione di tutte le strategie che non massimizzano l’attesa soggettiva del giocatore, qualunque siano le sue credenze sulle strategie adottate dagli altri giocatori.
Il risultato più sorprendente della soluzione di questo gioco con strategie razionalizzabili è che, qualora si considerino le strategie I e II stocasticamente dipendenti, la scelta ottima di III sarà B, altrimenti sarà la prima ad essere eliminata.

2.1 – Introduzione alla teoria dei giochi – Strumenti di soluzione: l’eliminazione iterata

Continuando il percorso iniziato con la definizione di teoria dei giochi e una breve classificazione delle principali forme di rappresentazione e dei tipi di informazione, in questo post ci occuperemo di introdurre in che modo questa teoria possa tradursi in strumento analitico per la risoluzione di situazione di interazione strategica.

Per soluzione di un gioco si intendono le strategie dei giocatori e le corrispondenti situazioni sociali che sono compatibili con alcune ipotesi riguardanti l’intelligenza e la razionalità dei giocatori, nonché il loro grado di conoscenza della struttura del gioco stesso. La classificazione più accreditata in dottrina identifica quattro concetti base di soluzione: le strategie che sopravvivono all’eliminazione iterata delle strategie strettamente dominate, le strategie razionalizzabili, l’equilibrio strategico (o di Nash) e l’equilibrio correlato.

Una strategia è strettamente dominata per un giocatore se non massimizza la sua utilità attesa soggettiva, qualunque siano le sue credenze sulle strategie adottate dagli altri. La letteratura sul tema delle strategie dominate opera una distinzione tra dominanza rispetto ai pay-off e dominanza rispetto al rischio. Harsanyi e Selten (1988) hanno evidenziato come tale distinzione si rifletta sulla distribuzione probabilistica associata a ciascuna strategia.

Di seguito è riportato un gioco in forma strategica al fine di illustrare il concetto di
eliminazione iterata.

Gioco proposto per esemplificare l'eliminazione iterata
Gioco proposto per esemplificare l’eliminazione iterata

Si ipotizzi che il giocatore I si trovi a dover scegliere quale strategia adottare tra A, B e C. Qualunque sia la strategia adottata dal giocatore II, B ≻ A (infatti se a 4>3, se b 3>2). Si può tuttavia immaginare che il giocatore I attribuisca una probabilità p al fatto che II giochi a e una probabilità 1-p al fatto che giochi b. In questo caso si avranno le seguenti utilità attese:

prob

Sapendo che si tratta di una distribuzione probabilistica, avremo 0≤p≤1 per definizione, e ∀p u(B) > u (A). Per il giocatore I B ≻ C allora u(B) > u(C), pertanto se p < 0,5. Risolvendo si avrà p + 3 > 5p + 1, quindi 4p < 2. Di qui si può affermare che se p < 0,5 I giocherà B, se p >0,5 giocherà C e se p = 0,5, allora sarà indifferente per I giocare B o C. Tuttavia, poiché i giocatori sono razionali, intelligenti e conoscono la struttura del gioco, II saprà che A rappresenta una strategia strettamente dominata di I, quindi dovrà scegliere tra le strategie aB, bB, aC e bC. Siccome aB ≻ bB (4 > 3) e aC ≻ bC (5 > 1), a ≻ b e la probabilità p che II giochi a è pari a 1. La soluzione sarà quindi aC.

sol

Il procedimento proposto in questa sede è valido anche nei casi in cui la soluzione sia raggiungibile solo adottando strategie miste. Ponendo il problema in termini di giochi a forma costante, si ricercheranno quei valori corrispondenti al min-max (in altri termini, la peggiore tra le migliori soluzioni) e al max-min (la migliore tra le peggiori). Il punto di sella nelle strategie pure è quello che individua contestualmente min-max e max-min.

Il teorema del minimax di Von Neumann assicura l’esistenza di una coppia di strategie miste (x*,y*) tali che:

minmax

La soluzione per il primo giocatore si ottiene risolvendo il  seguente problema di programmazione lineare:

maxv

nei vincoli

par1

dove m è il numero di strategie pure q disposizione del giocatore.

La soluzione per il secondo giocatore si ottiene invece con il duale del problema precedente:

minv

nei vincoli

par2

Dopo aver illustrato in maniera prima operativa e poi matematica il funzionamento di questo semplice meccanismo, potremo affrontare nel prossimi post gli altri tre metodi descritti nella sezione introduttiva del presente.

Ricordo che, per chi volesse, il testo integrale della mia tesi è disponibile a questo indirizzo.

Harsanyi J., Selten R. (1988), A general Theory of Equilibrium Selection in Games, MIT Press, Cambridge p. 344-352

1- Introduzione alla teoria dei giochi – Forme di rappresentazione e tipi di informazione

Continuando il percorso iniziato qualche giorno fa, concludiamo oggi la parte di definizioni necessaria a introdurre gli strumenti di teoria dei giochi che hanno trovato applicazione nella tesi discussa lo scorso febbraio. In questo post parleremo in particolare delle forme di rappresentazione di un gioco e dei tipi di informazione. La seconda questione era già stata trattata nel corso del mio primo intervento su questo blog, ma è bene riprendere tutti gli elementi necessari ad una comprensione globale della questione.

Forme di rappresentazione di un gioco

Come suggerito da Colombo (2003), affrontando lo studio di un gioco, si ricorrerà alle due forme di rappresentazione dello stesso più ricorrenti, ovvero la forma strategica e la forma estesa.
Un gioco in forma strategica è costituito da un insieme di giocatori, un insieme di strategie per ogni giocatore ed una funzione di pay-off per ogni giocatore, che ad ogni situazione sociale associa l’utilità per quel giocatore di trovarsi in quella particolare situazione
sociale.
Un gioco in forma estesa con n giocatori è in un albero dotato di un nodo iniziale, al quale sono associate delle etichette e dei pay-off in base alle regole seguenti: i nodi che appartengono al medesimo stato informativo sono collegati tramite una linea tratteggiata; ogni stato informativo che non sia un nodo terminale ha un’etichetta-giocatore; ogni alternativa in ogni nodo ha un’etichetta mossa; ad ogni nodo terminale è associato un payoff per ogni giocatore, che rappresenta l’utilità associata al raggiungimento di quel nodo.

Rappresentazione di un gioco in forma estesa
Rappresentazione di un gioco in forma estesa

E’ importante richiamare la rappresentazione di un gioco in forma estesa per illustrare alcune nozioni relative all’informazione nei giochi.

Informazione nei giochi

Si dice pertanto che un gioco è caratterizzato da informazione perfetta se tutti gli stati informativi sono “singleton”, ovvero non esistono due o più nodi che appartengono al medesimo stato informativo. In caso contrario, si ha un gioco con informazione imperfetta.
Un evento è conoscenza comune (CPA) tra una serie di giocatori se tutti lo conoscono, tutti sanno che tutti lo conoscono, tutti sanno che tutti sanno che tutti lo conoscono – e così ad infinitum. Come dimostrato da Luce e Raiffa (1957), questo concetto è fondamentale poiché, a prescindere dal tipo di informazione, ogni giocatore deve assumere la conoscenza del gioco, altrimenti non vi sarebbero sufficienti elementi per spiegarlo e l’analisi risulterebbe incoerente. Un’analisi più approfondita della questione in Fagin et al. (1995) muove dall’ormai celeberrimo esempio del Muddy Children Puzzle.

Tuttavia, l’applicazione di questi modelli a casi reali obbliga gli operatori a scontrarsi con situazioni in cui un giocatore possiede almeno un’informazione, detta informazione privata, che non sia conoscenza comune. Si parla di gioco con informazione incompleta qualora all’inizio del gioco esista almeno un giocatore che ha un’informazione privata. Risulta intuitivo al lettore il fatto che nessun gioco possa essere davvero ad informazione completa, in quanto ci sono sempre delle sfumature nei gusti e nelle preferenze degli altri giocatori di cui non possiamo essere a conoscenza. Le implicazioni dettate da questo dato di fatto potrebbero di per sé confutare l’intero apparato della teoria, poiché viene considerata come assunto la CPA.

Si può, quindi, considerare un gioco ad informazione incompleta, quale, a titolo esemplificativo, il card’s game in forma estesa presente in Myerson (1991): il giocatore I e il giocatore II ripongono entrambi un dollaro su un tavolo. Il giocatore I pesca una carta dal mazzo e, senza mostrarla al giocatore II, può scegliere se passare P o rilanciare R. Nel caso in cui il giocatore I decida di giocare P, i pay-off saranno (1,-1) qualora abbia pescato una carta rossa e (-1,1) se avrà pescato una carta nera. Se invece decide di giocare R, il giocatore II dovrà scegliere se vedere – con pay-off (2,-2) se la carta è rossa e (-2,2) se nera – o se ritirarsi, con pay-off sempre pari a (1,-1). In un certo senso, la prima mossa di questo gioco non è effettuata dal giocatore I, bensì dalla Natura (N) che equiprobabilmente farà estrarre al giocatore I una corta rossa o nera. Il giocatore I ha quindi un’informazione privata che può dare origine alla c.d. infinita gerarchia di credenze da parte del giocatore II riguardo la strategia adottata dal giocatore I, il colore della carta posseduta, nonché sulle strategie che il giocatore I adotterà in funzione delle credenze del giocatore II etc. A questo punto, ciascuno dei due giocatori assegnerà una distribuzione di probabilità al tipo di giocatore θ (ad es. “onesto” o “disonesto”) che si trova di fronte, senza risolvere il problema dell’infinita gerarchia di credenze che ha costituito per anni un ostacolo insormontabile per la trattazione di questi giochi.
L’esempio del card’s game si rifà al contributo di Harsanyi (1968) che aggira il problema dell’informazione incompleta subordinando la funzione di pay-off di ciascun giocatore ad una lieve perturbazione casuale. Si consideri un gioco con n giocatori in cui ciascuno di essi rappresenti uno di un numero finito di tipi θ1a , θ1b , θ1c … θnx . Il tipo di un giocatore descrive le credenze che un giocatore-tipo θ ha riguardo i tipi degli altri giocatori. Un sistema di credenze è una distribuzione di probabilità soggettive di ciascun tipo di giocatore θ. Si dice che un sistema di credenze è coerente se esiste una certa probabilità π su un insieme dei vettori di ogni tipo θ tale che le credenze di ciascun tipo di giocatore θ sia pari a una certa probabilità π condizionata da θ. In altre parole, questa differenza nelle probabilità associate ai singoli tipi θ dai diversi giocatori deve essere spiegata in ragione di una differenza informativa a priori. Le aspettative soggettive si aggiustano, poi, secondo la regola di Bayes riportata di seguito:

La regola di Bayes
La regola di Bayes

Per approfondimenti sul tema, si rimanda ai contributi successivi di Aumann (1987)Morris (1995), Nehring (2000) e Nyarko (2010).

Riferimenti bibliografici:

Aumann R. (1987), Correlated Equilibrium as an Expression of Bayesian Rationality, in “Econometrica” n. 55 p. 1007-1028

Colombo (2003), Introduzione alla teoria dei giochi, Carrocci Editore, Roma

Fagin R. et al. (1995), Reasoning About Knowledge, The MIT Press, Cambridge

Harsanyi J. (1968), Games with incomplete information played by Bayesian players, Parts I, II, III, in “Management Science” n. 14 p. 159-182

Luce R., Raiffa H. (1957), Games and Decisions: Introduction and Critical Survey, Dover Publications, New York

Morris S. (1995), The common prior assumption in Economic theory, in “Economics and Philosophy” n. 11, Cambridge University Press p. 227-253

Myerson R. (1991), Game Theory. Analysis of Conflict, Harvard University Press

Nehring K. (2000), Common Priors under Incomplete Information: A Unification, University of California

Nyarko Y. (2010), Most games violate the common priors doctrine, in “International Journal of Economic Theory” n. 6 p. 189–194

0. Introduzione alla teoria dei giochi – definizioni

In vista di una prossima riorganizzazione di questo blog per renderne maggiormente fruibili i contenuti, comincio oggi a presentare in maniera sintetica e ridotta parte dell’attività di approfondimento svolta nel corso della stesura della mia tesi laurea specialistica dal titolo “Investimenti diretti esteri: la scelta dell’impresa in un contesto di oligopolio” .

Si è trattato di un percorso estremamente interessante che ha permesso di miscelare una sensibilità umanistica ereditata da studi classici, una formazione cosmopolita ricevuta nel corso degli anni trascorsi studiando Scienze Internazionali e Diplomatiche e competenze operative maturate durante i tirocini. Per interrogarsi, quindi, sull’arché della scelta di un’impresa di perseguire al di fuori dei propri confini un’interesse durevole ho provveduto a una rassegna della letteratura economica in materia suddividendola per tipo di approccio adottato da parte degli autori. In seguito, mi sono focalizzato su elementi più quantitativi, approfondendo le dinamiche competitive nelle varie strutture di mercato e mostrando in che modo, all’interno di questo framework, alcuni strumenti forniti dalla teoria dei giochi tornassero molto utili.

Il termine “teoria dei giochi” deriva dalla somiglianza formale dei problemi di decisione interattiva con giochi di società come il bridge o gli scacchi. I primi studi in materia furono compiuti all’inizio del Novecento producendo come primo risultato il teorema di Zermelo nel 1913, il quale afferma che il gioco degli scacchi è strettamente determinato. Riguardo la teoria dei giochi in quanto disciplina matematica, convenzionalmente viene fatta risalire la sua nascita alla pubblicazione di Von Neumann e Morgenstern nel 1944. Per una più ampia trattazione delle origini della teoria dei giochi si rimanda per il momento a Schwalbe, Walker (2001) – senza escludere tuttavia di riprendere il discorso più avanti.

Le definizioni di tale materia sono varie e talvolta discordanti. Dopo attente ricerche e una vasta comparazione dei testi più autorevoli, la definizione operativa a cui sono giunto è la seguente:

Con teoria dei giochi si intende la teoria dei modelli matematici di interazione strategica fra decisori intelligenti e razionali.

Riprendendo la precisazione effettuata da Myerson (1991), un giocatore si definisce razionale se ha preferenze complete e transitive sulle conseguenze e se cerca di individuare, tra le azioni a sua disposizione, l’azione o le azioni che gli assicurano il risultato migliore. Un giocatore si dice intelligente qualora le capacità logiche che gli permettono, date le sue preferenze sulle conseguenze, di individuare senza mai compiere errori l’azione o di ordinare le azioni che gli assicurano il risultato migliore.

Nel corso dei prossimi post, saranno spiegate alcune caratteristiche e forme di gioco e, in seguito, sarà presentata l’applicazione che ne è stata data nel mio elaborato.

Consiglio la lettura di:

Myerson R. (1991), Game Theory. Analysis of Conflict, Harvard University Press

CPA and Gödel. The need of a n+1 player

In my opinion, CPA (Common Prior Assumption) is a part of a game structure.
This is in contradiction with Gödel’s Second Incompleteness Theorem, so we can’t state if the players are rational and intelligent or not, and if they know the game structure or not (with related loop “I know that you know…”).

That’s because I disagree with Aumann (1987): we need always an Harsanyi transformation, not only in case of incomplete information games. A player n+1 has to exist necessary, and we can call him God, State or Market. The most relevant issue is that he defines the game structure.

References

AUMANN (1987) Correlated Equilibrium as an Expression of Bayesian Rationality, in “Econometrica” vol. 55 http://www.econ.yale.edu/~dirkb/teach/pdf/a/aumann/1987-correlatedequilibrium.pdf
BOOLOS (1994) Gödel’s Second Incompleteness Theorem, in Mind vol. 103 http://www2.kenyon.edu/Depts/Math/Milnikel/boolos-godel.pdf
MORRIS (1995) The Common Prior Assumption in Economic Theory http://www.princeton.edu/~smorris/pdfs/paper_6_Common_Prior.pdf
Technische Universität Kaiserlautern – Harsanyi Transformation http://vwl-mikro.wiwi.uni-kl.de/fileadmin/user_upload/spieltheorie/0601.errata.s18to19and_39to40.pdf

Follow me on Twitter