Teoria dei Giochi: lezione del 27 Marzo 2017

Teoria dei Giochi: lezione del 27 Marzo 2017

Chiara Mocenni

Corso di Teoria dei Giochi e Giochi Evolutivi

Giochi simmetrici a due giocatori

Un gioco `e simmetrico quando i due giocatori hanno lo stesso guadagno in condizioni analoghe.

Un gioco simmetrico coinvolge dunque due giocatori con lo stesso numero di strategie e la funzione payoff di ogni strategia `e indipendente dalla postazione del giocatore dalla quale viene giocata.

Richiedere l’equivalenza delle funzioni payoff delle strategie pure `e equivalente a richiedere che la matrice dei payoff del secondo giocatore sia la trasposta della matrice dei payoff del primo, ovvero: B = A^T.

Giochi simmetrici a due giocatori

Utilizzando la funzione di payoff π(x , y ) = x^TAy , si ha che:

π1(x , y ) = π(x , y )

π2(x , y ) = x^TBy = y^TB^Tx = y^TAx = π(y , x ).

Con K = {1, 2, ..., k} indichiamo l’insieme delle strategie pure Con x ∈ ∆ e y ∈ ∆ indichiamo le strategie miste del primo e del secondo giocatore, dove ∆ = {x ∈ R₊^k :P

i ∈Kxi = 1}, mentre Θ = ∆².

L’insieme di best reply β(z) `e rispetto ad una strategia z ∈ ∆ ed `e lo stesso per entrambi i giocatori:

β(z) = {x ∈ ∆ : π(x , z) ≥ π(y , z) ∀y ∈ ∆}.

Equilibri di Nash simmetrici

Una coppia di strategie (x , y ) ∈ Θ = ∆² costituisce un equilibrio di Nash, (x , y ) ∈ Θ^NE, se e solo se x ∈ β(y ) e y ∈ β(x ). Se x = y , l’equilibrio (x , y ) si dice `e simmetrico.

Il sottoinsieme di strategie x ∈ ∆ che sono in equilibrio con se stesse `e:

∆^NE = {x ∈ ∆ : (x , x ) ∈ Θ^NE}

Non `e detto che gli equilibri di Nash di un gioco simmetrico siano simmetrici, ma ogni gioco simmetrico ha almeno un equilibrio di Nash simmetrico.

Theorem

Per ogni gioco simmetrico finito a due giocatori, ∆^NE 6= ∅.

Classificazione dei giochi simmetrici 2 x 2

In questa sezione analizziamo i giochi in cui i giocatori hanno solamente due strategie pure a disposizione. Considerando la matrice dei payoff di un generico gioco simmetrico 2 × 2:

A =

 a11 a12

a21 a22



Sottraendo a₂₁dalla prima colonna e a₁₂dalla seconda, otteniamo:

A⁰ =

 a₁₁− a₂₁ 0 0 a22− a₁₂



Si ottiene cos`ı una matrice simmetrica e quindi un gioco totalmente simmetrico, con matrice dei payoff:

A⁰=

 a1 0 0 a2



Con a₁ = a₁₁− a₂₁ e a₂= a₂₂− a₁₂.

Rappresentazione grafica

La matrice ottenuta, per ogni gioco simmetrico 2 × 2, `e identificata da un punto a = (a<sub>1</sub>, a<sub>2</sub>) ∈ R<sup>2</sup>. Questo punto apparterr`a ad uno dei quadranti del piano cartesiano, consentendoci di identificare la categoria alla quale appartiene il gioco.

Calcolo degli equilibri di Nash simmetrici

Se x ∈ ∆^NE (x `e un equilibrio di Nash simmetrico), allora x ∈ β(x ). In altri termini:

π(x , x ) ≥ π(y , x ) ∀y ∈ ∆, ovvero

x^TAx ≥ y^TAx ∀y ∈ ∆.

E possibile riscrivere la precedente equazione usando le` sommatorie:

k

X

i =1

x_i[Ax ]_i ≥

k

X

i =1

y_i[Ax ]_i ∀y ∈ ∆, (1) dove [Ax ]_i indica l’i -esima componente del vettore Ax .

Teorema per gli equilibri puri

Theorem

Sia x una strategia pura (x = e^h). Se [Ax ]_h≥ [Ax]_i ∀i 6= h, allora x ∈ ∆^NE.

Dimostrazione.

Sia M = [Ax ]_h. Si ha che:

k

X

i =1

x_i[Ax ]_i = x_h[Ax ]_h= M, e

k

X

i =1

y_i[Ax ]_i = y_h[Ax ]_h+

k

X

i =1,i 6=h

y_i[Ax ]_i = y_hM +

k

X

i =1,i 6=h

y_i[Ax ]_i.

... continua

Poich`e M ≥ [Ax ]_i ∀i 6= h, allora:

k

X

i =1,i 6=h

y_i[Ax ]_i ≤

k

X

i =1,i 6=h

y_iM = (1 − y_h)M.

Dunque:

Pk

i =1x_i[Ax ]_i = M, e Pk

i =1y_i[Ax ]_i ≤ M.

Da cui segue che

k

X

i =1

x_i[Ax ]_i ≥

k

X

i =1

y_i[Ax ]_i ∀y ∈ ∆.

Teorema per gli equilibri misti

Theorem

Sia x una strategia appartenente a int∆, cio`e una strategia mista tale per cui xi > 0 ∀i . Se [Ax ]i = [Ax ]j ∀i , j, allora x ∈ ∆^NE. Dimostrazione.

Poniamo M = [Ax ]_i ∀i . Allora::

k

X

i =1

xi[Ax ]i =

k

X

i =1

xiM = M

k

X

i =1

xi = M · 1 = M,

e k

X

i =1

y_i[Ax ]_i =

k

X

i =1

y_iM = M

k

X

i =1

y_i = M · 1 = M.

... continua

Dunque, la 6 vale sempre in maniera non stretta, ovvero:

k

X

i =1

xi[Ax ]i =

k

X

i =1

yi[Ax ]i ∀y ∈ ∆.

Questo significa x `e un equilibrio di Nash simmetrico. Inoltre, tale equilibrio `e non stretto.

Teorema per gli equilibri puri/misti

Theorem

Sia x una strategia mista con un’unica componente nulla (x_h= 0, x_i > 0 ∀i 6= h). Se [Ax ]_i = [Ax ]_j ∀i 6= h, j 6= h, e [Ax ]_i ≥ [Ax]_h ∀i 6= h allora x ∈ ∆^NE.

Dimostrazione. Poniamo M = [Ax ]_i ∀i 6= h. Allora:

k

X

i =1

xi[Ax ]i =

k

X

i =1

xiM = M

k

X

i =1

xi = M · 1 = M, e

k

X

i =1

yi[Ax ]i =

k

X

i =1,i 6=h

yiM + yh[Ax ]h= M

k

X

i =1,i 6=h

yi + yh[Ax ]h=

= M(1 − y_h) + y_h[Ax ]_h.

... continua

Nella seconda equazione `e stato sfruttato il fatto che

k

X

i =1

y_i = 1 ⇒

k

X

i =1,i 6=h

y_i = 1 − y_h. Per ipotesi, si ha che M ≥ [Ax ]_h. Da cui:

M ≥ [Ax]_h ⇒

y_hM ≥ y_h[Ax ]_h ⇒

yhM + M − M ≥ y_h[Ax ]h ⇒

M − M(1 − y_h) ≥ y_h[Ax ]_h ⇒ M ≥ M(1 − y_h) + y_h[Ax ]_h ⇒

k

X

i =1

xi[Ax ]i ≥

k

X

i =1

yi[Ax ]i ∀y ∈ ∆.

Dunque, poich`e x soddisfa la 6 per ogni y , allora x `e un equilibrio di Nash simmetrico.