Dinamiche Evolutive ed Equilibri Correlati

83
POLITECNICO DI MILANO Scuola di Ingegneria dei Sistemi Dipartimento di Matematica ”F. Brioschi” Corso di Laurea Magistrale in Ingegneria Matematica Dinamiche Evolutive ed Equilibri Correlati Tesi di Laurea Magistrale in Ingegneria Matematica Relatore Candidata Prof. Roberto Lucchetti Benedetta Bizzarri Matricola 766743 Anno Accademico 2011-2012

Transcript of Dinamiche Evolutive ed Equilibri Correlati

Page 1: Dinamiche Evolutive ed Equilibri Correlati

POLITECNICO DI MILANO

Scuola di Ingegneria dei Sistemi

Dipartimento di Matematica ”F. Brioschi”

Corso di Laurea Magistrale in Ingegneria Matematica

Dinamiche Evolutive ed Equilibri Correlati

Tesi di Laurea Magistrale in Ingegneria Matematica

Relatore Candidata

Prof. Roberto Lucchetti Benedetta Bizzarri

Matricola 766743

Anno Accademico 2011-2012

Page 2: Dinamiche Evolutive ed Equilibri Correlati

Indice

Introduzione 6

1 Richiami 9

1.1 Strategie e Payoff . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1.1 Strategie Pure . . . . . . . . . . . . . . . . . . . . . . 9

1.1.2 Strategie Miste . . . . . . . . . . . . . . . . . . . . . . 10

1.1.3 Strategie Debolmente, Strettamente e Iterativamente

Dominate . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Equilibri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.1 Equilibri di Nash . . . . . . . . . . . . . . . . . . . . . 12

1.2.2 Equilibri Correlati . . . . . . . . . . . . . . . . . . . . 15

1.3 Giochi Simmetrici . . . . . . . . . . . . . . . . . . . . . . . . 18

1.3.1 Giochi Doppiamente Simmetrici . . . . . . . . . . . . 18

1.4 Classificazione dei Giochi Simmetrici 2x2 . . . . . . . . . . . 18

1.5 Sistemi Dinamici . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 Teoria Evolutiva Dei Giochi 24

2.1 Strategie Evolutivamente Stabili . . . . . . . . . . . . . . . . 24

2.1.1 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2 Dinamica di Gioco . . . . . . . . . . . . . . . . . . . . . . . . 30

2.2.1 Le Equazioni della Replicazione . . . . . . . . . . . . . 30

2.2.2 Dinamica ed ESS . . . . . . . . . . . . . . . . . . . . . 33

2.2.3 Dinamica e Strategie Strettamente Dominate . . . . . 39

2.2.4 Non convergenza . . . . . . . . . . . . . . . . . . . . . 43

2.3 Il Gioco Carta-Sasso-Forbice . . . . . . . . . . . . . . . . . . 45

2.4 Giochi Asimmetrici . . . . . . . . . . . . . . . . . . . . . . . . 50

2.4.1 Dinamica di Gioco Asimmetrica . . . . . . . . . . . . 52

3 Un’Applicazione 60

3.1 Il Modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2

Page 3: Dinamiche Evolutive ed Equilibri Correlati

INDICE 3

3.2 Dinamica della Replicazione ed ESS . . . . . . . . . . . . . . 63

3.3 Altre Dinamiche ed Esempi . . . . . . . . . . . . . . . . . . . 65

4 Dinamica ed Equilibri Correlati 67

4.1 Dinamica della Replicazione . . . . . . . . . . . . . . . . . . . 67

4.2 Altre Dinamiche . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.3 Giochi 2× 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.3.1 Giochi Asimmetrici . . . . . . . . . . . . . . . . . . . . 77

4.3.2 Giochi Simmetrici . . . . . . . . . . . . . . . . . . . . 78

Conclusioni 80

Bibliografia 81

Page 4: Dinamiche Evolutive ed Equilibri Correlati

Elenco delle figure

2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.2 ε < 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.3 ε < 1, k=0.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.4 ε < 1, k=2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.5 ε < 1, k=10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.6 ε = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.7 ε = 1, k=0.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.8 ε = 1, k=2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.9 ε = 1, k=10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.10 ε > 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.11 ε = 1, k=0.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.12 ε = 1, k=2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.13 ε = 1, k=10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.14 a12a21 ≤ 0 e b12b21 ≤ 0 . . . . . . . . . . . . . . . . . . . . . . 56

2.15 a12b12 > 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

2.16 a12b12 < 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.1 Caso 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.2 Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.3 Caso 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.4 Caso 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.5 Caso 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.6 Caso 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.1 ε = 23 , α = 0.01 . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.2 ε = 23 , α = 0.001 . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.3 ε = 45 , α = 0.01 . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.4 ε = 45 , α = 0.001 . . . . . . . . . . . . . . . . . . . . . . . . . 76

4

Page 5: Dinamiche Evolutive ed Equilibri Correlati

Sommario

In questa tesi viene studiata la teoria evolutiva dei giochi come connubio tra

teoria dei giochi classica e teoria dei sistemi dinamici. L’obiettivo e quello di

porre in relazione i concetti noti di equilibrio di Nash, equilibrio correlato e

strategia con quello di Strategia Evolutivamente Stabile, analizzando i giochi

non piu dal punto di vista della massimizzazione del payoff, ma da quello

della strategia piu conveniente per una specie nel lungo termine. In que-

sto senso l’introduzione di una dinamica evolutiva che rappresenti il gioco e

molto utile in quanto, grazie allo studio delle sue orbite, e possibile risalire

a quelle strategie che portano al raggiungimento di un equilibrio. Si concen-

tra l’attenzione in particolare sulla cosiddetta Dinamica della Replicazione,

suggerita dalla legge di selezione naturale, di cui si forniscono diversi esempi

anche numerici ottenuti con l’ambiente Matlab.

Abstract

In this work Evolutionary Game Theory is presented. We shall see how

this theory is a natural extension of classical game theory by adding some

dynamical systems’ tools. Our purpose is to present some new concepts, such

as Evolutionary Stable Strategies, and study their connection with classical

ones, such as strategies, correlated and Nash equilibria. An alternative

approach will be used: instead of reasoning by maximum payoffs, we will

look for those strategies which lead to what is best for the population of

players in the long run. The introduction of a dynamic to represent the

game it is found very useful since, by studying its orbits, it is possible to

find those strategies which lead to an equilibrium. We will focus especially

on the so-called Replication Dynamic, a particular dynamic suggested by the

natural selection law. Examples will be provided, some of them numerical,

obtained with the aid of Matlab.

Page 6: Dinamiche Evolutive ed Equilibri Correlati

Introduzione

La teoria evolutiva dei giochi e un’estensione della teoria dei giochi clas-

sica che studia il comportamento di vaste popolazioni di agenti che intera-

giscono ripetutamente in modo strategico. Essa infatti e nata nel 1973 dal

tentativo di John Maynard Smith e George R.Price in The logic of Animal

Conflict, [16], di modellizzare matematicamente i conflitti tra diversi ani-

mali di una o piu specie, introducendo il concetto fondamentale di Strategia

Evolutivamente Stabile o ESS. Successivamente, questo concetto e stato

formalizzato e ampliato da Maynard Smith in Evolution and the Theory of

Games nel 1982 ([15]), collegando strettamente la tematica a quella dell’e-

voluzione biologica.

Nella teoria dei giochi ‘classica’ si ipotizza che i giocatori siano razionali, in

grado cioe di valutare razionalmente le strategie a loro disposizione e di agire

di conseguenza, dando per scontato che anche l’avversario sia in grado di

fare le stesse valutazioni. Diversamente, la teoria evolutiva dei giochi non si

basa su queste ipotesi, in realta molto restrittive. Di fatto, essa assume che

i giocatori non solo non siano in grado di analizzare razionalmente il gioco,

ma addirittura potrebbero non essere consapevoli di partecipare. Da questa

caratteristica si intuisce quanto questa nuova teoria possa aderire al contesto

biologico, in quanto l’ipotesi di razionalita dei giocatori chiaramente non e

applicabile agli animali. E’ il caso, per esempio, del ‘gioco’ della selezione

naturale, in cui gli agenti sono i geni, e le strategie che portano ad un payoff

minore vengono usate via via con minore frequenza, secondo il principio del

darwinismo.

In generale, il cambiamento di comportamento di una popolazione e guidato

da una qualche ‘legge’ che indirizza all’utilizzo delle strategie piu proficue

dal punto di vista collettivo. A questo proposito, la teoria evolutiva si svi-

luppa su due piani: da un lato si hanno i concetti di equilibrio e strategie

propri della teoria dei giochi classica, rivisitati in chiave evolutiva; dall’altro

si ha una stretta connessione con la teoria dei sistemi dinamici che permette

di analizzare dal punto di vista strettamente matematico l’evoluzione nel

6

Page 7: Dinamiche Evolutive ed Equilibri Correlati

INTRODUZIONE 7

tempo della frequenza con cui una strategia viene utilizzata all’interno di

una popolazione. In questo senso esistono numerosi studi che considerano

sistemi dinamici differenti, piu o meno aderenti al problema da modellizzare.

Si vedano per esempio [12], [13] e [6].

Nonostante la teoria evolutiva dei giochi sia nata in un contesto specifico,

essa si e dimostrata utile in molti altri campi, quali quello economico e so-

ciale.

Nel primo capitolo riportiamo gli strumenti necessari per introdurre la teo-

ria evolutiva dei giochi: dapprima vengono ricordati i concetti fondamentali

della teoria dei giochi quali la definizione di gioco, le diverse tipologie di stra-

tegie ed equilibri, alcuni esempi importanti. Successivamente richiamiamo

brevemente alcune definizioni e proprieta principali della teoria dei sistemi

dinamici. Una particolare attenzione e posta sulla nozione di punto di equi-

librio e sulle condizioni di stabilita, stabilita asintotica e attrattivita. Uno

strumento molto importante ai fini dello studio della teoria evolutiva si ri-

velera essere il teorema di Lyapunov.

Nel secondo capitolo introduciamo la teoria evolutiva con il concetto chiave

di strategia evolutivamente stabile o ESS, dapprima concentrandoci sui gio-

chi simmetrici a due giocatori. Vengono forniti inoltre alcuni risultati che

mettono in relazione ESS ed equilibri di Nash. Proseguiamo poi addentran-

doci nel contesto dinamico delle cosiddette equazioni della replicazione e di

altre dinamiche che possono descrivere il gioco, fornendo risultati di equiva-

lenza tra i punti di equilibrio della dinamica ed equilibri di Nash del gioco.

Completiamo la teoria evolutiva per giochi simmetrici con l’analisi del gioco

Carta-Sasso-Forbice generalizzato. Concludiamo il capitolo estendendo tutti

i risultati al caso piu generale dei giochi asimmetrici a due giocatori, rilevan-

do alcune differenze rispetto al caso simmetrico. Particolare rilevanza ha il

fatto che, diversamente dal caso simmetrico, la relazione tra ESS e punti di

equilibrio asintoticamente stabili nella dinamica di gioco e di equivalenza.

Nel terzo capitolo viene studiato un esempio di applicazione della teoria evo-

lutiva dei giochi ad un contesto di tipo sociale: l’interazione tra immigrati di

uno stesso paese d’origine e cittadini del paese ospitante. Supponendo che

i primi possano adottare una strategia di integrazione, imparando l’idioma

del paese ospitante per esempio, oppure di indifferenza, ed i secondi possano

agire in modo accogliente oppure ostile, ogni incontro tra un immigrato ed

un cittadino si puo rappresentare come un gioco che, a seconda dei payoff

fissati, puo portare a punti di equilibrio diversi della dinamica di gioco.

Nel quarto capitolo, viene studiata la relazione tra ESS ed equilibri correlati.

In particolare, seguendo l’impronta di Viossat, [17], viene dimostrato che le

strategie nel supporto di un equilibrio correlato tendono ad essere abbando-

Page 8: Dinamiche Evolutive ed Equilibri Correlati

8 INTRODUZIONE

nate nel tempo, per una vasta classe di giochi 4 × 4 e diverse dinamiche di

gioco. Non e il caso pero dei giochi 2× 2 e 3× 3. La verifica viene fatta in

questo lavoro per i giochi 2× 2 sia nel caso simmetrico che asimmetrico, co-

me diretta conseguenza delle proprieta studiate di equilibri correlati e punti

di equilibrio della dinamica di gioco. Per quanto riguarda i giochi 3 × 3 si

rimanda a [19].

Si conclude con un capitolo riassuntivo dei risultati ottenuti, proponendo

possibili spunti per ulteriori studi ed approfondimenti.

Page 9: Dinamiche Evolutive ed Equilibri Correlati

Capitolo 1

Richiami

In questo capitolo vengono forniti gli strumenti della teoria dei giochi

classica indispensabili per la trattazione della teoria evolutiva. In particola-

re, definiremo il gioco discreto, finito, non cooperativo in forma normale, con

i relativi concetti di equilibrio di Nash, di equilibrio correlato e di funzioni

di risposta ottima (best reply). Introdurremo poi la particolare classe di

giochi simmetrici a due giocatori, e tutte le loro proprieta. Infine, forniremo

un breve richiamo sulla teoria dei sistemi dinamici.

1.1 Strategie e Payoff

1.1.1 Strategie Pure

Sia I = 1, . . . , n l’insieme dei giocatori, dove n e un intero positivo; per

ogni giocatore i ∈ I, indicheremo con σi il suo insieme (finito) di strategie

pure. Per semplicita, ogni strategia pura per il giocatore i verra indicata

con un numero intero, ovvero σi = 1, 2, . . . ,mi. Chiameremo profilo di

strategie pure un vettore s = (s1, . . . , sn), dove si e una strategia pura per

il giocatore i. Lo spazio delle strategie pure del gioco sara quindi dato da

σ =∏ni=1 σi. Per ogni profilo di strategie s ∈ σ il payoff o guadagno (in

strategie pure) del giocatore i ∈ I e una funzione πi(s) ∈ R, πi : σ → R.

La funzione di payoff del gioco e indicata con π(s) = (π1(s), . . . , πn(s)),

π : σ → Rn.

In possesso di questi elementi, possiamo dare la seguente

Definizione 1.1. Un gioco non cooperativo, in forma normale, e una terna

G = (I, σ, π).

9

Page 10: Dinamiche Evolutive ed Equilibri Correlati

10 CAPITOLO 1. RICHIAMI

Nel caso in cui n = 2, se i giocatori hanno a disposizione rispettivamente

m1 ed m2 strategie, possiamo rappresentare il payoff di entrambi come una

bimatrice P =(A,BT

)∈ Rm1×m2 dove A = (aij) = (π1(i, j)) e B = (bji) =

(π2(i, j)), per ogni i ∈ σ1 e j ∈ σ2. Il primo giocatore scegliera che riga

giocare, mentre il secondo scegliera la colonna.

Esempio 1.1 (Falchi e Colombe). In questo gioco i giocatori possono sce-

gliere se comportarsi in modo aggressivo, da Falco, o remissivo, cioe da

Colomba. La bimatrice dei payoff del gioco e:[((v − c)/2, (v − c)/2) (v, 0)

(0, v) (v/2, v/2)

]

Ritorneremo su questo gioco piu avanti.

1.1.2 Strategie Miste

Una strategia mista per il giocatore i e una distribuzione di probabilita

sul suo insieme di strategie pure σi. Dal momento che consideriamo solo

giochi discreti finiti, indicando con mi il numero di strategie pure per il

giocatore i (|σi| = mi), possiamo rappresentare ogni sua strategia mista x

come vettore in Rmi , dove la componente xh ∈ R e la probabilita con cui

il giocatore i gioca la strategia pura h. E importante notare il fatto che∑mih=1 xh = 1 e che xh ∈ [0, 1] per ogni h = 1, . . . ,mi; pertanto l’insieme

delle possibili strategie miste per il giocatore i e il simplesso unitario, mi

dimensionale

Smi = x = (x1, . . . , xmi) ∈ [0, 1]mi |∑

xh = 1.

Osserviamo che i vertici del simplesso Smi sono i vettori unitari ei1 =

(1, 0, . . . , 0) , . . . , eimi = (0, 0, . . . , 1), che sono le strategie pure o particolari

strategie miste che assegnano probabilita 1 alla strategia pura h.

D’ora in avanti concentreremo l’attenzione sui giochi a due giocatori,

I = 1, 2.Se indichiamo con u1(ek,x) il payoff che il giocatore 1 ottiene usando la

strategia mista x contro la strategia pura k del giocatore 2, allora il valore

atteso del payoff per il giocatore 1 che gioca una strategia mista x ∈ Sm1 ,

contro la strategia mista y per il secondo, e

u1(x,y) =

m1∑k=1

u1(ek,x)yk y ∈ Sm2 . (1.1)

Page 11: Dinamiche Evolutive ed Equilibri Correlati

1.1. STRATEGIE E PAYOFF 11

In altre parole, u1(x,y) e calcolato come somma pesata dei payoff che il

giocatore 1 ottiene contro ogni strategia pura giocata dal giocatore 2, dove

i pesi sono le probabilita assegnate dalla strategia mista di quest’ultimo.

Inoltre, e importante notare che dall’equazione (1.1) risulta che u1(x) e

lineare in y ∈ Sm2 . In generale, u1(x,y) verra semplicemente chiamato

payoff della strategia mista x e tutto cio vale analogamente per il giocatore

2.

Se i payoff sono lineari, dato un gioco rappresentato dalla bimatrice P =

(A,B), se i giocatori giocano rispettivamente le strategie miste x ∈ Sm1 e

y ∈ Sm2 , i loro guadagni attesi sono

u1(x,y) =∑i

xi∑j

aijyj = xTAy

per il primo e

u2(x,y) =∑i

xi∑j

bijyj = xTBy = yTBTx

per il secondo.

Si ha dunque la seguente estensione del gioco alle strategie miste:

Definizione 1.2. L’estensione mista di un gioco non cooperativo, in forma

normale, e una terna G = (I,Θ, u) dove Θ = Sm1 × Sm2 e lo spazio delle

strategie miste del gioco e u(x) = (u1(x,y), u2(x,y)) e la funzione di payoff

in strategie miste del gioco.

1.1.3 Strategie Debolmente, Strettamente e Iterativamente

Dominate

Definizione 1.3. Una strategia yi ∈ Smi , i = 1, 2:

• domina debolmente una strategia xi ∈ Smi se ui(yi, zj) ≥ ui(xi, zj) ∀zj ∈Smj , con disuguaglianza stretta per qualche z ∈ Smj ;

• domina strettamente xi ∈ Smi se ui(yi, zj) > ui(xi, zj) ∀z ∈ Smj .

Una strategia xi ∈ Smi e non dominata se non esiste una strategia yi ∈ Smiche la domina (debolmente o strettamente).

E’ possibile che una strategia pura sia strettamente dominata da una

strategia mista, pur non essendo dominata da alcuna strategia pura.

Un assioma di razionalita alla base della teoria dei giochi presuppone che i

giocatori siano razionali, nel senso che non usano mai strategie strettamente

Page 12: Dinamiche Evolutive ed Equilibri Correlati

12 CAPITOLO 1. RICHIAMI

dominate. Pertanto, tutte le strategie pure strettamente dominate possono

essere eliminate dal gioco senza che il risultato venga alterato. Questo pro-

cedimento si puo iterare un numero finito di volte, poiche al gioco partecipa

un numero finito di giocatori con un numero finito di strategie.

Esempio 1.2. Consideriamo il gioco rappresentato dalla bimatrice(3, 1) (4, 1) (6, 3)

(2, 5) (1, 3) (1, 8)

(7, 3) (0, 0) (1, 4)

.Supponiamo che il giocatore A giochi le righe ed il giocatore B giochi le

colonne. Per A, la strategia 1 (giocare la prima riga) domina strettamente

la strategia 2. Analogamente, per il giocatore B la strategia 3 (giocare la

terza colonna) domina strettamente la strategia 2. Eliminando le strategie

strettamente dominate si perviene alla seguente bimatrice, equivalente a

quella di partenza: [(3, 1) (6, 3)

(7, 3) (1, 4)

].

Ripetendo il ragionamento, si possono eliminare anche la prima strategia per

B e la seconda strategia per A, ottenendo l’equilibrio di Nash in strategie

pure (nel gioco originale) (e1, e3) con payoff (6, 3).

Definizione 1.4. Una strategia pura si ∈ σi, i = 1, 2 e non iterativamente

strettamente dominata se non e strettamente dominata nel gioco origina-

le G, ne nel gioco G1 ottenuto eliminando da G alcune(o tutte) le strate-

gie strettamente dominate, ne nel gioco G2 ottenuto eliminando le strategie

strettamente dominate da G1 e cosı via, finche non vi siano piu strategie che

possano essere eliminate (cioe finche Gk+1 = Gk per un intero positivo k).

1.2 Equilibri

1.2.1 Equilibri di Nash

Un equilibrio di Nash e un profilo di strategie (pure o miste) x =

(x1, . . . , xn) tale che, se ogni giocatore i gioca la rispettiva strategia xi,

allora nessuno ha interesse a deviare.

Nel caso di un gioco a due giocatori si ha la seguente definizione:

Definizione 1.5. Un equilibrio di Nash per il gioco non cooperativo, in

forma normale, a due giocatori G = (Sn, Sm, u1 : Sn × Sm → R, u2 : Sn ×Sm → R) e una coppia di strategie (x, y) ∈ Sn × Sm tale che

u1(x, y) ≥ u1(x, y) ∀x ∈ Sn;

Page 13: Dinamiche Evolutive ed Equilibri Correlati

1.2. EQUILIBRI 13

u2(x, y) ≥ u2(x,y) ∀ y ∈ Sm.

In particolare, se entrambe sono disuguaglianze strette per x 6= x, y 6= y,

l’equilibrio di Nash e detto stretto.

Osserviamo che, sotto l’ipotesi di razionalita dei giocatori, se per esempio

il giocatore 1 pensasse che il giocatore 2 usi la strategia y, allora cerchereb-

be di massimizzare la sua funzione di utilita x 7→ u1(x,y), ovvero vorrebbe

scegliere la strategia x ∈ BR1(y) = x ∈ Sn : u1(x,y) ≥ u1(s,y)∀s ∈ Sn.Seguendo lo stesso ragionamento per il giocatore 2 risultano definite le multi-

funzioni di risposta ottima (best reaction) BR1 : Sm → Sn e BR2 : Sn → Sm. Sia ora BR : Sn × Sm → Sm × Sn, definita come

BR(x, y) = (BR1(y), BR2(x)) .

Allora

Definizione 1.6. Un equilibrio di Nash per il gioco G = (Sn, Sm, u1 : Sn ×Sm → R, u2 : Sn × Sm → R) e un punto fisso per BR, cioe (x, y) e un

equilibrio di Nash se e solo se

(x, y) ∈ BR(x, y).

Proposizione 1.1. Un equilibrio di Nash stretto e necessariamente una

coppia di strategie pure.

Dimostrazione. Dato un equilibrio di Nash in strategie miste (x,y), per

almeno uno dei giocatori esisterebbero almeno due strategie pure che portano

allo stesso payoff massimo, violando almeno una delle disuguaglianze strette

della Definizione (1.5).

Osserviamo che non tutti i giochi hanno equilibri in strategie pure.

Esempio 1.3. Consideriamo il gioco delle monete: due bambini, ciascuno

con una moneta, devono mostrarla nello stesso momento, decidendo se tenere

in alto testa o croce. Se entrambi mostrano la stessa faccia, vince il primo

bambino, altrimenti vince il secondo.

La bimatrice dei payoff e pertanto[(1,−1) (−1, 1)

(−1, 1) (1,−1)

].

Chiaramente non esistono equilibri di Nash in strategie pure, infatti per qual-

siasi profilo di strategie pure, uno dei due giocatori vorrebbe deviare. Tutta-

via esiste un equilibrio di Nash in strategie miste: (x,y) =([

12 ,

12

],[

12 ,

12

]).

Page 14: Dinamiche Evolutive ed Equilibri Correlati

14 CAPITOLO 1. RICHIAMI

Si puo dimostrare che nei giochi discreti esiste sempre almeno un equi-

librio di Nash in strategie miste; a questo scopo occorrono alcuni richiami:

Definizione 1.7. Sia Z un sottospazio compatto e convesso di uno spazio

Eucliedeo e Φ : Z → Z. Il grafico di Φ e l’insieme (x, y) : y ∈ F (x).

Definizione 1.8. Una funzione h : Z → R, dove Z e un insieme convesso,

si dice quasi convessa se l’insieme x : h(z) ≥ a e convesso per ogni a.

A questo punto un teorema di punto fisso garantisce l’esistenza di un

equilibrio di Nash; in particolare useremo il teorema di Kakutani.

Teorema 1.2 (di Kakutani). Sia Z un sottoinsieme compatto e convesso

di uno spazio Euclideo e sia F : Z → Z tale che

• F (z) e un insieme non vuoto, chiuso e convesso per ogni z;

• il grafico di F e chiuso.

Allora F ha punto fisso: esiste z ∈ Z tale che z ∈ F (z).

Grazie a questi strumenti e ora possibile dimostrare il seguente

Teorema 1.3 (di Nash). Dato il gioco G = (Sn, Sm, u1 : Sn× Sm → R, u2 :

Sn×Sm → R), supponiamo che Sn e Sm siano sottoinsiemi convessi e com-

patti di qualche spazio euclideo; supponiamo inoltre che u1, u2 siano funzioni

continue e che

• x 7→ u1(x,y) sia quasi concava per ogni y ∈ Sm;

• y 7→ u2(x,y) sia quasi concava per ogni x ∈ Sn.

Allora esiste un equilibrio per il gioco.

Dimostrazione. Proviamo che BR1(y) e un insieme chiuso, non vuoto e

convesso per ogni y. Analogamente cio puo essere fatto per BR2(x), da cui

segue la validita delle affermazioni per BR.

BR1(y) e un insieme non vuoto dal momento che u1(x,y),funzione continua,

e massimizzata su Sn, insieme compatto. Per il teorema di Weierstrass,

infatti, segue che esiste almeno un punto di massimo. Inoltre, per l’ipotesi

di quasi concavita di u1 segue che l’insieme dei punti di massimo BR1 e

convesso. Infine, supponiamo che xn ∈ BR1(y) e che xn → x; perche

BR1 sia chiuso dobbiamo verificare che x ∈ BR1(y). Dal momento che

xn ∈ BR1(y), u1(xn,y) ≥ u1(x,y)∀x; essendo u1 continua per ipotesi,

possiamo passare al limite ottenendo u1(x,y) ≥ u1(x,y)∀x in virtu del

Page 15: Dinamiche Evolutive ed Equilibri Correlati

1.2. EQUILIBRI 15

teorema di permanenza del segno, ovvero x ∈ BR1(y).

Vogliamo ora dimostrare che BR1 ha grafico chiuso. Seguendo la procedura

gia utilizzata, supponiamo che la coppia (xn,yn) appartenga al grafico di

BR1 e che (xn,yn) → (x, y); bisogna ora vedere che (x, y) appartiene al

grafico di BR1.

Deve valere u1(xn,yn) ≥ u1(x,yn)∀x; passando al limite e utilizzando il

teorema di permanenza del segno si ha u1(x, y) ≥ u1(x, y)∀x ma cio e vero

solo se x ∈ BR1(y) cioe la coppia (x, y) appartiene al grafico di BR1.

A questo punto, dal teorema di Kakutani, segue la tesi.

1.2.2 Equilibri Correlati

Ci concentreremo ora sui giochi finiti, in forma strategica, a due gio-

catori. Definiremo il concetto di equilibrio correlato, una generalizzazione

del concetto di equilibrio di Nash introdotta da Aumann nel 1974. L’idea

e che sia possibile per i giocatori di accordarsi su un certo piano di azione,

con un accordo che non sia vincolante per rimanere nell’ambito dei giochi

non cooperativi. Ogni giocatore infatti sceglie la sua azione a seguito del-

l’osservazione di un segnale fornito da un ‘mediatore affidabile’, sulla base

del quale egli valuta strategicamente anche i segnali che gli altri giocatori

potrebbero aver ricevuto, ed agisce di conseguenza.

Una soluzione e un equilibrio correlato se ogni giocatore ritiene conveniente

non deviare dalla strategia suggerita dal mediatore sotto l’ipotesi fonda-

mentale di razionalita dei giocatori, ovvero che nessuno abbia motivo di

deviare.

Diamo ora una definizione formale:

Definizione 1.9. Dato il gioco G = (Sn, Sm, u1, u2), dove u1, u2 : Sn ×Sm → R, Sn = (x1, . . . ,xn) e Sm = (y1, . . . ,ym),una distribuzione di equili-

bri correlati o, piu semplicemente, un equilibrio correlato e una distribuzione

di probabilita µ su Sn × Sm tale che, detta µij la probabilita assegnata alla

coppia (xi,yj), ∀i ∈ 1, . . . , n si ha che

m∑j=1

µiju1(xi,yj) ≥m∑j=1

µiju1(xi,yj) ∀i ∈ 1, . . . , n (1.2)

e ∀j ∈ 1, . . . ,m

n∑i=1

µiju2(xi,yj) ≥n∑i=1

µiju2(xi,yj) ∀j ∈ 1, . . . ,m (1.3)

Page 16: Dinamiche Evolutive ed Equilibri Correlati

16 CAPITOLO 1. RICHIAMI

Definizione 1.10. Una strategia pura i e usata in un equilibrio correlato

se esiste un equilibrio correlato µ tale che esista una strategia pura j per la

quale µ(i, j) > 0.

Per chiarire il significato della definizione 1.9 dividiamo a destra e a

sinistra della (1.2) per la quantita∑m

j=1 µij (analogamente dividiamo per∑ni=1 µij la (1.3)):

m∑j=1

µij∑mj=1 µij

u1(xi,yj) ≥m∑j=1

µij∑mj=1 µij

u1(xi,yj).

La quantita a sinistra della disequazione e, infatti, il payoff atteso del primo

giocatore che sa di dover giocare la strategia i, mentre quella a destra e il

payoff atteso del primo giocatore nel caso in cui non giochi la strategia i (di-

scorso analogo per il secondo giocatore). E’ chiaro quindi che le disequazioni

riflettono le condizioni per l’equilibrio di Nash.

Un equilibrio correlato e dunque un vettore che soddisfa un certo numero

di disequazioni lineari, quindi l’insieme degli equilibri correlati e convesso

e compatto in un certo spazio Euclideo. Inoltre risulta essere non vuoto:

ogni equilibrio di Nash e infatti un equilibrio correlato e, dal momento che

esiste sempre un equilibrio di Nash (in strategie miste) per la classe di giochi

considerata, l’insieme degli equilibri correlati e non vuoto.

Esempio 1.4 (Semaforo). Due automobili giungono in prossimita di un

incrocio con semaforo rotto. Entrambe devono decidere se passare o dare

la precedenza. Nel caso in cui entrambe decidano di passare, ha luogo un

incidente, che per entrambe le automobili si traduce in un payoff negativo

−100. Se una decide di dare la precedenza e l’altra passa, la prima ottiene 0

e la seconda guadagna 1. Infine, se entrambe decidono di fermarsi, ottengono

un payoff −1. La matrice dei payoff e[(−100,−100) (1, 0)

(0, 1) (−1,−1)

]Ci sono due equilibri di Nash in strategie pure: (e1, e2) e (e2, e1), con valore

atteso 1 per chi passa e 0 per chi si ferma (la loro somma e 1). Vi e inoltre

un equilibrio di Nash in strategie miste (x,x) dove x =(

151 ,

5051

), con valore

atteso per entrambi −850867 .

Se il semaforo viene riparato, si ha ora un mediatore affidabile che fa passare

meta delle volte un’automobile e meta l’altra. Si verifica facilmente che[0 1/2

1/2 0

]

Page 17: Dinamiche Evolutive ed Equilibri Correlati

1.2. EQUILIBRI 17

e un equilibrio correlato, che assicura ad entrambi il valore atteso 12 (e somma

anch’esso ad 1).

Teorema 1.4. Se un gioco finito a n giocatori ha un unico equilibrio cor-

relato σ, allora l’(unico) equilibrio correlato di ogni gioco in un suo intorno

ha lo stesso supporto di σ.

Per una prova di questo teorema, si rimanda a [19].

Osservazione 1.1. Sugli equilibri correlati esiste uno studio sperimentale

condotto da Timothy N. Cason e Tridib Sharma (si veda [2]), i quali hanno

messo a confronto diversi giocatori in un gioco la cui matrice dei payoff era[(3, 3) (48, 9)

(9, 48) (39, 39)

]. (1.4)

Considerando i payoff in termini monetari, e stato riscontrato che molto

spesso i giocatori sono portati a deviare dalla strategia proposta, pur essen-

do a conoscenza degli svantaggi. Per spiegare questo fenomeno, gli autori

hanno posto i giocatori davanti ad un computer come avversario, conside-

rando anche una variante del gioco in cui i guadagni del computer venivano

trasferiti ad un individuo esterno al gioco. La ragione di questa variante e

quella di capire se la scelta di deviare e dettata da una funzione di utilita in

cui la preferenza e minimizzare la differenza tra il payoff dell’avversario e il

proprio piuttosto che massimizzare il proprio. Il risultato e stato che, con-

tro un avversario non ‘umano’, cioe perfettamente razionale, i giocatori non

hanno deviato dalla strategia suggerita, indipendentemente da chi ottenesse

il guadagno del computer.

Gli autori hanno concluso che la causa di questo comportamento potrebbe

essere che i giocatori non si ‘fidano’ della razionalita degli avversari e, di

conseguenza, tentano di prevedere in che modo essi devieranno, deviando

loro stessi dalla strategia suggerita. Tuttavia e stato riscontrato che i gioca-

tori con piu esperienza tendono a seguire le raccomandazioni piu degli altri,

quindi e ragionevole supporre che col tempo essi arriveranno all’equilibrio

correlato.

Gli autori hanno potuto fornire solo congetture per spiegare questo feno-

meno, una delle quali ipotizza che gli individui meno esperti, pur essendo

razionali, suppongano che gli avversari possano in realta commettere degli

errori di valutazione nella scelta della strategia. Man mano che il gioco

viene ripetuto, ogni giocatore modifica la sua percezione dell’avversario in

base al sue azioni e di conseguenza diventa sempre piu propenso a seguire

le indicazioni.

Page 18: Dinamiche Evolutive ed Equilibri Correlati

18 CAPITOLO 1. RICHIAMI

1.3 Giochi Simmetrici

In molte applicazioni della teoria dei giochi evolutivi i giocatori vengono

considerati indistinguibili, motivo per cui e utile introdurre la particolare

classe di giochi simmetrici:

Definizione 1.11. Un gioco non cooperativo G = (I, σ, π),a due giocatori,

in forma normale e simmetrico se I = 1, 2, σ1 = σ2 = K e π2(s1, s2) =

π1(s2, s1) per ogni (s1, s2) ∈ σ.

La simmetria del gioco implica che, se U indica la matrice dei payoff del

giocatore 1 e V quella del giocatore 2, allora V = UT .

Definizione 1.12. Un equilibrio di Nash (x,y) si dice simmetrico se x = y,

cioe se i due giocatori utilizzano la stessa strategia.

Osservazione 1.2. Un gioco simmetrico non ha necessariamente solo equi-

libri simmetrici, tuttavia esiste sempre un equilibrio simmetrico nelle stra-

tegie miste. Per convincersene basta applicare il teorema di Kakutani a

BR1(= BR2).

La definizione di equilibrio correlato vale ovviamente anche per la ca-

tegoria dei giochi simmetrici. Notiamo inoltre che, se µ e un equilibrio

correlato per un gioco a due giocatori simmetrico, lo e anche µT (definito da

µT (i, j) = µ(j, i)), e quindi anche µ+µT

2 . Pertanto, se una strategia e usata in

un equilibrio correlato, e usata anche in un equilibrio correlato simmetrico.

1.3.1 Giochi Doppiamente Simmetrici

Un caso piu specifico di giochi simmetrici si ha quando i due gioca-

tori hanno uguale successo o insuccesso. In tal caso si parla di giochi

doppiamente simmetrici.

Definizione 1.13. Un gioco simmetrico a due giocatori e doppiamente

simmetrico se la matrice dei payoff U = UT .

1.4 Classificazione dei Giochi Simmetrici 2x2

In questa sezione consideriamo giochi simmetrici a due giocatori, in cui

ogni giocatori ha esattamente due strategie pure. La trattazione tornera

utile piu avanti per fornire esempi.

Per prima cosa enunciamo una proprieta di invarianza:

Page 19: Dinamiche Evolutive ed Equilibri Correlati

1.4. CLASSIFICAZIONE DEI GIOCHI SIMMETRICI 2X2 19

Proposizione 1.5. Dati due giochi G = (I, σ, π) e G′ = (I, σ, π′), se per

ogni giocatore i ∈ I esiste λi ∈ R+ ed µi ∈ R tali che π′i(s, t) = λiπi(s, t)+µiper ogni profilo di strategie s ∈ σ, allora i due giochi sono equivalenti1.

Dimostrazione. Concentriamoci sul giocatore 1, il discorso per il secondo e

analogo. Supponiamo che la coppia (s, t) sia un equilibrio di Nash per G,

cioe

π1(s, t) ≥ π1(s, t) ∀s.

Vogliamo verificare che questa coppia di strategie sia un equilibrio di Nash

anche per il gioco G′, ma cio e immediato infatti

π′1(s, t) ≥ π′1(s, t) ∀s⇔ λ1π1(s, t) + µ1 ≥ λ1π1(s, t) + µ1 ∀s,

che e banalmente verificata.

Consideriamo ora un qualsiasi gioco simmetrico 2x2 con matrice dei

payoff

A =

[a11 a12

a21 a22

].

In virtu della proposizione (1.5), e possibile sottrarre alla prima colonna la

quantita a21 ed alla seconda a12, ottenendo la matrice equivalente

A′ =

[a11 − a21 0

0 a22 − a12

].

Abbiamo cosı ottenuto un gioco doppiamente simmetrico con matrice dei

payoff

A′ =

[a1 0

0 a2

]dove a1 = a11 − a21 e a2 = a22 − a12. In questo modo possiamo identificare

ogni gioco simmetrico come un punto nel piano a = (a1, a2) ∈ <2 ed, in base

alla posizione, classificarlo.

• Categoria I: a1 ≤ 0, a2 > 0 o a1 < 0, a2 ≥ 0

La seconda riga domina strettamente la prima, la seconda colonna do-

mina strettamente la prima: si ha un unico equilibrio di Nash (e2, e2)

con payoff a2. E’ speculare alla categoria IV, di cui forniremo un

esempio molto noto.

1Due giochi sono equivalenti se hanno gli stessi equilibri (ma non necessariamente gli

stessi payoff).

Page 20: Dinamiche Evolutive ed Equilibri Correlati

20 CAPITOLO 1. RICHIAMI

• Categoria II: a1 > 0, a2 > 0

Vi sono due equilibri di Nash (simmetrici e stretti) in strategie pure:

(e1, e1) e (e2, e2). Vi e inoltre un equilibrio (simmetrico) in strate-

gie miste (x,x) con x =[

a2a1+a2

, a1a1+a2

]. Un esempio e il Gioco di

Coordinazione che ha matrice dei payoff[2 0

0 1

].

• Categoria III: a1 < 0, a2 < 0

Vi sono due equilibri di Nash in strategie pure, questa volta asim-

metrici, (e1, e2) e (e2, e1), ed un equilibrio (simmetrico) in strategie

miste (x,x), dove x e la stessa della categoria II. Un esempio e quel-

lo di Falchi e Colombe: i due giocatori possono decidere di usare una

strategia aggressiva (falco) o remissiva (colomba). Se un falco incontra

una colomba, vince lo scontro guadagnando v mentre la colomba non

guadagna nulla. Se un falco si scontra con un altro falco, puo vince-

re (v) o perdere (c) con uguale probabilita: il payoff medio e quindi

(v − c)/2 < 0. Se una colomba incontra un’altra colomba, infine, lo

scontro si risolve in modo pacifico, con payoff v/2. La matrice dei

payoff e [(v − c)/2 v

0 v/2

].

• Categoria IV: a1 ≥ 0, a2 < 0 o a1 > 0, a2 ≤ 0

E’ il caso speculare alla categoria I: vi e un unico equilibrio di Nash

(e1, e1) con payoff a1 . Un esempio di questa categoria e il dilemma

del prigioniero: due ladri complici vengono catturati, se entrambi con-

fessano il furto la pena e di 3 anni di carcere ciascuno, se solo uno dei

due confessa, chi confessa viene rilasciato e l’altro sconta una pena di

5 anni, se nessuno dei due confessa, sconteranno ciascuno 1 anno di

carcere. La matrice dei payoff e quindi[−3 0

−5 −1

].

1.5 Sistemi Dinamici

In questo capitolo vengono riportate alcune nozioni sui sistemi dinamici

fondamentali per la trattazione successiva.

Page 21: Dinamiche Evolutive ed Equilibri Correlati

1.5. SISTEMI DINAMICI 21

Definizione 1.14. Dati uno spazio vettoriale E ed un insieme aperto W ⊂E, un sistema dinamico e una coppia (W,ψ), dove ψ : J ×W → W , con

J intervallo di <, e un’applicazione differenziabile che verifica le seguenti

proprieta:

1. ∃t0 ∈ J tale che ψ(t0,x) = x,

2. ψ(t+ s,x) = ψ(t, ψ(s,x)).

Per l’ipotesi di differenziabilita, e possibile definire un campo vettoriale

f(x) ≡ d

dtψ(t,x)|t=t0 (1.5)

per ogni x ∈W e per qualche t0 ∈ J fissato; se poniamo x(t) = ψ(t,x), sot-

tolineando la sola dipendenza dal tempo della ψ, la (1.5) puo essere riscritta

come

x ≡ dx

dt= f(x).

Definizione 1.15. Dato un sistema dinamico x = f(x), un punto di equili-

brio z e tale che f(z) = 0.

Definizione 1.16. Un punto di equilibrio z di un sistema dinamico x = f(x)

e

• stabile, se per ogni intorno U di z, esiste un altro intorno W, tale che

ogni soluzione che parte in W rimane in U;

• attrattivo, se esiste un intorno W di z, tale che ogni soluzione che

parte in W converge verso z;

• asintoticamente stabile, se e stabile e attrattivo;

• globalmente stabile, se tutte le soluzioni che partono nell’insieme di

definizione del sistema convergono a z;

• instabile, se non e stabile.

Definizione 1.17. Sia x = f(x) un sistema dinamico con punto di equili-

brio z. Sia J la matrice Jacobiana di f calcolata in z. Le parti reali degli

autovalori di J si chiamano esponenti di Lyapunov.

Il calcolo degli esponenti di Lyapunov in corrispondenza di un punto di

equilibrio permette di ottenere informazioni sulla sua stabilita.

Teorema 1.6. Il punto di equilibrio z e:

Page 22: Dinamiche Evolutive ed Equilibri Correlati

22 CAPITOLO 1. RICHIAMI

• asintoticamente stabile se tutti gli esponenti di Lyapunov sono negativi

(pozzo);

• instabile se tutti gli esponenti di Lyapunov sono positivi (sorgente) o

se sono uno positivo e l’altro negativo (sella);

Definizione 1.18. Una funzione V definita e di classe C1 in un intorno U

di un punto di equilibrio z si dice funzione di Lyapunov per z se valgono le

condizioni:

• V (x) = dV (x(t))dt ≤ 0

• V (z) = 0 e V (x) > 0 ∀x 6= z ∈ U

Se la prima condizione vale col segno di disuguaglianza stretta, V e una

funzione di Lyapunov stretta.

Teorema 1.7 (di Lyapunov). Dato un punto di equilibrio z di un sistema

dinamico x = f(x), se esiste una funzione di Lyapunov V per z, allora z

e un punto di equilibrio stabile. Se V e una funzione di Lyapunov stretta,

allora V e asintoticamente stabile.

Teorema 1.8 (di esistenza ed unicita locale). Sia f : D → Rk con D aperto,

D ⊂ Rk+1. Se:

(i) f e continua in D.

(ii) f = f(t,x) e localmente lipschitziana in D, rispetto a z ed uniforme-

mente in t (ovvero esiste una costante L tale che ‖f(t,x)− f(t,y)‖ ≤L ‖x− y‖ per ogni coppia di punti (t,x) ∈ D e (t, z) in un intorno di

(t,x) ).

Allora, per ogni punto (τ, ξ) ∈ D esiste un intorno Iδ di τ , Iδ = [τ−δ, τ+δ],

nel quale e definita un’unica soluzione Φ(·, ξ) : Iδ → D. Tale soluzione

e unica nel senso che ogni altra soluzione coincide con Φ nell’intervallo

comune di definizione.

Lemma 1.9 (di Gronwall). Sia I = [a, b) ⊂ R un intervallo tale che a ∈ Re b ∈ R ∪ ∞. Siano inoltre u, v : I → R due funzioni continue in I e non

negative. Se u e derivabile in I e soddisfa

u(t) ≤ |v(t)u(t)| ∀t ∈ I

allora

u(t) ≤ u(a)exp |∫ t

av(s)ds | ∀t ∈ I

.

Page 23: Dinamiche Evolutive ed Equilibri Correlati

1.5. SISTEMI DINAMICI 23

Definizione 1.19. L’orbita passante per un punto x0 e data dall’insiemex : ∃t ∈ R,x = Φ

(t,x0

).

Le orbite di un sistema dinamico possono essere di tre tipi:

1. ridotte ad un solo punto (equilibrio);

2. curve regolari chiuse (orbite periodiche);

3. orbite aperte senza punti di intersezione.

Proposizione 1.10. Sia dato un sistema dinamico

xi = fi(x1, . . . , xn).

Sia W (x1, . . . , xn) una funzione positiva sull’insieme di definizione del si-

stema dinamico. Allora quest’ultimo ammette le stesse orbite del sistema

xi = fi(x1, . . . , xn)W (x1, . . . , xn)

Definizione 1.20. Dato un campo vettoriale f, continuo e differenziabile,

definito su X ⊂ Rn, la divergenza di f nel punto x ∈ X e

div(f(x)) =

n∑i=1

∂fi∂xi

(x),

cioe e la traccia dello Jacobiano di f.

Forti di questa definizione, riportiamo un risultato molto utile:

Proposizione 1.11. Se l’insieme X e aperto e f ∈ C1(X), con div(f(x)) ≥0 per ogni x ∈ X, allora il sistema dinamico x = f(x) non ammette punti di

equilibrio asintoticamente stabili.

Page 24: Dinamiche Evolutive ed Equilibri Correlati

Capitolo 2

Teoria Evolutiva Dei Giochi

La teoria dei giochi evolutiva e nata come applicazione della teoria dei

giochi alla biologia, grazie all’introduzione alla nozione di strategia evoluti-

vamente stabile (ESS) da parte di John Maynard Smith in ‘Evolution and

the Theory of Games’, [15]. Diversamente dalla teoria classica, in cui i gioca-

tori sono ritenuti perfettamente razionali e giocano una volta sola, in questo

contesto si considera una popolazione dalla quale vengono ripetutamente

scelti dei giocatori ‘programmati’ ad utilizzare una specifica strategia. A

modificare la frequenza con cui ciascuna strategia viene giocata e un qual-

che processo evolutivo, su cui i giocatori non hanno nessuna influenza e di

cui non sono a conoscenza. Tipicamente, una strategia viene considerata

una caratteristica genetica dell’individuo, il cui payoff e determinato in base

alla capacita riproduttiva dello stesso. In molti contesti, la teoria dei giochi

evolutiva risulta essere piu accreditata di quella classica, sostituendo all’i-

potesi molto stringente di razionalita dei giocatori il concetto di stabilita

evolutiva, e fornendo una scala unidimensionale di guadagno come successo

riproduttivo, al posto di una piuttosto soggettiva funzione di utilita dei gio-

catori.

2.1 Strategie Evolutivamente Stabili

Un concetto-chiave nella teoria evolutiva e quello di strategia evoluti-

vamente stabile. Con esso si intende che una strategia e resistente alla

pressione evolutiva che deriva dalla ripetizione di un gioco non cooperativo,

discreto e finito, a due giocatori. Una particolare importanza hanno i giochi

simmetrici, ai quali d’ora in poi faremo riferimento.

Il contesto e dunque quello di una popolazione sufficientemente vasta, in

24

Page 25: Dinamiche Evolutive ed Equilibri Correlati

2.1. STRATEGIE EVOLUTIVAMENTE STABILI 25

cui ogni individuo e ‘programmato’ geneticamente ad utilizzare una certa

strategia S, pura o mista, e dalla quale vengono ripetutamente scelti due

giocatori che si affrontano nel gioco, dove per gioco intendiamo un modello

matematico di interazione strategica dove i risultati delle azioni degli indi-

vidui dipendono dalle azioni degli altri.

Supponiamo ora che vi sia una mutazione, ovvero una piccola percentuale

della popolazione sia ora programmata all’utilizzo di una strategia diversa

M. La strategia S sara quindi detta evolutivamente stabile se, per ogni pos-

sibile strategia mutante M, esiste una soglia di popolazione, la cosiddetta

barriera di invasione, tale che, se la percentuale di individui che giocano la

strategia M e minore, allora S ottiene un payoff migliore di M.

Questo approccio e focalizzato su interazioni simmetriche tra coppie di gio-

catori di un’unica popolazione. Inoltre vi e una stretta correlazione implicita

tra payoff e diffusione di una strategia tra la popolazione: secondo un’inter-

pretazione biologica il payoff misura il guadagno della fitness di un individuo.

E’ importante ricordare che, come la nozione di equilibrio di Nash, la pro-

prieta di stabilita evolutiva non specifica come la popolazione arrivi a sele-

zionare una tale strategia, ma permette solo di riconoscerla come tale, una

volta che ci si arriva.

Oltre al campo biologico, la stabilita evolutiva risulta un criterio note-

volmente robusto anche per quanto riguarda i comportamenti umani, per

esempio nelle interazioni nel campo economico o sociale. In tali contesti,

la stabilita evolutiva richiede che ogni piccolo gruppo che prova una stra-

tegia alternativa ottenga risultati peggiori di chi si attiene allo status quo.

Si potrebbe quindi pensare ad una strategia evolutivamente stabile come

convenzione.

Come abbiamo detto, la teoria evolutiva ha come scenario i giochi non

cooperativi, discreti, simmetrici, con strategie pure che appartengono all’in-

sieme K = R1, ...,Rn. Le strategie miste sono invece i punti del simplesso

Sn.

Denotando con m ∈ Sn la strategia media della popolazione, il guadagno

atteso di una strategia p ∈ Sn sara pTAm. Per esempio, se una frazione ε

della popolazione gioca la strategia q ed il resto gioca p, m = εq + (1− ε)p.

La seguente definizione formalizza il concetto si stabilita evolutiva:

Definizione 2.1. Una strategia p ∈ Sn e evolutivamente stabile (ESS) se,

per ogni q 6= p ∈ Sn esiste ε(q) ∈ (0, 1) tale che vale

qTA (εq + (1− ε)p) < pTA (εq + (1− ε)p) (2.1)

per ogni ε : 0 < ε < ε(q) .

Page 26: Dinamiche Evolutive ed Equilibri Correlati

26 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

In poche parole, cio significa che se p viene adottata da una popolazione

di giocatori, non puo essere invasa da alcuna strategia alternativa che sia

inizialmente rara.

Proposizione 2.1. Una strategia p ∈ Sn e ESS se e solo se

qTAp ≤ pTAp,∀q ∈ Sn (2.2)

qTAp = pTAp⇒ qTAq < pTAq,∀q 6= p ∈ Sn (2.3)

Dimostrazione. Se si scrive la (2.1) come

(1− ε)(pTAp− qTAp

)+ ε(pTAq − qTAq

)> 0

si vede subito che vale solo se sono verificate le condizioni (2.2) e (2.3).

Proposizione 2.2. Ogni equilibrio di Nash stretto e ESS. Ogni ESS e

equilibrio di Nash.

Dimostrazione. Un equilibrio di Nash e stretto se vale

qTAp < pTAp ∀q ∈ Sn

ovvero se e solo se vale la (2.2) strettamente.

La (2.2) esprime esattamente il fatto che (p,p) e un equilibrio simmetrico

di Nash.

Osserviamo che il contrario della prima affermazione non e vero: basti

pensare ad una ESS in strategie miste, essa non puo essere equilibrio di Nash

stretto dal momento che un equilibrio di Nash stretto e necessariamente in

strategie pure.

Esempio 2.1. Consideriamo il gioco con matrice dei payoff

A =

[3 6

4 5

].

Ricorrendo alla classificazione dei giochi 2 × 2 della sezione 1.4, possiamo

immediatamente identificare due equilibri di Nash in strategie pure anti-

simmetrici, (e1, e2) e (e2, e1), ed un equilibrio in strategie miste (p,p) con

p = (1/2, 1/2). Si verifica immediatamente che p e ESS, infatti, dalla 2.2),

pTAp = 9/2 > qTAp = 5/2 ∀q ∈ Sn.

La strategia p e pertanto ESS ma il corrispondente equilibrio di Nash

simmetrico non puo essere stretto, essendo in strategie miste.

Page 27: Dinamiche Evolutive ed Equilibri Correlati

2.1. STRATEGIE EVOLUTIVAMENTE STABILI 27

Per fare un esempio, invece, di ESS pura ma che non sia equilibrio stretto,

basta considerare un qualsiasi gioco con matrice dei payoff del tipo[x x

x y

]

con x > y. Infatti si verifica facilmente che la strategia p = e1 = [1, 0]T e

ESS, ma non e equilibrio stretto.

Per un esempio in cui non valga la seconda affermazione, rimandiamo agli

esempi.

Proposizione 2.3. Se p ∈ intSn e ESS, allora e l’unica ESS.

Dimostrazione. Ponendo q = ei nella (2.2) si ha

(Ap)i ≤ pTAp (2.4)

per i = 1, . . . , n. Moltiplicando (Ap)i per pT e utilizzando la definizione di

prodotto scalare

pTAp =∑pi>0

pi (Ap)i ≤

∑pi>0

pi

pTAp = pTAp

Quindi, per gli indici tali che pi > 0 deve valere l’uguaglianza in (2.4). Dal

momento che pTAp e una costante a priori incognita, che possiamo indicare

con c, si ottiene che (Ap)i ≤ c per tutti gli i, con l’uguaglianza dove pi > 0.

Se p ∈ intSn le sue componenti sono tutte non nulle, allora p soddisfa le

condizione d’equilibrio se e solo se le sue componenti soddisfano il sistema(Ap)1 = . . . = (Ap)n = c

p1 + . . .+ pn = 1.

Infine, ∀q ∈ Sn, qTAp = pTAp quindi deve necessariamente valere la condi-

zione di stabilita (2.3) per ogni q 6= p. Allora, se esistesse q 6= p ∈ Sn ESS,

dal momento che la (2.2) varrebbe col segno di uguaglianza, si dovrebbe

avere qTAp > pTAp che non puo essere verificata poiche p ∈ intSn.

Proposizione 2.4. p ∈ Sn e una ESS se e solo se

pTAx > xTAx (2.5)

per ogni x 6= p in qualche intorno di p.

Page 28: Dinamiche Evolutive ed Equilibri Correlati

28 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Dimostrazione. Vediamo che se p e ESS allora la (2.5) e verificata. Sce-

gliendo appropriatamente q per esempio all’interno del compatto C :=

q ∈ Sn| qi = 0 per qualche i ∈ supp(p), l’unione delle facce del sim-

plesso che non contengono p, possiamo scrivere i punti vicini a p come

x = εq + (1− ε) p, per un opportuno ε. Dal momento che q ∈ C, vale la

definizione di ESS 2.1 per ogni ε < ε(q). Per provare che vale la (2.5) bi-

sogna trovare un ε indipendente da q, per cui la disequazione sia verificata.

Si puo definire ε(q) come funzione continua, per esempio

ε(q) =

(p−q)TAp

(p−q)TA(p−q)se (p− q)T Aq < 0,

1 altrimenti.

Grazie al teorema di Weierstrass, si puo concludere che esiste ε :=

min ε(q)|q ∈ C. Moltiplicando la (2.1) per ε < ε ed aggiungendo (1− ε) pTA (εq + (1− ε) p)

ad entrambi i membri, si trova, riarrangiando i termini(εqT + (1− ε) pT

)︸ ︷︷ ︸xT

A (εq + (1− ε) p)︸ ︷︷ ︸x

< pTA (εq + (1− ε) p)︸ ︷︷ ︸x

.

Facendo variare ε ∈ (0, ε) , si ottiene la (2.5) in un intorno di p.

Per l’implicazione inversa, il ragionamento e simile: per ogni q ∈ Sn,

basta scegliere un x vicino a p come combinazione convessa di q e p, per

un opportuno ε. Con questa scelta, per quanto visto, la 2.1 e la (2.5) sono

equivalenti.

Proposizione 2.5. Se p ∈ Sn e una strategia debolmente dominata, allora

non puo essere ESS.

Dimostrazione. Supponiamo che p sia un equilibrio di Nash, debolmente

dominato da un’altra strategia q ∈ Sn. Allora q e una best reply alternativa

a p (pTAp = qTAp), e per la dominanza debole qTAq ≥ pTAq, cioe p non

e ESS.

2.1.1 Esempi

Esempio 2.2. Qualsiasi gioco che abbia matrice dei payoff antisimmetrica, 0 x −x−x 0 x

x −x 0

Page 29: Dinamiche Evolutive ed Equilibri Correlati

2.1. STRATEGIE EVOLUTIVAMENTE STABILI 29

ha un equilibrio di Nash p =(

13 ,

13 ,

13

), ma si verifica facilmente che que-

sto non puo essere ESS perche prendendo, per esempio, q = e1, si ha,

considerando la (2.1),

0 = eT1 Ap ≤ pTAp = 0.

Deve valere allora la (2.2), ma si ha

0 = eT1 Ae1 < pTAe1 = 0

ovvero la condizione di stabilita non e verificata. Il gioco quindi non ha ESS.

L’esempio piu conosciuto di giochi con matrice dei payoff di questo tipo e

sasso-carta-forbice: 0 1 −1

−1 0 1

1 −1 0

Esempio 2.3. Seguendo l’impronta della sezione 1.4, vediamo per quali

categorie di giochi simmetrici 2x2 esistono una, piu o nessuna ESS.

• Categoria I e IV: Abbiamo visto che in questa categoria ricadono i

giochi tipo Dilemma del Prigioniero, per i quali vi e un unico equilibrio

di Nash stretto. In virtu della proposizione 2.2 possiamo concludere

che esso e l’unica ESS per questa categoria.

• Categoria II: Per questa categoria, esistono due equilibri di Nash che

sono stretti e quindi sono ESS. Tuttavia, esiste anche un equilibrio di

Nash in strategie miste (x,x) ∈ intS2. Pertanto, per la proposizione

2.3, x non puo essere ESS, altrimenti dovrebbe essere l’unica.

• Categoria III: In questo caso i due equilibri di Nash in strategie pure

non sono stretti. Inoltre, dopo qualche verifica, risulta che (x,x) e ESS

e, dal momento che (x,x) ∈ intS2, e l’unica.

Tornando al caso specifico di Falchi e Colombe, la cui matrice dei

payoff e [(v − c)/2 v

0 v/2

]si trova facilmente che, seguendo la notazione della sezione 1.4, a1 =

(v − c)/2 e a2 = −v/2, quindi x =(

a2a1+a2

, a1a1+a2

)=(vc ,

c−vc

), dove il

primo termine e la probabilita di giocare la strategia Falco, o meglio,

la frequenza di Falchi nella popolazione, ed il secondo quella delle

Colombe. (x,x) e una ESS, infatti

xTAy− yTAy =(v − cy1)2

2c> 0 ∀y1 6=

v

c.

Page 30: Dinamiche Evolutive ed Equilibri Correlati

30 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Cerchiamo di capire il senso che in questo gioco assume il concetto di

ESS: se la frequenza dei Falchi e minore di v/c, allora questa e la stra-

tegia mutante, ovvero i pochi Falchi della popolazione si scontrano piu

spesso contro le Colombe che coi loro simili, ottenendo un payoff mag-

giore e quindi un successo maggiore come strategia. A questo punto

la frequenza dei Falchi cresce, essendo la strategia migliore, fino ad un

punto in cui sono le Colombe ad essere rare ed i Falchi molto frequenti.

Dal momento che per un Falco e piu dispendioso in media affrontare

uno scontro con un altro Falco di quanto lo sia per una Colomba in-

contrare un Falco ((v − c)/2 < 0), e ora la strategia della Colomba a

diffondersi come piu conveniente. In questo senso, in corrispondenza

della ESS questa oscillazione non si verifica, ovvero nessuna delle due

strategie puo essere invasa dall’altra.

2.2 Dinamica di Gioco

In generale, un processo evolutivo e una combinazione di due elementi:

un meccanismo di mutazione che introduce varieta, e un meccanismo di

selezione che predilige certe varieta ad altre. Il criterio di stabilita evolutiva

ha a che fare con il ruolo delle mutazioni, mentre le dinamiche di replicazione

con quello della selezione.

La teoria evolutiva dei giochi studia la dinamica del gioco modellandola con

equazioni differenziali sul simplesso Sn.

2.2.1 Le Equazioni della Replicazione

Consideriamo una popolazione vasta che dispone di n strategie E1, . . . ,En

pure o miste, sia ai(t) il numero di individui che utilizza la strategia Ei.

Supponiamo che a(t) =∑

i ai(t) ≥ 0 sia il numero totale di individui della

popolazione.

Definizione 2.2. Lo stato della popolazione e un vettore x = (x1, . . . , xn),

in cui ogni componente xi(t) = ai(t)a(t) e la frazione di individui che utilizza la

strategia corrispondente, ovvero la frequenza della strategia.

Definizione 2.3. Una strategia i e eliminata (per qualche stato iniziale

x(0)) se xi(t)→ 0 per t→∞.

Chiaramente∑

i xi(t) = 1 ∀t, quindi x ∈ Sn.

Supponiamo che la popolazione sia sufficientemente vasta e che vi sia un

Page 31: Dinamiche Evolutive ed Equilibri Correlati

2.2. DINAMICA DI GIOCO 31

passaggio sufficientemente veloce tra una generazione e l’altra; allora pos-

siamo assumere che lo stato della popolazione x(t) evolva come funzione

differenziabile del tempo in Sn. Il rapporto xi/xi e il tasso di crescita della

strategia Ei e quindi misura il suo successo evolutivo. Possiamo suppor-

re che questo successo possa essere espresso in termini della differenza tra

il guadagno fi(x) della strategia Ei e il guadagno medio della popolazio-

ne f(x) =∑xifi(x), imitando il meccanismo della selezione naturale: si

ottengono le cosiddette equazioni della replicazione

xi = xi(fi(x)− f(x)

)i = 1 . . . n. (2.6)

I replicatori sono le strategie, le quali vengono copiate identiche di genera-

zione in generazione. Cio che puo cambiare e lo stato della popolazione.

Osservazione 2.1. La frazione di popolazione ‘programmata’ ad usare una

certa strategia cresce nella dinamica della replicazione solo se la strategia

guadagna un payoff maggiore di quello medio attuale della popolazione.

Proposizione 2.6. Il simplesso Sn, il suo interno intSn e il suo bordo ∂Snsono invarianti rispetto alle equazioni della replicazione (2.6).

Dimostrazione. • invarianza di ∂Sn: ∂Sn e dato dall’insieme x ∈ Sn|∃i, xi =

0; se ∃t|i(t) = 0, allora xi = 0∀t in base alle (2.6).

• invarianza di Sn: per prima cosa osserviamo che l’insieme H = x ∈<n|

∑xi = 1 e invariante. Infatti, se x ∈ H,

d

dt

∑xi =

∑xi =

∑xifi(x)−

1︷ ︸︸ ︷(∑xi

) f(x)︷ ︸︸ ︷∑xjfj(x) = 0

Notiamo inoltre che Sn = H ∩ Rn+. Vogliamo dimostrare che ogni

soluzione che parta nel simplesso, non ne esce: se per assurdo non

fosse vero, esisterebbero ξ ∈ Sn ed un tempo t, tali che la soluzione

Φ(t, ξ) /∈ Sn (ma Φ(t, ξ) ∈ H dal momento che H e invariante). Questa

soluzione dovrebbe quindi attraversare il bordo di Sn; supponendo che

f sia lipschitziana, possiamo applicare il teorema di esistenza ed uni-

cita, il quale garantisce che Φ sia soluzione unica delle equazioni della

replicazione e che sia continua in t. Per continuita, dunque, dovreb-

bero esistere un tempo s < t ed una strategia i, tali che Φi(s, ξ) = 0 e

Φi(t, ξ) < 0. Cio e assurdo in virtu del fatto che abbiamo ottenuto una

soluzione Φ(t, ξ) : < → Rn passante per Φi(s, ξ), distinta da quella con

la i-esima coordinata costantemente pari a 0, violando l’unicita.

Page 32: Dinamiche Evolutive ed Equilibri Correlati

32 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

• invarianza di intSn: ripetendo lo stesso ragionamento, si vede subito

che un punto che parte all’interno del simplesso, non puo raggiungere

il bordo altrimenti si avrebbero due soluzioni distinte passanti per uno

stesso punto sul bordo, violando l’unicita.

Grazie a questo risultato, possiamo d’ora in avanti considerare solo la

restrizione delle (2.6) al simplesso Sn.

Osservazione 2.2. Esistono altre dinamiche, oltre quella della replicazione,

che si basano su ipotesi diverse. In particolare segnaliamo le dinamiche

di imitazione, di risposta ottima e correzione. Introduciamo brevemente

le prime due, la terza verra approfondita in seguito. Per un discorso piu

approfondito, si faccia riferimento a [7],[12] e [14].

Dinamica di Imitazione

In molti contesti, per esempio per quanto riguarda le interazioni sociali

tra giocatori umani, le strategie che ottengono piu successo si diffondono

attraverso l’imitazione piu che per ereditarieta.

Supponiamo quindi che occasionalmente venga scelto a caso un giocatore

dalla popolazione, e che gli venga offerta l’opportunita di cambiare la sua

strategia. Egli quindi sceglie casualmente un altro giocatore, di cui adottare

la strategia con una certa probabilita.

Un possibile modello potrebbe essere il seguente:

xi = xi∑j

[fij(x)− fji(x)]xj ,

dove

fij(x) = f ((Ax)i, (Ax)j)

definisce una regola di imitazione, identica per ogni giocatore ed indipenden-

te da i e j. Ovviamente, diverse scelte di f definiscono diverse dinamiche.

Una scelta abbastanza naturale potrebbe essere quella di imitare una stra-

tegia migliore della propria, cioe f(u, v) = 0 se u < v e f(u, v) = 1 se

u > v.

Dinamica di Risposta Ottima

Consideriamo generazioni discrete di individui ed assumiamo che ad ogni

generazione subentri un nuovo giocatore, razionale, in grado di valutare ed

Page 33: Dinamiche Evolutive ed Equilibri Correlati

2.2. DINAMICA DI GIOCO 33

adottare come strategia la risposta ottima allo stato corrente della popola-

zione. Pertanto, alla generazione k+1, il nuovo arrivato sceglie una strategia

rk+1 ∈ E1, . . . ,En che massimizzi il suo payoff atteso contro la strategia

media (o stato) della popolazione sk = 1k

∑ki=1 ri. Il nuovo giocatore uti-

lizzera la strategia rk+1 per il resto del gioco. La strategia media viene

modificata nel modo seguente:

sk+1 − sk =rk+1 − skk + 1

,

con rk+1 ∈ β(sk), l’insieme delle risposte ottime contro la strategia sk ∈ Sn,

cioe

β(x) = y ∈ SN : yTAx = maxz∈SN

zTAx. (2.7)

Passando da generazioni discrete a continue, dopo alcune considerazioni si

perviene alla dinamica di risposta ottima

x = β(x)− x.

2.2.2 Dinamica ed ESS

Torniamo al contesto iniziale: consideriamo un gioco G in cui una po-

polazione dispone di N strategie pure R1, . . . ,RN , vertici del simplesso

SN ; tutte le strategie per questo gioco (pure e miste) sono indicate con

E1, . . . ,En ∈ SN dove N ≤ n. Indichiamo con U ∈ RN×N la matrice dei

payoff e con x, vettore di n componenti (i.e. x ∈ Sn), lo stato della popola-

zione nel gioco G. Costruendo una matrice A ∈ Rn×n con, come componenti,

i payoff di una strategia i contro una strategia j (i.e. aij = ETi UEj ), si puo

considerare un nuovo gioco G nel quale A e la matrice dei payoff e per il

quale E1, . . . , En possono essere considerate strategie pure, mentre le com-

ponenti dello stato della popolazione x = (x1, . . . , xn) per G diventano le

strategie miste per G. Osserviamo inoltre che

fi(x) = ETi U∑j

xjEj =∑j

ETi UEjxj =

∑j

aijxj = (Ax)i .

Con questa notazione, quindi, le equazioni della replicazione diventano

xi = xi((Ax)i − xTAx

). (2.8)

I punti di equilibrio per (2.8) saranno quei punti z = (z1, . . . , zn) ∈ Sn tali

che (Az)i = zTAz = c per ogni zi > 0.

Page 34: Dinamiche Evolutive ed Equilibri Correlati

34 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Osservazione 2.3. In seguito, salvo diverse indicazioni, la condizione ini-

ziale per la dinamica della replicazione sara del tipo

x(0) = x ∈ intSn

perche altrimenti, per l’invarianza di ∂Sn, troveremmo soltanto soluzioni sul

bordo del simplesso.

Ricapitolando, vi e un parallelismo tra le strategie pure R1, . . . ,RN ,

punti di SN , e matrice dei payoff U di dimensione N ×N da una parte e i

‘tipi di giocatori’ E1, . . . ,En, punti di Sn, e matrice dei guadagni attesi A

di dimensione n× n dall’altra.

Definizione 2.4. x ∈ Sn e equilibrio di Nash (simmetrico) per G se

yTAx ≤ xTAx ∀x ∈ Sn.

Definizione 2.5. Uno stato x ∈ Sn e evolutivamente stabile se valgono

yTAx ≤ xTAx ∀y ∈ Sn (2.9)

yTAx = xTAx⇒ yTAy < xTAy ∀y 6= x ∈ Sn, (2.10)

ovvero x ∈ Sn e uno stato evolutivamente stabile per G se e ESS per G.

Esempio 2.4. Riprendiamo l’esempio di Falchi e Colombe: vi sono due

strategie pure, E1 = (1, 0) ed E2 = (0, 1), e due giocatori, la matrice di

payoff e

U =

[(v − c)/2 v

0 v/2

].

Vogliamo scrivere le equazioni della replicazione: chiamiamo x1 e x2 rispet-

tivamente le frequenze di E1 ed E2. Dal momento che, per questo gioco,

n = 2 e quindi x2 = 1 − x1, il sistema della replicazione si riduce alla sola

equazione per x1:

x1 = x1(1− x1)((Ax)1 − (Ax)2)

ed in questo caso (x1 = x)

x =1

2x(1− x)(v − cx).

Come abbiamo gia visto, la strategia(vc ,

c−vc

)e una ESS per il gioco. No-

tiamo, inoltre, che il punto x = vc e di equilibrio per l’equazione della repli-

cazione, e asintoticamente stabile dal momento che lo Jacobiano e negativo,

Page 35: Dinamiche Evolutive ed Equilibri Correlati

2.2. DINAMICA DI GIOCO 35

ed un teorema che vedremo in seguito garantisce addirittura che sia global-

mente stabile.

Supponiamo ora che, alle due strategie pure, si aggiunga una terza strategia

mista, ovvero una terza razza che si comporti a volte come un falco, a volte

come una colomba: E3 = xE1 + (1− x)E2 =(vc ,

c−vv

).

Costruiamo la matrice dei payoff A:

A =

ET1 UE1 ET

1 UE2 ET1 UE3

ET2 UE1 ET

2 UE2 ET2 UE3

ET3 UE1 ET

3 UE2 ET3 UE3

=

v−c

2 v v(c−v)2c

0 v2

v(c−v)2c

v(c−v)2c

v(c+v)2c

v(c−v)2c

e osserviamo che E3 e ESS nel gioco originale e per questo non puo essere

invasa da E1 o E2. Tuttavia, lo stato corrispondente e3 = (0, 0, 1) non e

evolutivamente stabile.

Ricordiamo che, ripetendo il ragionamento della dimostrazione della

proposizione 2.3, le condizioni perche x sia ESS per G diventano

(Ax)i < xTAx ∀i t.c. xi = 0 (2.11)

(Ax)i = xTAx ∀i t.c. xi > 0 (2.12)

Teorema 2.7. Valgono le seguenti proprieta:

1. Se z e un equilibrio di Nash per G, allora e punto di equilibrio per

(2.8);

2. Se z e un punto di equilibrio stabile per (2.8), allora e equilibrio di

Nash per G;

3. Se z e un punto limite di un’orbita interna per (2.8) ( cioe ∃ξ 6= z ∈intSn tale che limt→∞Φ(t, ξ) = z), allora e un equilibrio di Nash per

G.

4. Se z e uno stato evolutivamente stabile per G (ovvero e ESS per G),

allora e un punto di equilibrio asintoticamente stabile per (2.8).

Dimostrazione. 1. Se z e equilibrio di Nash allora verifica (Az)i = zTAz ∀jtale che zj > 0, quindi annulla la parte destra di (2.8) ovvero e punto

di equilibrio per il sistema.

2. Supponiamo per assurdo che z sia un punto di equilibrio stabile per il

sistema, ma che non sia un equilibrio di Nash per G.

Essendo punto di equilibrio del sistema, z soddisfa (Az)i = zTAz ∀j

Page 36: Dinamiche Evolutive ed Equilibri Correlati

36 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

tale che zj > 0, ma non essendo equilibrio di Nash deve necessariamen-

te esistere un indice i tale che zi = 0 e (Az)i > zTAz (cioe e violata

la condizione (2.3) ). Per continuita esiste dunque un δ = δ(z) tale

che in un intorno I di z (Ay)i − yTAy ≥ δ ∀y ∈ I. Una qualsiasi

soluzione y(t) del sistema (2.8) con y(0) ∈ I allora soddisfa

yi(t) = yi(t)((Ay)i − yTAy

)≥ yi(t)δ ∀t > 0 t.c. y(t) ∈ I.

Applicando il lemma di Gronwall con v(t) = δ otteniamo

y(t) ≥ y(0)eδt ∀t > 0 t.c. y(t) ∈ I,

ovvero qualsiasi soluzione del sistema che parta in I, si allontana da z

con velocita esponenziale, in contraddizione con la nozione di equilibrio

stabile.

3. Come per il punto precedente procediamo per assurdo: supponiamo

che ∃ξ 6= z ∈ intSn, tale che limt→∞Φ(t, ξ) = z ma che ∃i tale che

zi = 0 e (Az)i > zTAz, cioe z non sia un equilibrio di Nash. Come

prima, deve esistere δ = δ(z) tale che, in corrispondenza della strategia

i, (Az)i − zTAz > δ. Dal momento che per ipotesi Φ(t, ξ) → z, esiste

un certo tempo t tale che,

(AΦ)i − ΦTAΦ > δ/2 ∀t ≥ t

cioe

Φi(t, ξ) > Φi(t, ξ)δ

2∀t ≥ t.

Applicando il lemma di Gronwall con v(t) = δ2 , risulta

Φ(t, ξ) > Φ(t, ξ)eδ2

(t−t) ∀t ≥ t,

ma, dal momento che Φ(t, ξ) > 0, si avrebbe Φ(t, ξ)→∞, in contrad-

dizione con l’ipotesi di partenza su z.

4. Supponiamo che z sia uno stato evolutivamente stabile; vogliamo usare

il teorema di Lyapunov per dimostrare che e un punto di equilibrio

asintoticamente stabile. La funzione

V (x) =∏zi>0

zzii −∏zi>0

xzii ,

risulta infatti essere una funzione di Lyapunov per z:

Page 37: Dinamiche Evolutive ed Equilibri Correlati

2.2. DINAMICA DI GIOCO 37

• V (z) = 0

• V (x) > 0 per x 6= z in un intorno di z, infatti,

V (x) > 0⇔∏zi>0

xzii <∏zi>0

zzii ⇔ log

(∏zi>0

xzii

)< log

(∏zi>0

zzii

)

che equivale a ∑zi>0

zi log

(xizi

)< 0.

Quest’ultima disuguaglianza e verificata, come si puo vedere sfrut-

tando la stretta concavita del logaritmo e la disuguaglianza di

Jensen: ∑zi>0

zi log

(xizi

)≤ log

(∑zi>0

zixizi

)= log 1 = 0

dove l’uguaglianza si ha solo nel caso in cui xi = zi per i =

1, . . . , n.

• V (x) < 0 ∀x 6= z, in un intorno di z: per verificarlo e sufficiente

dimostrare che P (x) > 0 in un intorno di z, dove

P := −V +∏zi>0

zzii =∏zi>0

xzii ,

poiche il termine∏zi>0 z

zii e costante rispetto a x e pertanto le

derivate di V e P differiscono solo per il segno. Notiamo che P e

una funzione non negativa, dunque limitiamo lo studio del segno

della derivata agli x ∈ x|xi > 0 ∀i t.c. zi > 0:

P (x) = Pd logP

dt= P

d

dt

∑zi>0

zi log xi =

= P∑zi>0

zixixi

= P∑zi>0

zi((Ax)i)− xTAx

)= P

(zTAx− xTAx

).

Dal momento che z per ipotesi e uno stato evolutivamente stabile,

per ogni x 6= z, questa quantita risulta positiva, di conseguenza

V (x) e negativa.

Abbiamo verificato quindi che V (x) e funzione di Lyapunov per z, in

particolare essa risulta essere di Lyapunov stretta, dunque applicando

il teorema risulta che z e asintoticamente stabile per (2.8).

Page 38: Dinamiche Evolutive ed Equilibri Correlati

38 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Esempio 2.5. Consideriamo il gioco con matrice dei payoff[6 4

5 7

].

Gli equilibri di Nash (simmetrici) sono (e1, e1), (e2, e2), stretti, e

(p,p) := ([3/4, 1/4] , [3/4, 1/4]) ∈ intSn. In virtu dei teoremi 2.2 e 2.3,

possiamo immediatamente concludere che e1 ed e2 sono ESS, mentre p non

lo e. Dal teorema precedente, ci aspettiamo che e1, e2 e p siano punti di

equilibrio per la dinamica della replicazione e che, in particolare, le due ESS

siano asintoticamente stabili nella dinamica della replicazione.

L’equazione della replicazione risulta

x = x(−4x2 + 7x− 3),

la cui parte destra si annulla per x = 1, 0, 3/4, come previsto. Calcolando

gli esponenti di Lyapunov, si trova

x = 1→ λ = −1 < 0

x = 0→ λ = −3 < 0

x = 3/4→ λ = 3/4 > 0

Pertanto, grazie al teorema 1.6, possiamo concludere che effettivamente

le due ESS sono asintoticamente stabili nella dinamica della replicazione.

Invece la strategia p risulta essere instabile.

Osservazione 2.4. Il viceversa della prima affermazione vale solo se z ∈intSn. Infatti, in quel caso zi 6= 0 per ogni i ed essendo z punto di equilibrio

(Az)1 = . . . = (Az)n, quindi z e equilibrio di Nash. Invece, se z ∈ ∂Sn,

esiste un indice i tale che zi = 0, ma il fatto che z sia punto di equilibrio

non esclude che possa verificarsi che (Az)i > zTAz, quindi z potrebbe non

essere equilibrio di Nash.

Esempio 2.6. Un esempio che mostra che non e verificato il viceversa della

quarta affermazione del teorema 2.7, ovvero di punto di equilibrio asintoti-

camente stabile che non sia evolutivamente stabile, si ottiene considerando

la matrice

A =

0 6 −4

−3 0 5

−1 3 0

.Per questo gioco, vi sono due equilibri di Nash (simmetrici): e1 = (1, 0, 0)

e m =(

13 ,

13 ,

13

). Ricordando che x3 = 1 − x1 − x2, le equazioni della

Page 39: Dinamiche Evolutive ed Equilibri Correlati

2.2. DINAMICA DI GIOCO 39

replicazione sono:

x1 = x1(−5x21 + 8x2

2 + 9x1 + 2x2 − 4)

x2 = x2(−5x21 + 8x2

2 − 3x1 − 13x2 + 5)

Il punto m e di equilibrio per il sistema della replicazione; inoltre gli espo-

nenti di Lyapunov del sistema risultano avere parte reale negativa: −13±√

23 i.

Ne segue che m e un pozzo e quindi e asintoticamente stabile.

Tuttavia e immediato verificare che e1 e ESS; cio esclude la possibilita che

lo sia anche m dal momento che m ∈ intS3 e quindi, se fosse ESS, sarebbe

l’unica.

Per gli esempi in cui non sono verificate le altre affermazioni, rimandia-

mo all’esempio dettagliato del gioco Carta-Sasso-Forbice.

Corollario 2.8. Se z ∈ intSn e una ESS per G, allora e un punto di

equilibrio globalmente asintoticamente stabile per (2.8).

Dimostrazione. Ricalcando la dimostrazione del teorema, si ha che P (x) >

0 ∀x 6= z ∈ intSn.

2.2.3 Dinamica e Strategie Strettamente Dominate

Vogliamo ora vedere come si comportano le strategie strettamente do-

minate nella dinamica della replicazione. Ricordiamo che, dato il gioco sim-

metrico con matrice dei payoff A, una strategia ei e strettamente dominata

se esiste una strategia (pura o mista) y ∈ Sn tale che

(Ax)i < yTAx

per ogni x ∈ Sn. Se i giocatori sono razionali, si puo supporre che nes-

suno di essi usera mai una strategia strettamente dominata. La dinamica

della replicazione tuttavia, non presuppone la razionalita dei giocatori ed

una domanda legittima puo essere quindi come ‘evolve’ la frequenza di una

strategia strettamente dominata. Ci proponiamo ora di dare una risposta:

vedremo che la frequenza di tali strategie tende effettivamente a zero.

Introduciamo una classe piu generale di giochi, per i quali la dinamica e

descrivibile con equazioni del tipo

xi = xigi(x), (2.13)

dove ogni funzione gi e C1(Ω), Ω aperto, Ω ⊃ Sn, e ha la proprieta che∑xigi(x) = 0 per ogni x ∈ Sn, (2.14)

in modo che Sn e ∂Sn siano invarianti.

Page 40: Dinamiche Evolutive ed Equilibri Correlati

40 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Definizione 2.6. Una dinamica di gioco e detta a payoff monotono se, per

ogni x ∈ Sngi(x) > gj(x)⇔ (Ax)i > (Ax)j . (2.15)

Cio significa che i tassi di crescita della frequenza di strategie diverse so-

no ordinati secondo il loro payoff (la frequenza di strategie pure con payoff

maggiore cresce piu velocemente).

Osservazione 2.5. La dinamica della replicazione e a payoff monotono,

infatti

gi(x) = (Ax)i − xTAx

e quindi

gi(x)− gj(x) = (Ax)i − (Ax)j .

Esempio 2.7. Un modello molto popolare e il seguente:

xi = xi

ek(Ax)i −n∑j=1

xjek(Ax)j

, (2.16)

con k costante positiva. Questo modello e interessante perche approssima la

dinamica della replicazione per k → 0 e la dinamica di risposta ottima per

k →∞.

Ripetendo ragionamenti gia fatti per la dinamica della replicazione, si

puo dimostrare il seguente risultato:

Proposizione 2.9. Ogni dinamica di gioco a payoff monotono ha gli stessi

punti di equilibrio della dinamica della replicazione. Inoltre vale il teorema

2.7.

Lemma 2.10. Sia x(t) ∈ Sn lo stato della popolazione. Se xi(t) soddisfa le

equazioni della dinamica di gioco (2.13), allora vale la regola del quoziente:

˙(xixj

)=

(xixj

)(gi(x)− gj(x)) (2.17)

Dimostrazione. Sviluppando il termine di destra e sostituendo le equazioni

(2.13) per xi ed xj si ha la tesi.

Dimostriamo ora un primo risultato.

Proposizione 2.11. Se una strategia pura i e strettamente dominata da

un’altra strategia pura j, cioe (Ax)i < (Ax)j per ogni x ∈ Sn, allora xi → 0

lungo tutte le soluzioni interne della dinamica (2.13) a payoff monotono.

Page 41: Dinamiche Evolutive ed Equilibri Correlati

2.2. DINAMICA DI GIOCO 41

Dimostrazione. Dal momento che la dinamica di gioco e a payoff monotono,

(Ax)i < (Ax)j ⇒ gi(x) < gj(x).

Per continuita esiste δ > 0 tale che gi(x) − gj(x) < −δ. Allora, grazie alla

regola del quoziente, si ottiene

˙(xi(t)

xj(t)

)< −xi(t)

xj(t)δ ∀t,

ovvero il rapporto xi(t)/xj(t)→ 0 con velocita esponenziale. Dal momento

che xj e limitata dal valore 1, cio significa che xi(t)→ 0 per t→∞.

Possiamo ora passare ad un risultato piu generale, introducendo per

prima cosa la dinamica di gioco monotona convessa:

Definizione 2.7. Una dinamica di gioco (2.13) e detta monotona convessa

se

yTAx > (Ax)i ⇒∑

yjgj(x) > gi(x) (2.18)

per ogni i e per ogni x,y ∈ Sn.

Osservazione 2.6. La dinamica della replicazione e monotona convessa.

Infatti gi(x) = (Ax)i − xTAx e∑yjgj(x) =

∑yj (Ax)j −

∑yjx

TAx = yTAx− xTAx.

Teorema 2.12. Se la dinamica di gioco (2.13) e monotona convessa e

la strategia pura Ri e iterativamente strettamente dominata, allora la sua

frequenza xi(t)→ 0.

Dimostrazione. Supponiamo inizialmente che Ri sia strettamente dominata

da una strategia y ∈ Sn; per la proprieta di monotonia convessa e per

continuita, esiste una costante δ > 0 tale che

gi(x)−∑

yjgj(x) < −δ

per ogni x ∈ Sn. Consideriamo la funzione P (x) := xi∏j x−yjj , cosı definita

si ha xi(t) < P (x(t)) per ogni t. Supponiamo che inizialmente vengano

giocate tutte le strategie: per ogni x(t) ∈ intSn

P (x) =∑k

∂P (x)

xjxj = xi

∏j

x−yjj − xi

∑k

xkykx−yk−1k

∏j 6=k

x−yjj =

= P (x)

(gi(x)−

∑k

ykgk(x)

)< −δP (x),

Page 42: Dinamiche Evolutive ed Equilibri Correlati

42 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

dove l’ultima uguaglianza e dovuta al fatto che gi(x) = xi/xi. Pertanto,

P (x(t)), e quindi xi(t), decrescono con andamento esponenziale. Questo

ragionamento puo essere ripetuto per le strategie strettamente dominate

al round successivo e cosı via, finche non vi sono piu strategie da elimi-

nare. Quindi tutte le frequenze di strategie pure strettamente dominate

convergono a 0.

Esempio 2.8. Consideriamo il gioco con matrice dei payoff

A =

a c b γ

b a c γ

c b a γ

a+ β a+ β a+ β 0

,con c < a < b, 0 < β < b − a e γ > 0, le strategie R1,R2,R3 formano un

ciclo di risposte ottime (se il primo giocatore gioca la prima riga, la risposta

ottima del secondo e giocare la seconda colonna, e cosı via), pertanto la faccia

del simplesso con x4 = 0 e limitato da un’orbita eteroclina e1 → e2 → ~e3 →e1. Inoltre, in questa faccia giace il punto p = (1/3, 1/3, 1/3, 0). Notiamo

che la strategia R4 puo essere invasa da ciascuna delle altre Ri, i = 1, 2, 3,

infatti

RT4 AR4 = 0 < γ = RT

i AR4, ∀i = 1, 2, 3.

Analogamente, ogni Ri, i = 1, 2, 3 puo essere invasa da R4 dal momento

che

RTi ARi = a < a+ β = RT

4 ARi, ∀i = 1, 2, 3.

Quindi sul bordo del simplesso ci sono altri tre punti di equilibrio z1 =(γ

γ+β , 0, 0,β

γ+β

), z2 e z3 analoghi, che attraggono tutte le orbite sulle facce

x2 = 0, x3 = 0 e x1 = 0 rispettivamente, e che, pertanto, cono collegati da

un’altra orbita eteroclina (figura 2.1).

Se

a+ b+ c > 3(a+ β) (2.19)

la strategia ~p e un equilibrio di Nash e domina strettamente la strategia

R4. Per il teorema 2.12 possiamo concludere che, per la dinamica della

replicazione, e in generale per ogni dinamica monotona convessa, x4(t)→ 0.

In particolare la (2.19) implica 2a < b + c, quindi per l’equazione della

replicazione vecp e globalmente stabile: attrae tutte le orbite nell’interno

della faccia del simplesso con x4 = 0.

Page 43: Dinamiche Evolutive ed Equilibri Correlati

2.2. DINAMICA DI GIOCO 43

Figura 2.1

2.2.4 Non convergenza

Nel paragrafo 3.2.2 abbiamo visto che, se tutte le strategie sono gioca-

te inizialmente con frequenza non nulla e la soluzione della dinamica della

replicazione converge ad un punto, allora questo punto e un equilibrio di

Nash. In particolare, risulta che le soluzioni di diverse dinamiche evolutive

convergono agli equilibri di Nash per importanti classi di giochi, quali i gio-

chi con potenziale o i giochi a somma zero (si veda per esempio [14]).

Tuttavia, in generale, le soluzioni di dinamiche evolutive non devono neces-

sariamente convergere agli equilibri di Nash. Per illustrarne un esempio,

introduciamo una dinamica piu generale di quella della replicazione.

Definizione 2.8. Un’equazione differenziale x = f(x) su Sn e detta dina-

mica di correzione, se

xTAx ≥ 0, (2.20)

con disuguaglianza stretta se x non e equilibrio di Nash (o punto stazionario

della dinamica della replicazione).

Questa definizione richiede, di fatto, che la popolazione del gioco si

muova verso una risposta miglioro contro la situazione attuale, cioe x(t +

h)TAx(t) > x(t)TAx(t), per h > 0 piccolo. Nel limite per h → 0 si ha la

definizione.

Proposizione 2.13. Ogni dinamica a payoff monotono e una dinamica di

correzione.

Page 44: Dinamiche Evolutive ed Equilibri Correlati

44 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Da questo risultato segue che anche la dinamica della replicazione e una

dinamica di correzione.

Esempio 2.9. Sia, ε ≥ 0,

A =

0 0 −1 ε

ε 0 0 −1

−1 ε 0 0

0 −1 ε 0

. (2.21)

Per ε 6= 0 il gioco ha un unico equilibrio di Nash: p = (1/4, 1/4, 1/4, 1/4).

Le equazioni della replicazione risultanox1 = x1 (ε (x4 − x1x2 − x2x3 − x3x4 − x1x4) + (2x1x3 + 2x2x4 − x3))

x2 = x2 (ε (x1 − x1x2 − x2x3 − x3x4 − x1x4) + (2x1x3 + 2x2x4 − x4))

x3 = x3 (ε (x2 − x1x2 − x2x3 − x3x4 − x1x4) + (2x1x3 + 2x2x4 − x1))

x4 = x4 (ε (x3 − x1x2 − x2x3 − x3x4 − x1x4) + (2x1x3 + 2x2x4 − x2))

che si annullano nei vertici del simplesso, in p e in altri due punti: F13 =

(1/2, 0, 1/2, 0) e F24 = (0, 1/2, 0, 1/2). Esiste un ciclo di risposte ottime in

strategie pure Γ := e1 → e2 → e3 → e4 → e1 (cioe se il primo giocatore

gioca la prima riga, il secondo ha come risposta ottima la seconda colonna

e cosı via, ricordando che B = AT ).

Per ε = 0, si ha A = AT . In questo caso non vi e piu un unico equilibrio

di Nash: oltre a p, tutti i punti di Γ sono equilibri di Nash. Il payoff medio

e dato da P (x) = xTAx = −2(x1x3 + x2x4) ed ha valore massimo 0 su Γ,

valore minimo −1/2 in corrispondenza di F13 ed F24. Infine, P (p) = −1/4.

Chiaramente P (x(t)) cresce monotonicamente lungo ogni soluzione di una

dinamica di correzione, infatti

P (x) = xTAx + xTAx = 2xTAx ≥ 0 ∀x,

dove l’ultima uguaglianza segue dalla simmetria di A. Dalla definizione di

dinamica di correzione sappiamo, in particolare, che cresce strettamente in

ogni punto del simplesso eccetto gli equilibri di Nash ed al piu i punti F13 ed

F24. P (x) e dunque una funzione di Lyapunov stretta per l’insieme di equili-

bri di Nash Γ che, pertanto, risulta asintoticamente stabile per ogni dinamica

di correzione, con bacino di attrazione l’insieme x : P (x) > −1/4.

Formalizziamo il risultato dell’esempio nel seguente teorema:

Page 45: Dinamiche Evolutive ed Equilibri Correlati

2.3. IL GIOCO CARTA-SASSO-FORBICE 45

Teorema 2.14. Per ogni dinamica di correzione che dipenda in modo con-

tinuo dai payoff, e per ogni δ > 0, esiste un ε0 > 0 tale che, per ogni

scelta di ε nel gioco (2.21) con |ε| < ε0, e per ogni condizione iniziale x con

P (x) > −1/4 + δ, le soluzioni non convergono all’equilibrio interno di Nash

p, ma entrano nell’insieme x : P (x) > −δ e ci rimangono per sempre.

Dimostrazione. Segue dal fatto che P (x) e ancora una funzione di Lyapunov

per la dinamica perturbata fuori da un qualche intorno di Γ e p.

Questo teorema sottolinea il fatto che l’analisi degli equilibri di Nash non

garantisce in ogni caso la convergenza della dinamica del gioco. In molte

situazioni un comportamento ciclico e inevitabile.

2.3 Il Gioco Carta-Sasso-Forbice

Il gioco Carta-Sasso-Forbice (o Rock-Paper-Scissors, RPS) consiste nello

scegliere tra tre strategie pure tali che R1 viene battuta da R2 la quale viene

battuta da R3 che a sua volta viene sconfitta da R1. La matrice generica

dei payoff e

A =

0 −a2 b3b1 0 −a3

−a1 b2 0

(2.22)

dove ai, bi > 0. Questo genere di giochi ha un unico equilibrio di Nash

z ∈ intS3 dato da

z =1

Σ(a2a3 + a3b2 + b2b3, a1a3 + a1b3 + b3b1, a1a2 + a2b1 + b1b2) (2.23)

con Σ scelto opportunamente, in modo che z ∈ S3.

Nel caso di simmetria ciclica (cioe a1 = a2 = a3 e b1 = b2 = b3), l’unico

equilibrio di Nash e z =(

13 ,

13 ,

13

); inoltre, dividendo ogni termine per ai, la

matrice dei payoff diventa

A =

0 −1 ε

ε 0 −1

−1 ε 0

. (2.24)

Il gioco originale si ottiene per ε = 1.

Vogliamo capire per quali valori di ε z e stabile o instabile nel sistema della

replicazione. Per fare cio, studiamo la funzione f(x) = x1x2x3 e vediamo

Page 46: Dinamiche Evolutive ed Equilibri Correlati

46 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

dove cresce, decresce o e costante. Il sistema della replicazione ex1 = x1

(εx3 − x2 − xTAx

)x2 = x2

(εx1 − x3 − xTAx

)x3 = x3

(εx2 − x1 − xTAx

) (2.25)

quindi la derivata di f(x) e

f = x1x2x3 + x1x2x3 + x1x2x3 =

= x1x2x3

(ε− 1− 3xTAx

) .

Ricordando che

1 = (x1 + x2 + x3)2 = ‖x‖2 + 2(x1x2 + x1x3 + x2x3)

possiamo calcolare xTAx che risulta

xTAx =ε− 1

2

(1− ‖x‖2

),

da cui

f = x1x2x3ε− 1

2

(3 ‖x‖2 − 1

).

La funzione ‖x‖2 e massima nei tre vertici del simplesso S3, in cui raggiunge

il valore 1, ed ha un minimo nel punto z = (1/3, 1/3, 1/3) che vale 1/3.

Percio, f e nulla nel punto z; per ogni x 6= z ∈ intS3 e positiva se ε > 1,

negativa se ε < 1 ed e costantemente nulla se ε = 1.

Come nella dimostrazione del teorema 2.7, abbiamo trovato una funzione

di Lyapunov V (x) = f(x)1/3 per z nei casi ε > 1 ed ε = 1 la quale risulta

essere minima su ∂S3 ed ha un massimo in x = z.

In particolare, per ε > 1, V (x) e di Lyapunov stretta, quindi z e un punto

di equilibrio asintoticamente stabile nel sistema della replicazione. Inoltre

risulta essere anche una ESS, infatti (proposizione 2.4):

xTAx =ε− 1

2

(1− ‖x‖2

)<ε− 1

3= zTAx ∀x 6= z.

Se, invece ε = 1, V (x) e funzione di Lyapunov, ma non stretta, il che

garantisce solo la stabilita del punto z. Cio significa che, per ogni punto

iniziale x0 ∈ intS3, la soluzione del sistema della replicazione Φ(t,x0) si

muove lungo la curva chiusa x01x

02x

03 = γ, ovvero le soluzioni sono periodiche.

Se x0 = z, la curva coincide con il punto.

Invece, se ε < 1, si ha il seguente risultato dovuto a Zeeman [21]:

Page 47: Dinamiche Evolutive ed Equilibri Correlati

2.3. IL GIOCO CARTA-SASSO-FORBICE 47

Proposizione 2.15. Se ε < 1, per ogni condizione iniziale x0 6= z, la

soluzione x(t) converge al bordo del simplesso ∂S3 = x ∈ S3 : V (x) = 0per t→∞.

Dimostrazione. Se ε < 1, ∀x ∈ S3,x 6= z, zTAx < xTAx.

Piu precisamente

zTAx− xTAx = −(z− x)TA(z− x) = −(

1− ε2

) 3∑1

(zi − xi)2 (2.26)

dove la prima uguaglianza segue dal fatto che z ∈ intS3, quindi (Az)i −zTAz = 0 per ogni i. Ricordando che V (x) assume valore minimo 0 su ∂S3

e massimo 1/3 in z, denotando con v(t) := V (x(t)) abbiamo

v(t) = (zTAx−xTAx)v(t) = −v(t)

(1− ε

2

) 3∑1

(zi−xi)2 < 0 v(t) 6= 0,x 6= z.

(2.27)

Ne segue che, per ogni condizione iniziale x(0) 6= z, v(t) decresce verso zero,

quindi x(t) converge al bordo del simplesso.

Cio significa che il punto z e instabile nella dinamica della replicazione e

che le soluzioni del sistema della replicazione sono delle curve spiraleggianti

che si allontanano da z. Inoltre, il caso ε < 1 e un esempio del fatto che il

viceversa della prima affermazione del teorema 2.7 non e verificato: i punti

di equilibrio della dinamica della replicazione sono infatti quattro (e1, e2, e3

e z) ma solo z e equilibrio di Nash. In particolare, seguendo il ragionamento

dell’osservazione 2.4, si ha per esempio

(Ae1)2 = ε > eT1 Ae1 = 0.

Ricapitolando, z e:

• instabile, quando ε < 1; questo caso mostra dunque che i viceversa

della prima e della seconda affermazione del teorema 2.7 non sono

verificati(figura 2.2);

• stabile, ma non asintoticamente, quando ε = 1; z non e attrattivo

quindi non puo essere punto limite di alcuna soluzione (cioe non vale

il contrario della terza affermazione,figura 2.6);

• asintoticamente stabile, quando ε > 1. In particolare, grazie al teore-

ma 2.8, e addirittura globalmente stabile.

Page 48: Dinamiche Evolutive ed Equilibri Correlati

48 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Notiamo, infine, che nei primi due casi il teorema 2.7 implica che z non

possa essere evolutivamente stabile, mentre, come abbiamo gia visto, nel

terzo caso z e ESS (figura 2.10).

Consideriamo ora la dinamica definita da (2.16); per il gioco RPS risultax1 = x1(ek(−x2+εx3) − x1e

k(−x2+εx3) − x2ek(−x3+εx1) − x3e

k(−x1+εx2));

x2 = x2(ek(−x1+εx1) − x1ek(−x2+εx3) − x2e

k(−x3+εx1) − x3ek(−x1+εx2));

x3 = x3(ek(−x3+εx2) − x1ek(−x2+εx3) − x2e

k(−x3+εx1) − x3ek(−x1+εx2)).

(2.28)

Per la proposizione 2.9, sappiamo che valgono gli stessi risultati della dina-

mica della replicazione. Di seguito mettiamo a confronto le figure ottenute

per la dinamica della replicazione (in blu) (figure 2.2, 2.6, 2.10) e per il si-

stema (in azzurro)(2.28) rispettivamente per k=0.2 ( figure 2.3, 2.7, 2.11),

k=2 (figure 2.4, 2.8, 2.12) e k=10 (figure 2.5, 2.9, 2.13).

Figura 2.2: ε < 1 Figura 2.3: ε < 1, k=0.2

Figura 2.4: ε < 1, k=2 Figura 2.5: ε < 1, k=10

Page 49: Dinamiche Evolutive ed Equilibri Correlati

2.3. IL GIOCO CARTA-SASSO-FORBICE 49

Figura 2.6: ε = 1 Figura 2.7: ε = 1, k=0.2

Figura 2.8: ε = 1, k=2 Figura 2.9: ε = 1, k=10

In generale, per ogni gioco del tipo (2.22) vale un risultato analogo,

formalizzato dal seguente teorema:

Teorema 2.16. Sono equivalenti le seguenti condizioni (si vedano [6] e [7]):

1. z e asintoticamente stabile;

2. z e globalmente stabile;

3. det A > 0, cioe a1a2a3 < b1b2b3;

4. zT Az > 0.

Se detA = 0, tutte le orbite in intSn sono orbite chiuse intorno a z. Se

detA < 0, allora tutte le orbite in intSn, a parte quelle che partono da z,

convergono verso il bordo. Piu precisamente, per x ∈ intSn, l’insieme di

Page 50: Dinamiche Evolutive ed Equilibri Correlati

50 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Figura 2.10: ε > 1 Figura 2.11: ε = 1, k=0.2

Figura 2.12: ε = 1, k=2 Figura 2.13: ε = 1, k=10

punti di accumulazione di x(t), per t → ∞, e un’orbita eteroclina che con-

siste dei tre vertici del simplesso e dei tre bordi che li congiungono.

Questo e dunque un esempio del fatto che un equilibrio di Nash puo non

descrivere l’outcome della dinamica della replicazione.

2.4 Giochi Asimmetrici

Fino ad ora abbiamo sempre considerato conflitti tra individui di una

stessa specie o tipo, con gli stessi payoff e le stesse strategie. Tuttavia i casi

piu realistici sono quelli in cui gli individui appartengono ad una o piu specie

o tipi diversi, generando conflitti asimmetrici come per esempio quelli tra

maschi e femmine o tra genitori e figli. In particolare ci concentreremo sui

giochi finiti in forma normale a due giocatori, i cui payoff verranno descritti

Page 51: Dinamiche Evolutive ed Equilibri Correlati

2.4. GIOCHI ASIMMETRICI 51

tramite bimatrici. Ovviamente i giocatori che si affrontano apparterranno

sempre a specie diverse, X e Y .

Supponiamo che X e Y abbiano a disposizione, rispettivamente, N ed

M strategie pure. Quando un giocatore in X usa la strategia i ∈ I :=

1, . . . , N contro una strategia j ∈ J := 1, . . . ,M di un giocatore in Y , il

primo guadagna U = (uij) ed il secondo V = (vji). Le strategie miste per il

primo sono E1, . . . ,En, Ei ∈ SN ∀i ∈ I, e F1, . . . ,Fm, Fj ∈ SM ∀j ∈ Jper il secondo.

Come nel caso simmetrico, invece del gioco caratterizzato dalle matrici U e

V , ci concentreremo sul gioco (che avevamo denotato con G) in cui le matrici

dei payoff sono

A = (aij) =(ETi UFj

)e

B = (bji) =(FTj VEi

).

Gli stati della popolazione verranno in seguito indicati con x ∈ Sn e y ∈ Sm.

I payoff medi delle popolazioni saranno rispettivamente xTAy e yTBx.

Ricordiamo la definizione di equilibrio di Nash:

Definizione 2.9. Una coppia (p, q) ∈ Sn × Sm e un equilibrio di Nash se

p e una risposta ottima a q e viceversa, cioe

xTAq ≤ pTAq (2.29)

per ogni x ∈ Sn e

yTBp ≤ qTBp (2.30)

per ogni y ∈ Sm.

Se entrambe le disuguaglianze sono strette, la coppia (p, q) si dice equilibrio

di Nash stretto.

Per quanto riguarda la nozione di stabilita evolutiva, non esiste un’esten-

sione ovvia del caso simmetrico. Chiaramente, perche una coppia di strategie

(p,q) sia evolutivamente stabile, deve essere innanzitutto un equilibrio di

Nash. Tuttavia, se x fosse un’altra risposta ottima a q, cioe la (2.29) fosse

un’uguaglianza, non ci sarebbe nessuna condizione che impedisca l’invasione

di p. Per questo motivo, nel caso asimmetrico, bisogna escludere la presenza

di risposte ottime alternative; cio comporta che la definizione di strategie

evolutivamente stabili coincida con quella di equilibrio di Nash stretto.

Definizione 2.10. Un coppia di strategie (p, q) ∈ Sn × Sm si dice evoluti-

vamente stabile per un gioco asimmetrico a due specie se

pTAq > xTAq ∀x 6= p ∈ Sn (2.31)

Page 52: Dinamiche Evolutive ed Equilibri Correlati

52 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

qTBp > yTBp ∀y 6= q ∈ Sm (2.32)

Ricordiamo che un equilibrio di Nash stretto e necessariamente una ESS,

da cui deriva la

Proposizione 2.17. Una coppia di strategie e evolutivamente stabile se e

solo se e un equilibrio di Nash stretto.

Corollario 2.18. Una coppia di strategie evolutivamente stabile e necessa-

riamente nelle strategie pure.

Dimostrazione. Un equilibrio di Nash stretto e necessariamente nelle stra-

tegie pure. Come conseguenza del teorema precedente, dunque, si ha la

tesi.

Esempio 2.10 (Buyer/Seller Game). Consideriamo due popolazioni distin-

te: quella dei venditori, che possono decidere di comportarsi in modo onesto

oppure di alzare il prezzo scorrettamente, e quella dei clienti, i quali possono

fidarsi del venditore oppure verificare se il prezzo proposto sia onesto.

Se il venditore e onesto ma il cliente decide di controllare, il payoff sara 2 per

il primo (perche se il cliente controlla significa che non ripone grande fiducia

nel venditore) e 3 per il secondo (perche fa una ‘gaffe’). Se il cliente con-

trolla e il venditore e disonesto, guadagnano rispettivamente 2 e 1, perche la

fiducia tra i due cala notevolmente. Se il cliente non controlla ed il venditore

e onesto, la fiducia reciproca e massima ed i due ottengono rispettivamente

4 e 3. Infine, se il cliente ripone la sua fiducia in un venditore disonesto, il

primo guadagna 1 mentre il secondo 4. La bimatrice dei payoff del gioco e

quindi [(3, 2) (2, 1)

(4, 3) (1, 4)

].

Il gioco ha un unico equilibrio di Nash, [(1/2, 1/2) , (1/2, 1/2)], che essendo

misto non puo essere ESS. Il gioco dunque non ha strategie evolutivamente

stabili.

2.4.1 Dinamica di Gioco Asimmetrica

Come nel caso simmetrico, supponiamo che gli stati della popolazione

siano funzioni differenziabili del tempo e che i tassi di crescita delle fre-

quenze, delle strategie i e j possano essere espressi come la differenza tra

il payoff della strategia stessa e quello medio della rispettiva popolazione.

Formalmente, se xi e la frequenza della strategia Ei nella specie X e yj

Page 53: Dinamiche Evolutive ed Equilibri Correlati

2.4. GIOCHI ASIMMETRICI 53

e la frequenza della strategia Fj nella specie Y , si ottiene il sistema della

replicazione

xi = xi((Ay)i − xTAy

)∀i = 1, . . . , n

yj = yj

((Bx)j − yTBx

)∀j = 1, . . . ,m

(2.33)

per (x,y) ∈ Sn × Sm.

Come nel caso simmetrico, e possibile provare la seguente

Proposizione 2.19. Gli insiemi Sn × Sm, int (Sn × Sm) e ∂ (Sn × Sm)1

sono invarianti rispetto alla dinamica della replicazione.

Salvo diverso avviso, concentreremo l’attenzione su problemi con condi-

zioni iniziali (x(0),y(0)) ∈ int(Sn × Sm). I punti di equilibrio del sistema

(2.33) in int(Sn × Sm) sono le soluzioni (x,y) del sistema di equazioni

(Ay)1 = . . . = (Ay)n ,m∑j=1

yj = 1

(Bx)1 = . . . = (Bx)m ,n∑i=1

xi = 1

(2.34)

tali che xi > 0 ∀i = 1, . . . , n e yi > 0 ∀j = 1, . . . ,m. Se n 6= m, l’insieme

dei punti di equilibrio in int(Sn × Sm) o e vuoto o contiene un sottoinsieme

|n−m| dimensionale.

Percio puo esistere un punto di equilibrio isolato se e solo se n = m. Se un

tale punto esiste, e unico. D’ora in poi, quindi, n = m.

Proposizione 2.20. I punti di equilibrio del sistema (2.33) in int(Sn×Sm)

non possono essere ne pozzi ne sorgenti.

Dimostrazione. Dalla prima relazione in (2.34) sappiamo che (Ay)i = xTAx

e pertanto ricaviamo

∂xi∂xj

=∂

∂xjxi((Ay)i − xTAy

)= = δij

((Ay)i − xTAy

)− xi

(∂

∂xj(xTAy)

)= = xi

(− ∂

∂xj(xTAy)

).

1Si tratta dell’insieme dove almeno un xi o yj e nullo.

Page 54: Dinamiche Evolutive ed Equilibri Correlati

54 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Per 1 ≤ j ≤ n− 1 si ha

∂xj(xTAy) =

∂xj

(n−1∑i=1

xi(Ay)i +

(1−

n−1∑i=1

)(Ay)n

)=

= (Ay)j − (Ay)n = 0.

Quindi ∂xi∂xj

= 0 per 1 ≤ i, j ≤ n − 1. Poiche una relazione analoga vale

per yj , la matrice Jacobiana del sistema (2.33) in un punto di equilibrio in

int(Sn × Sm) ha la forma

J =

[0 C

D 0

]∈ R(n−m−2)×(n+m−2),

dove C ∈ R(n−1)×(m−1) e D ∈ R(m−1)×(n−1). Il polinomio caratteristico,

moltiplicando per -1 le prime n−1 colonne e le ultime m−1 righe di J−λI,

diventa

p(λ) = (−1)n+m−2p(−λ).

Pertanto, se λ e autovalore di J , lo e anche −λ, escludendo la possibilita di

avere pozzi (Re(λ) < 0 per ogni λ) o sorgenti (Re(λ) > 0 per ogni λ).

In particolare, il sistema (2.33) ammette come pozzi solo i vertici del

simplesso Sn × Sm, poiche uno stato evolutivamente stabile non puo essere

misto, in un gioco asimmetrico.

Proposizione 2.21. L’aggiunta di costanti alle colonne delle matrici dei

payoff lascia invariato il sistema della replicazione.

Dimostrazione. Supponiamo di aggiungere ad ogni componente i, j−esima

di A la costante cj e ad ogni componente i, j−esima di B la costante dj ,

ottenendo le matrici A e B. Poniamo c = (c1, . . . , n) e d = (d1, . . . , dn);

si verifica facilmente che (Ayi = (Ay)i + 〈c,y〉 e xT Ay = xTAy + 〈c,y〉.Analogamente (Bxi = (Bx)i + 〈d,x〉 e yT Bx = yTBx + 〈d,x〉. A questo

punto si ha immediatamente la tesi.

Forti di questo risultato, vediamo cosa succede in un generico gioco con

n = m = 2. Date due matrici dei payoff A e B, possiamo supporre infatti,

senza perdita di generalita, che i termini diagonali siano nulli:

A =

[0 a12

a21 0

]B =

[0 b12

b21 0

]. (2.35)

Page 55: Dinamiche Evolutive ed Equilibri Correlati

2.4. GIOCHI ASIMMETRICI 55

Consideriamo il sistema della replicazione per le sole variabili x e y, dove

x = (x, 1− x) e y = (y, 1− y). (2.33) diventa:

x = x(1− x)(a12 − (a12 + a21)y)

y = y(1− y)(b12 − (b12 + b21)x)

sul quadrato Q = S2 × S2 = (x, y) : 0 ≤ x, y ≤ 1.Se a12a21 ≤ 0 (cioe a12 e a21 hanno segni opposti), x non cambia segno in Q

e una delle due strategie del primo giocatore domina l’altra (figura 2.14). In

questo caso quindi, x(t) puo essere costante o convergere monotonicamente

verso 0 o 1. Altrettanto vale nella seconda equazione per b12b21 ≤ 0. Dob-

biamo pertanto studiare il caso a12a21 > 0 e b12b21 > 0, il quale ammette

l’unico punto di equilibrio in intQ

F =

(b12

b12 + b21,

a12

a12 + a21

).

La matrice Jacobiana in F e

J =

[0 −(a12 + a21) b12b21

(b12+b21)2

−(b12 + b21) a12a21(a12+a21)2

0

]

con autovalori

λ = ±

√a12a21b12b21

(a12 + a21)(b12 + b21).

Se a12b12 > 0, gli autovalori sono reali e di segno opposto, quindi F e un

punto di sella e tutte le orbite convergono verso uno o l’altro di due angoli

opposti di Q(figura 2.15). Se invece a12b12 < 0, i due autovalori sono imma-

ginari puri (cioe la parte reale e nulla) e quindi le orbite sono curve chiuse

che ruotano periodicamente intorno a F(figura 2.16).

Tra equilibri di Nash e punti di equilibrio della dinamica della replica-

zione, esistono risultati analoghi al caso simmetrico.

Lemma 2.22. Un punto (z,w) ∈ Sn×Sm e asintoticamente stabile se esiste

un intorno U di (z,w) tale che, per ogni (x,y) ∈ U si ha

zTAy− xTAy + wTBx− yTBx > 0

Dimostrazione. Vogliamo trovare una funzione di Lyapunov stretta per (z,w).

Scegliamo come candidata

V (x,y) =∏zi>0

xzii∏wj>0

ywii −∏zi>0

zzii∏wi>0

wwii

Page 56: Dinamiche Evolutive ed Equilibri Correlati

56 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Figura 2.14: a12a21 ≤ 0 e b12b21 ≤ 0 Figura 2.15: a12b12 > 0

Figura 2.16: a12b12 < 0

e procediamo come nella dimostrazione del punto 4 del teorema 2.7: V (z,w) =

0 e con la disuguaglianza di Jensen si dimostra che V (x,y) < 0 per (x,y) 6=(z,w). Per dimostrare che V > 0, poniamo

P := V +∏zi>0

zzii∏wi>0

wwii

Page 57: Dinamiche Evolutive ed Equilibri Correlati

2.4. GIOCHI ASIMMETRICI 57

e vediamo che P > 0:

P = Pd

dtlogP = P

d

dt

∑zi>0

zi log xi +∑wj>0

wj log yj =

= P

∑zi>0

zixixi

+∑wj>0

yjyj

=

= P

∑zi>0

((Ay)i − xTAy) +∑wj

((Bx)j − yTAx)

=

= P (zTAy− xTAy + wTBx− yTBx) > 0

se (x,y) ∈ U ∩M 6= 0, essendo M = (x,y) : xi > 0 se xi > 0 e yj >

0 se wi > 0, l’insieme su cui P > 0. Possiamo quindi concludere che (z,w)

e asintoticamente stabile.

Teorema 2.23. Valgono le seguenti proprieta:

1. se (z,w) e un equilibrio di Nash, allora e un punto di equilibrio per la

dinamica (2.33);

2. se (z,w) e un punto di equilibrio stabile, allora e equilibrio di Nash;

3. se (z,w) e un punto limite di un’orbita interna (cioe esiste (x0,y0) ∈int(Sn×Sm), diverso da (z,w) tale che limt→∞Φ(t, (x0,y0) = (z,w)),

allora e un equilibrio di Nash;

4. se (z,w) e uno stato evolutivamente stabile, allora e punto di equilibrio

asintoticamente stabile.

Dimostrazione. Per le prime tre affermazioni, il procedimento e lo stesso

della dimostrazione del teorema 2.7.

Proviamo la quarta affermazione: per ipotesi si ha

zTAw > xTAw ∀x 6= z e wTBz > yTBz ∀y 6= w.

Per continuita, esiste un intorno U di (z,w) tale che, per ogni (x,y) ∈ Uvale

zTAy− xTAy + wTBx− yTBx > 0.

Grazie al lemma precedente possiamo concludere che (z,w) e asintoticamen-

te stabile.

Proposizione 2.24. Sia (z,w) ∈ Sn × Sm un punto di equilibrio per la

dinamica della replicazione, se z e w non sono entrambe pure, allora (z,w)

non puo essere asintoticamente stabile.

Page 58: Dinamiche Evolutive ed Equilibri Correlati

58 CAPITOLO 2. TEORIA EVOLUTIVA DEI GIOCHI

Dimostrazione. Dobbiamo distinguere due casi: (z,w) ∈ int(Sn × Sm) op-

pure z o w sono su una faccia del simplesso a cui appartengono (cioe esiste

i tale che zi = 0 o j tale che wj = 0).

Consideriamo, per il primo caso, la funzione

V :=

n∏i=1

xi

m∏j=1

yj .

Poniamo x1 = 1 −∑

i>1 xi e y1 = 1 −∑

j>1 yj ed esaminiamo il sistema

dinamico

xi =xiV

((Ay)i − xTAy

)yj =

xiV

((By)j − yTBx

) (2.36)

per i = 1, . . . , n, j = 2, . . . ,m, ben definito su Rn−1+ × Rm−1

+ . In virtu della

proposizione 1.10, aver diviso il sistema per V non ne altera le orbite. Per

dimostrare che (z,w) non e asintoticamente stabile e sufficiente dimostrare

che il sistema (2.36) non ammette equilibri asintoticamente stabili. Per

fare cio, utilizziamo il teorema 1.11: calcolando la divergenza del campo

vettoriale associato al sistema (2.36) si trova∑k>1

∂xk∂xk

= 0,

∑h>1

∂yh∂yh

= 0

,

quindi non possono esserci equilibri asintoticamente stabili.

Per il secondo caso, consideriamo invece

V :=∏zi 6=0

xi∏wj 6=0

yj .

Indicando con i e j due indici per i quali zi 6= 0 e wj 6= 0, possiamo scrivere

xi = 1−∑

i 6=i xi e yj = 1−∑

j 6=j yj e considerare il sistema

xi =xiV

((Ay)i − xTAy

)yj =

yjV

((Bx)j − yTBx

)per i, j tali che zi 6= 0,wj 6= 0, i 6= i e j 6= j. Ponendo c1 := |i : zi 6= 0|e c2 := |j : wj 6= 0|, il sistema e ben definito su Rc1−1

+ × Rc2−1+ . A questo

punto, procedendo esattamente come nel primo caso, si ha la tesi.

Page 59: Dinamiche Evolutive ed Equilibri Correlati

2.4. GIOCHI ASIMMETRICI 59

Diversamente dal caso simmetrico, la quarta affermazione del teorema

2.23 e in realta un’equivalenza, come mostra il teorema seguente:

Teorema 2.25. Sia (z,w) un equilibrio asintoticamente stabile nella dina-

mica della replicazione di un gioco asimmetrico. Allora (z,w) e una coppia

di strategie evolutivamente stabile.

Dimostrazione. Per la proposizione precedente, sappiamo che z e w devono

essere necessariamente strategie pure.

Supponiamo per assurdo che (z,w) sia asintoticamente stabile ma non evo-

lutivamente stabile; cio implica che (z,w) non e neanche equilibrio di Nash

stretto. Senza perdita di generalita, possiamo quindi assumere che esista

una strategia i tale che zTAw = (Aw)i (cioe z e su uno spigolo di Sn).

Chiamiamo E lo spigolo di Sn che connette i punti z ed ei, allora l’insieme

E × w e un insieme di punti di equilibrio del sistema della replicazione.

Pertanto (z,w) non puo essere asintoticamente stabile, assurdo.

Page 60: Dinamiche Evolutive ed Equilibri Correlati

Capitolo 3

Un’Applicazione

Vediamo ora un’applicazione dei risultati studiati fino a questo punto.

Consideriamo una nazione la cui popolazione sia composta in parte da citta-

dini originari del luogo, in parte da immigrati. L’idea e quella di utilizzare gli

strumenti forniti dalla teoria evolutiva dei giochi per analizzare le interazioni

tra le due controparti. Il contesto e, quindi, quello dei giochi asimmetrici a

due giocatori e di particolare interesse e il caso in cui entrambe le contro-

parti dispongono di due strategie.

Nella prima sezione introduciamo il modello del gioco; nella seconda sezione

studiamo la dinamica della replicazione. Infine, nella terza sezione, pre-

sentiamo alcune considerazione su altre dinamiche con alcuni esperimenti

numerici.

3.1 Il Modello

Denotiamo con A la popolazione locale di una nazione, e con B la popo-

lazione di immigrati all’interno della stessa (supponiamo che vengano tutti

da uno stesso stato). Supponiamo che gli immigrati siano dispersi nel ter-

ritorio, rendendo trascurabili le interazioni tra loro; per il caso in cui sia

rilassata questa ipotesi si fa riferimento a [1].

I cittadini forniscono i servizi piu essenziali (ospedali, servizi pubblici, tra-

sporti, eccetera) e le interazioni con gli immigrati avvengono quando uno di

questi ultimi ha bisogno di utilizzare uno di questi servizi e deve interagire

con un cittadino che ci lavora. Ricordiamo che non e necessaria alcuna ipo-

tesi di razionalita.

Durante l’incontro, un individuo di A puo comportarsi in modo ostile (

strategia pura che denotiamo con N) oppure in modo accogliente (che de-

notiamo con W ). Un individuo di B, invece, puo essere integrato, e quindi

60

Page 61: Dinamiche Evolutive ed Equilibri Correlati

3.1. IL MODELLO 61

e in grado di esprimersi in modo corretto nella lingua del paese ospitante,

(strategia L) oppure no (H). Supponiamo, inoltre, che la strategia L im-

plichi che l’individuo possa accedere al servizio in questione senza ostacoli,

indipendentemente dall’impiegato che trova.

Traduciamo in termini di payoff quanto detto:

• un immigrato che adotta la strategia L ottiene un guadagno f1(P ) dal

servizio e un guadagno f2(K) dall’interazione con l’impiegato e con

altri individui di A che potrebbe incontrare; tuttavia deve sostenere

un certo ‘costo’ f3(c) dovuto allo sforzo di imparare una nuova lin-

gua, sforzo che dipende dalla distanza dalla propria lingua madre ξ.

Pertanto ∂f3(c)∂ξ > 0.

• Un immigrato che usa la strategia H non incorre in questo costo ma

nemmeno ha un guadagno dalle interazioni con individui appartenenti

ad A. Inoltre, e possibile che non riesca ad accedere ad un servizio

pubblico, nel caso in cui non riesca a farsi comprendere o incontri un

impiegato ostile, ottenendo un guadagno αf1(P ) con α ∈ [0, 1].

Per un immigrato, entrambe le strategie portano ad un costo f4(∆), dovuto

al fatto di sentirsi discriminati, nel caso in cui incontrino un impiegato ostile.

Per quanto riguarda i cittadini:

• quelli ostili sostengono una costo f5(X) dovuto al fatto che sia spia-

cevole per loro avere a che fare con un individuo appartenente a B.

Tuttavia ottengono un certo guadagno nell’ostacolarlo (possibile solo

nel caso che l’immigrato sia di tipo H) dato da (1− α)f1(P );

• quelli accoglienti non fanno distinzione tra cittadini e immigranti,

pertanto non perdono o guadagnano nulla.

La bimatrice dei payoff, pertanto, risulta

(A,B) =

[(a11, b11) (a12, b21)

(a21, b12) (a22, b22)

],

Page 62: Dinamiche Evolutive ed Equilibri Correlati

62 CAPITOLO 3. UN’APPLICAZIONE

dove

a11 = −f5(X) = u(N,L)

a12 = −f5(X) + (1− α)f1(P ) = u(N,H)

a21 = 0 = u(W,L)

a22 = 0 = u(W,H)

b11 = f1(P ) + f2(K)− f3(c)− f4(∆) = v(N,L)

b12 = f1(P ) + f2(K)− f3(c) = v(W,L)

b21 = αf1(P )− f4(∆) = v(N,H)

b22 = f1(P ) = v(W,H)

e fi(·) ∈ R+, fi(0) = 0; f ′i(·) > 0; f ′′i (·) < 0 ∨ f ′′i (·) < 0 e f(x, y) = fi(x) +

fj(y). Osserviamo inoltre che v(W,L) > v(N,L) e v(W,H) > v(N,H), cioe

chiaramente ogni immigrato preferisce incontrare un impiegato accogliente

piuttosto che uno ostile.

Grazie alla proposizione 1.5, possiamo effettuare una trasformazione che

renda nulli i termini diagonali, ottenendo

(A,B) =

[(0, 0) (a1, b2)

(a2, b1) (0, 0)

],

con

a1 = a12 − a22 = −f5(X) + (1− α)f1(P )

a2 = a21 − a11 = f5(X)

b1 = b12 − b22 = f2(K)− f3(c)

b2 = b21 − b11 = −(1− α)f1(P )− f2(K) + f3(c)

Osserviamo le seguenti proprieta:

• se (1− α)f(P ) > f(X) allora a1 > 0;

• a2 > 0 sempre;

• se f(c) ∈ [0; f(K)− ε], b1 > 0, b2 < 0;

• se f(c) ∈ [f(K) + ε; f(K) + (1− α)f(P )− ε], b1 < 0, b2 < 0

• se f(c) ∈ [f(K) + (1− α)f(P ) + ε; +∞), b1 < 0, b2 > 0

• b1 > 0, b2 > 0 non si verifica mai (f(c) ≥ 0).

Page 63: Dinamiche Evolutive ed Equilibri Correlati

3.2. DINAMICA DELLA REPLICAZIONE ED ESS 63

3.2 Dinamica della Replicazione ed ESS

Scriviamo ora le equazioni della replicazione per il gioco. D’ora in avanti,

per semplicita, indicheremo ogni funzione fi con f . Indichiamo con (p, 1−p)e (q, 1− q) gli stati della popolazione, rispettivamente di A e B. Si ricava

p = p(1− p)(a1 − q(a1 + a2))

q = q(1− q)(b1 − p(b1 + b2))(3.1)

Per trovare gli equilibri di Nash e le ESS dobbiamo distinguere sei casi, in

ciascuno dei quali il gioco risulta avere un solo equilibrio di Nash:

1. a1 > 0, a2 > 0, b1 > 0, b2 < 0: l’equilibrio e (e2, e1) con payoff

(a2, b1);

2. a1 < 0, a2 > 0, b1 > 0, b2 < 0: come nel caso precedente, (e2, e1) e

equilibrio di Nash;

3. a1 > 0, a2 > 0, b1 < 0, b2 < 0: non esistono equilibri di Nash

in strategie pure ma quello in strategie miste e dato da (x,y) con

x =(

b1b1+b2

, b2b1+b2

)= (x, 1− x) e y =

(a1

a1+a2, a2a1+a2

)= (y, 1− y);

4. a1 < 0, a2 > 0, b1 < 0, b2 < 0: l’equilibrio e (e2, e2) con payoff (0, 0);

5. a1 > 0, a2 > 0, b1 < 0, b2 > 0: l’equilibrio e (e1, e2) con payoff

(a1, b2);

6. a1 < 0, a2 > 0, b1 < 0, b2 > 0: come nel caso 4, l’equilibrio di Nash

e (e2, e2) con payoff (0, 0).

E’ facile verificare che i punti (0, 0), (1, 1), (1, 0), (0, 1) e (x1, y1) sono punti

di equilibrio per la dinamica della replicazione (3.1). Questi punti, tranne

(1, 1), corrispondono agli equilibri di Nash del gioco. Grazie alla proposi-

zione 2.17 e al corollario 2.18 possiamo concludere che, in tutti e cinque i

casi in cui si ha un equilibrio di Nash in strategie pure, l’equilibrio di Nash

e una coppia di ESS, mentre nel caso 3 l’equilibrio di Nash non puo essere

evolutivamente stabile. Inoltre, per il teorema 2.25, le ESS sono punti di

equilibrio asintoticamente stabili nella dinamica della replicazione, mentre

il punto di equilibrio interno al simplesso non puo esserlo.

Per classificare le proprieta di stabilita degli altri punti di equilibrio di (3.1),

calcoliamo la matrice Jacobiana del sistema:

J =

[(1− 2p)(a1 − q(a1 + a2)) −p(1− p)(a1 + a2)

−q(1− q)(b1 + b2) (1− 2q)(b2 − p(b1 + b2))

].

Ne ricaviamo le seguenti considerazioni:

Page 64: Dinamiche Evolutive ed Equilibri Correlati

64 CAPITOLO 3. UN’APPLICAZIONE

• il punto (1, 1) (corrispondente alla coppia di strategie (e1, e1)) e insta-

bile per ogni scelta dei parametri;

• (1, 0) (corrispondente a (e1, e2)) e asintoticamente stabile nel caso 5

(come gia sappiamo), e un punto di sella nei casi 1,3 e 6, ed e instabile

nei casi 2 e 4;

• (0, 1) (corrispondente a (e2, e1)) e, come gia osservato, asintoticamente

stabile nei casi 2 e 4; e invece un punto di sella negli altri casi;

• (1, 1) (corrispondente a (e2, e2))e asintoticamente stabile nei casi 4 e

6, un punto di sella nei casi 2, 3 e 5, instabile nel caso 1.

Per quanto riguarda il punto (x, y) (corrispondente a (x,y)), abbiamo gia

detto che non puo essere asintoticamente stabile, tuttavia possiamo dimo-

strare che e stabile nel caso 3, verificando che la funzione

V (p, q) = b1 ln p+b2 ln(1−p)−a1 ln q−a2 ln(1−q)−c, c tale che V (x, y) = 0

(3.2)

e di Lyapunov non stretta per (x, y).

Proposizione 3.1. Il punto (x, y) nel caso 3 e un punto di equilibrio stabile

per la dinamica della replicazione.

Dimostrazione. Per costruzione, V (x, y) = 0. Per mostrare che V (p, q) > 0

per ogni (p, q) 6= (x, y), verifichiamo che V abbia un minimo stretto in (x, y).

Con un semplice calcolo si verifica che le ∂V (p,q)∂p e ∂V (p,q)

∂q si annullano in

(x, y). La matrice Hessiana risulta:

H =

−( b1p2 + b2(1−p)2

)0

0(a1q2

+ a2(1−q)2

) ;

essendo definita positiva (H11 > 0, H11H22 > 0), V ha un minimo in (x, y).

Sia ora B una palla aperta nel piano, che contiene (x, y). Dobbiamo veri-

ficare che dV (p,q)dt ≤ 0 per ogni (p, q) ∈ B − (x, y) e che dV (x,y)

dt = 0. Si

trova

dV (p, q)

dt= p(1− p)(a1 − q(a1 + a2))

b1(1− p)− b2pp(1− p)

+

+ q(1− q)(b1 − p(b1 + b2))−a1(1− q) + a2q

q(1− q)= 0

per ogni (p, q) 6= (x, y). Possiamo quindi concludere che, per il caso 3, V e

una funzione di Lyapunov non stretta per (x, y) che, pertanto, e stabile (ma

non asintoticamente).

Page 65: Dinamiche Evolutive ed Equilibri Correlati

3.3. ALTRE DINAMICHE ED ESEMPI 65

Da tutte queste considerazioni, si possono trarre numerose conclusioni.

Abbiamo visto che, se il costo per imparare la lingua del paese ospitante e

basso e non c’e nessuna prevenzione (da parte dello stato) contro il com-

portamento aggressivo dei cittadini (caso 1), man man nel tempo entrambe

le popolazioni tendono a diventare monomorfe, ossia ad usare ciascuna una

sola strategia. In particolare, in questa situazione, i cittadini tendono a

diventare accoglienti e gli immigrati tendono ad integrarsi completamente.

Cio accade piu facilmente quando gli immigrati provengono da un paese di

cultura molto simile a quella del paese ospitante.

Nel caso in cui il costo per l’integrazione e molto alto (caso 5), di nuovo si

ha un’evoluzione verso popolazioni monomorfe dove pero i cittadini si com-

portano tutti in modo ostile e gli immigrati non si integrano.

Se, invece, il costo per l’integrazione non e ne troppo alto ne troppo basso

(caso 3), nel tempo entrambe le popolazioni rimangono polimorfe, e l’uso di

una strategia o l’altra ha un andamento oscillatorio di generazione in gene-

razione.

Nelle situazioni in cui si puo prevenire un atteggiamento ostile da parte dei

cittadini (a1 < 0), a meno che il costo per l’integrazione sia basso (caso

2), gli immigrati non si integrano, anche se la popolazione locale tende ad

abbandonare le ostilita nei loro confronti (casi 4 e 6). Per esempi storici e

di attualita, si consulti [1].

3.3 Altre Dinamiche ed Esempi

Consideriamo la dinamica definita dalla (2.16). Ricordiamo che, per k →0, viene approssimata la dinamica della replicazione, mentre per k → +∞si ottiene la dinamica di risposta ottima. Scriviamo la dinamica del gioco:

p = p(1− p)(eka1(1−q) − eka2q

)q = q(1− q)

(ekb1(1−p) − ekb2p

) (3.3)

Come ci aspettiamo dal teorema 2.9, i punti di equilibrio del sistema sono

gli stessi della dinamica della replicazione. Nelle figure seguenti mostriamo

delle simulazioni dei vari casi, in blu sono le traiettorie del sistema (3.3) con

k = 1, in verde quelle del sistema della replicazione. I parametri utilizzati

sono i seguente: fissato (1− α)f(P ) = 1.5, per avere a1 > 0 abbiamo scelto

f(X) = 0.6 e per a1 < 0 f(X) = 2. Nei casi in cui b1 > 0 e b2 < 0 sono

stati fissati f(K) = 0.5 e f(c) = 0.4. Per avere b1 < 0 e b2 < 0, f(K) = 0.2

e f(c) = 0.55 e per b1 < 0 e b2 > 0, f(K) = 0.2 e f(c) = 1.8.

Page 66: Dinamiche Evolutive ed Equilibri Correlati

66 CAPITOLO 3. UN’APPLICAZIONE

Figura 3.1: Caso 1 Figura 3.2: Caso 2

Figura 3.3: Caso 3 Figura 3.4: Caso 4

Figura 3.5: Caso 5 Figura 3.6: Caso 6

Page 67: Dinamiche Evolutive ed Equilibri Correlati

Capitolo 4

Dinamica ed Equilibri

Correlati

In questo capitolo, seguendo [17] e [18], introduciamo una famiglia di

giochi simmetrici 4×4, ottenuti aggiungendo una strategia ad un gioco RPS,

e studiamo nel dettaglio le orbite della dinamica della replicazione. Vedremo

che, a partire da un insieme aperto di condizioni iniziali, tutte le strategie

usate in equilibri correlati vengono eliminate, ovvero la loro frequenza tende

a 0 per t → ∞. Forniremo poi degli esempi, estendendo questo risultato

ad altre dinamiche di gioco. Vedremo infine che nei giochi 2 × 2 cio non si

verifica, anzi, ogni strategia nel supporto di un equilibrio correlato non viene

mai eliminata nella dinamica della replicazione. Per l’estensione ai giochi

3× 3 rimandiamo a [19].

4.1 Dinamica della Replicazione

Per prima cosa dimostreremo che esiste un unico equilibrio correlato per

il gioco RPS (2.22). Successivamente, ci concentreremo sui giochi RPS del

tipo (2.24) e ne studieremo l’estensione 4× 4.

Proposizione 4.1. Ogni gioco RPS ha un unico equilibrio correlato: z⊗z1

(z e dato dall’espressione (2.23) ).

Dimostrazione. Supponiamo che µ sia un equilibrio correlato per (2.22).

Usando la definizione, sappiamo che, per esempio scegliendo i = 1, i = 2, 3,

1 Per x ∈ Sn, x ⊗ x e la distribuzione di probabilita su Sn indotta da x: se x e un

vettore colonna x⊗ x = xxT

67

Page 68: Dinamiche Evolutive ed Equilibri Correlati

68 CAPITOLO 4. DINAMICA ED EQUILIBRI CORRELATI

devono valere le disuguaglianze

− b1µ11 − a2µ12 + (a3 + b3)µ13 ≥ 0, (4.1)

a1µ11 − (a2 + b2)µ12 + b3µ13 ≥ 0. (4.2)

Sommiamo ora le due disequazioni, avendo moltiplicato la (4.1) per a1 e la

(4.2) per b1:

−(a1a2 + a2b1 + b1b2)µ12 + µ13(a1a3 + a1b3 + b1b3) ≥ 0

la quale, ricordando che z = 1Σ(z1, z2, z3) = 1

Σ(a2a3 + a3b2 + b2b3, a1a3 +

a1b3 + b1b3, a1a2 + a2b1 + b1b2) diventa

z2µ13 ≥ z3µ12.

Essendo il gioco simmetrico, sara verificata anche

z2µ31 ≥ z3µ21.

Ripetendo il ragionamento anche per i = 2, i = 1, 3 e i = 3, i = 2, 3 si

ottiene la seguente catena di disuguaglianze

z2µ13 ≥ z3µ12 ≥ z1µ32 ≥ z2µ31 ≥ z3µ21 ≥ z1µ23 ≥ z2µ13

da cui risulta che tutte le disuguaglianze sono uguaglianze.

Scegliendo una costante λ tale che tutti i termini siano uguali a λΣ2 z1z2z3,

si ha che µij = λΣ2 zizj , ∀i 6= j. Dalle (4.1) e (4.2), anche µ11 = λ

Σ2 z21 e,

analogamente, µii = λΣ2 z

2i per ogni i. Dal momento che

∑ij µij = 1, λ = 1

e quindi µ = z⊗ z.

Torniamo ora ai giochi RPS a simmetria ciclica (2.24) a cui aggiungiamo

una strategia per introdurre la famiglia di giochi 4× 4:

Aα =

0 −1 ε −αε 0 −1 −α−1 ε 0 −α

ε−13 + α ε−1

3 + α ε−13 + α 0

, (4.3)

dove ε ∈ (0, 1) e 0 < α < (1− ε)/3.

La strategia d = (1/3, 1/3, 1/3, 0) e il punto di equilibrio per la dinamica

della replicazione che corrisponde all’equilibrio di Nash nel gioco RPS sot-

tostante. Distinguiamo ora i due casi α = 0 ed α > 0:

Page 69: Dinamiche Evolutive ed Equilibri Correlati

4.1. DINAMICA DELLA REPLICAZIONE 69

Caso α = 0. Notiamo che d ed e4 sono equilibri di Nash, infatti:

dTA0d =ε− 1

3≥ xTA0d =

ε− 1

3∀x ∈ S4,

eT4 A0e4 = 0 ≥ xTA0e4 = 0 ∀x ∈ S4.

Inoltre d ed e4 guadagnano sempre lo stesso payoff:

dTA0x = eT4 A0x =ε− 1

3(x1 + x2 + x3) ∀x ∈ S4, (4.4)

cio vuol dire che l’insieme di equilibri di Nash simmetrici e il segmento

E0 = [d, e4], cioe tutte le combinazioni convesse di d ed e4. Notiamo inoltre

che

xTA0e4 = 0 ∀x ∈ S4, (4.5)

osservazione che ci tornera utile in seguito.

Vogliamo ora dimostrare una proprieta fondamentale: ogni strategia che

appartiene all’insieme E0 guadagna meno del payoff medio contro un profilo

della popolazione che non appartenga ad E0:

pTA0x < xTA0x ∀x /∈ E0, ∀p ∈ E0.

Cerchiamo di formalizzare questo risultato:

Lemma 4.2. Per ogni p ∈ E0 e per ogni x 6= e4

pTA0x− xTA0x = −1− ε2

(1− x4)23∑i=1

(xi − 1/3)2 < 0, (4.6)

dove, dato x = (x1, x2, x3, x4), x = (x1, x2, x3), xi = xi/(x1 + x2 + x3).

Dimostrazione. Sia K = pTA0x − xTA0x = (p − x)TA0x. Dal momento

che p ∈ E0, possiamo scriverlo come combinazione convessa di d ed e4 :

p = p4e4 + (1− p4)d . Grazie alla (4.4),

pTA0x = (p4e4 + (1− p4)d)T A0x = dTA0x,

da cui risulta K = (d− x)TA0x.

Sia ora y = (x1, x2, x3, 0), allora x puo essere riscritto come

x = (x1 + x2 + x3)y + x4e4 = (1− x4)y + x4e4.

Applicando questa relazione a K e utilizzando (2.26)

K = (1− x4)(d− x)TA0y.

Notando che d−x = (1−x4)(d−y)+x4(d−e4) ed usando la(4.4) otteniamo

K = (1− x4)2(d− y)TA0y, applicando ora la (2.26) si ha la tesi.

Page 70: Dinamiche Evolutive ed Equilibri Correlati

70 CAPITOLO 4. DINAMICA ED EQUILIBRI CORRELATI

Osservazione 4.1. Dal momento che ogni punto p ∈ E0 e equilibrio di

Nash, nel caso α = 0 non vi sara un unico equilibrio correlato.

Caso α > 0. La strategia mista d non e piu un equilibrio di Nash:

dTAαd =ε− 1

3≤ xTAαd =

ε− 1

3+ αx4 ∀x ∈ S4

D’altra parte, e4 e in questo caso un equilibrio di Nash stretto:

e4Aαe4 = 0 > xAαe4 = −α ∀x ∈ S4.

Proposizione 4.3. Se α > 0, esiste un intorno del gioco con matrice dei

payoff (4.3), in cui ogni gioco ha un unico equilibrio correlato: ν = e4 ⊗ e4

(νij = 0 ∀i, j 6= 4, ν44 = 1).

Dimostrazione. Grazie al teorema 1.4, sappiamo che se vi e un unico equi-

librio correlato nel gioco, ogni gioco in un suo intorno ha un unico equili-

brio correlato con lo stesso supporto. Pertanto e sufficiente dimostrare che

ν = e4 ⊗ e4 e l’unico equilibrio correlato per il gioco (4.3).

Supponiamo per assurdo che esista un equilibrio correlato µ diverso da

ν. Siccome e4 e un equilibrio stretto, deve esistere almeno una coppia

1 ≤ i, j ≤ 3 tale che µij > 0. Definiamo la distribuzione correlata del

RPS sottostante con µ tale che

µij =µijM

1 ≤ i, j ≤ 3

con M =∑3

i,j=1 µij > 0. Vediamo che µ e equilibrio correlato per il gioco

RPS sottostante G: per 1 ≤ i, i′ ≤ 3 risulta ai4 = ai′4 = −α, quindi,

sfruttando il fatto che µ e equilibrio correlato per il gioco 4× 4

3∑j=1

µij[aij − ai′j

]=

3∑j=1

µijM

[aij − ai′j

]=

1

M

4∑j=1

µij[aij − ai′j

]≥ 0.

Questa disequazione, insieme a quella simmetrica, implica che µ e un equi-

librio correlato per G. Per la proposizione 4.1, inoltre, deve essere l’unico

e tale che µ = z ⊗ z, ovvero µij = 1/9 ∀1 ≤ i, j ≤ 3, quindi µij = M/9.

Questo, unito al fatto che a44 > ai4 per ogni 1 ≤ i ≤ 3, implica che

4∑j=1

µij [aij − a4j ] ≤3∑j=1

µij [aij − a4j ] = −Mα

3< 0, 1 ≤ i ≤ 3.

Cio contraddice l’ipotesi che µ sia equilibrio correlato.

Page 71: Dinamiche Evolutive ed Equilibri Correlati

4.1. DINAMICA DELLA REPLICAZIONE 71

Ci prefiggiamo ora l’obbiettivo di dimostrare che, se α > 0 e abbastanza

piccolo, l’insieme

Γ := x ∈ S4 : x4 = 0, x1x2x3 = 0 (4.7)

attrae tutte le orbite vicine; cio significa non solo che x4 → 0 per t →∞ ma anche che, per t → ∞ il gioco 4 × 4 si comporta come il gioco

RPS sottostante (2.24). A tal scopo e utile dimostrare il seguente risultato,

secondo il quale e possibile decomporre la dinamica della replicazione in

intS4 come un andamento crescente/decrescente in x4 ed un movimento

spiraleggiante verso l’esterno intorno al segmento E0.

Innanzitutto, notiamo che per ogni x ∈ E0, (Aαx)1 = (Aαx)2 = (Aαx)3;

cio comporta che E0 e globalmente invariante: sia φ(x, t) una soluzione al

tempo t delle equazioni della replicazione con condizione iniziale x e sia

φ(E0, t) = φ(x, t),x ∈ E0, allora ∀t ∈ R, φ(E0, t) = E0.

Ricordiamo inoltre che A e la matrice del gioco RPS sottostante e che, per

x 6= e4, x = (x1, x2, x2).

Lemma 4.4. Sia x(·) una soluzione delle equazioni della replicazione (2.8),

con x(0) 6= e4. Per ogni 1 ≤ i ≤ 3

˙xi = (1− x4)xi

[(Ax)i − xTAx

]. (4.8)

Dimostrazione. Consideriamo xi > 0, 1 ≤ i ≤ 3 (se xi = 0 la (4.8) e

banalmente verificata); per ogni 1 ≤ j ≤ 3 tale che xj > 0

˙xixi−

˙xjxj

=d

dtln

(xixj

)=

d

dtln

(xixj

)=xixi− xjxj

= (Aαx)i − xTAαx− (Aαx)j − xTAαx = (Aαx)i − (Aαx)j =

= (x1 + x2 + x3) (Ax)i − (x1 + x2 + x3) (Ax)j = (1− x4)[(Ax)i − (Ax)j

].

Moltiplicando da entrambe le parti per xj > 0 e sommando sui j tali che

xj > 0 si ha la (4.8).

Questo lemma formalizza quanto detto precedentemente: a seguito di un

cambio di velocita, x segue la dinamica della replicazione del gioco con ma-

trice dei payoff A, cioe si avvicina al bordo del simplesso S3 con andamento

spiraleggiante.

Vogliamo ora ricavare un risultato analogo alla proposizione 2.15 per x. Ri-

cordiamo che, per y ∈ S3, avevamo definito la funzione V (y) = (y1y2y3)1/3.

Per x ∈ S4/e4, definiamo V (x) := V (x):

V (x) = (x1x2x3)1/3 =(x1x2x3)1/3

x1 + x2 + x3. (4.9)

Page 72: Dinamiche Evolutive ed Equilibri Correlati

72 CAPITOLO 4. DINAMICA ED EQUILIBRI CORRELATI

Corollario 4.5. Sia x(·) una soluzione delle equazioni della replicazione

(2.8)in S4, con x(0) 6= e4. La funzione v(t) := V (x(t)) soddisfa

v(t) = −v(t)f(x(t)) con f(x) = (1− x4)

(1− ε

2

) 3∑i=1

(xi− 1/3)2. (4.10)

Dimostrazione. Sia τ ∈ < e y(·) ∈ S3 soluzione delle equazioni della replica-

zione (2.8) in S3 per il gioco RPS, con condizione iniziale y(0) = x(τ). Sia

v(t) = V (y(t)). Dal lemma precedente abbiamo ∀1 ≤ i ≤ 3

˙xi(τ) = (1− x4(τ))xi(τ)[(Ax(τ))i − x(τ)TAx(τ)

]=

= (1− x4(τ))yi(0)[(Ay(0))i − y(0)TAy(0)

]=

= (1− x4(τ))yi(0)

cioe ˙x(τ) = (1− x4(τ))y(0), quindi, con un cambio di variabile,

v(τ) =dV (x(t))

dt|t=τ = (1− x4(τ))

dV (y(t))

dt|t=0 = (1− x4(τ)) ˙v(0).

Da (2.27) sappiamo inoltre che

˙v(0) = −v(0)

(1− ε

2

) 3∑i=1

(yi(0)− 1/3)2 ,

a questo punto sostituendo questa espressione nella precedente, yi(0) con

xi(τ) e v(0) con v(τ) si ha la tesi.

Osserviamo che v(t) e non negativa (perche xi ≥ 0∀i,∀t) e che la funzio-

ne f e positiva ovunque tranne nell’intervallo E0 dove si annulla. Quindi V

decresce lungo tutte le traiettorie interne, eccetto quelle che cominciano, e

quindi rimangono, nell’intervallo (d, e4).

Abbiamo quindi dimostrato che vi e un comportamento decrescente delle

traiettorie lungo la componente del simplesso e4. Vogliamo costruire ora una

funzione di Lyapunov per l’insieme Γ, per dimostrare che attrae le orbite

vicine. A tale proposito, introduciamo la funzione candidata

W (x) =

max(x4, 3V (x)) se x 6= e4

1 se x = e4

, (4.11)

ricordiamo che V (x) e data dalla (4.9). Cosı definita, W e continua, ha

valore massimo 1 sul segmento E0, dove V definita su S4/e4 raggiunge il

Page 73: Dinamiche Evolutive ed Equilibri Correlati

4.1. DINAMICA DELLA REPLICAZIONE 73

suo massimo 1/3, e ha valore minimo 0 su Γ.

Sia δ ≥ 0, consideriamo l’insieme compatto

Kδ := x ∈ S4,W (x) ≤ δ, (4.12)

notiamo che K0 = Γ e K1 = S4.

Proposizione 4.6. Sia 0 < δ < 1. Esiste γ tale che, per ogni gioco (4.3)

con 0 < α < γ e per ogni condizione iniziale x(0) ∈ Kδ

W (x(t)) ≤W (x(0)) e−γt ∀t ≥ 0.

In particolare, l’insieme Γ attrae tutte le soluzioni che partono in Kδ

Dimostrazione. E0 ∩ Kδ = ∅, poiche E0 = x : W (x) = 1 e Kδ = x :

W (x) ≤ δ, δ < 1. Applichiamo la (4.6) scegliendo p = e4, ne risulta che

(A0x)4−xTA0x < 0. Inoltre, per ogni x ∈ Kδ, la funzione f definita in (4.10)

e strettamente positiva (perche si annulla solo in E0 che non si interseca con

Kδ). Per la compattezza di Kδ, grazie al teorema di Weierstrass possiamo

trovare una costante γ > 0 tale che

maxx∈Kδ

(A0x)4 − xTA0x,−f(x)

≤ −3γ < 0. (4.13)

Fissiamo ora α ∈ (0, γ) e consideriamo le equazioni della replicazione per

il gioco con matrice dei payoff Aα. Per ogni x ∈ S4 e per ogni 1 ≤ i ≤ 4,

|[(Aα −A0) x]i| ≤ α. Da questa e dalla (4.13) segue

(Aαx)4 − xTAαx ≤ 2α+ (A0x)4 − xTA0x ≤ 2α− 3γ ≤ −γ

Dal momento che x4 = x4

((Aαx)4 − xTAαx

), si ottiene che

x(t) ∈ Kδ ⇒ x4 ≤ −γx4(t). (4.14)

Utilizzando il corollario precedente e la (4.13) risulta

x(t) ∈ Kδ ⇒ v(t) ≤ −3γv(t) ≤ −γv(t). (4.15)

Sia w(t) := W (x(t)) = max(x4(t), 3v(t)). Dal momento che x4(t) e v(t)

decrescono debolmente ((4.14) e (4.15)), ne segue che, se x(t) ∈ Kδ, anche

w decresce debolmente. Cio implica che Kδ e invariante nel tempo percio

le (4.14) e (4.15) valgono per ogni condizione iniziale x(0) ∈ Kδ e per ogni

t ≥ 0.

Ne segue che, per ogni t ≥ 0, x4(t) ≤ x4(0)e−γt e v(t) ≤ v(0)e−γt e quindi

anche w(t) ≤ w(0)e−γt.

Page 74: Dinamiche Evolutive ed Equilibri Correlati

74 CAPITOLO 4. DINAMICA ED EQUILIBRI CORRELATI

Abbiamo quindi dimostrato che se scegliamo α > 0 sufficientemente

piccolo, il gioco (4.3) ha un’unica strategia usata nell’equilibrio correlato, e4,

ma x4(t)→ 0 per un insieme aperto di condizioni iniziali, ovvero la strategia

tende ad essere abbandonata per t→∞. In particolare abbiamo visto anche

l’andamento qualitativo delle orbite che decrescono lungo il segmento E0 con

movimento spiraleggiante, avvicinandosi al bordo del simplesso S3 denotato

con Γ.

Ogni gioco del tipo (4.3), con ε sufficientemente piccolo, e un caso particolare

del gioco con payoff

A =

a1 b2 c3 d1

c1 a2 b3 d2

b1 c2 a3 d3

f1 f2 f3 a4

(4.16)

che soddisfa

bi < ai < ci, i = 1, 2, 3,3∏i=1

(ai − bi) >3∏i=1

(ci − ai) (4.17)

e

fi < ai, i = 1, 2, 3 (4.18)

Grazie alla (4.17), il gioco ristretto alle sole prime tre strategie e il gioco

Carta-Sasso-Forbice (RPS). Inoltre, insieme alla (4.18), implica l’esistenza

un ciclo di risposte ottime Γ := e1 → e2 → e3 → e1. L’estensione

dei risultati visti a questa classe piu generale di giochi non e difficile da

dimostrare, per i dettagli si rimanda a [19].

4.2 Altre Dinamiche

Il risultato della sezione precedente, di fatto, vale anche per dinamiche di

gioco diverse da quella della replicazione. Viossat, nella sua tesi di dottora-

to ([19]), dimostra questa estensione per le dinamiche di risposta ottima, di

Brown-von Neumann-Nash e a payoff monotono. In questa sezione vogliamo

analizzare con l’ausilio di Matlab le dinamiche della replicazione e a payoff

monotono (2.16) ( che ricordiamo approssima la dinamica della replicazione

per k → 0 e la dinamica di risposta ottima per k →∞), per verificare i risul-

tati teorici. Scriviamo le dinamiche di gioco: la dinamica della replicazione

Page 75: Dinamiche Evolutive ed Equilibri Correlati

4.2. ALTRE DINAMICHE 75

risultax1 = x1

(−x2 + εx3 − αx4 − (ε− 1)(x1x2 + x1x3 + x2x3)− ε−1

3 x4(1− x4

)x2 = x2

(−x3 + εx1 − αx4 − (ε− 1)(x1x2 + x1x3 + x2x3)− ε−1

3 x4(1− x4

)x3 = x3

(−x1 + εx2 − αx4 − (ε− 1)(x1x2 + x1x3 + x2x3)− ε−1

3 x4(1− x4

)x4 = x4

((ε−1

3 + α)

(1− x4)− (ε− 1)(x1x2 + x1x3 + x2x3)− ε−13 x4(1− x4

) ;

la (2.16) e altrettanto facilmente ricavabile. I punti di equilibrio delle due

dinamiche sono gli stessi: i vertici del simplesso S4 ed il punto d. Riportiamo

di seguito le figure ottenuto effettuando alcuni esperimenti numerici. Le

orbite in blu sono quelle della dinamica della replicazione, quelle in rosso

sono della dinamica (2.16), avendo fissato k = 1.

Page 76: Dinamiche Evolutive ed Equilibri Correlati

76 CAPITOLO 4. DINAMICA ED EQUILIBRI CORRELATI

Figura 4.1: ε = 23 , α = 0.01 Figura 4.2: ε = 2

3 , α = 0.001

Figura 4.3: ε = 45 , α = 0.01 Figura 4.4: ε = 4

5 , α = 0.001

4.3 Giochi 2× 2

In questa sezione studiamo la dinamica della replicazione per giochi 2×2,

simmetrici e asimmetrici, per verificare che, a differenza dei giochi n × n

con n > 3, le strategie nel supporto di un equilibrio correlato non vengono

eliminate. Innanzitutto ricordiamo che l’insieme degli equilibri correlati e un

insieme compatto e convesso in uno spazio Euclideo e che contiene l’insieme

degli equilibri di Nash. Per i giochi 2 × 2 l’insieme degli equilibri correlati

si riduce all’unico equilibrio di Nash sia che esso sia in strategie pure sia in

miste, mentre se il gioco ha tre equilibri di Nash, due in strategie pure e uno

in miste, esistono equilibri correlati che non sono di Nash. Per una prova si

veda [11].

Page 77: Dinamiche Evolutive ed Equilibri Correlati

4.3. GIOCHI 2× 2 77

4.3.1 Giochi Asimmetrici

Consideriamo un generico gioco con bimatrice dei payoff

(A,B) =

[(a11, b11) (a12, b12)

(a21, b21) (a22, b22)

]. (4.19)

Lemma 4.7. L’insieme degli equilibri correlati di un gioco con bimatrice

dei payooff (A,B) non cambia se la matrice A viene moltiplicata per una

costante positiva o se un vettore riga fissato viene aggiunto ad ogni riga di A.

Anche la matrice B puo essere moltiplicata per ogni costante positiva oppure

un qualsiasi vettore colonna fissato puo essere aggiunto ad ogni colonna B

senza cambiare l’insieme degli equilibri correlati.

Dimostrazione. Si verifica facilmente che, con le modifiche proposte, il si-

stema di disuguaglianze da soddisfare e equivalente.

Grazie a questo risultato possiamo, senza perdita di generalita, conside-

rare la bimatrice

(A,B) =

[(0, 0) (α1, β1)

(α2, β2) (0, 0)

], (4.20)

dove αi = aij − ajj e βi = bij − bii. Analizziamo tre casi:

1. il gioco ha un unico equilibrio di Nash in strategie miste;

2. il gioco ha un unico equilibrio di Nash in strategie pure;

3. il gioco ha due equilibri di Nash in strategie pure ed uno in strategie

miste.

Caso 1

Si tratta del caso in cui, per esempio, α1, α2 > 0 e β1, β2 < 0 oppure

α1, α2 < 0 e β1, β2 > 0. L’unico equilibrio di Nash e (p,q) dove p =(β2β1β2

, β1β1+β2

)e q =

(α1

α1+α2, α2α1+α2

). Dai teoremi della sezione 2.4 sappiamo

che, avendo un unico equilibrio di Nash in strategie miste esso non puo essere

ESS e pertanto neanche asintoticamente stabile. L’unica possibilita che le

strategie utilizzate non vengano eliminate nella dinamica della replicazione

e che l’equilibrio di Nash sia un punto di equilibrio stabile. Sulla scia della

proposizione 3.1 e facile verificare che la funzione

L(x, y) = β2 ln p+ β1 ln(1− p)− α1 ln q − α2 ln(1− q)− c

e funzione di Lapunov non stretta per (p,q), garantendo cosı la stabilita del

punto di equilibrio.

Page 78: Dinamiche Evolutive ed Equilibri Correlati

78 CAPITOLO 4. DINAMICA ED EQUILIBRI CORRELATI

Osservazione 4.2. La funzione L e di Lyapunov nel caso α1, α2 > 0 e

β1, β2 < 0; per l’altro caso basta invertirne il segno.

Abbiamo quindi visto che in questo caso nessuna strategia pura usata

nell’equilibrio correlato viene eliminata nella dinamica della replicazione.

Caso 2

In questo caso si ha una strategia dominata (almeno debolmente) ed un uni-

co equilibrio di Nash in strategie pure. Dai risultati visti, se la dominazione

e stretta, le strategie usate nell’equilibrio di Nash sono ESS e, conseguente-

mente, il punto di equilibrio corrispondente e asintoticamente stabile nella

dinamica della replicazione. Se invece la dominazione e debole, come ac-

cade per esempio se α1 > 0, α2, β1 < 0 e β2 = 0 con equilibrio di Nash

(e1, e1), le strategie usate in esso non possono essere ESS ed il corrispon-

dente punto di equilibrio (1, 1) non e asintoticamente stabile nella dinamica

della replicazione. Calcolando pero la matrice Jacobiana si ottiene, in questo

caso,

J(e1, e1) =

[α2 0

0 0

]da cui risulta λ1 = α2 < 0 e λ2 = 0, per cui possiamo concludere che il

punto (1, 1) e almeno stabile. In tutti gli altri casi in cui si ha dominanza

debole si arriva ad una conclusione analoga.

Caso 3

Si tratta del caso banale, essendo ogni strategia pura nel supporto di ogni

equilibrio correlato. Infatti i due equilibri di Nash in strategie pure so-

no stretti, pertanto le strategie in essi utilizzate sono ESS ed i corrispon-

denti punti di equilibrio sono asintoticamente stabili nella dinamica della

replicazione.

4.3.2 Giochi Simmetrici

Dal momento che la teoria per i giochi asimmetrici differisce in alcuni

risultati da quella per i giochi simmetrici, analizziamo brevemente cosa suc-

cede agli equilibri correlati nella dinamica della replicazione anche per questi

ultimi.

Consideriamo un gioco con matrice dei payoff

A =

[a11 a12

a21 a22

];

Page 79: Dinamiche Evolutive ed Equilibri Correlati

4.3. GIOCHI 2× 2 79

possiamo ricondurci al gioco

A =

[α1 0

0 α2

],

con α1 = a11 − a21 e α2 = a22 − a12. A questo punto e facile trarre le

conclusioni, in virtu dei risultati ottenuti nell’esempio 2.3.

• Categorie I e IV: vi e un unico equilibrio di Nash stretto pertanto

la strategia usata e ESS ed il punto di equilibrio corrispondente nella

dinamica della replicazione e asintoticamente stabile. Cio significa

che le orbite della dinamica della replicazione convergono verso l’unico

equilibrio correlato;

• Categorie II e III: si tratta nuovamente di casi banali essendo l’in-

sieme degli equilibri correlati l’inviluppo convesso dell’insieme degli

equilibri di Nash. Tuttavia per i giochi che rientrano nella Categoria

II le orbite della dinamica della replicazione convergono verso i punti

di equilibrio corrispondenti agli equilibri di Nash in strategie pure (es-

sendo stretti e quindi ESS), mentre per la Categoria III e l’equilibrio

in strategie miste ad essere asintoticamente stabile. In entrambi i casi

pero e valido il risultato che ci siamo proposti di verificare.

Page 80: Dinamiche Evolutive ed Equilibri Correlati

Conclusioni

In questo lavoro e stata studiata la teoria evolutiva dei giochi, a parti-

re dalla teoria dei giochi classica combinata con i risultati principali della

teoria dei sistemi dinamici. Il concetto chiave e quello di stabilita di una

strategia all’interno di una popolazione, intesa come resistenza all’introdu-

zione o meglio, all’invasione di nuove strategie. La sola nozione di ESS non

fornisce alcuna indicazione di come la ripetizione di un gioco abbia portato

ad essa ma questo problema e ovviato dall’introduzione di una dinamica di

gioco. Studiandone le orbite infatti, e possibile, a partire da ogni condizione

iniziale, seguire l’evoluzione delle frequenze delle strategie. Abbiamo intro-

dotto quindi diverse dinamiche di gioco possibili, evidenziandone analogie e

differenze. Si e posta una particolare attenzione alle relazioni tra equilibri

di Nash ed equilibri correlati da una parte, ed ESS e punti di equilibrio della

dinamica di gioco dall’altra. Il risultato di Viossat studiato nella prima par-

te del capitolo 4 e indicativo del fatto che e molto difficile poter generalizzare

ad ogni gioco e ad ogni dinamica la teoria proposta, specialmente quando

i giochi considerati sono di dimensione maggiore di tre. Ricordiamo infatti

che tale risultato e stato provato per una famiglia di giochi riconducibili ad

un gioco RPS generalizzato del tipo (2.22) e che, pertanto, possiede alcune

comode proprieta dei giochi a somma zero. Inoltre, ricordiamo che il gioco

considerato ha un unico equilibrio correlato. Potrebbe quindi essere interes-

sante estendere i risultati ad una piu vasta classe di giochi, rilassando alcune

delle ipotesi.

Al di la di questo risultato particolare, comunque, in generale e stata riscon-

trata una certa coerenza tra teorie dei giochi classica ed evolutiva, nel senso

che, nonostante non si faccia alcuna ipotesi sulla razionalita dei giocatori,

alcuni comportamenti sembrano fare parte di un bagaglio genetico o di un

certo ‘buon senso’ insito in ogni individuo. Abbiamo infatti verificato che le

strategie strettamente dominate, eliminate per razionalita nella teoria clas-

sica, vengono eliminate anche nella dinamica di gioco, almeno per quanto

riguarda le dinamiche studiate in questo lavoro. Un ulteriore spunto per

80

Page 81: Dinamiche Evolutive ed Equilibri Correlati

CONCLUSIONI 81

studi futuri potrebbe pertanto essere quello di estendere il discorso a dina-

miche che non soddisfano questa proprieta, confrontandole con quelle che

invece la soddisfano.

Abbiamo infine concluso che le strategie usate negli equilibri di Nash nei

giochi 2× 2 non vengono mai eliminate, ovvero la relazione tra teoria clas-

sica e teoria evolutiva dei giochi e molto piu evidente che per i giochi di

dimensione maggiore.

Page 82: Dinamiche Evolutive ed Equilibri Correlati

Bibliografia

[1] Andre Barreira da Silva Rocha, An Evolutionary Game Approach to the

Issues of Migration, Nationalism, Assimilation and Enclaves. (2010),

University of Essex, Department of Economics.

[2] Timothy N. Cason, Tridib Sharma, Recommended Play and Correla-

ted Equilibria: An Experimental Study. (2006) http://www.krannert.

purdue.edu/faculty/cason/papers/corr_equil_reco.pdf.

[3] Vito Fragnelli, Teoria dei Giochi. (2010-2011), http://people.

unipmn.it/fragnelli/dispense/TdGB.PDF.

[4] Daniel Friedman, Evolutionary Games in Economics. Econometrica,

Vol. 59, No. 3 (May, 1991), 637-666

[5] Josef Hofbauer, Heteroclinic Cycles in Ecological Differential Equations.

(1994), Tatra Mountains Mathematical Publications 4, 105-116.

[6] Josef Hofbauer, Karl Sigmund, Evolutionary Game Dynamics. Bulletin

of the American Mathematical Society 40, (2003), 479-511.

[7] Josef Hofbauer, Karl Sigmund, Evolutionary Games and Population

Dynamics. Cambridge University Press 1988.

[8] Roberto Lucchetti,A Primer in Game Theory. (2011), Esculapio.

[9] C.D. Pagani, Sandro Salsa, Analisi Matematica volume 2. (2006),

Zanichelli.

[10] Fioravante Patrone, Paola Radrizzani, Equilibri Correlati. (2006),

http://www.fioravante.patrone.name/mat/TdG/DRI/equilibri_

correlati/equilibri_correlati.pdf.

[11] Ronald Peteers, Jon Potters, On the Structure of the Set of Correla-

ted Equilibria in two-by-two Bimatrix Games, (1999), http://ideas.

repec.org/p/dgr/kubcen/199945.html.

82

Page 83: Dinamiche Evolutive ed Equilibri Correlati

BIBLIOGRAFIA 83

[12] William H. Sandholm, Deterministic Evolutionary Dynamics. (2005),

New Palgrave Dictionary of Economics, 2nd edition

[13] William H. Sandholm, Evolutionary Game Theory. (2007), University

of Wisconsin.

[14] William H. Sandholm, Population Games and Evolutionary Dynamics.

(2008), MIT Press.

[15] J. Maynard Smith, Evolution and the Theory of Games. Cambridge

Univeristy Press 1982.

[16] J. Maynard Smith, G.R. Price, The Logic of Animal Conflict. (1973),

Nature Vol. 246 (5427).

[17] Yannick Viossat, The replicator dynamics does not lead to correlated

equilibria. Games and Economic Behavior 59 (2007) 397-407.

[18] Yannick Viossat, Evolutionary dynamics may eliminate all strategies

used in correlated equilibrium. Mathematical Social Sciences 56, 1

(2008) 27-43.

[19] Yannick Viossat, Correlated equilibria, evolutionary games and po-

pulation dynamics. (2005) PhD dissertation. Ecole Polytechnique,

Paris.

[20] Jorgen W. Weibull, Evolutionary Game Theory. Cambridge: MIT Press

1995.

[21] E.C. Zeeman, Population Dynamics from Game Theory. (1980),

Lecture Notes in Math., vol. 819. Springer, pp. 471-497