Teoria dei Giochi: lezione del 23 Marzo 2017

Teoria dei Giochi: lezione del 23 Marzo 2017

Chiara Mocenni

Corso di Teoria dei Giochi e Giochi Evolutivi

Le funzioni di payoff

In un gioco a due giocatori si introducono delle funzioni di payoff sulla base delle matrici di payoff del gioco assegnate a ciascun giocatore.

Se A ∈ R ^m

^×m

e B ∈ R ^m

^×m

sono le matrici di payoff del giocatore 1 e del giocatore 2, rispettivamente, si hanno 4 casi:

entrambi scelgono strategie pure, uno dei due sceglie una strategia

pure a l’altro una strategia mista, entrambi scelgono strategie

miste.

Entrambi i giocatori scelgono strategie pure

Se il giocatore 1 sceglie la strategia pura i e il giocatore 2 la strategia pura j , il payoff ottenuto dal giocatore 1 ` e:

a i ,j

e il payoff ottenuto dal giocatore 2 ` e:

b _{i ,j}

Un giocatore sceglie una strategia pura e l’altro una mista

Il giocatore 1 sceglie la strategia pura i e il giocatore 2 sceglie la strategia mista x 2 . Il payoff ottenuto dal giocatore 1 ` e:

u _1i =

m

X

j =1

a _ij x _2j

mentre se il giocatore 2 sceglie la strategia pura j e il giocatore 1 la strategia mista x ₁ il payoff ottenuto dal giocatore 2 ` e:

u 2j =

m

X

i =1

b ij x 1i

Entrambi i giocatori scelgono strategie miste

Siano x 1 e x 2 le strategie miste del giocatore 1 e del giocatore 2, rispettivamente. Il giocatore 1 in media guadagna:

π 1 (x 1 , x 2 ) = x ₁ ^T Ax 2

mentre il giocatore 2 in media guadagna

π ₂ (x ₁ , x ₂ ) = x ₁ ^T Bx ₂

I giochi con 2 giocatori e 2 strategie

Consideriamo i giochi a due giocatori e due strategie. I payoff dei 2 giocatori sono rappresentati dalle seguenti matrici:

A =

 a ₁ b ₁ c 1 d 1



, B =

 a ₂ c ₂ b 2 d 2

 . e la relativa bimatrice ` e:

G 2

s1 s2

s1 (a ₁ , a ₂ ) (b ₁ , c ₂ ) G 1

s2 (c ₁ , b ₂ ) (d ₁ , d ₂ )

Le funzioni di payoff nei giochi con 2 giocatori e 2 strategie

Le funzioni di payoff ottenute con le matrici A e B, ed usando come vettori

x = [x ₁ 1 − x ₁ ] ^T e y = [y ₁ 1 − y ₁ ] ^T , sono:

π 1 (x , y ) = x 1 [(a 1 − c ₁ + d 1 − b ₁ )y 1 + b 1 − d ₁ ] + (c 1 − d ₁ )y 1 + d 1

π ₂ (x , y ) = y ₁ [(a ₂ − c ₂ + d ₂ − b ₂ )x ₁ + b ₂ − d ₂ ] + (c ₂ − d ₂ )x ₁ + d ₂

Gli equilibri di Nash nei giochi con 2 giocatori e 2 strategie

Calcolando le derivate

∂π 1

∂x 1

e ∂π 2

∂y 1

e ponendole uguali a 0, si ottengono le seguenti soluzioni:

x ₁ ^∗ = (d 2 − b ₂ )

(d ₂ − b ₂ ) + (a ₂ − c ₂ ) , x ₂ ^∗ = (a 2 − c ₂ ) (d ₂ − b ₂ ) + (a ₂ − c ₂ ) y ₁ ^∗ = (d 1 − b ₁ )

(d ₁ − b ₁ ) + (a ₁ − c ₁ ) , y ₂ ^∗ = (a 1 − c ₁ )

(d ₁ − b ₁ ) + (a ₁ − c ₁ )

Equilibri di Nash puri e misti ammissibili

Tali soluzioni sono valide se appartengono al simplesso ∆ di dimensione 2 e rappresentano l’eventuale equilibrio misto del gioco.

Gli equilibri puri invece possono essere ricavati utilizzando il metodo della bimatrice.

Esercizio. Calcolare gli equilibri di Nash dei giochi a 2 giocatori e 2

strategie visti fino ad ora e analizzarne l’ammissibilit` a.

Calcolo degli equilibri di Nash misti: 2 giocatori e 3 strategie

Mostriamo come calcolare l’equilibrio di Nash misto della morra cinese.

Si noti che la morra cinese non ha equilibri puri, e quindi per il teorema di Nash deve esserci per forza almeno un equilibrio misto.

Le matrici di payoff del gioco sono le seguenti:

A = B ^T =





0 −1 1

1 0 −1

−1 1 0





Le funzioni di payoff

Si costruiscano i vettori x ed y come spiegato in precedenza:

x =





x ₁ x 2

1 − x 1 − x ₂



 , y =





y ₁ y 2

1 − y 1 − y ₂



 Le funzioni di payoff diventano:

π 1 (x , y ) = x ^T Ay = (−3y 2 + 1)x 1 + (3y 1 − 1)x ₂ − y ₁ + y 2

π ₂ (x , y ) = x ^T By = (−3x ₂ + 1)y ₁ + (3x ₁ − 1)y ₂ − x ₁ + x ₂

Massimizzazione delle funzioni di payoff (1/2)

Calcoliamo le derivate...



 

 

 

 

∂π ₁

∂x ₁ = −3y ₂ + 1

∂π ₁

∂x 2

= 3y 1 − 1 ,



 

 

 

 

∂π ₂

∂y 1

= −3x ₂ + 1

∂π ₂

∂y 2

= 3x 1 − 1

Massimizzazione delle funzioni di payoff (2/2)

...e poniamole pari a 0:



 

 

 

 

∂π 1

∂x ₁ = −3y 2 + 1 = 0

∂π ₁

∂x 2

= 3y ₁ − 1 = 0

=⇒



 

 

 

 



 

 

 

 



y ₁ ^∗ = 1 3 y ₂ ^∗ = 1 3

y ₃ ^∗ = 1 − y ₁ ^∗ − y ₂ ^∗ = 1 3



 

 

 

 

∂π 2

∂y ₁ = −3x 2 + 1 = 0

∂π 2

∂y ₂ = 3x ₁ − 1 = 0

=⇒



 

 

 

 



 

 

 

 



x ₁ ^∗ = 1 3 x ₂ ^∗ = 1 3

x ₃ ^∗ = 1 − x ₁ ^∗ − x ₂ ^∗ = 1

3

Il Dilemma del Prigioniero

A =

 3 0 4 1



, B =

 3 4 0 1



.

Il gioco Stug-Hunt

A =

 2 0 1 3



, B =

 3 1 0 2



.

Il Chicken Game

A =

 −10 1

−1 0



, B =

 −10 −1

1 0



.

Il gioco Falchi e Colombe

A =

 −1/2 2

0 1/2



, B =

 −1/2 0

2 1/2



.