Teoria dei Giochi: lezione del 15 Maggio 2017: Strategie Evolutivamente Stabili

Teoria dei Giochi: lezione del 15 Maggio 2017:

Strategie Evolutivamente Stabili

Chiara Mocenni

Corso di Teoria dei Giochi e Giochi Evolutivi

Strategie Evolutivamente Stabili (ESS)

Una strategia si dice ESS se `e robusta rispetto a pressioni evolutive da parte di altre strategie

Si consideri una popolazione di individui indistinti e

programmati a giocare una determinata strategia pura o mista (strategia prevalente) nell’ambito di una serie ripetuta di giochi a due giocatori scelti a caso nella popolazione

Supponiamo di inserire nella popolazione un piccolo numero di individui che giocano un’altra strategia pura o mista

La strategia prevalente viene detta ESS se per ogni strategia mutante esiste una barriera di invasione tale che il numero di individui che gioca la strategia mutante rimane al di sotto di questa barriera in quanto la strategia prevalente fornisce sempre un payoff pi`u alto

Questo approccio considera interazioni simmetriche tra coppie di individui appartenenti ad una popolazione infinita

Il concetto di strategia evolutiva si basa sulla connessione che esiste tra i payoffs di un gioco e la diffusione di una

determinata strategia in una popolazione: i payoffs del gioco rappresentano il guadagno in termini di fitness biologica o di capacit`a riproduttiva derivante dall’interazione in questione Le strategie ESS generalizzano l’evoluzione biologica in senso darwiniano, cio`e l’idea della sopravvivenza di coloro che utilizzano strategie che forniscono una fitness pi`u alta delle altre possibili, e in cui la fitness stessa dipende dal

comportamento (dalle strategie) degli altri individui della popolazione

Analogamente all’equilibrio di Nash, la stabilit`a evolutiva non spiega come la popolazione `e arrivata ad adottare tale strategia

Il concetto di ESS pu`o essere utilizzato anche per spiegare la robustezza del comportamento umano in un’ampia gamma di situazioni, come l’ambito sociale ed economico

In questo caso, la stabilit`a evolutiva richiede che un piccolo gruppo di individui che tenta di utilizzare una strategia alternativa ottiene un risultato peggiore di coloro che adottano la strategia prevalente, i quali dunque non hanno motivo di cambiare il proprio comportamento

Una strategia ESS in questo contesto viene chiamata convenzione

Sia ˆx una strategia prevalente e x una strategia divergente che viene giocata con una probabilit`a 

La strategia mista giocata nella popolazione sar`a dunque

x + (1 − )ˆx

La strategia ˆx si dice evolutivamente stabile se per ogni strategia divergente x si ha che la disuguaglianza

x^TA(x + (1 − )ˆx) < ˆx^TA(x + (1 − )ˆx)

`

e verificata per ogni  > 0 inferiore ad un valore ¯(x) > 0, detto barriera di invasione

Riscriviamo la disuguaglianza come

(1 − )(ˆx^TAˆx − x^TAˆx) + (ˆx^TAx − x^TAx) > 0.

Facendo tendere  a 0, abbiamo che la strategia ˆx `e

evolutivamente stabile se sono verificate le due condizioni seguenti:

a Condizione di equilibrio

ˆx^TAˆx ≥ x^TAˆx, per ogni x ∈ S ; b Condizione di stabilit`a

se x 6= ˆx e ˆx^TAˆx = x^TAˆx, allora ˆx^TAx > x^TAx.

La strategia ˆx `e una best response a se stessa, ma questo fatto da solo non `e sufficiente a garantire la non invadibilit`a da parte di un’altra strategia, infatti nel caso dell’uguaglianza esiste una best response alternativa x

Va allora verificato che ˆx fornisce un payoff maggiore se giocata contro x di quanto ottenuto giocando x stessa.

Se una strategia `e un equilibrio di Nash stretto allora `e ESS Se una strategia `e ESS, allora `e un equilibrio di Nash

Theorem

Una strategia ˆx ∈ S `e ESS sse ˆ

x^TAy > y^TAy per ogni y 6= ˆx in qualche intorno di ˆx in S .

Da ci`o segue che se vi `e una strategia ESS nell’interno del simplesso S , allora questa `e unica. La dimostrazione di questo fatto `e nella slide successiva.

Si definisce supporto C (x ) di una strategia x l’insieme delle strategia pure a cui x assegna probabilit`a non nulla.

Sia ˆx una strategia ESS interna al simplesso. Supponiamo che esista un’altra strategia ESS y 6= ˆx tale che C (y ) ⊆ C (ˆx ). Allora y^TAˆx = ˆx^TAˆx (verificare).

Dalla condizione di stabilit`a delle strategie ESS segue che y<sup>T</sup>Ay < ˆx<sup>T</sup>Ay , dunque y non pu`o essere equilibrio di Nash e dunque non pu`o essere ESS.

Di conseguenza, se vi sono ESS multiple, esse devono appartenere alla frontiera di S . In particolare, se vi `e una strategia ESS interna al simplesso essa `e unica.

Esercizio 2. Verificare che nel gioco Falchi e Colombe, descritto dalla matrice di payoff:

A =

 _{G −C}

2 G

0 ^G₂



(1) l’unica strategia ESS `e ˆx = (G /C ,^{C −G}_C ), con C > G .

Per verificare questo fatto, calcoliamo ˆx^TAy , ˆx^TAˆx , y^TAˆx e y^TAy con y = (y , 1 − y ) generica.

ˆ

x^TAy = ^G₂(1 +^G_C − 2y ) ˆ

x^TAˆx = ^G₂(1 −^G_C) y^TAˆx = ^G₂(1 −^G_C) y^TAy =^G₂(1 −^G_Cy²)

ˆ

x `e Nash sse ˆx<sup>T</sup>Aˆx ≥ y<sup>T</sup>Aˆx , cio`e sse ^G₂(1 − ^G_C) ≥ ^G₂(1 −^G_C).

Vera nel caso non stretto.

Inoltre, ˆx `e ESS sse ˆx^TAy > y^TAy , ∀y 6= ˆx sse

G

2(1 +^G_C − 2y ) −^G₂(1 −^G_Cy²) > 0, ∀y 6= ˆx sse

G

Cy²− 2y +^G_C > 0∀y 6= ˆx , condizione verificata per ogni y 6= ^G₂.

Dunqe la strategia mista ˆx `e un equilibrio di Nash

evolutivamente stabile (ESS) per il gioco falchi e colombe.

Notiamo che ˆx `e anche l’unica strategia ESS e l’unico equilibrio di Nash.

Esercizio 3. Verificare che nel gioco descritto dalla matrice di payoff

A =





0 6 −4

−3 0 5

−1 3 0



 (2)

la strategia mista x = (1/3, 1/3, 1/3) non `e ESS. Sol. La strategia pura e<sub>1</sub> `e ESS.

Esercizio 4. Verificare la presenza di strategie pure e degli equilibri di Nash (misti e puri) nel gioco descritto dalla matrice di payoff:

A =





1 0 0

0 1 0

0 0 1



. (3)

Sol. Nel gioco vi sono 3 ESS (e1, e2, e3) e un NE misto.

Esercizio 5. Verificare la presenza di strategie pure e degli equilibri di Nash (misti e puri) nel gioco descritto dalla matrice di payoff:

A =





0 1 −1

−1 0 1

1 −1 0



. (4)

Sol. Nel gioco non vi sono ESS e vi `e un NE misto (1/3, 1/3, 1/3).

NE e ESS puri in giochi a 2 strategie

Nel gioco evolutivo a 2 strategie, descritto dalla matrice dei payoff A =

 a b c d

 , valgono le seguenti propriet`a.

La strategia s1 `e un equilibrio di Nash stretto se a > c;

La strategia s₁ `e un equilibrio di Nash se a ≥ c;

La strategia s₂ `e un equilibrio di Nash stretto se d > b;

La strategia s₂ `e un equilibrio di Nash se d ≥ b.

La strategia pura s₁ si dice evolutivamente stabile se a > c, oppure a = c e b > d .

Sotto queste condizioni la selezione si oppone all’invasione di s2 su s₁.

Nel caso pi`u generale di n strategie pure, sia π(ei, ej) il payoff della strategia e_i rispetto a e_j.

i Una strategia e_k `e un equilibrio di Nash stretto se π(ek, ek) > π(ei, ek), ∀i 6= k;

ii Una strategia e_k `e un equilibrio di Nash se π(ek, ek) ≥ π(ei, ek), ∀i 6= k.

iii Una strategia e_k `e evolutivamente stabile se

π(e_k, e_k) > π(ei, e_k), ∀i 6= k, oppure π(e_k, e_k) = π(ei, e_k) e π(e_k, e_i) > π(e_i, e_i) ∀i 6= k.

Strategie miste ESS

Gli equilibri di Nash misti non sono mai stretti. Dunque per questo tipo di strategie sar`a sempre necessario verificare la condizione di stabilit`a.

Classificazione delle strategie ESS nei giochi simmetrici a due strategie

Nella categorie I e IV, in cui i coefficienti a1 e a2 sono di segno opposto (ne `e un esempio il dilemma del prigioniero), Una delle due strategie domina l’altra, dunque esiste un unico equilibrio di Nash stretto, che dunque `e anche ESS

Nella categoria II, in cui a1 > 0 e a2 > 0, le due strategie pure sono equilibri di Nash stretti e dunque entrambi ESS, di conseguenza l’equilibrio di Nash interno non pu`o esserlo Nella categoria III (ne `e un esempio `e il gioco falchi e

colombe), invece, abbiamo un unico equilibrio di Nash interno.

Dunque in questo caso dobbiamo verificare la condizione di stabilit`a per poter stabilire se esso `e anche ESS. La risposta segue dalla soluzione dell’esercizio 2 proposto in precedenza