Teoria dei giochi
Teoria che analizza in modo formale l’interazione strategica di soggetti razionali che agiscono in modo strategico
Situazione strategica
Sette 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 7 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
In un gioco vi sono tre
elementi
caratteristici
Rappresentazione di un gioco
• Forma normale: matrice delle vincite
• Forma estesa: albero del gioco
Esempio
Giocatori
B
A
Sinistra Destra
Alto 1 , 2 0 , 1
Basso 2 , 1 1, 0
Strategie B
Strategie A
Uno dei 4 esiti del gioco
Payoff A Payoff B
A
B B
Dx
Non
Dx Sx Dx
Sx
Sx
2 , 3 1 , 2 2 , 0 0 , 1
Forma estesa
Rami Nodi
Uno dei 4 esiti del gioco
Payoff A Payoff BClassificazione dei giochi
Cooperativi i giocatori possono assumere degli impegni che hanno valore
VINCOLANTE
NON Cooperativi i giocatori NON possono assumere degli impegni che hanno valore
VINCOLANTE
Informazione completa Informazione
incompleta
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
Giochi NON a somma zero
La somma delle vincite (o delle perdite) dei giocatori NON È COSTANTE
Giochi statici
Giochi one-shot
I giocatori fanno le loro mosse SIMULTANEAMENTE
Vengono giocati UNA SOLA volta
Giochi dinamici
I giocatori fanno le loro mosse SEQUENZIALMENTE
Vengono giocati PIÙ VOLTE fra gli stessi
giocatori
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
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
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
B
b1 b2 b3
a1 0,3 2,2 1,3
A a2 2,1 3,2 2,3
a3 5,1 1,4 1,0
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
Se A cambiasse otterrebbe 1
giocando a1 e 1 giocando a3
Se B cambiasse otterrebbe 1
giocando b1 e 2 giocando b2
B
b1 b2 b3
a1 0,3 2,2 1,3
A a2 2,1 3,2 2,3
a3 5,1 1,4 1,0
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
L’equilibrio non produce né per A né per B necessariamente il payoff più alto
A preferirebbe il 5 di (a3,b1)
ma allora A si
sposterebbe in a2
infine B si sposterebbe in b3 da qui NON ci si muove più
ma (a3,b1) non è un equilibrio perché B cambierebbe la sua scelta in b2
Equilibrio di Nash
) s
,.., sˆ
,...
s , s ( )
s ,.., s
,...
s , s
( 1 * * 2 * i * n i 1 * * 2 i * n
i
*
s i
i i
* i n
* 2
* 1 s i
S s
s.t.
) s ,.., s
,...
s , s ( Max
i
è la soluzione del problema
*
s i 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 che risulta migliore
(garantisce più alti payoffs) per un giocatore indipendentemente dalle strategie adottate dagli altri giocatori
Strategia DOMINANTE
Strategia DOMINATA
strategia che risulta inferiore
(garantisce più bassi payoffs) per un giocatore indipendentemente dalle strategie adottate dagli altri giocatori
Se esiste una strategia dominante un giocatore razionale giocherà
QUELLA
Se esiste una strategia
dominata un giocatore
razionale non la giocherà
MAI
Definzione
strategia che risulta non
peggiore (garantisce payoffs non inferiori) per un giocatore indipendentemente dalle
strategie adottate dagli altri giocatori
Strategia (debolmente) DOMINANTE
Strategia (debolmente) DOMINATA
strategia che risulta non superiore (garantisce payoffs non più alti) per un giocatore
indipendentemente dalle strategie
adottate dagli altri giocatori
B
b1 b2 b3
a1 0,3 2,2 1,3 A a2 2,1 3,2 2,3 a3 5,1 1,4 1,0
Esempio: strategia dominata
Confrontiamo a1 con a2 qualunque sia la scelta di B
(b1,b2,b3) a1 permette di ottenere un payoff più basso
Strategia Dominata
Nessun giocatore razionale sceglierebbe a1 se esiste a2
Per definire una strategia come dominata è
sufficiente che esista una sola altra strategia che permetta di avere un payoff più altro qualunque sia la scelta dell’altro giocatore
B
b1 b2 b3
a1 1,3 2,4 1,3
A a2 2,1 3,2 1,1
a3 5,1 4,4 2,0
Esempio: strategia dominante
Confrontiamo b2 con b1 e b3 qualunque sia la scelta di A
(a1,a2,a3) b2 permette di ottenere un payoff più alto
Strategia Dominante
Ogni giocatore razionale sceglierebbe b2
Per definire una strategia come dominante è necessario che permetta di ottenere un payoff
qualunque sia la strategia scelta dall’altro giocatore
Strategie dominanti e dominate sono collegate
B
b1 b2 b3 a1 1,3 2,4 1,3 A a2 2,1 3,2 1,1 a3 5,1 4,4 2,0
Per definizione:
se esiste una strategia dominante tutte le altre (dello stesso giocatore sono dominate
b1 e b3 sono dominate
Ma non è vero che se la strategia b1 è dominata dalla strategia b2 questa sia necessariamente dominante.
Strategie dominanti e dominate sono collegate
B
b1 b2 b3 a1 1,3 2,4 1,3 A a2 2,1 3,2 1,1 a3 5,1 4,4 2,5
La strategia b1 è dominata da b2 ma b2 non è una strategia dominante perché se A giocasse a3 sarebbe meglio per B scegliere b3
Nota è cambiato solo il payoff in rosso (5 al posto di 0)
Strategia Dominata b2 non è più una
strategia dominate
B
b1 b2 b3 a1 0,3 3,2 1,3 A a2 2,1 3,2 2,3 a3 5,1 1,4 1,0
Esempio: prendiamo questi altri due giochi
B
b1 b2 b3 a1 1,3 2,4 1,3 A a2 2,1 3,2 1,1 a3 5,1 4,4 2,4
Strategia debolmente Dominata
Strategia debolmente Dominante
Gli unici valori differenti sono i payoffs segnati in
rosso
B
b1 b2 b3
a1 1,3 2,4 1,3
A a2 2,1 3,2 1,1
a3 5,1 4,4 2,0
Come si trova l’equilibrio di Nash se esiste una strategia dominante
Ora se A sceglie a1 ottiene 2 a2 ottiene 3 a3 ottiene 4
A sceglie a3
Il giocatore B sceglie b2 e A lo sa
(a3,b3) Equilibrio di Nash
B
B1 b2 B3
a1 0,3 4,2 1,3
A a2 2,1 3,2 2,3
a3 5,1 1,4 1,0
Non ci sono né strategie dominate né strategie dominanti Per trovare la soluzione occorre utilizzare la funzione di
risposta ottima (BRF)
risposta ottima La migliore strategia che un giocatore può effettuare DATA la strategia scelta dagli ALTRI GIOCATORI
Funzione di
risposta ottima L’insieme delle risposte ottime di un giocatore
Come si trova l’equilibrio di Nash
B
b1 b2 b3
a1 0,3 4,2 1,3
A a2 2,1 3,2 2,3
a3 5,1 1,4 1,0
Trovare l’ E.d.N. utilizzando la BRF
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 a3 la migliore risposta di B è b2
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
E.d.N deve essere la coppia di strategie che
è la risposta ottima di
entrambi i giocatori
Gioco della mano invisibile figura 4.2 del libro
Anil e Bala sono due agricoltori
• i payoff sono i profitti che ottengono dalla coltivazione
• possono piantare solo R o M (due strategie)
• il terreno di A è più produttivo se si pianta M
• il terreno di B è più produttivo se si pianta R
• se entrambi piantano la stessa cosa il prezzo diminuisce così come il loro profitto
(M,R)
Il giocatore di linea che sceglie M e il giocatore di colonna che sceglie R è
l’equilibrio di Nash
Equilibrio in strategie dominanti
Gioco della mano invisibile
In questo caso la natura strategica della interazione fra i soggetti non preclude la possibilità che le decisione individuali vengano coordinate e si raggiunga un risultato socialmente desiderabile
Mano invisibile
Ma non è sempre così
Limiti della definizione di equilibrio di Nash
Gioco del calcio di rigore
cerchiamo l’equilibrio con il metodo della risposta ottima
E’ evidente che non esiste un equilibrio di Nash per questo gioco
P
dx cx sx
dx 0,2 2,0 2,0
A cx 2,0 0,2 2,0
sx 2,0 2,0 0,2
equilibrio di Nash
Lui
Opera Stadio
Lei
Opera 1 , 2 0 , 0 Stadio 0 , 0 2 , 1
Consideriamo questo gioco classico
La guerra dei sessi
Esiste una molteplicità
(due) di equilibri di
Nash
Quale selezionare ?
Consideriamo un altro gioco
Sempre Anil e Bala
Payoff differenti
In questo caso immaginiamo che nel caso A e B producano lo
stesso bene i prezzi
diminuiscano in modo molto forte
Ci sono due equilibri di Nash
Quale selezionare ?
Le due programmatrici
Di nuovo
Due equilibri di Nash
Come risolviamo il problema della ambiguità della molteplicità degli equilibri
S
P F
D P -2, -2 2 , 0 F 0 , 2 0 , 0
Prendiamo un altro gioco
Gioco dell’incrocio
Due auto (S e D) arrivano contemporaneamente all’incrocio
Possono Fermarsi o Passare
Molteplicità equilibri di Nash: giochi sequenziali
Auto A
Auto B Auto B
F P
F P F P
0 , 0 0 , 2 2 , 0 -2 , -2
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
rappresentazione La del gioco a forma
estesa è preferibile
Giochi sequenziali in forma estesa: induzione a ritroso
Auto A
Auto B Auto B
F P
F P F P
0 , 0 0 , 2 2 , 0 -2 , -2
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
B sceglierà F che gli da 0 al posto di -2 A lo sa e sa che se
sceglierà P prenderà 2 A sceglierà P che
gli garantisce 2 mentre se scegliesse F
avrebbe 0
Giochi sequenziali in forma estesa: induzione a ritroso
Auto A
Auto B Auto B
F P
F P F P
0 , 0 0 , 2 2 , 0 -2 , -2
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
B sceglierà F che gli da 0 al posto di -2 A lo sa e sa che se
sceglierà P prenderà 2 A sceglierà P che
gli garantisce 2 mentre se scegliesse F
avrebbe 0
Bettina M
Astrid
Java C++
4 , 3 0 , 0 3 , 6
Java C++ Java
C++
2 , 2
Gioco delle due programmatrici
Ipotesi
Astrid sceglie per prima Se c’è una sequenza
temporale l’ambiguità
sparisce
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à
Gioco dell’incrocio il semaforo, regola codice della strada
Risolvere questo tipo di ambiguità è una delle spiegazioni della nascita delle istituzioni
Guerra dei sessi Se il rapporto dura nel tempo, la coppia cerca una regola di
buona convivenza
Gioco programmatrici Se sono inserite in un’impresa ci può essere una struttura
gerarchica (la superiore decide
per prima)
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
Criterio Paretiano (da W. Pareto)
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
Il “ criterio di Pareto ” afferma quanto segue:
Criterio Paretiano
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).
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
oppure
Non tutte le allocazioni sono Pareto Ordinabili
A = (10, 3, 7) B = (10, 2, 7) C = (9, 5, 16)
Un'allocazione è efficiente 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
Criterio Paretiano (da W. Pareto)
Criterio di efficienza distributiva e non di equità
Dilemma del prigioniero
• Thelma e Louise sono complici in un grave delitto e sono detenute in celle separate (non possono comunicare).
• Ci sono le prove solo per accusarle di un reato minore la cui pena è 1 anno di reclusione
• Ogni prigioniera può confessare il delitto grave o negare.
• Se confessa uscirà subito di prigione, mentre la complice avrà una pena di 10 anni di reclusione.
• Se entrambe confessano saranno condannate a una pena intermedia di 2 anni.
• Se nessuna delle due confessa la pena sarà di 1 anno.
O.P
Nash
Thelma
Nega Confessa
Louise
Nega 1 , 1 10 , 0
Confessa 0 , 10 5 , 5
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
Nota: essendo anni di prigione si tende a minimizzare i payoffs
Louise
Nega Confessa
Thelma
Nega 1 , 1 10 , 0
Confessa 0 , 10 2 , 2
Dilemma del prigioniero
Confessa è la strategia
dominante per entrambe
Gioco del controllo dei parassiti (par. 4.3)
Dilemma del prigioniero
Ipotesi
a) Ci sono due contadini Anil e Bala (sempre quelli) cha hanno due campi identici e adiacenti
b) Per distruggere i parassiti che rovinano il raccolto hanno 2 strategie
a) Usare un potente antiparassitario (Terminator) che distrugge qualsiasi tipo di insetto ma inquina la falda acquifera costa poco
b) usare la lotta integrata che non ha effetti sulla falda costa di più
c) Se entrambi scelgono il T il danno alla falda sarà elevato e si renderà necessario acquistare un costoso sistema di filtraggio;
d) Se solo uno sceglie di usare il T il danno sarà limitato e il
filtraggio non sarà necessario
Beatrix
IPC T
Ana IPC 3, 3 1 , 4 T 4, 1 2 , 2
Gioco del controllo dei parassiti
Dilemma del prigioniero framework generale
Payoff Monetari
Sotto-ottimalità dell’equilibrio di Nash (DP) possibili soluzioni
Ruolo delle istituzioni si vieta l’uso del Terminator
Soluzione A Intervento dall’esterno
Meccanismi istituzionali Mafia, malavita organizzata dilemma del prigioniero
Modificano dall’esterno la struttura degli incentivi
Nella realtà il gioco è spesso ripetuto
Possono emergere dei meccanismi endogeni di punizione di comportamenti devianti
Se uno dei due contadini utilizzasse il Terminator lo
farebbe anche l’altro
Ogni volta che sono chiamate a collaborare, Anil e Bala devono decidere se collaborare (IPC) o «fregarsi» a vicenda
Meccanismo punitivo
Sotto-ottimalità dell’equilibrio di Nash (DP) possibili soluzioni
Soluzione B Reputazione e giochi ripetuti
Immaginiamo che il gioco venga giocato per tre periodi
Al tempo t
1Anil deve decidere se usare il terminator Se lo usa oggi sa che dal prossimo periodo in poi lo
userà anche Bala
π
TA= 4 + 2 + 2 = 8
Payoff di Anil se decide di «fregare»Bala e passare al Terminator
π
IPCA= 3 + 3 + 3 = 9
Payoff di Anil se preferisce continuare ad usare l’IPCQuesto calcolo è troppo semplificato valore attuale = al valore futuro
Sotto-ottimalità dell’equilibrio di Nash (DP) possibili soluzioni
Soluzione B Reputazione e giochi ripetuti
4
3
2
π
tempo
1 2 3 4
Vantaggio immediato
Perdita futura
Immaginiamo che il gioco venga giocato per più periodi Sotto-ottimalità dell’equilibrio di Nash (DP)
possibili soluzioni
Soluzione B Reputazione e giochi ripetuti
Se i giocatori sono sufficientemente pazienti (attribuiscono un peso adeguato ai guadagni futuri)
Il risultato pareto ottimale può essere raggiunto Reputazione -- Credibilità
Nota
Il gioco deve durare all’infinito o avere una durata finita ma incerta
