Teoria dei giochi - D'Orio - prima parte1 Esempio 1 Bruce e Sheila decidono se andare allopera...

Teoria dei giochi - D'Orio - prima parte 1

Esempio 1

Bruce e Sheila decidono se andare all’opera oppure ad un incontro di wrestling.

Sheila ottiene una utilità di 4 se andrà all’opera e di 1 se va a veder il wrestling.

Bruce ottiene una utilità di 1 se andrà all’opera e di 4 se va a vedere il wrestling.

I due decidono cosa fare nel modo seguente: Bruce e Sheila mettono entrambi un euro sulla guida

televisiva in salotto (assumiamo che nessuno cerca di guardare come punta l’altro). Contano fino a 3 e simultaneamente svelano quale faccia dell’euro è su. Se le facce dell’euro sono uguali (entrambe testa (heads), o entrambe croce (tails)), Sheila decide dove andare, mentre se le monente mostrano due facce diverse decide Bruce.


Esempio 1

Il payoff atteso di Bruce giocando Head è il seguente: EU1(H, (q, 1–q)) = q×1 + (1–q)×4 = 4–3q

Il payoff atteso di Bruce giocando Tail è il seguente: EU1(T, (q, 1–q)) = q×4 + (1–q)×1 = 1+3q

Bruce è indifferente fra giocare Head o Tail quando EU1(H, (q, 1–q)) = EU1(T, (q, 1–q))

4–3q = 1+3q 6q = 3 Ciò dà un valore di q = 1/2

Sheila

H ( q ) T ( 1–q )

BruceH ( r ) 1 , 4 4 , 1

T ( 1–r ) 4 , 1 1 , 4


Esempio 1

Il payoff di Sheila giocando Head è il seguente: EU2(H, (r, 1–r)) = r ×4+(1–r)×1 = 3r + 1

Il payoff di Sheila giocando Tail è il seguente: EU2(T, (r, 1–r)) = r×1+(1–r)×4 = 4 – 3r

Sheila è indifferente fra giocare Head o Tail quando EU2(H, (r, 1–r)) = EU2(T, (r, 1–r))

3r + 1 = 4 – 3r 6r = 3 Ciò da un valore di r = ½

( (1/2, 1/2), (1/2, 1/2) ) è un MNE.

Sheila

H ( q ) T ( 1–q )

BruceH ( r ) 1 , 4 4 , 1

T ( 1–r ) 4 , 1 1 , 4


Esempio 2

Il payoff atteso di Player 1 giocando T è: EU1(T, (q, 1–q)) = q×6 + (1–q)×0 = 6q

Il payoff atteso di Player 1 giocando B è: EU1(B, (q, 1–q)) = q×3 + (1–q)×6 = 6-3q

Player 1 è indifferente tra giocare T e B se EU1(T, (q, 1–q)) = EU1(B, (q, 1–q))

6q = 6-3q 9q = 6 Ciò da un valore di q = 2/3

Player 2

L ( q ) R ( 1–q )

Player 1T ( r ) 6 , 0 0 , 6

B ( 1–r ) 3 , 2 6 , 0


Example 2

Il payoff atteso di Player 2 giocando L è: EU2(L, (r, 1–r)) = r ×0+(1–r)×2 =2- 2r

Il payoff atteso di Player 2 giocando R è: EU2(R, (r, 1–r)) = r×6+(1–r)×0 = 6r

Player 2 è indifferente tra giocare L e R quando EU2(L, (r, 1–r)) = EU2(R, (r, 1–r))

2- 2r = 6r 8r = 2 Ciò da un valore di r = ¼

( (1/4, 3/4), (2/3, 1/3) ) è un MNE.

Player 2

L ( q ) R ( 1–q )

Player 1T ( r ) 6 , 0 0 , 6

B ( 1–r ) 3 , 2 6 , 0


Esempio 3: Il gioco di entrata nel mercato Due imprese, Firm 1 e Firm 2, devono decidere

simultaneamente se aprire un ristorante in un centro commerciale.

Ognuna ha due strategie: Enter, Not Enter Se entrambe giocano “Not Enter”, guadagnano 0

profitti Se una gioca “Enter” e l’altra gioca “Not Enter” allora

l’impresa che gioca “Enter” guadagna $500K Se entrambe giocano “Enter” allora entrambe

perdono $100K perché la domanda è limitata


Esempio 3: Il gioco di entrata nel mercato

Quanti equilibri di Nash potete trovare? Due equilibri di Nash in strategie pure

(Not Enter, Enter) e (Enter, Not Enter) Un equilibrio di Nash in strategie miste

((5/6, 1/6), (5/6, 1/6)) questo perchè r=5/6 e q=5/6

Firm 2

Enter ( q ) Not Enter ( 1–q )

Firm 1Enter ( r ) -100 , -100 500 , 0

Not Enter ( 1–r ) 0 , 500 0 , 0


Esempio 4

Quanti equilibri di Nash trovate? Due equilibri di Nash in strategie pure

(B, L) e (T, R) Un equilibrio di Nash in strategie miste

((2/3, 1/3), (1/2, 1/2)) Questo perchè r=2/3 e q=1/2

Player 2

L ( q ) R ( 1–q )

Player 1T ( r ) 1 , 1 1 , 2

B ( 1–r ) 2 , 3 0 , 1


Esempio: Roccia, carta e forbici

Ognuno dei due giocatori annuncia simultaneamente Roccia (R), o Carta (P), o Forbici (S).

La carta batte la roccia La roccia batte le forbici Le forbici battono la carta Il giocatore che nomina l’oggetto vincente

riceve $1 dall’avversario Se entrambi giocano lo stesso oggetto

nessuno vince o perde



Riuscite a trovare un equilibrio di Nash in strategie miste?

Player 2

Rock Paper Scissors

Player 1

Rock 0 , 0 -1 , 1 1 , -1

Paper 1 , -1 0 , 0 -1 , 1

Scissors -1 , 1 1 , -1 0 , 0


2-giocatori ognuno con un numero finito di strategie pure

Insieme dei giocatori: {Player 1, Player 2} Insiemi delle strategie:

player 1: S1= { s11, s12, ..., s1J } player 2: S2= { s21, s22, ..., s2K }

Funzioni di payoffs:player 1: u1(s1j, s2k)player 2: u2(s1j, s2k) per j = 1, 2, ..., J e k = 1, 2, ..., K



La strategia mista di Player 1: p1=(p11, p12, ..., p1J )

La strategia mista di Player 2: p2=(p21, p22, ..., p2K )

Player 2s21 (p21) s22 (p22) ....... s2K (p2K)

s11 (p11)

u2(s11, s21)

u1(s11, s21)

u2(s11, s22)

u1(s11, s22)

....... u2(s11, s2K)

u1(s11, s2K)

s12 (p12)

u2(s12, s21)

u1(s12, s21)

u2(s12, s22)

u1(s12, s22)

....... u2(s12, s2K)

u1(s12, s2K)

.... ...... ....... ....... ......

s1J (p1J)

u2(s1J, s21)

u1(s1J, s21)

u2(s1J, s22)

u1(s1J, s22)

...... u2(s1J, s2K)

u1(s1J, s2K)

Pla

yer

1


Payoffs attesi: 2-giocatori ognuno con un numero finito di strategie pure

Il payoff atteso di Player 1 dalla strategia pura s11:

EU1(s11, p2)=p21×u1(s11, s21)+p22×u1(s11, s22)+...+p2k×u1(s11, s2k)+...+p2K×u1(s11, s2K)


EU1(s12, p2)=p21×u1(s12, s21)+p22×u1(s12, s22)+...+p2k×u1(s12, s2k)+...+p2K×u1(s12, s2K)

.........

Il payoff atteso di Player 1 dalla strategia pura s1J:

EU1(s1J, p2)=p21×u1(s1J, s21)+p22×u1(s1J, s22)+...+p2k×u1(s1J, s2k)+...+p2K×u1(s1J, s2K)

Il payoff atteso di Player 1 dalla strategia mista p1:v1(p1, p2)=p11EU1(s11, p2)+p12EU1(s12, p2)+...+p1jEU1(s1j, p2)+... +p1JEU1(s1J, p2)


Payoffs attesi : 2-giocatori ognuno con un numero finito di strategie pure


EU2(s21, p1)=p11×u2(s11, s21)+p12×u2(s12, s21)+...+p1j×u2(s1j, s21)+...+p1J×u2(s1J, s21)


EU2(s22, p1)=p11×u2(s11, s22)+p12×u2(s12, s22)+...+p1j×u2(s1j, s22)+...+p1J×u2(s1J, s22)

...........

Il payoff atteso di Player 1 dalla strategia pura s2K:

EU2(s2K, p1)=p11×u2(s11, s2K)+p12×u2(s12, s2K)+...+p1j×u2(s1j, s2K)+...+p1J×u2(s1J, s2K)

Il payoff atteso di Player 2 dalla strategia mista p2:v2(p1, p2)=p21EU2(s21, p1)+p22EU2(s22, p1) +...+p2kEU2(s2k, p1)+.... +p2KEU2(s2K, p1)


MNE: 2-giocatori ognuno con un numero finito di strategie pure Una coppia di strategie miste (p1*, p2*), dove

p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) è un MNE se la strategia mista p1* del giocatore 1 è una risposta ottima alla strategia mista del giocatore 2 p2*, e p2* è una risposta ottima a p1*.

Oppure, v1(p1*, p2*) v1(p1, p2*), per tutte le strategie miste del giocatore 1 p1, e v2(p1*, p2*) v2(p1*, p2), per tutte le strategie miste del giocatore 2 p2.

Ciò significa, data la strategia mista del giocatore 2 p2*, il giocatore 1 non può migliorare deviando da p1*. Data la strategia mista del giocatore 1 p1*, il giocatore 2 non può fare di meglio deviando da p2*.



Teorema 3 (proprietà del MNE) Una coppia di strategie miste (p1*, p2*), dove

p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) è un MNE se e solo se v1(p1*, p2*) EU1(s1j, p2*), per j = 1, 2, ..., Jev2(p1*, p2*) EU2(s2k, p1*), per k= 1, 2, ..., K


2-giocatori ognuno con un numero finito di strategie pure Teorema 4: Una coppia di strategie miste (p1*, p2*), dove

p1*=(p11*, p12*, ..., p1J* ) p2*=(p21*, p22*, ..., p2K* ) è un MNE se e solo se soddisfa le seguenti condizioni: player 1: per ogni m e n, se p1m*>0 e p1n*>0 allora

EU1(s1m, p2*) = EU1(s1n, p2*); se p1m*>0 e p1n*=0 allora EU1(s1m, p2*) EU1(s1n, p2*)

player 2: per ogni i e k, se p2i*>0 e p2k*>0 allora EU2(s2i, p1*) = EU2(s2k, p1*); se p2i*>0 e p2k*=0 allora EU2(s2i, p1*) EU2(s2k, p1*)


2-giocatori ognuno con un numero finito di strategie pure Cosa ci dice il Teorema 4?

Una coppia di strategie miste (p1*, p2*), dovep1*=(p11*, p12*, ..., p1J* ), p2*=(p21*, p22*, ..., p2K* ) è un MNE se e solo se soddisfa le seguenti condizioni:

Data la strategia mista del giocatore 2 p2*, il payoff atteso del giocatore 1 da ogni strategia pura al quale egli assegna una probabilità positiva di realizzo è la stessa, e il payoff atteso dal giocatore 1 di ogni strategia pura alla quale assegna una probabilità positiva è non inferiore del payoff atteso di ogni strategia pura alla quale assegna zero probabilità.

Data la strategia mista del giocatore 1 p1*, il payoff atteso del giocatore 2 da ogni strategia pura al quale egli assegna una probabilità positiva di realizzo è la stessa, e il payoff atteso dal giocatore 2 di ogni strategia pura alla quale assegna una probabilità positiva è non inferiore del payoff atteso di ogni strategia pura alla quale assegna zero probabilità.


2-giocatori ognuno con un numero finito di strategie pure Il Teorema 4 implica che abbiamo un MNE nella

situazione seguente: Data la strategia mista del giocatore 2, Il giocatore 1 è

indifferente tra le sue strategie pure alle quali assegna probabilità positiva. Il payoff atteso di ogni strategia pura che ha probabilità positiva è non inferiore del payoff atteso di ogni strategia pura alla quale il giocatore 1 assegna probabilità nulla.

Data la strategia mista del giocatore 1, Il giocatore 2 è indifferente tra le sue strategie pure alle quali assegna probabilità positiva. Il payoff atteso di ogni strategia pura che ha probabilità positiva è non inferiore del payoff atteso di ogni strategia pura alla quale il giocatore 2 assegna probabilità nulla.


Teorema 4: esempio dimostrativo

Controllare se ((3/4, 0, 1/4), (0, 1/3, 2/3)) è un MNE Player 1:

EU1(T, p2) = 00+3(1/3)+1(2/3)=5/3, EU1(M, p2) = 40+0(1/3)+2(2/3)=4/3EU1(B, p2) = 30+5(1/3)+0(2/3)=5/3.

Quindi, EU1(T, p2) = EU1(B, p2) > EU1(M, p2)

Player 2

L (0) C (1/3) R (2/3)

Player 1

T (3/4) 0 , 2 3 , 3 1 , 1

M (0) 4 , 0 0 , 4 2 , 3

B (1/4) 3 , 4 5 , 1 0 , 7


Teorema 4: esempio dimostrativo

Player 2: EU2(L, p1)=2(3/4) + 00 + 4(1/4)=5/2,

EU2(C, p1)=3(3/4) + 40 + 1(1/4)=5/2,EU2(R, p1)=1(3/4) + 30 + 7(1/4)=5/2.

Quindi, EU2(C, p1)=EU2(R, p1)EU2(L, p1) Allora, ((3/4, 0, 1/4), (0, 1/3, 2/3)) dato il Teorema 4

è un MNE.

Player 2

L (0) C (1/3) R (2/3)

Player 1

T (3/4) 0 , 2 3 , 3 1 , 1

M (0) 4 , 0 0 , 4 2 , 3

B (1/4) 3 , 4 5 , 1 0 , 7



Controllate che esista un MNE in cui p11>0, p12>0, p13>0, p21>0, p22>0, p23>0.

Player 2

Rock (p21) Paper (p22) Scissors (p23)

Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



Se ogni giocatore assegna una probabilità positiva ad ognuna delle sue strategie miste allora,per il Teorema 4, ogni giocatore è indifferente tra le sue tre strategie pure.

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



Il giocatore 1 è indifferente fra le sue 3 strategie: EU1(Rock, p2) = 0p21+(-1) p22+1 p23

EU1(Paper, p2) = 1 p21+0 p22+(-1) p23

EU1(Scissors, p2) = (-1) p21+1 p22+0 p23

EU1(Rock, p2)= EU1(Paper, p2)= EU1(Scissors, p2) Avendo che p21+ p22+ p23=1, abbiamo tre equazioni e tre

incognite.

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



0p21+(-1) p22+1 p23= 1 p21+0 p22+(-1) p23

0p21+(-1) p22+1 p23 = (-1) p21+1 p22+0 p23

p21+ p22+ p23=1

La soluzione è p21= p22= p23=1/3

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



Il giocatore 2 è indifferente fra le tre strategie: EU2(Rock, p1)=0p11+(-1) p12+1 p13

EU2(Paper, p1)=1 p11+0 p12+(-1) p13

EU2(Scissors, p1)=(-1) p11+1 p12+0 p13 EU2(Rock, p1)= EU2(Paper, p1)=EU2(Scissors, p1) Insieme con p11+ p12+ p13=1, abbiamo tre equazioni e tre

incognite.

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



0p11+(-1) p12+1 p13=1 p11+0 p12+(-1) p13

0p11+(-1) p12+1 p13=(-1) p11+1 p12+0 p13 p11+ p12+ p13=1

La soluzione è p11= p12= p13=1/3

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



Player 1: EU1(Rock, p2) = 0(1/3)+(-1)(1/3)+1(1/3)=0 EU1(Paper, p2) = 1(1/3)+0(1/3)+(-1)(1/3)=0 EU1(Scissors, p2) = (-1)(1/3)+1(1/3)+0(1/3)=0

Player 2: EU2(Rock, p1)=0(1/3)+(-1)(1/3)+1(1/3)=0 EU2(Paper, p1)=1(1/3)+0(1/3)+(-1)(1/3)=0 EU2(Scissors, p1)=(-1)(1/3)+1(1/3)+0(1/3)=0

Quindi, (p1=(1/3, 1/3, 1/3), p2=(1/3, 1/3, 1/3)) dato il teorema 4 è un MNE.

Player 2

Rock (1/3) Paper (1/3) Scissors (1/3)

Player 1

Rock (1/3) 0 , 0 -1 , 1 1 , -1

Paper (1/3) 1 , -1 0 , 0 -1 , 1

Scissors (1/3) -1 , 1 1 , -1 0 , 0



Controllare se esiste un MNE nel quale p11, p12, p13 è positivo, e almeno due fra p21, p22, p23 sono positivi.

La risposta è No.

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



Controllare se esiste un MNE dove due fra p11, p12, p13 sono positivi, e almeno due fra p21, p22, p23 sono positivi.

La risposta è No.

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0



Quindi, (p1=(1/3, 1/3, 1/3), p2=(1/3, 1/3, 1/3)) dato il Teorema 4 è l’unico equilibrio di Nash.

Player 2


Player 1

Rock (p11) 0 , 0 -1 , 1 1 , -1

Paper (p12) 1 , -1 0 , 0 -1 , 1

Scissors (p13) -1 , 1 1 , -1 0 , 0

Teoria dei giochi - D'Orio - prima parte1 Esempio 1 Bruce e Sheila decidono se andare allopera...

Documents

Transcript of Teoria dei giochi - D'Orio - prima parte1 Esempio 1 Bruce e Sheila decidono se andare allopera...