Teoria dei Giochi: lezione del 18 Maggio 2017:
Equilibri di Nash, Strategie ESS e RE
Chiara Mocenni
Corso di Teoria dei Giochi e Giochi Evolutivi
Replicator equation, equilibri di Nash ed equilibri ESS
Possiamo riscrivere l’insieme degli equilibri di Nash (NE) a l’equazione replicator (RE) come segue:
∆
NE= {x ∈ ∆ : π(e
i, x ) = max
z∈∆
π(z, x ) ∀i ∈ C (x )}
˙
x
i= π(e
i, x ) − π(x , x ) x
i= π(e
i− x, x)x
idove π(·, ·) ` e una funzione di payoff.
Uno stato di popolazione x ` e stazionario nella RE sse π(e
i− x, x)x
i= 0 per ogni strategia pura i ∈ K
Equivalentemente, lo stato di popolazione x ` e stazionario nella RE sse tutte le strategie pure i guadagnano precisamente lo stesso payoff contro la strategia mista x .
Dunque, l’insieme degli stati stazionari della RE ` e:
∆
0= {x ∈ ∆ : π(e
i, x ) = π(x , x ) ∀i ∈ C (x )}
La condizione di stazionariet` a ` e banalmente soddisfatta da ogni vertice del simplesso x = e
i, dal momento che in tale stato x , tutti gli individui utilizzano la stessa strategia pura i e guadagnano lo stesso payoff. Da qui l’insieme finito
{e
1, ..., e
k} di vertici `e un sottoinsieme di ∆
0.
L’insieme non vuoto e chiuso ∆
NE` e un sottoinsieme di ∆
0: se tutte le strategie pure nel supporto della strategia x guadagnano lo stesso payoff massimo contro x , allora tutti guadagnano il payoff medio della popolazione.
π(x , x ) =
k
X
j =1
π(e
j, x )x
j= X
j ∈C (x )
π(e
j, x )x
jLo stesso risultato vale per gli stati interni della popolazione x : Se x ∈ int(∆) ` e stazionario nella RE, allora
π(e
i, x ) = π(x , x ) per ogni strategia pura i nel gioco, quindi ogni strategia pura ` e una best reply per le strategie miste x e conseguentemente x ∈ ∆
NESia ora ∆
00(non necessariamente non vuoto) l’insieme di stati stazionari interni ∆
00= ∆
0∩ int(∆). Dal momento che tutti gli equilibri di Nash sono stazionari otteniamo
∆
00= ∆
NE∩ int(∆)
L’insieme ∆
00` e necessariamente convesso, infatti ogni
combinazione lineare di stati stazionari ` e sempre uno stato
stazionario
Figura:Relazione tra i punti stazionari delle equazioni di replicator e gli equilibri di Nash del gioco
Gli stati stazionari che non sono equilibri di Nash, non soddisfano il
criterio di stabilit` a di Lyapunov (stabilit` a debole). La ragione per
la quale uno stato della popolazione x non appartenente a ∆
NE` e
instabile, ` e semplicemente che esistono alcune strategie pure i che
non vengono utilizzate (x
i= 0), ma che otterrebbero un payoff
maggiore contro x rispetto alle strategie pure utilizzate nello stato
x . Quindi, se un parte arbitrariamente piccola della popolazione
iniziasse a utilizzare tale strategia redditizia i , gli individui individui
di questo gruppo guadagnerebbero un payoff maggiore, il che
porterebbe lo stato della popolazione a lasciare x .
Theorem
Se x ∈ ∆ ` e Lyapunov stabile nella RE, allora x ∈ ∆
NE.
Dimostrazione.Supponiamo che x ∈ ∆
0e che x / ∈ ∆
NE. Allora tutte le strategie
pure nel supporto C (x ) hanno lo stesso payoff non ottimale contro
x . Quindi esistono i / ∈ C (x) tali che π(e
i− x, x) > 0. Dalla
continuit` a di π, esiste un δ > 0 ed un intorno U di x tale che
π(e
i− y , y ) ≥ δ per ogni y ∈ U ∩ ∆. Cos`ı ξ
i(t, x
0) aumenta
inizialmente in modo esponenziale da ogni x
0∈ U ≥ int(∆), e
anche x
i= 0, quindi x non ` e Lyapunov stabile.
Figura:Relazione tra gli equilibri di Nash e la stabilit`a dei punti stazionari delle equazioni di replicator
Tutti gli individui nella popolazione conoscono la distribuzione delle strategie pure della popolazione durante il trascorrere del tempo, e cercano di massimizzare il payoff ottenuto contro questa distribuzione
Se uno stato ` e il limite di una soluzione del sistema di equazioni differenziali ordinarie, allora tale stato ` e
necessariamente stazionario. Se accade che la traiettoria di
una soluzione della RE converge a qualche stato interno della
popolazione, allora questo stato limite appartiene a ∆
00e
quindi anche a ∆
NETheorem
Se x
0∈ int(∆) e ξ(t, x
0)
t→∞→ x, allora x ∈ ∆
NEDimostrazione.
Supponiamo che x
0∈ int(∆), ξ(t, x
0)
t→∞→ x ma x / ∈ ∆
NE. Allora esistono alcune strategie i ∈ K tali che π(e
i− x, x) = per alcuni > 0. Dato che ξ(t, x
0) → x e che π ` e continua, esistono alcuni T ∈ R tali che π(e
i− ξ(t, x
0), ξ(t, x
0)) > /2 ∀t ∈ T . Dalla (2.14) ˙ x
i= x
i/2 ∀t ∈ T , e quindi
ξ(t, x
0) > ξ(T , x
0) exp((t − T )/2) ∀t ≥ T , implica che
ξ
i(t, x
0) → ∞ (da ξ(T , x
0) > 0), una contraddice l’ipotesi. Quindi x ∈ ∆
NE.
In altre parole, uno stato x ∈ ∆ si dice raggiungibile se esiste
qualche stato interno a partire dal quale la soluzione converge a x .
Ogni stato raggiungibile x ∈ ∆ appartiene a ∆
NE.
Teorema. Se x
∗∈ S
N` e un NE del gioco descritto dalla matrice di payoff A, allora x
∗` e uno stato stazionario della RE (cio` e ˙ x
∗= 0). Inoltre, se x
∗` e Lyapunov stabile, allora ` e un NE del gioco.
Teorema. Se x
∗∈ S
N` e un ESS del gioco con matrice di payoff A, allora ` e uno stato stazionario asintoticamente stabile della RE.
Un esempio di stato stazionario asintoticamente stabile ma non ESS ` e rappresentato dall’equilibrio interno al simplesso S
3presente nel gioco descritto dalla matrice
A =
0 6 −4
−3 0 5
−1 3 0
Infatti nel gioco vi sono anche altre strategie ESS nel bordo.
Studiare la dinamica del gioco Falchi e Colombe generalizzato, descritto dalla matrice di payoff (dove C > G ):
A =
G −C
2
G
G (C −G )2C0
G2 G (C −G )2CG (G −C ) 2C
G (G +C ) 2C
G (C −G ) 2C