Teoria dei giochi
Teoria che analizza in modo formale
l’interazione strategica di soggetti razionali che
agiscono in modo strategico
Situazione strategica
Dieci persone si recano insieme al ristorante
a) Si paga alla romana  semplice problema di scelta (Max U s.t. VdB)
 Ciascuno è in grado di controllare autonomamente il risultato delle sue
scelte
b) Si paga dividendo il conto per 10  problema strategico
Non riesco a controllare la mia spesa
 Il risultato delle mie azioni dipende anche dalle scelte degli altri
Gioco
insieme astratto di regole
che vincolano il
comportamento dei
giocatori
definiscono i risultati
sulla base delle azioni che
essi intraprendono
Il gioco è le regole
1) I giocatori (A,B,C…)
In un gioco vi
sono tre
elementi
caratteristici
2) Le strategie a loro disposizione
Per ogni giocatore le regole stabiliscono
un insieme di strategie (SA,SB,SC….)
Le mosse che le regole rendono
possibili (si  Si)
3) I Payoffs associati agli esiti finali
del gioco
i (sA,sB,sC….)
Rappresentazione di un gioco
• Forma normale: matrice delle vincite
• Forma estesa: albero del gioco
Forma Normale
• Uso di matrice a doppia entrata
• Le righe rappresentano le mosse che
può compiere il giocatore di riga
• Le colonne rappresentano le mosse che
può compiere il giocatore di colonna
• In ogni cella sono rappresentate le vincite
che i due giocatori (di riga e di colonna)
ottengono attuando le mosse raffigurate
nelle corrispondenti righe e colonne
Esempio
Giocatori
Strategie B
B
A Alto
Basso
Sinistra
Destra
1,2
0,1
2,1
1, 0
Payoff A
Strategie A
Uno dei 4 esiti del gioco
Payoff B
Forma estesa
• Albero del gioco: descrive le regole e i
possibili premi di un gioco
• Nodo: punto decisionale dov’è indicata
l’identità del giocatore cui spetta la mossa
• Rami: rappresentano le scelte fatte nei
nodi
Forma estesa
Rami
Nodi
A
Sx
Dx
B
B
Dx
2,3
Uno dei 4 esiti del gioco
Non
Sx
Dx
1,2
2,0
Sx
Payoff A
0,1
Payoff B
Ipotesi sul comportamento dei giocatori
Razionalità
- Sono interessati a massimizzare il payoff materiale
individuale
- Sono “calcolatori” perfetti
- Tutti conoscono la razionalità degli altri e si aspettano che
gli altri si comportino in modo razionale
Classificazione dei giochi
Cooperativi
NON Cooperativi
Informazione
completa
Informazione
incompleta
i giocatori possono assumere degli
impegni che hanno valore
VINCOLANTE
i giocatori NON possono assumere
degli impegni che hanno valore
VINCOLANTE
Tutte le informazioni del gioco sono
note a tutti i giocatori
NON tutte le informazioni del gioco
sono note a tutti i giocatori
Classificazione dei giochi
Giochi a somma
zero
il guadagno di un giocatore CORRISPONDE
sempre alla perdita di un altro giocatore
La somma delle vincite (o delle perdite) dei
giocatori NON È COSTANTE
Giochi statici
I giocatori fanno le loro mosse
SEQUENZIALMENTE
Giochi one-shot
Vengono giocati PIÙ VOLTE fra gli stessi
giocatori
Giochi NON a somma
zero
I giocatori fanno le loro mosse
SIMULTANEAMENTE
Giochi dinamici
Vengono giocati UNA SOLA volta
Giochi ripetuti
Soluzione dei giochi
Equilibrio per un gioco: situazione in cui
nessun giocatore desidera modificare il
suo comportamento unilateralmente dato il
comportamento degli altri giocatori
Equilibrio di Nash
Un insieme di strategie, una per ogni giocatore, tale che
la strategia di ogni giocatore sia la migliore per lui,
quando anche gli altri giocatori giochino la loro strategia di
equilibrio
L’equilibrio di Nash si definisce strategicamente stabile o
autovincolante perché nessun giocatore, singolarmente
preso, desidera deviare dalla propria strategia di equilibrio
ferme restando le strategie adottate dagli altri giocatori
Equilibrio di Nash
Diremo che un vettore n dimensionale (n è il numero dei giocatori)
s  (s , s ....., s )
*
*
1
*
2
*
n
È un equilibrio di Nash se e solo se
* *
*
*
* *
*
i (s1 , s2 ,...si ,.., sn )  i (s1 , s2 ,...ŝi ,.., sn )
E questo sia vero per ogni i (per ogni giocatore) e per ogni
ŝ i  s e ŝi  Si
*
i
Payoff che ottiene il giocatore i-esimo
quando egli gioca la strategia di Nash e
quando tutti gli altri giocano la strategia
di Nash
Payoff che ottiene il giocatore i-esimo
quando sceglie di deviare dalla strategia
di Nash giocando una strategia diversa
e tutti gli altri continuino a giocare la
strategia di Nash
Equilibrio di Nash
La strategia (a2,b3) è un equilibrio di Nash perché né A né B hanno
l’incentivo a cambiare strategia data la scelta dell’altro giocatore
B
A
b1
b2
b3
a1
0,3
2,2
1,3
a2
2,1
3,2
2,3
a3
5,1
1,4
1,0
Se B cambiasse otterrebbe 1
giocando b1 e 2 giocando b2
Se A cambiasse
otterrebbe 1
giocando a1 e 1
giocando a3
Equilibrio di Nash
La strategia (a2,b3) è un equilibrio di Nash perché né A né B hanno
l’incentivo a cambiare strategia data la scelta dell’altro giocatore
A preferirebbe il 5 di (a3,b1)
B
A
b1
b2
b3
a1
0,3
2,2
1,3
a2
2,1
3,2
2,3
ma (a3,b1) non è un equilibrio
perché B cambierebbe la sua
scelta in b2
ma allora A si
sposterebbe in a2
infine B si sposterebbe in b3
a3
5,1
1,4
1,0
da qui NON ci si muove più
L’equilibrio non produce né per A né per B necessariamente il
payoff più alto
Equilibrio di Nash
Il giocatore i-esimo, cosi come tutti gli altri, non può ottenere
un payoff superiore giocando una strategia diversa se gli
altri continuano a giocare la strategia di Nash
* *
*
*
* *
*
i (s1 , s2 ,...si ,.., sn )  i (s1 , s2 ,...ŝi ,.., sn )
Nessun giocatore ha l’incentivo a cambiare le
sue scelte se gli altri non lo fanno
Equilibrio di Nash
* *
*
*
* *
*
i (s1 , s2 ,...si ,.., sn )  i (s1 , s2 ,...ŝi ,.., sn )
*
si
è la soluzione del problema
* *
Max i (s1 , s 2 ,...si
si
*
si
*
,.., s n )
s.t. si  Si
Può essere vista come la ottima risposta del
giocatore i-esimo alle mosse degli altri giocatori
Possiamo definire una risposta ottima per ogni strategia degli altri
giocatori costruendo una funzione di risposta ottima
BRF  funzione di risposta ottima
L’equilibrio di Nash sarà caratterizzato dal fatto che per tutti i
giocatori è una risposta ottima alle scelte degli altri
Come si trova l’equilibrio di Nash
Strategia DOMINANTE
Se esiste una strategia
dominante un giocatore
razionale giocherà
QUELLA
Se esiste una strategia
dominata un giocatore
razionale non la giocherà
MAI
Strategia DOMINATA
strategia che risulta migliore
(garantisce più alti payoffs) per
un giocatore indipendentemente
dalle strategie adottate dagli altri
giocatori
strategia che risulta inferiore
(garantisce più bassi payoffs) per
un giocatore indipendentemente
dalle strategie adottate dagli altri
giocatori
Esempio: prendiamo i due giochi che seguono
Strategia Dominante
A
B
B
B1 b2 B3
B1 b2 B3
a1 0,3 2,2 1,3
a1 1,3 2,4 1,3
a2 2,1 3,2 2,3
a3 5,1 1,4 1,0
Strategia Dominata
A
a2 2,1 3,2 1,1
a3 5,1 4,4 2,0
Come si trova l’equilibrio di Nash
Eliminazione iterata delle strategie dominate
Vengono eliminate via le strategie
dominate finche non si ottiene
l’equilibrio di Nash
E
S
E
M
P
I
O
A
B
B1
b2
B3
a1
0,3
2,2
1,3
a2
2,1
3,2
2,3
a3
5,1
1,4
1,0
Eq. di
Nash.
Equilibrio di Nash verifica
A (a 2 , b3 )  2  A (a1, b3 )  1
A (a 2 , b3 )  2  A (a 3 , b3 )  1
Strategia di Nash
Possibile mossa alternativa
B (a 2 , b3 )  3  B (a 2 , b1 )  1
B (a 2 , b3 )  3  B (a 2 , b 2 )  2
Problema  non sempre è possibile trovare la soluzione di
Nash utilizzando tale procedura
Consideriamo lo stesso gioco di
prima con la sola differenza
rappresentata dal payoff del
giocatore A nella in (a1,b2)
A
a1
a2
a3
B1
B
b2
B3
0,3
2,1
5,1
4,2
3,2
1,4
1,3
2,3
1,0
Ora non ci sono né strategie dominate né strategie dominanti
Per trovare la soluzione occorre utilizzare la funzione di
risposta ottima (BRF)
risposta ottima
Funzione di
risposta ottima
La migliore strategia che un giocatore può effettuare
DATA la strategia scelta dagli ALTRI GIOCATORI
L’insieme delle risposte ottime di un giocatore
Trovare l’ E.d.N. utilizzando la BRF
A
a1
a2
a3
b1
B
b2
b3
0,3
2,1
5,1
4,2
3,2
1,4
1,3
2,3
1,0
E.d.N deve essere la
coppia di strategie che
è la risposta ottima di
entrambi i giocatori
Se il giocatore B sceglie b1 la migliore risposta di A è a3
Se il giocatore B sceglie b2 la migliore risposta di A è a1
Se il giocatore B sceglie b3 la migliore risposta di A è a2
Se il giocatore A sceglie a1 la migliore risposta di B è b1 o b3
Se il giocatore A sceglie a2 la migliore risposta di B è b3
Se il giocatore A sceglie a3 la migliore risposta di B è b2
Limiti della definizione di equilibrio di Nash
P
Gioco del calcio di rigore
A
e cerchiamo l’equilibrio con il
metodo della risposta ottima
dx
cx
sx
dx
0,2
2,0
2,0
cx
2,0
0,2
2,0
sx
2,0
2,0
0,2
E’ evidente che non esiste un equilibrio di
Nash per questo gioco
L’equilibrio di Nash può non esistere in strategie pure
Tuttavia se allarghiamo la definizione di strategie per considerare
le strategie miste
Strategie miste: strategie che definiscono combinazioni
probabilistiche di tutte le possibile strategie pure del
gioco
Il giocatore non sceglie direttamente una mossa (ad esempio, sx)
ma la probabilità con la quale adotterà ciascuna mossa
 Valore atteso strategia mista: media ponderata dei
premi che il giocatore si aspetta di ricevere, ove i pesi
sono le probabilità. del verificarsi di tali vincite
Si può dimostrare che se consideriamo le strategie
miste esiste sempre un equilibrio di Nash
Limiti della definizione di equilibrio di Nash
Consideriamo questo gioco classico
La guerra dei sessi
Lei
Esiste una
molteplicità
(due) di
equilibri di Lui
Nash
Opera
Stadio
Opera
1,2
0,0
Stadio
0,0
2,1
Quale selezionare ?
Limiti della definizione di equilibrio di Nash
Molteplicità equilibri di Nash
Prendiamo due altri esempi di gioco
Gioco dell’incrocio
Due auto (S e B) arrivano
contemporaneamente all’incrocio
Possono Fermarsi o Passare
Gioco dell “appuntamento”
Due amici (Nino e Luca) devono
andare al cinema ma si non si sono
accordati su dove incontrarsi
Davanti al cinema o al bar del Paese
S
D
P
F
P
F
-2, -2 2 , 0
0,2 0,0
Nino
c
Luca
c
b
Qual è la differenza fra questi due giochi?
b
3,3 0,0
0,0 1,1
Criterio Paretiano (da W. Pareto)
Abbiamo visto che l’individuo ordina i panieri alternativi secondo le sue
preferenze e scegli il paniere che massimizza il suo benessere dati i
vincoli cui è soggetto
Come possiamo confrontare allocazioni che coinvolgano più di un soggetto
Problema
L’utilità non è misurabile
Non possiamo semplicemente sommare la soddisfazione
individuale
Esiste un punto di vista sociale per valutare le
allocazioni? Ci sono o no criteri che ci consentano di dire
se l’allocazione A è superiore all’allocazione B,
oppure se è vero il contrario?
Allocazione = distribuzione di beni, benessere o quant’altro fra più soggetti
Criterio Paretiano
Criterio Paretiano
Il “criterio di Pareto ” afferma quanto segue:
Un’allocazione A è superiore a un’altra allocazione B,
se almeno un soggetto preferisce A a B
e nessuno preferisce B ad A (e viceversa).
oppure
Un’allocazione A è superiore a un’altra allocazione B,
se in A tutti stanno altrettanto bene che in B e
almeno uno sta meglio in A che in B
Non tutte le allocazioni
sono Pareto Ordinabili
A = (10, 3, 7)
B = (10, 2, 7)
C = (9, 5, 16)
Criterio Paretiano (da W. Pareto)
Un'allocazione è efficiente (ottima) nel senso
di Pareto
se non ne esiste un'altra che sia migliore sulla
base del principio di Pareto;
cioè, se non è possibile migliorare il benessere
di qualcuno senza peggiorare quello di qualcun
altro
Molteplicità equilibri di Nash
Nel caso del gioco dell’incrocio (e nella guerra dei sessi)
gli equilibri di Nash non sono Pareto Ordinabili
Nel caso del gioco dell’appuntamento gli equilibri
di Nash sono Pareto Ordinabili
2,0 e 0,2
1, 1 e 3, 3
La differenza è importante quando si considerano giochi ripetuti
Gioco
Ripetuto
Gioco in cui un numero fisso di giocatori effettua ripetutamente lo
stesso gioco l’uno contro l’altro
I giocatori scelgono le loro mosse sulla base delle azioni compiute
dalle rivali nei periodi precedenti
Le strategie ed i comportamenti sono più complessi ma anche più
realistici che nei giochi uniperiodali
Nel caso giochi ripetuti ed equilibri Pareto ordinabili allora vi sarà un
Folk
endogeno coordinamento verso la soluzione Pareto Superiore
Theorem
In caso la questo ripetizione del gioco
può far scomparire la molteplicità
Molteplicità equilibri di Nash: giochi sequenziali
Consideriamo il gioco dell’incrocio, immaginando che l’auto A si
presenti per prima all’incrocio
Il gioco non è più simultaneo ma sequenziale, l’auto A effettuerà
la prima mossa e successivamente muoverà l’auto B
Auto A
La
rappresentazione
del gioco a forma
estesa è
preferibile
P
F
Auto B
F
0,0
Auto B
P
F
0,2
2,0
P
-2 , -2
Giochi sequenziali in forma estesa: induzione a ritroso
Induzione a ritroso
Si parte dai nodi finali del gioco e si analizzano le scelte dei giocatori fino
a risalire all’inizio del gioco
B sceglierà P
che gli da 2 al
posto di 0
A lo sa e sa che
se sceglierà F
prenderà 0
Auto B
F
0,0
Auto A
P
F
A sceglierà P che
gli garantisce 2
mentre se
scegliesse F
F
P
avrebbe 0
0,2
2,0
B sceglierà F che gli
da 0 al posto di -2
A lo sa e sa che se
sceglierà P
prenderà 2
Auto B
P
-2 , -2
Minacce non credibili
Gioco del bambino capriccioso
Pierino
1
Zia
Cinema
2
1
1
M&P
Punire
Non punire
-1
-1
2
0
Induzione all’indietro e perfezione nei sottogiochi
A
B
B
2, 5
S
3,3
D
S
A
1,2
Sottogioco
D
S
D
A
2, 1
3,3
2,5
S
1,0
S
D
2, 1
2, 1
D
3, 3
Molteplicità equilibri di Nash: meccanismi istituzionali
Quando non esistono altri sistemi per eliminare la molteplicità degli
equilibri possono intervenire dei meccanismi istituzionali che
regolamentano il comportamento individuale e risolvono l’ambiguità
Esempio classico  il semaforo nel gioco
dell’incrocio
Risolvere questo tipo di ambiguità è una delle
spiegazioni della nascita delle istituzioni
Dilemma del prigioniero
• Due criminali che hanno commesso in complicità un grave
delitto e sono detenuti in celle separate (non possono
comunicare).
• Ci sono le prove solo per accusarli di un delitto minore la
cui pena è 1 anno di reclusione
• Ogni prigioniero può confessare il delitto grave o tacere.
• Se confessa uscirà subito di prigione, mentre il complice
avrà una pena di 20 anni di reclusione.
• Se entrambi confessano saranno condannati ad una pena
intermedia di 5 anni.
• Se nessuno dei 2 confessa la pena sarà di 1 anno.
Dilemma del prigioniero
L’EQUILIBRIO DI NASH È SOTT'OTTIMALE (in senso
Paretiano) rispetto ad un altro esito del gioco che sarebbe
preferito da entrambi i giocatori ma che non è ottenibile
Risultato
paradossale
Un comportamento
teso a massimizzare
il benessere
individuale produce
un risultato non
ottimo da un punto
di vista individuale
B
Confessa
Tace
Nash
Confessa
5,5
B
0 , 20
O.P
Tace
20 , 0
1,1
Dilemma del prigioniero framework generale
Prendiamo due altri esempi di gioco
Gioco del traffico
Due soggetti (sig. Rossi e sig.
Bianchi) devono decidere se prendere
l’auto o il tram
Gioco della Pubblicità
Due imprese devono decidere quanto
investimento pubblicitario effettuare
il prossimo anno
R
B
T
A
T
A
3, 3 0 , 4
4, 0 1 , 1
Pampers
NF
Lines
FP
NF
FP
500,500
150,750
750,150
250,250
Sotto-ottimalità dell’equilibrio di Nash
possibili soluzioni
Meccanismi istituzionali
Mafia, malavita organizzata
dilemma del prigioniero
Blocco del traffico
gioco del traffico
Modificano dall’esterno la struttura degli incentivi
Meccanismi endogeni
accordo fra i giocatori
Non sono credibili perché in assenza di meccanismi istituzionali
esterni qualsiasi accordo fra le parti non sarebbe rispettato
Dilemma del prigioniero e giochi ripetuti
Ma nella realtà il gioco è spesso ripetuto
Possono emergere dei meccanismi endogeni di punizione di
comportamenti devianti
Prendiamo il gioco della
Se una delle due aziende
pubblicità
violasse l’accordo di non fare
Immaginiamo un accordo
pubblicità l’altra farebbe
(esplicito o tacito) per non fare
pubblicità per sempre
pubblicità
Meccanismo punitivo
All’inizio di ogni periodo le due imprese devono decidere se violare
o meno l’accordo
Dilemma del prigioniero e giochi ripetuti
Se si viola
l’accordo
250
250
(FP)  750 


.....
1  r (1  r ) 2
Se non si
viola
l’accordo
500
500
( NF)  500 


.....
1  r (1  r) 2
Ponendo
Si ottiene
1
d
1 r
e notando che sono serie convergenti
250d
(FP)  750 
1 d
500
( NF) 
1 d
Dilemma del prigioniero e giochi ripetuti
( NF)  (FP) se d  0.5 o se r  1
Se i giocatori sono sufficientemente pazienti (attribuiscono un
peso adeguato ai guadagni futuri)
Nota
Il gioco deve durare
all’infinito o avere una
durata finita ma incerta
Il risultato pareto ottimale può essere raggiunto
Reputazione -- Credibilità
Dilemma del prigioniero e giochi ripetuti
Altro esempio
Prendiamo il gioco seguente
A
B
L
C
R
T
5,5
3,6
0,0
M
6,3
4,4
0,0
B
0,0
0,0
1,1
Se il gioco è statico, allora gli equilibri saranno (M, C) e (B,R)
entrambi sotto ottimali rispetto a (T,L)
Dilemma del prigioniero e giochi ripetuti
Ma se il gioco viene ripetuto 2 volte allora le cose cambiano
Mentre in ciascun periodo un giocatore ha sempre 3 opzioni possibili, se
consideriamo entrambi i periodi il numero di strategie cresce a 3x3x9=81
(tre azioni possibili nel primo periodo, tre nel secondo e nove possibili risultati nel primo
periodo)
Come si trova equilibrio ?
a) un primo equilibrio è semplicemente quello che replica in
ciascun gioco l’equilibrio del gioco statico, ad esempio, (M,C)
Esistono nuovi equilibri ?
giocatore A: giocare T nel periodo 1 e M nel periodo 2 se si è
verificato (T,L) altrimenti giocare B
giocatore B: giocare L nel periodo 1 e nel periodo 2 giocare C se
nel se si è verificato (T,L) altrimenti giocare R
Equilibrio nel gioco ripetuto
Periodo 2: visto che sono entrambi equilibri nel gioco costitutivo nessuno
dei due giocatori ha l’incentivo a cambiare strategia nel secondo periodo
A
B
T
M
B
L
5,5
6,3
0,0
C
3,6
4,4
0,0
R
0,0
0,0
1,1
Periodo 1: giocatore A: se sceglie T in 1, allora ottiene 5 + 4, se sceglie M
ottiene 6 + 1, se gioca B ottiene 0+1 e quindi non ha incentivo a variare la sua
strategia se B non la cambia
Lo stesso vale per B: se gioca L (5+4), C(6+1) R(0+1)