Post on 01-May-2015
Teoria dei giochi - D'Orio - I parte 1
Giochi statici (o a mosse simultanee) con informazione completa
Corso di Teoria dei Giochi
Laurea specialistica in Economia Applicata
Docente: Giovanni D’Orio
E-mail: giovanni.dorio@unical.it
Teoria dei giochi - D'Orio - I parte 2
Prospetto di sintesi dei giochi statici ad informazione completa Introduzione ai giochi Rappresentazione in forma Normale (o
strategica) Eliminazione iterata delle strategie
strettamente dominate Equilibrio di Nash Ripasso delle funzioni concave,
ottimizzazione Applicazione dell’equilibrio di Nash Equilibrio di Nash in strategie miste
Teoria dei giochi - D'Orio - I parte 3
Agenda
Che cosa è la teoria dei giochi Esempi
Dilemma del prigioniero La battaglia dei sessi Matching pennies
Giochi statici ad informazione completa (o a mosse simultanee)
Rappresentazione in forma Normale o strategica
Teoria dei giochi - D'Orio - I parte 4
Che cosa è la teoria dei giochi?
Noi ci concentreremo su giochi dove: Ci sono almeno due giocatori razionali Ogni giocatore ha più di una scelta Il risultato finale dipende dalle strategie scelte da tutti i
giocatori; c’è interazione strategica.
Esempio: Sei persone vanno ad un ristorante. Ogni persona paga il proprio pasto – un problema
semplice di decisione Prima del pranzo, ogni persona è d'accordo a dividere
il conto fra tutti i partecipanti – un gioco
Teoria dei giochi - D'Orio - I parte 5
Che cosa è la teoria dei giochi?
La Teoria dei Giochi è un modo formale di analizzare l’interazione strategica tra un gruppo di giocatori (o agenti) razionali che si comportano strategicamente
La teoria dei giochi ha applicazioni Economiche Politiche etc.
Teoria dei giochi - D'Orio - I parte 6
Esempio Classico: Il Dilemma del prigioniero Due sospetti detenuti in celle separate sono accusati di un crimine
rilevante. Non ci sono però prove sufficienti. Ad entrambi I sospetti viene comunicata la seguente regola:
Se nessuno confessa allora entrambi saranno accusati di un crimine minore e condannati ad un mese di carcere.
Se entrambi confessano allora entrambi saranno condannati a sei mesi di carcere.
Se uno confessa ma l’altro nega, allora chi confessa sarà rilasciato ma l’altro sconterà nove mesi di carcere.
-1 , -1 -9 , 0
0 , -9 -6 , -6Prigioniero 1
Prigioniero 2
Confessa
Nega
Confessa
Nega
Teoria dei giochi - D'Orio - I parte 7
Esempio: La battaglia dei sessi
In posti separati, Chris e Pat devono scegliere di passare la serata all’opera o a un combattimento di boxe.
Sia Chris che Pat sanno quanto segue: Entrambi vorrebbero passare la serata insieme. Ma Chris preferisce l’opera. Pat preferisce la boxe.
2 , 1 0 , 0
0 , 0 1 , 2Chris
Pat
Boxe
Opera
Boxe
Opera
Teoria dei giochi - D'Orio - I parte 8
Esempio: Matching pennies Ognuno dei due giocatori ha una monetina. I due giocatori devono scegliere simultaneamente se mostrare
Testa o Croce. Entrambi i giocatori conoscono le seguenti regole:
Se le due monetine hanno entrambi lo stesso esito (entrambe testa or entrambe croce) allora il giocatore 2 vince la moneta del giocatore 1.
In caso diverso, il giocatore 1 vince la moneta del giocatore 2.
-1 , 1 1 , -1
1 , -1 -1 , 1Giocatore 1
Giocatore 2Croce
Testa
Croce
Testa
Teoria dei giochi - D'Orio - I parte 9
Gioco statico (o a mosse simultanee) con informazione completa
Un insieme di giocatori (almeno 2)
Per ogni giocatore, un insieme di strategie/azioni
Payoffs ottenuti da ogni giocatore data la combinazione delle strategie, o preferenze per ogni giocatore sulle combinazioni delle strategie
{Giocat. 1, Giocat. 2, ... Giocat. n}
S1 S2 ... Sn
ui(s1, s2, ...sn), per ogni s1S1, s2S2, ... snSn.
Un gioco statico consiste di:
Teoria dei giochi - D'Orio - I parte 10
Gioco statico (o a mosse simultanee) con informazione completa Mosse simultanee
Ogni giocatore sceglie la propria strategia senza conoscere la scelta degli altri.
Informazione completa Ogni strategia possibile di ogni giocatore e la funzione dei
payoff sono conoscenza comune fra tutti I giocatori. Assunzioni sui giocatori
Razionalità• I giocatori vogliono massimizzare il proprio payoffs• I giocatori sono dei calcolatori perfetti (no errori)
Ogni giocatore sa che gli altri giocatori sono razionali
Teoria dei giochi - D'Orio - I parte 11
Gioco statico (o a mosse simultanee) con informazione completa I giocatori cooperano?
No. Questi sono giochi non cooperativi Il timing (la sequenza degli eventi)
Ogni giocatore i sceglie la propria strategia si senza conoscere la scelta altrui.
Solo adesso ogni giocatore i riceve il proprio payoff ui(s1, s2, ..., sn).
Il gioco finisce
Teoria dei giochi - D'Orio - I parte 12
Definizione: Rappresentazione in forma normale o strategica La rappresentazione in forma normale (o
strategica) di un gioco G specifica: Un insieme finito di giocatori {1, 2, ..., n}, Lo spazio delle strategie dei giocatori S1
S2 ... Sn e
Le funzioni di pay-off u1 u2 ... un dove ui : S1 × S2 × ...× Sn→R.
Teoria dei giochi - D'Orio - I parte 13
Rappresentazione in forma normale: gioco a 2 giocatori
Rappresentazione Bi-matriciale 2 giocatori: Player 1 e Player 2 Ogni giocatore ha un numero finito di strategie
Esempio:S1={s11, s12, s13} S2={s21, s22}
Player 2
s21 s22
Player 1
s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)
s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)
s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)
Teoria dei giochi - D'Orio - I parte 14
Esempio Classico: Rappresentazione “normale” del Dilemma del Prig. Insieme di giocatori:{Prigioniero 1, Prigioniero 2} Insieme delle strategie: S1 = S2 = {Nega, Confessa} Funzioni di Payoff :
u1(N, N)=-1, u1(N, C)=-9, u1(C, N)=0, u1(C, C)=-6;u2(N, N)=-1, u2(N, C)=0, u2(C, N)=-9, u2(C, C)=-6
-1 , -1 -9 , 0
0 , -9 -6 , -6Prig. 1
Prig. 2
Confessa
Nega
Confessa
NegaGiocat.
Strateg.
Payoffs
Teoria dei giochi - D'Orio - I parte 15
Esempio: La battaglia dei sessi
Rappresentazione in forma Normale: Insieme giocatori:{ Chris, Pat } (={Player 1, Player 2}) Insieme strategie: S1 = S2 = { Opera, Boxe}
Funzioni di Payoff : u1(O, O)=2, u1(O, B)=0, u1(B, O)=0, u1(B, B)=1; u2(O, O)=1, u2(O, B)=0, u2(B, O)=0, u2(B, B)=2
2 , 1 0 , 0
0 , 0 1 , 2Chris
Pat
Boxe
Opera
Boxe
Opera
Teoria dei giochi - D'Orio - I parte 16
Esempio: Matching pennies
Rappresentazione in forma normale: Insieme giocatori: {Player 1, Player 2} Insieme strategie: S1 = S2 = { Testa, Croce }
Funzioni di Payoff : u1(T, T)=-1, u1(T, C)=1, u1(C, T)=1, u1(C, C)=-1; u2(T, T)=1, u2(T, C)=-1, u2(C, T)=-1, u2(C, C)=1
-1 , 1 1 , -1
1 , -1 -1 , 1Player 1
Player 2
Croce
Testa
Croce
Testa
Teoria dei giochi - D'Orio - I parte 17
Esempio: Turisti e Nativi
Solo due bars (bar 1, bar 2) in città Si può applicare un prezzo di $2, $4, o $5 6000 turisti scelgono un bar casualmente 4000 nativi scelgono il bar con il prezzo minore
Esempio 1: Entrambi fissano $2 Ognuno guadagna 5,000 clienti e $10,000
Esempio 2: Il Bar 1 fissa $4, Il Bar 2 fissa $5 Bar 1 prende 3000+4000=7,000 clienti e $28,000 Bar 2 prende 3000 clienti e $15,000
Teoria dei giochi - D'Orio - I parte 18
Esempio: Il modello di duopolio di Cournot Un prodotto è prodotto solo da 2 imprese: impresa 1
e impresa 2. Le quantità sono rispettivamente q1 e q2,. Ogni impresa sceglie la quantità senza conoscere la quantità scelta dall’altra..
Il prezzo di mercato è P(Q)=a-Q, dove Q=q1+q2. Il costo dell’impresa i di produrre qi è Ci(qi)=cqi.
Rappresentazione in forma normale: Insieme giocatori: { Firm 1, Firm 2} Insieme strategie: S1=[0, +∞), S2=[0, +∞) Funzione di Payoff :
u1(q1, q2)=q1(a-(q1+q2)-c), u2(q1, q2)=q2(a-(q1+q2)-c)
Teoria dei giochi - D'Orio - I parte 19
Ancora un esempio
Ognuno di n giocatori seleziona un numero tra 0 e 100 simultaneamente. Sia xi il numero selezionato dal giocatore i.
Sia y la media di questi numeri Il payoff del giocatore i sia = xi – 3y/5
La rappresentazione in forma normale:
Teoria dei giochi - D'Orio - I parte 20
Risolvere il Dilemma del Prigioniero
Confessare dà sempre un risultato migliore indipendentemente dalla scelta dell’altro
Strategia dominata Esiste un’altra strategia che dà sempre risultati migliori
indipendentemente dalla scelta degli altri.
-1 , -1 -9 , 0
0 , -9 -6 , -6Prigion. 1
Prisoner 2
Confessa
Nega
Confessa
NegaGiocatori
Strategie
Payoffs
Teoria dei giochi - D'Orio - I parte 21
Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un}, siano si', si" Si strategie possibili per I giocatori i. La strategia si' è strettamente dominata dalla strategia si" se
ui(s1, s2, ... si-1, si', si+1, ..., sn) < ui(s1, s2, ... si-1, si", si+1, ..., sn)
Per ogni s1 S1, s2 S2, ..., si-1Si-1, si+1 Si+1, ..., sn Sn.
Definizione: strategie strettamente dominate
-1 , -1 -9 , 0
0 , -9 -6 , -6Prig. 1
Prig. 2
Confessa
Nega
Confessa
NegaIndipend. Scelta altrui
si” è strettamente meglio di si’
Teoria dei giochi - D'Orio - I parte 22
Riassunto
Giochi statici ad informazione completa Rappresentazione normale o strategica
Prossimo argomento Strategie dominate Eliminazione iterata di strategie strettamente
dominate Equilibrio di Nash
Teoria dei giochi - D'Orio - I parte 23
Ripasso veloce
La forma normale di un gioco G specifica: Un insieme finito di giocatori {1, 2, ..., n}, Lo spazio delle strategie dei giocatori S1 S2 ... Sn e
Le loro funzioni di payoff u1 u2 ... un dove ui : S1 × S2 × ...× Sn→R.
Prig. 2
Nega Confessa
Prig. 1Nega -1 , -1 -9 , 0
Confessa 0 , -9 -6 , -6
Tutte le combinazioni delle strategie.
Una combinazione di strategie è un insieme di strategie, una per ogni giocatore
Teoria dei giochi - D'Orio - I parte 24
Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un}, siano si', si" Si strategie possibili per I giocatori i. La strategia si' è strettamente dominata dalla strategia si" se
ui(s1, s2, ... si-1, si', si+1, ..., sn) < ui(s1, s2, ... si-1, si", si+1, ..., sn)
Per ogni s1 S1, s2 S2, ..., si-1Si-1, si+1 Si+1, ..., sn Sn.
Definizione: strategie strettamente dominate
-1 , -1 -9 , 0
0 , -9 -6 , -6Prig. 1
Prig. 2
Confessa
Nega
Confessa
NegaIndipend. Scelta altrui
si” è strettamente meglio di si’
Teoria dei giochi - D'Orio - I parte 25
Esempio
Due imprese, Reynolds e Philip, si dividono il mkt. Ogni impresa guadagna $60 milioni dalla propria
clientela se nessuna fa pubblicità (Ad) La pubblicità costa all’impresa $20 milioni La pubblicità attrae $30 milioni di fatturato dell’altro
concorrente
Philip
No Ad Ad
ReynoldsNo Ad 60 , 60 30 , 70
Ad 70 , 30 40 , 40
Teoria dei giochi - D'Orio - I parte 26
Gioco a 2 con strategie finite
S1={s11, s12, s13} S2={s21, s22} s11 è strettamente dominata da s12 se
u1(s11,s21)<u1(s12,s21) e u1(s11,s22)<u1(s12,s22). s21 è strettamente dominata da s22 se
u2(s1i,s21) < u2(s1i,s22), per i = 1, 2, 3
Player 2
s21 s22
Player 1
s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)
s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)
s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)
Teoria dei giochi - D'Orio - I parte 27
Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un}, siano si', si" Si strategie possibili per il giocatore i. La strategia si' è debolmente dominata dalla strategia si" se
ui(s1, s2, ... si-1, si', si+1, ..., sn) (ma non sempre =) ui(s1, s2, ... si-1, si", si+1, ..., sn)
per tutte s1 S1, s2 S2, ..., si-1Si-1, si+1 Si+1, ..., sn Sn.
Definizione: strategie debolmente dominate
1 , 1 2 , 0
0 , 2 2 , 2Player 1
Player 2
R
U
B
LQualsiasi sia la scelta altrui
si” è almeno tanto buono quanto si’
Teoria dei giochi - D'Orio - I parte 28
Strategie dominate in modo stretto o in modo debole Un giocatore razionale non sceglie mai
strategie strettamente dominate. Quindi ogni strategia strettamente dominata può essere eliminata.
Un giocatore razionale può scegliere una strategia debolmente dominata.
Teoria dei giochi - D'Orio - I parte 29
Eliminazione iterata di strategie strettamente dominate Se una strategia è strettamente dominata,
eliminatela La dimensione e complessità del gioco
risulterà ridotta Eliminate ogni strategia strettamente
dominata dal gioco ridotto Continuate le eliminazioni finchè non ci
saranno più strategie strettam. dominate
Teoria dei giochi - D'Orio - I parte 30
Eliminazione iterata di strategie strettamente dominate: un esempio
1 , 0 1 , 2 0 , 1
0 , 3 0 , 1 2 , 0Player 1
Player 2
Centro
Su
Giù
Sinistra
1 , 0 1 , 2
0 , 3 0 , 1Player 1
Player 2
Centro
Su
Giù
Sinistra
Destra
Teoria dei giochi - D'Orio - I parte 31
Esempio: Turisti e Nativi
Solo due bar (bar 1, bar 2) in una città Si possono fissare prezzi di $2, $4, o $5 6000 turisti scelgono un bar casualmente 4000 nativi selezionano il bar con il prezzo inferiore
Esempio 1: Entrambi fissano $2 Ognuno attrae 5,000 clienti e $10,000
Esempio 2: Bar 1 fissa $4, Bar 2 fissa $5 Bar 1 attrae 3000+4000=7,000 clienti e $28,000 Bar 2 attrae 3000 clienti e $15,000
Teoria dei giochi - D'Orio - I parte 32
Esempio: Turisti e Nativi
Bar 2
$2 $4 $5
Bar 1
$2 10 , 10 14 , 12 14 , 15
$4 12 , 14 20 , 20 28 , 15
$5 15 , 14 15 , 28 25 , 25
Payoffs sono in migliaia di dollari
Bar 2
$4 $5
Bar 1$4 20 , 20 28 , 15
$5 15 , 28 25 , 25
Teoria dei giochi - D'Orio - I parte 33
Ancora un esempio
Ognuno di n giocatori seleziona un numero tra 0 e 100 simultaneamente. Sia xi il numero selezionato dal giocatore i.
Sia y la media di questi numeri Il payoff del giocatore I sarà = xi – 3y/5
Teoria dei giochi - D'Orio - I parte 34
Un esempio ulteriore
La rappresentazione in forma normale: Giocatori: {player 1, player 2, ..., player n} Strategie: Si =[0, 100], per i = 1, 2, ..., n.
Funzione di payoff:
ui(x1, x2, ..., xn) = xi – 3y/5
Ci sono strategie dominate?
Quali numeri dovrebbero essere selezionati?
Teoria dei giochi - D'Orio - I parte 35
Un nuovo concetto di soluzione: l’equilibrio di Nash
Giocat. 2
L C R
Giocat. 1
T 0 , 4 4 , 0 5 , 3
M 4 , 0 0 , 4 5 , 3
B 3 , 5 3 , 5 6 , 6
La combinazione di strategie (B, R) ha la seguente proprietà:
Il Giocatore 1 NON PUO’ fare meglio scegliendo una strategia diversa da B, dato il fatto che giocatore 2 sceglie R.
Il Giocatore 2 NON PUO’ fare meglio scegliendo una strategia diversa da R, dato il fatto che il giocatore 1 sceglie B.
Teoria dei giochi - D'Orio - I parte 36
Un nuovo concetto di soluzione: l’equilibrio di Nash
Giocat. 2
L’ C’ R’
Giocat. 1
T’ 0 , 4 4 , 0 3 , 3
M’ 4 , 0 0 , 4 3 , 3
B’ 3 , 3 3 , 3 3.5 , 3.6
La combinazione di strategie (B’, R’) ha la seguente proprietà:
Il giocatore 1 NON PUO’ fare meglio scegliendo una strategia diversa da B’, dato il fatto che il giocatore 2 sceglie R’.
Il giocatore 2 NON PUO’ fare meglio scegliendo una strategia diversa da R’, dato il fatto che il giocatore 1 sceglie B’.
Teoria dei giochi - D'Orio - I parte 37
Equilibrio di Nash : l’idea
L’equilibrio di Nash Un insieme di strategie, una per ogni
giocatore, tale che la strategia di ogni giocatore sia la migliore risposta possibile nel momento in cui gli altri giocatori stanno giocando le loro strategie di equilibrio.
BR to BR= Best response to a best response
Teoria dei giochi - D'Orio - I parte 38
Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 ,
u2 , ..., un}, una combinazione di strategie ),...,( **1 nss è
un equilibrio di Nash se, per ogni giocat. i,
),...,,,,...,(
),...,,,,...,(
**1
*1
*1
**1
**1
*1
niiii
niiii
sssssu
sssssu
per tutte ii Ss . Ciò implica che, *is solve
Max ),...,,,,...,( **1
*1
*1 niiii sssssu
soggetto a ii Ss
Definizione: L’equilibrio di Nash
Data la scelta altrui, il giocat. i non può migliorare se devia da si*
Prig. 2
Nega Confessa
Prig. 1Nega -1 , -1 -9 , 0
Confessa 0 , -9 -6 , -6
Teoria dei giochi - D'Orio - I parte 39
Gioco a 2 giocatori con strategie finite
S1={s11, s12, s13} S2={s21, s22} (s11, s21)è un equilibrio di Nash se u1(s11,s21) u1(s12,s21), u1(s11,s21) u1(s13,s21) eu2(s11,s21) u2(s11,s22).
Giocatore 2
s21 s22
Gioc. 1
s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)
s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)
s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)
Teoria dei giochi - D'Orio - I parte 40
Ricerca dell’equilibrio di Nash: ispezione cella a cella
1 , 0 1 , 2 0 , 1
0 , 3 0 , 1 2 , 0Player 1
Player 2
Middle
Up
Down
Left
1 , 0 1 , 2
0 , 3 0 , 1Player 1
Player 2
Middle
Up
Down
Left
Right
Teoria dei giochi - D'Orio - I parte 41
Riassunto
Strategie dominate Eliminazione iterata Equilibrio di Nash
Prossimo argomento Equilibrio di Nash Funzione di risposta ottima
Teoria dei giochi - D'Orio - I parte 42
Equilibrio di Nash : idea
Equilibrio di Nash Un insieme di strategie, una per ogni giocatore, tale
che la strategia di ogni giocatore sia la sua migliore possibile considerato che tutti gli altri giocatori stanno giocando la loro migliore strategia o
Una situazione stabile nella quale nessun giocatore vuole deviare se gli altri confermano la propria posizione
Prig. 2
Nega Confessa
Prig. 1Nega -1 , -1 -9 , 0
Confessa 0 , -9 -6 , -6
(Confessa, Confessa) è un equilibro di Nash.
Teoria dei giochi - D'Orio - I parte 43
Esempio: Turisti e Nativi
Bar 2
$2 $4 $5
Bar 1
$2 10 , 10 14 , 12 14 , 15
$4 12 , 14 20 , 20 28 , 15
$5 15 , 14 15 , 28 25 , 25
Payoffs sono in migliaia di dollari
Bar 2
$4 $5
Bar 1$4 20 , 20 28 , 15
$5 15 , 28 25 , 25
Teoria dei giochi - D'Orio - I parte 44
Ancora quell’esempio
Rappresentazione in forma normale: Giocatori: {player 1, player 2, ..., player n} Strategie: Si =[0, 100], for i = 1, 2, ..., n.
Funzioni di Payoff :
ui(x1, x2, ..., xn) = xi – 3y/5
Quale è l’equilibrio di Nash?
Teoria dei giochi - D'Orio - I parte 45
Funzione di risposta ottima: esempio
Se Player 2 sceglie L’ allora la strategia ottima di Player 1 è M’ Se Player 2 sceglie C’ allora la strategia ottima di Player 1 è T’ Se Player 2 sceglie R’ allora la strategia ottima di Player 1 è B’ Se Player 1 sceglie B’ allora la strategia ottima di Player 2’ è R’
Risposta ottima: la migliore strategia giocabile da un giocatore, data la strategia scelta da altri giocatori
Player 2
L’ C’ R’
Player 1
T’ 0 , 4 4 , 0 3 , 3
M’ 4 , 0 0 , 4 3 , 3
B’ 3 , 3 3 , 3 3.5 , 3.6
Teoria dei giochi - D'Orio - I parte 46
Esempio: Turisti e Nativi
Quale è la risposta ottima del Bar 1 alle strategie di Bar 2 pari a $2, $4 o $5?
Quale è la risposta ottima del Bar 2 alle strategie di Bar 1 pari a $2, $4 or $5?
Bar 2
$2 $4 $5
Bar 1
$2 10 , 10 14 , 12 14 , 15
$4 12 , 14 20 , 20 28 , 15
$5 15 , 14 15 , 28 25 , 25
Payoffs in migliaia di dollari
Teoria dei giochi - D'Orio - I parte 47
Gioco a 2 giocatori con strategie finite
S1={s11, s12, s13} S2={s21, s22} La strategia di Player 1 s11 è la migliore risposta alla
strategia di Player 2 s21 se u1(s11,s21) u1(s12,s21) eu1(s11,s21) u1(s13,s21).
Player 2
s21 s22
Player 1
s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)
s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)
s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)
Teoria dei giochi - D'Orio - I parte 48
Utilizzo delle funzioni di risposta ottima per trovare l’equilibrio di Nash In un gioco a due giocatori, ( s1, s2 ) è un
equilibrio di Nash se e solo se la strategia di player 1’ s1 è la migliore risposta alla strategia di player 2 s2, e la strategia di player 2 s2 è la migliore risposta alla strategia di player 1 s1.
-1 , -1 -9 , 0
0 , -9 -6 , -6Prisoner 1
Prisoner 2
Confess
Mum
Confess
Mum
Teoria dei giochi - D'Orio - I parte 49
Utilizzo delle funzioni di risposta ottima per trovare l’equilibrio di Nash : esempio
M’ è la risposta ottima di Player 1 alla strategia L’ di Player 2 T’ è la risposta ottima di Player 1 alla strategia C’ di Player 2 B’ è la risposta ottima di Player 1 alla strategia R’ di Player 2 L’ è la risposta ottima di Player 2 alla strategia T’ di Player 1 C’ è la risposta ottima di Player 2 alla strategia M’ di Player 1 R’ è la risposta ottima di Player 2 alla strategia B’ di Player 1
Player 2
L’ C’ R’
Player 1
T’ 0 , 4 4 , 0 3 , 3
M’ 4 , 0 0 , 4 3 , 3
B’ 3 , 3 3 , 3 3.5 , 3.6
Teoria dei giochi - D'Orio - I parte 50
Esempio: Turisti e Nativi
Bar 2
$2 $4 $5
Bar 1
$2 10 , 10 14 , 12 14 , 15
$4 12 , 14 20 , 20 28 , 15
$5 15 , 14 15 , 28 25 , 25
I Payoffs sono in migliaia di dollari
Usate la funzione di rsposta ottima per trovare l’equilibrio di Nash.
Teoria dei giochi - D'Orio - I parte 51
Esempio: La battaglia dei sessi
Opera è la risposta ottima di Player 1 alla strategia di Player 2 Opera Opera è la risposta ottima di Player 2 alla strategia di Player 1 Opera
Quindi, (Opera, Opera) è un Equilibrio di Nash
Fight è la risposta ottima di Player 1 alla strategia di Player 2 Fight Fight è la risposta ottima di Player 2 alla strategia di Player 1 Fight
Quindi, (Fight, Fight) è un Equilibrio di Nash
2 , 1 0 , 0
0 , 0 1 , 2Chris
Pat
Prize Fight
Opera
Prize Fight
Opera
Teoria dei giochi - D'Orio - I parte 52
Esempio: Matching pennies
Head è la risposta ottima di Player 1 alla strategia di Player 2 Tail Tail è la risposta ottima di Player 2 alla strategia di Player 1 Tail
Tail è la risposta ottima di Player alla strategia di Player 2 Head Head è la risposta ottima di Player 2 alla strategia di Player 1 Head
Quindi, NON c’è equilibrio di Nash
-1 , 1 1 , -1
1 , -1 -1 , 1Player 1
Player 2
Tail
Head
Tail
Head
Teoria dei giochi - D'Orio - I parte 53
Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un},
Se i giocat. 1, 2, ..., i-1, i+1, ..., n scelgono rispettivamente
nii ssss ,...,,,..., 111 , strategie, Allora la funzione di risposta ottima del giocatore i è
definita da } le per tutte ),,...,,,,...,(
),...,,,,...,(:{
) ,...,,,..., (
111
111
111
iiniiii
niiiiii
niii
Sssssssu
sssssuSs
ssssB
Definizione: funzione di risposta ottima
La risposta ottima di Player i
Date le strategie degli altri
Teoria dei giochi - D'Orio - I parte 54
Una definizione alternativa: La strategia di Player i ),...,,...,( 111 niiii ssssBs se e solo se risolve (o è soluzione d’ottimo)
Max ),...,,,,...,( 111 niiii sssssu oggetto a ii Ss dove nii ssss ..., , , ..., , 111 sono date.
Definizione: funzione di risposta ottima
La risposta ottima di Player 1 alle strategie altrui è una soluzione d’ottimo di
Teoria dei giochi - D'Orio - I parte 55
Utilizzo delle funzioni di risposta ottima per la definizione degli equilibri di Nash
Insieme di strategie, una per giocatore, tale che la strategia di ogni giocatore è per lui la migliore, assunto che gli altri stanno giocando le loro strategie ottime, o
Una situazione stabile che nessun giocatore vuole cambiare se gli altri non cambiano
Nel gioco in forma normale {S1, ..., Sn , u1, ..., un}, una combinazione di strategie ),...,( **
1 nss è un equilibrio di Nash se per ogni giocatore i,
) ..., , , ,..., ( **1
*1
*1
*niiii ssssBs
Teoria dei giochi - D'Orio - I parte 56
Riassunto
Equilibrio di Nash Funzione di risposta ottima Utilizzo della funzione di risposta ottima per la
definizione dell’equilibrio di Nash Utilizzo della funzione di risposta ottima per la
determinazione dell’equilibrio di Nash
Prossimo argomento Funzioni concave e ottimizzazione Applicazioni
Teoria dei giochi - D'Orio - I parte 57
Riassunto
In un gioco a n-giocatori in forma normale, se l’eliminazione iterata di strategie strettamente dominate elimina tutte le strategie tranne ( s1*, s2*, ..., sn*), allora (s1*, s2*, ..., sn*) è l’unico equilibrio di Nash.
In un gioco a n-giocatori in forma normale, se le strategie ( s1*, s2*, ..., sn*) è un equilibrio di Nash allora esse sopravvivono all’eliminazione iterata di strategie strettamente dominate. Male strategie che superano l’eliminazione iterata di strategie strettamente dominate non necessariamente sono equilibri di Nash.
Teoria dei giochi - D'Orio - I parte 58
Il modello del duopolio di Cournot
Un prodotto è realizzato solo da due imprese: impresa 1 e impresa 2. Le quantità sono denotate rispettivamente da q1 e q2,. Ogni impresa sceglie la propria quantità senza conoscere la scelta dell’altra.
Il prezzo di mercato è P(Q)=a-Q, dove a è una costante e Q=q1+q2.
Il costo dell’impresa i per produrre la quantità qi è Ci(qi)=cqi.
Teoria dei giochi - D'Orio - I parte 59
Il modello del duopolio di Cournot
La rappresentazione in forma normale: Insieme dei giocatori: { Impresa 1, Impresa 2} Insieme delle strategie: S1=[0, +∞), S2=[0, +∞)
Funzioni di payoff: u1(q1, q2)=q1(a-(q1+q2)-c)u2(q1, q2)=q2(a-(q1+q2)-c)
Teoria dei giochi - D'Orio - I parte 60
Il modello del duopolio di Cournot
Come trovare l’equilibrio di Nash: Trovate la coppia di quantità (q1*, q2*) tale che q1* sia
la risposta ottima dell’impresa 1 alla quantità q2* dell’impresa 2 e q2* sia la risposta ottima dell’impresa 2 alla quantità q1* dell’impresa 1
Ciò significa che, q1* risolve Max u1(q1, q2*)=q1(a-(q1+q2*)-c)soggetto a 0 q1 +∞
e q2* risolveMax u2(q1*, q2)=q2(a-(q1*+q2)-c)soggetto a 0 q2 +∞
Teoria dei giochi - D'Orio - I parte 61
Una funzione )(xf è concava se, per ogni x e y, )()1()())1(( yfxfyxf
per tutti 10 .
Funzioni concave
x
f(x)
0
Teoria dei giochi - D'Orio - I parte 62
Una funzione )(xf è convessa se, per ogni x e y, )()1()())1(( yfxfyxf
per tutti 10 .
Funzioni convesse
x
f(x)
0
Teoria dei giochi - D'Orio - I parte 63
Alcuni risultati utili: Una funzione )(xf è concava se e solo se
.0)( xf
Una funzione )(xf è convessa se e solo se .0)( xf
)(xf è concava se e solo se )(xf è convessa.
Concavità e convessità
Teoria dei giochi - D'Orio - I parte 64
Esempio 1: 463)( 2 xxxf , 66)( xxf , 06)( xf . Quindi, )(xf è concava.
Esempio 2: xexf )( , 0)()( xexfxf . Quindi, )(xf è convessa. Esempio 3: 22 342),( yxyxyyxf Per ogni dato y, ),( yxf è concava in x perchè
02),( e 22),( yxfxyyxf xx Per ogni dato x, ),( yxf è convessa in y perchè
06),( e 642),( yxfyxyxf yy
Concavità e convessità
Teoria dei giochi - D'Orio - I parte 65
Un massimo di )(xf è un punto x' tale che )()( xfxf per ogni x.
Un minimo di )(xf è un punto x* tale che )(*)( xfxf per ogni x.
Massimi e minimi
x
f(x)
0 x* x’
Teoria dei giochi - D'Orio - I parte 66
Condizioni di primo ordine (FOC): se un punto x è un massimo o minimo allora x soddisfa le condizioni di primo ordine (FOC): 0)( xf .
Se )(xf è concave e x soddisfa le FOC, allora x è un massimo.
Se )(xf è convessa e *x soddisfa le FOC, allora *x è un minimo.
Massimo e minimo
x
f(x)
0 x
f(x)
0x’ x*
Teoria dei giochi - D'Orio - I parte 67
Trovare il max di una funzione concava )(xf Calcolate )(xf Calcolate )(xf e controllate se 0)( xf Se 0)( xf allora risolvete 0)( xf . La soluzione è un massimo
Esempio 1: 463)( 2 xxxf , 66)( xxf , 06)( xf . Quindi, )(xf è concava.
Risolvendo 0)( xf da x=1, il massimo. Esempio 3: 22 342),( yxyxyyxf Per ogni y fisso, ),( yxf è concava in x. Per ogni y fisso, trovate il massimo di ),( yxf
Trovare il massimo di una funzione concava
Teoria dei giochi - D'Orio - I parte 68
Un massimo di )(xf nel dominio [x1, x2] è un punto x' in [x1, x2] tale che )()( xfxf per ogni ] ,[ 21 xxx . Un minimo di )(xf nel dominio [x1, x2] è un punto x* in [x1, x2] ale che )(*)( xfxf per ogni ] ,[ 21 xxx .
Massimo e minimo
x
f(x)
0x1 x2x* x’
Teoria dei giochi - D'Orio - I parte 69
Trovare il massimo di una )(xf concava nel dominio ] ,[ 21 xx Trovate il max x di )(xf senza vincoli Se x è in ] ,[ 21 xx allora x è anche un max per il
problema vincolato Altrimenti,
a. se )()( 21 xfxf o 1xx allora 1x è un massimo; b. se )()( 21 xfxf o 2xx allora 2x è un massimo; c. se )()( 21 xfxf allora ogni punto in ] ,[ 21 xx è un
massimo.
Trovare il massimo di una funzione concava con vincoli
Teoria dei giochi - D'Orio - I parte 70
Esempio 4:
22 a s.
463)(Max 2
x
xxxf
Risolvere il problema senza vincolo dà come soluzione x=1. Dato che 1 è nel dominio, 1 è anche il punto di massimo del problema vincolato. Esempio 5:
463)( Max 2
2
xxxf
x
Trovare il massimo di una funzione concava con vincoli
Teoria dei giochi - D'Orio - I parte 71
Trovare il massimo di una funzione concava con vincoli
x
f(x)=-3x2+6x-4
Teoria dei giochi - D'Orio - I parte 72
Utilizzo della funzione di risposta ottima per la ricerca dell’equilibrio di Nash
In un gioco a due gioc., ( s1, s2 ) è un equilibrio di Nash se e solo se la strategia s1 del gioc.1 è la rsipsota ottima alla strategia s2 del gioc. 2, e se la strategia s2 del giocatore 2 è la risposta ottima alla strategia s1 del giocatore 1
-1 , -1 -9 , 0
0 , -9 -6 , -6Prig. 1
Prig. 2
Confessa
Nega
Confessa
Nega
Teoria dei giochi - D'Orio - I parte 73
Il modello del duopolio di Cournot
Come trovare l’equilibrio di Nash: Trovate la coppia di quantità (q1*, q2*) tale che q1* sia
la risposta ottima dell’impresa 1 alla quantità q2* dell’impresa 2 e q2* sia la risposta ottima dell’impresa 2 alla quantità q1* dell’impresa 1
Ciò significa che, q1* risolve Max u1(q1, q2*)=q1(a-(q1+q2*)-c)soggetto a 0 q1 +∞
e q2* risolveMax u2(q1*, q2)=q2(a-(q1*+q2)-c)soggetto a 0 q2 +∞
Teoria dei giochi - D'Orio - I parte 74
Il modello del duopolio di Cournot
Ricerca dell’equilibrio di Nash Risolvete
Max u1(q1, q2*)=q1(a-(q1+q2*)-c)s. a 0 q1 +∞
FOC: a - 2q1 - q2*- c = 0 q1 = (a - q2*- c)/2
Teoria dei giochi - D'Orio - I parte 75
Il modello del duopolio di Cournot
Ricerca dell’equilibrio di Nash Risolvete
Max u2(q1*, q2)=q2(a-(q1*+q2)-c)s. a 0 q2 +∞
FOC: a - 2q2 – q1* – c = 0 q2 = (a – q1* – c)/2
Teoria dei giochi - D'Orio - I parte 76
Il modello del duopolio di Cournot
Ricerca dell’equilibrio di Nash La coppia (q1*, q2*) è un equilibrio di Nash se
q1* = (a – q2* – c)/2 q2* = (a – q1* – c)/2
Risolvere queste due equazioni ci dà: q1* = q2* = (a – c)/3
Teoria dei giochi - D'Orio - I parte 77
Il modello del duopolio di Cournot Funzione di risposta ottima
La funzione di risposta ottima dell’impresa 1 alla quantità q2 dell’impresa 2R1(q2) = (a – q2 – c)/2 if q2 < a– c; 0 negli altri casi, e
La funzione di risposta ottima dell’impresa 2 alla quantità q1 dell’impresa 1
R2(q1) = (a – q1 – c)/2 if q1 < a– c; 0 negli altri casi
q1
q2
(a – c)/2
(a – c)/2
a – c
a – c
Equilibrio diNash
Teoria dei giochi - D'Orio - I parte 78
Il modello del duopolio di Cournot a n imprese Un prodotto è realizzato da n imprese:
dall’impresa 1 all’impresa n. La quantità dell’impresa i sia qi.Ogni impresa effettua la propria scelta senza sapere ciò che fanno le altre.
Il prezzo di mkt. è P(Q)=a-Q, dove a è una costante e Q=q1+q2+...+qn.
Il costo dell’impresa i di produrre la quantità qi è Ci(qi)=cqi.
Teoria dei giochi - D'Orio - I parte 79
Il modello del duopolio di Cournot
La rappresentazione in forma normale: Insieme dei giocatori: { Impresa 1, ...
Impresa n} Insieme delle strategie: Si=[0, +∞),
per i=1, 2, ..., nFunzioni di payoff:
ui(q1 ,..., qn)=qi(a-(q1+q2 +...+qn)-c)for i=1, 2, ..., n
Teoria dei giochi - D'Orio - I parte 80
Il modello del duopolio di Cournot
Come trovare l’equilibrio di Nash Trovate le quantità (q1*, ... qn*) tali che qi* e la risposta
ottima dell’impresa i alle quantità delle altre imprese. Ciò significa che q1* risolve
Max u1(q1, q2*, ..., qn*)=q1(a-(q1+q2* +...+qn*)-c)s. a 0 q1 +∞
e q2* risolveMax u2(q1*, q2 , q3*, ..., qn*)=q2(a-(q1*+q2+q3*+ ...+ qn*)-c)s. a 0 q2 +∞
.......
Teoria dei giochi - D'Orio - I parte 81
Riassunto
Equilibrio di Nash Funzioni concave e massimizzazione Il modello del duopolio e dell’oligopolio di
Cournot
Prossimo argomento Il modello del duopolio di Bertrand