Teoria dei Giochi - Università di Pavia · Se la somma dei due numeri è pari, vince II. ... É...

Teoria dei Giochi

Anna Torre

Almo Collegio Borromeo 9 marzo 2010

email: [email protected]

sito web del corso:www-dimat.unipv.it/atorre/borromeo2010.html

A. Torre Teoria dei giochi 2010-Almo Collegio Borromeo

TEOREMI DI ESISTENZA



Teorema di Von Neumann. Se (X, Y, f , −f ) è l’estensione mista di

un gioco a somma zero finito, allora esiste almeno una coppia distrategie che realizzano il maxmin=minmax.





Teorema di Nash. Se (X, Y, f , g) è l’estensione mista di un giocofinito, allora esiste almeno una coppia di strategie che realizzano un

equilibrio di Nash.





Teorema di Nash. Se (X, Y, f , g) è l’estensione mista di un giocofinito, allora esiste almeno una coppia di strategie che realizzano un

equilibrio di Nash.Gli equilibri di Nash di un gioco a somma zero sono le coppie di

strategie che realizzano il maxmin=minmax


ESEMPIO


ESEMPIO

Vediamo questo gioco:

I/II L R

T -2,2 3,-3

B 3,-3 -4,4


ESEMPIO


I/II L R

T -2,2 3,-3

B 3,-3 -4,4

Facendo i conti si vede che l’equilibrio si ottiene per p = 712 e q = 7

12

con un guadagno atteso per I uguale a 112 .


ESEMPIO


I/II L R

T -2,2 3,-3

B 3,-3 -4,4

Facendo i conti si vede che l’equilibrio si ottiene per p = 712 e q = 7

12

con un guadagno atteso per I uguale a 112 .

Quindi, questo gioco che a una analisi poco attenta sembra pari, in

realtà se entrambi i giocatori giocano al meglio delle loro possibilitàdà al primo giocatore un guadagno atteso positivo.


ESEMPIO


ESEMPIO

q

pA. Torre Teoria dei giochi 2010-Almo Collegio Borromeo

ESEMPIO

q

p

712

1A. Torre Teoria dei giochi 2010-Almo Collegio Borromeo

ESEMPIO

q

p

712

1712

1


Analogamente il gioco delle cinque dita:

I/II 1 2 3 4 5

1 -1 1 -1 1 -1

2 1 -1 1 -1 1

3 -1 1 -1 1 -1

4 1 -1 1 -1 1

5 -1 1 -1 1 -1

I giocatori (I e II) devono scegliere contemporaneamente eindipendentemente un numero tra 1 e 5. Se la somma dei due numeri

è pari, vince II. Altrimenti vince I. Questo gioco apparentementeavvantaggia il giocatore 2 ma l’equilibrio è ( 1

2 ,12 , 0, 0, 0)per il primo

giocatore e ( 12 ,

12 , 0, 0, 0) per il secondo con valore atteso 0. Questa è

la la differenza tra il trovarsi di fronte al caso o di fronte a un essere

intelligente che va a caso “con intelligenza”.


É RILEVANTE SCEGLIERE PER PRIMI?I/II L R

T 5,5 0,6

B 6,0 1,1


T 2,1 0,0

B 0,0 1,2


T -1,1 1,-1

B 1,-1 -1,1


Aumentare i Payoff migliora la situazione?I/II L R

T 12,12 102,11

B 11,102 101,101

I/II L R

T 9,9 99,10

B 10,99 100,100


È facile vedere se un gioco è pari?I/II L R

T -2,2 3,-3

B 3,-3 -4,4

I/II L R S

T -1 1 -1

B 1 -1 1

Q -1 1 -1


Riprendiamo il gioco del poker semplificato. Il gioco in formastrategica era:

I\\II P S

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

PARK (0, 0) (−3/2, 3/2)

RAPK (0, 0) (1/2,−1/2)

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

I payoff sono i valori attesi dei payoff con la distribuzione di probabilità

assegnata.

NB: la strategia RARK prevede (per via di RK) che il giocatore I bluffi.


q 1 − q

I\\II P S

p RAPK (0, 0) (1/2,−1/2)

1 − p RARK (1,−1) (0, 0)


f (p, q) = − 32 pq + 1

2 p + q = (− 32 q + 1

2 )p + q

che ha massimo per p = 1 quando q ≤ 13

per p = 0 se q ≥ 13 e per ogni valore di p se q = 1

3

Analogamente g(p, q) = ( 32 p − 1)q − 1

2 p

che ha massimo per q = 1 quando p ≥ 23

per q = 0 se p ≤ 23 e per ogni valore di q se p = 2

3

NB: la strategia RARK prevede (per via di RK) che il giocatore I bluffi.Si noti che la strategia ottimale per I prevede con probabilità positiva

(1/3) che I adotti la strategia RARK e quindi che, quando lui ha lacarta “bassa” (cioè K) bluffi mediamente 1/3 delle volte. Si noti che è

ottimale per I bluffare con questa “frequenza”, nè più spesso nèmeno spesso!


INDUZIONE A RITROSO


INDUZIONE A RITROSOSe un gioco è dato in forma estesa ed è finito e a informazione

perfetta, un modo per trovare equilibri di Nash in strategie pure è datodal cosidetto metodo dell’induzione a ritroso.




Si osservano gli ultimi nodi nei quali un giocatore è chiamato a

giocare e si suppone (coerentemente con le ipotesi di razionalità eintelligenza) che in questi nodi il giocatore scelga la strategia che gli

offre il payoff maggiore.






offre il payoff maggiore.Nei nodi precedenti, il giocatore che è chiamato a giocare sa cosa

farà l’ultimo giocatore in quanto egli conosce il gioco e sa che l’ultimogiocatore è intelligente e razionale. Così il giocatore si comporta

come se in realtà fosse l’ultimo a giocare, in quanto il payoff cheottiene giocando ciascuna strategia gli è noto perché sa quali

saranno le conseguenze della sua scelta.






offre il payoff maggiore.Nei nodi precedenti, il giocatore che è chiamato a giocare sa cosa

farà l’ultimo giocatore in quanto egli conosce il gioco e sa che l’ultimogiocatore è intelligente e razionale. Così il giocatore si comporta

come se in realtà fosse l’ultimo a giocare, in quanto il payoff cheottiene giocando ciascuna strategia gli è noto perché sa quali

saranno le conseguenze della sua scelta.

In questo modo si proceede passo dopo passo ...in conclusione nelprimo nodo il giocatore che è chiamato a scegliere in base alle ipotesi

di conoscenza comune della razionalità e intelligenza di tutti igiocatori, in realtà sa già cosa succederà in corrispondenza ad ogniA. Torre Teoria dei giochi 2010-Almo Collegio Borromeo

Si potrebbe (non è particolarmennte difficile) dimostrare che lesoluzioni ottenute in questo modo sono equilibri di Nash, ma non tutti

gli equilibri di Nash di un gioco a informazione perfetta si possono

ottenere in questo modo.


Si potrebbe (non è particolarmennte difficile) dimostrare che lesoluzioni ottenute in questo modo sono equilibri di Nash, ma non tutti

gli equilibri di Nash di un gioco a informazione perfetta si possono

ottenere in questo modo.Un sottogioco G′ di un gioco G in forma estesa a informazione

perfetta è il gioco formato da un nodo di G e da tutti i suoi successoriin G.


RAFFINAMENTI DELL’EQUILIBRIO DI NASHTutto ciò ci porta alla definizione di “equilibrio perfetto nei sottogiochi”

(SPE: subgame perfect equilibrium), che è dovuto a Selten (1965).



(SPE: subgame perfect equilibrium), che è dovuto a Selten (1965).Se ci limitiamo, per semplicità, ai giochi ad informazione perfetta, la

condizione che imponiamo è che non solo si abbia un equilibrio, mache tale resti anche quando “restringiamo” le strategie ai sottogiochi

del gioco dato.





del gioco dato.Per gioco ad informazione perfetta la definizione di sottogioco è

semplicissima: si tratta di considerare un generico nodo e prenderlo

come “radice” del gioco.





del gioco dato.Per gioco ad informazione perfetta la definizione di sottogioco è

semplicissima: si tratta di considerare un generico nodo e prenderlo

come “radice” del gioco.Il metodo della induzione a ritroso per trovare un equilibrio di Nash in

un gioco ad informazione perfetta fornisce, in realtà, un equilibrioperfetto nei sottogiochi. Si consideri il seguente gioco (in forma

estesa)


@@@@@@

��

��

��AAAA

��

�0

0

2

1

RL

BT

gioca 1

12

gioca 2


I\II L R

T 2, 1 0, 0

B 1, 2 1, 2

Si vede immediatamente che questo gioco ha due equilibri (in

strategie pure): (T, L) e (B,R): il primo è perfetto nei sottogiochi, ilsecondo no. Quale è il senso del nuovo equlibrio che abbiamo

trovato, ovvero (B,R)?non tutti gli equilibri di Nash sono “uguali”.


@@@@@@

��

��

��AAAA

��

�

��

��

AAAA

1

1

1

1

0

0

2

1100

DCBA

FE

gioca I

gioca IIgioca II


HHHHHHHHHHHH

III

BBBBBBB

��

��

��

��

��BBBBB

��

@@@@@@��

BBBBB

BBBBB

��

BBBBB

��

BBBBB

��

BBBBB

��

989721 3 99

S D S D DSS D S DS D

1 20 0 3 0 97 0 98 0 99 0

99 0 98 0 97 0 3 0 2 0 1 0

I

IIIIII IIII II


@@@@@@

��

��

��AAAA

��

�0

0

2

2

AC

OUTIN

gioca I

1

5

gioca S


Il centipede

s s s s s s s

s s s s s s

D D DDDD

C CCCC

0

0

−1

2

1

1

0

3

2

2

1

4

3

3I II I II I II


Il risultato è inefficiente. Ed un po’ di “capacità di vedere lontano”

dovrebbe portare i giocatori a non “defezionare” subito dal gioco.



dovrebbe portare i giocatori a non “defezionare” subito dal gioco.Cheragionamento fa II quando “defeziona” la terza volta in cui tocca a lui

giocare?.




giocare?.

Perchè “defezionare”? Perchè ritiene (da induzione a ritroso) chenella mossa successiva I defezionerebbe.




giocare?.


Ma se II si trova davvero a dover giocare la sua terza mossa, ciò èsolo perché I ha deciso per ben tre volte di comportarsi in modo

diverso da come prescrive lo SPE (ed anche II stesso, si noti!).




giocare?.


Ma se II si trova davvero a dover giocare la sua terza mossa, ciò èsolo perché I ha deciso per ben tre volte di comportarsi in modo

diverso da come prescrive lo SPE (ed anche II stesso, si noti!).Allora II “defeziona” ipotizzando un comportamento futuro di

“razionalità” da parte di I, che se fosse stato adottato in passato nonavrebbe certamente portato II a dover giocare!


I SPE sono un cosiddetto “raffinamento” degli equilibri di Nash che

sfrutta la forma estesa. Sono però stati proposti altri raffinamenti cheutilizzano solo la forma strategi Mi limito a citare gli equilibri perfetti

(introdotti da Selten nel 1975). Vediamo solo un esempio.




(introdotti da Selten nel 1975). Vediamo solo un esempio.Qui abbiamo due equilibri di Nash (in strategie pure): (T, L) e (B,R).

Ma solo (T, L) è “perfetto”.

I\II L R

T 1, 1 0, 0

B 0, 0 0, 0




(introdotti da Selten nel 1975). Vediamo solo un esempio.Qui abbiamo due equilibri di Nash (in strategie pure): (T, L) e (B,R).

Ma solo (T, L) è “perfetto”.

I\II L R

T 1, 1 0, 0

B 0, 0 0, 0

L’idea di equilibrio perfetto è basata sul fatto che il giocatore non è ingrado di evitare errori. E quindi un equilibrio dovrebbe essere, per

così dire, “limite” di equilibri che si ottengono “obbligando” i giocatori

ad effettuare errori.


Teoria dei Giochi - Università di Pavia · Se la somma dei due numeri è pari, vince II. ... É...

Documents

Transcript of Teoria dei Giochi - Università di Pavia · Se la somma dei due numeri è pari, vince II. ... É...