Teoria dei giochi - D'Orio - seconda parte1 Giochi dinamici ad informazione completa Corso di Teoria...

Teoria dei giochi - D'Orio - seconda parte 1

Giochi dinamici ad informazione completa

Corso di Teoria dei Giochi

Laurea specialistica in Economia Applicata

Docente: Giovanni D’Orio

E-mail: [email protected]


Panoramica dei giochi dinamici ad informazione completa Giochi dinamici ad informazione completa Rappresentazione in forma estensiva (o estesa) Giochi dinamici ad informazione completa e perfetta Albero del gioco Equilibrio di Nash perfetto nei sottogiochi Backward induction (Induzione all’indietro) Applicazioni Giochi dinamici ad informazione completa ed

imperfetta Altre applicazioni Giochi ripetuti


Gioco dell’entrata sul mercato

Un monopolista già sul mercato (incumbent) è posto di fronte ad una possibile entrata sul mercato di un challenger.

Il challenger può scegliere se entrare (enter) o restare fuori (stay out). Se il challenger entra, il monopolista (incumbent) può scegliere se

cooperare (accommodate) o se combatterlo (fight). I payoffs del gioco sono conoscenza comune.

Challenger

In Out

Incumbent

A F 1, 2

2, 1 0, 0

Il primo numero è il payoff del challenger. Il secondo numero è il payoff dell’incumbent.


Matching pennies a mosse sequenziali

Ognuno dei due giocatori ha un penny.

Player 1 sceglie per primo se giocare Head o Tail.

Dopo aver osservato la scelta del giocatore 1, il giocatore 2 sceglie se giocare Head o Tail

Entrambi conoscono le regole seguenti: Se i due pennies sono

uguali allora il giocatore 2 vince il penny del giocatore 1.

Negli altri casi vince il giocatore 1.

Player 1

Player 2

H T

-1, 1 1, -1

H T

Player 2

H T

1, -1 -1, 1


Giochi dinamici ad informazione perfetta (o a mosse sequenziali) Un insieme di giocatori Chi muove quando e quali scelte sono

disponibili? Cosa sanno i giocatori quando muovono? I payoff dei giocatori sono determinati dalle

proprie scelte. Tutte le scelte possibili sono conoscenza

comune dei due giocatori.


Definizione: rappresentazione in forma estensiva (o estesa)

La forma estesa di un gioco specifica: I giocatori del gioco Quando ogni giocatore deve muovere Cosa può fare ogni giocatore quando è il

suo turno Cosa conosce ogni giocatore quando è il

suo turno il payoff ricevuto da ogni giocatore per

ogni combinazione mosse che potrebbe essere scelta dai giocatori


Giochi dinamici ad informazione completa e perfetta Informazione perfetta

Tutte le mosse precedenti sono osservabili prima che venga scelta la prossima mossa.

Un giocatore sa Chi ha mosso e Cosa ha fatto prima che esso prenda una decisione


Albero del gioco

Un albero di un gioco ha un insieme di nodi e un insieme di segmenti tali che Ogni segmento collega

due nodi (questi due nodi sono detti adiacenti)

Per ogni coppia di nodi, c’è un sentiero unico che collega questi due nodi

x0

x1 x2

x3

x4 x5 x6

x7 x8

un nodo

Un segmento di connessione fra i nodi x1 e x5

Un sentiero da x0 a x4


Albero del gioco

Un sentiero è una sequenza di nodi distinti y1, y2, y3, ..., yn-1, yn tale che yi e yi+1 sono adiacenti, per i=1, 2, ..., n-1. Diremo che questo sentiero va da y1 a yn.

Possiamo anche utilizzare la sequenza dei segmenti fra i due nodi per denotare il sentiero.

La lunghezza di un sentiero è caratterizzato dal numero dei segmenti in esso contenuti.

Esempio 1: x0, x2, x3, x7 è un sentiero di dimensione 3.

Esempio 2: x4, x1, x0, x2, x6 è un sentiero di dimensione 4

x0

x1 x2

x3

x4 x5 x6

x7 x8

Un sentiero da x0 a x4


Albero del gioco

C’è un nodo speciale x0 chiamato la radice dell’albero che rappresenta l’inizio del gioco.

I nodi adiacenti a x0 sono successori di x0. I successori di x0 sono x1, x2

Per ogni due nodi adiacenti, il nodo che è connesso alla radice da un sentiero più lungo è un successore dell’altro nodo.

Esempio 3: x7 è un successore di x3 perché essi sono adiacenti e il sentiero da x7 a x0 is è più lungo rispetto al sentiero da x3 a x0

x0

x1 x2

x3

x4 x5 x6

x7 x8


Albero del gioco

Se un nodo x è un successore del nodo y allora y è chiamato predecessore di x.

In un albero, ogni nodo diverso dalla radice ha un predecessore unico.

Ogni nodo che non ha successori è chiamato nodo terminale. Potrebbe essere la fine del gioco

Esempio 4: x4, x5, x6, x7, x8 sono nodi terminali

x0

x1 x2

x3

x4 x5 x6

x7 x8


Albero del gioco

Ogni nodo diverso dai nodi terminali rappresenta qualche giocatore.

Per un nodo diverso da un terminale, I segmenti che lo collegano con i successori rappresentano le azioni disponibili per il giocatore rappresentato in quel nodo.

Player 1

Player 2

H T

-1, 1 1, -1

H T

Player 2

H T

1, -1 -1, 1


Albero del gioco

Un sentiero dalla radice ad un nodo terminale rappresenta una sequenza completa di mosse che determinano i payoffs al nodo terminale

Player 1

Player 2

H T

-1, 1 1, -1

H T

Player 2

H T

1, -1 -1, 1


Strategia

La strategia di un giocatore è un piano di azioni completo.

La strategia (o il piano completo di azioni) specifica una azione possibile per il giocatore in qualsiasi contingenza esso potrebbe essere chiamato in azione.


Gioco dell’entrata nel mercato Strategie del Challenger

In Out

Strategie dell’Incumbent Accommodate (se il challenger gioca In) Fight (se il challenger gioca In)

Payoffs Rappresentazione in forma Normale

Incumbent

Accommodate Fight

ChallengerIn 2 , 1 0 , 0

Out 1 , 2 1 , 2


Strategie e payoff

In un albero, la strategia di un giocatore è rappresentata da un insieme di segmenti.

Una combinazione di strategie (insiemi dei segmenti), una per ogni giocatore, sviluppa un sentiero dalla radice al nodo terminale, il quale determina i payoffs di tutti i giocatori.



Strategie del giocatore 1 Head Tail

Strategie del giocatore 2 H se player 1 gioca H, H se player 1 gioca T H se player 1 gioca H, T se player 1 gioca T T se player 1 gioca H, H se player 1 gioca T T se player 1 gioca H, T se player 1 gioca T

Le strategie del giocatore 2 sono denotate rispettivamente da HH, HT, TH e TT.



I payoffs Rappresentazione in forma Normale

Player 2

HH HT TH TT

Player 1

H -1 , 1 -1 , 1 1 , -1 1 , -1

T 1 , -1 -1 , 1 1 , -1 -1 , 1


Equilibrio di Nash

L’insieme degli equilibri di Nash in un gioco dinamico ad informazione completa è l’insieme degli equilibri di Nash nella sua forma normale.

Come trovare l’equilibrio di Nash in un gioco dinamico ad informazione completa Costruite la forma normale del gioco dinamico

ad informazione completa Trovate l’equilibrio di Nash nella forma

normale.


Equilibrio di Nash nel gioco dell’entrata nel mercato Due equilibri di Nash

( In, Accommodate ) ( Out, Fight )

Ha senso considerare il secondo equilibrio ( Out, Fight )?

Minacce non credibili

Incumbent

Accommodate Fight


Out 1 , 2 1 , 2


Rimozione degli equilibri di Nash non ragionevole L’equilibrio di Nash perfetto nei sottogiochi è

una “raffinazione” dell’equilibrio di Nash Questo processo di “refinement” può

eliminare equilibri di Nash non ragionevoli oppure minacce non credibili


Riassunto

Giochi dinamici ad informazione completa e perfetta

Rappresentazione dei giochi in forma estesa Albero del gioco

Prossimo argomento Sottogioco Equilibrio di Nash perfetto nei sottogiochi Backward induction (induzione all’indietro)


Strategia e payoff Una strategia per un

giocatore è un piano di azione completo.

Specifica una azione fattibile in ogni contingenza nella quale il giocatore potrebbe essere chiamato in azione.

Specifica cosa fa il giocatore ad ogni nodo specifico

Player 1

Player 2

H T

-1, 1 1, -1

H T

Player 2

H T

1, -1 -1, 1

Una strategia per

il giocatore 1: H

Una strategia per il giocatore 2: H se il giocatore 1 gioca H, T se il giocatore 2 gioca T (scritta HT)

Il payoff del giocatore 1 è -1 e il payoff del giocatore 2 è 1 se il giocatore 1 gioca H e il giocatore 2 gioca HT


Gioco dell’entrata nel mercato Strategie del Challenger

In Out

Strategie dell’Incumbent Accommodate Fight

Payoffs Rappresentazione in forma normale

Incumbent

Accommodate Fight


Out 1 , 2 1 , 2

Challenger

In Out

Incumbent

A F 1, 2

2, 1 0, 0


Equilibrio di Nash nel gioco dell’entrata nel mercato Due equilibri di Nash

( In, Accommodate ) ( Out, Fight )

Ha senso il secondo equilibrio?

Minacce non credibili

Incumbent

Accommodate Fight


Out 1 , 2 1 , 2

Challenger

In Out

Incumbent

A F 1, 2

2, 1 0, 0


Rimozione degli NE non credibili

SNE (equilibrio di Nash nei sottogiochi) è un equilibrio di Nash “raffinato”

Può eliminare NE che non hanno senso o minacce non credibili

Dobbiamo però definire prima i sottogiochi


Sottogioco

Un sottogioco in un gioco ad albero comincia in un nodo non terminale e include tutti i nodi e segmenti che seguono il nodo non terminale

Un sottogioco che comincia ad un nodo non terminale x può essere ottenuto come segue: Rimuovete i segmenti

che collegano x e i suoi predecessori

La parte connessa che contiene x è il sottogioco

-1, 1

Player 1

Player 2

H T

1, -1

H T

Player 2

H T

1, -1 -1, 1

Un sottogioco


Sottogiochi: esempi

Player 2

E F

Player 1

G H 3, 1

1, 2 0, 0

Player 1

C D

2, 0

Player 2

E F

Player 1

G H 3, 1

1, 2 0, 0

Player 1

G H

1, 2 0, 0

1 2

3


Equilibrio di Nash perfetto nei sottogiochi (SNE) Un equilibrio di Nash equilibrium of a dynamic

gadi un gioco dinamico è perfetto nei sottogiochi se le strategie del NE costituiscono un NE in ogni sottogioco del gioco stesso.

SNE è un NE.


Gioco dell’entrata nel mercato

Due equilibri di Nash ( In, Accommodate ) è un SNE. ( Out, Fight ) non è un SNE perché non costituisce un

NE nel sottogioco che comincia dall’Incumbent.

Challenger

In Out

Incumbent

A F 1, 2

2, 1 0, 0

Incumbent

A F

2, 1 0, 0

Accommodate è il NE di questo sottogioco.


Ricerca del SNE: backward induction

Cominciate (al contrario) dai sottogiochi più piccoli Muovete all’indietro fino a raggiungere la radice

Challenger

In Out

Incumbent

A F 1, 2

2, 1 0, 0

Il primo numero è il payoff del challenger.

Il secondo numero è il payoff dell’incumbent.


Ricerca del SNE: backward induction

SNE (DG, E) Il giocatore 1 gioca D, e gioca G se il giocatore 2 gioca E Il giocatore 2 gioca E se il giocatore 1 gioca C

Player 2

E F

Player 1

G H 3, 1

1, 2 0, 0

Player 1

C D

2, 0


Esistenza del SNE

Ogni gioco dinamico finito ad informazione perfetta e completa ha un SNE che può essere ricavato per backward induction.


Contrattazione sequenziale (2.1.D del Gibbons) I giocatori 1 e 2 stanno contrattando su un dollaro. La sequenza

è come segue: All’inizio del primo periodo, il giocatore 1 propone di prendere

una quota s1 del dollaro, lasciando 1-s1 al giocatore 2. Il giocatore 2 o accetta l’offerta o la rifiuta (in questo caso il

gioco passa al secondo stadio) All’inizio del secondo stadio, il giocatore 2 propone al giocatore

1 di prendersi una quota s2 del dollaro, lasciando 1-s2 al giocatore 2.

Il giocatore 1 o accetta l’offerta o la rifiuta (in questo caso il gioco passa al terzo stadio)

All’inizio del terzo periodo, il giocatore 1 riceve una quota s del dollaro, lasciando 1-s al giocatore 2, dove 0<s <1.

I giocatori sono impazienti. Essi scontano i payoff di un tasso di sconto pari a , dove 0< <1


Contrattazione sequenziale (2.1.D del Gibbons)

Player 2

accetta

rifiuta

Propone un’offerta ( s2 , 1-s2 )

Periodo 1

Player 1

accetta

propone un’offerta ( s1 , 1-s1 )

s1 , 1-s1

Player 1 s2 , 1-s2

s , 1-s

Periodo 2

Periodo 3

rifiuta

Player 2


Soluzione del gioco di contrattazione con la backward induction Periodo 2:

Il giocatore 1 accetta s2 se e solo se s2 s. (assumiamo che l’offerta verrà accettata se si è indifferenti)

Il giocatore 2 si trova di fronte a queste due opzioni:(1) offre s2 = s al giocatore 1, lasciando 1-s2 = 1-s per se stesso a questo periodo, oppure(2) offre s2 < s al giocatore 1 (e il giocatore 1 rifiuterà), e riceve 1-s al prossimo periodo. Il calore scontato di questa somma è (1-s)

Dato che (1-s)<1-s, il giocatore 2 dovrebbe proporre un’offerta (s2* , 1-s2* ), dove s2* = s. Il giocatore 1 la accetterà.


Contrattazione sequenziale (2.1.D del Gibbons)

Player 2

accetta

rifiuta

Propone un’offerta ( s2 , 1-s2 )

Periodo 1

Player 1

accetta

propone un offerta ( s1 , 1-s1 )

s1 , 1-s1

Player 1 s2 , 1-s2

s , 1-s

Periodo 2

Periodo 3

rifiuta

Player 2

s , 1- s


Soluzione del gioco di contrattazione con la backward induction Periodo 1:

Il giocatore 2 accetta 1-s1 se e solo se 1-s1 (1-s2*)=(1- s) o s1 1-(1-s2*), dove s2* = s.

Il giocatore 1 ha due opzioni:(1) offre 1-s1 = (1-s2*)=(1- s) al giocatore 2, tenendosi s1 = 1-(1-s2*)=1-+s per se stesso in questo periodo, oppure(2) offre 1-s1 < (1-s2*) al giocatore 2 (il giocatore 2 rifiuterà), e riceve s2* = s il prossimo periodo. Il suo valore scontato sarà però s

Dato che s < 1-+s, il giocatore 1 dovrà proporre un’offerta (s1* , 1-s1* ), dove s1* = 1-+s


Riassunto

SNE Backward induction

Prossimo argomento Il Modello del duopolio di Stackelberg Salari e occupazione in una impresa

sindacalizzata


Backward induction: esempio

SNE (C, EH). Il giocatore 1 gioca C; Il giocatore 2 gioca E se il giocatore 1 gioca C, gioca H

se il giocatore 1 gioca D.

Player 1

C D

Player 2

E F

3, 02, 1

Player 2

G H

1, 30, 2


SNE multipli: esempio

SNE (D, FHK). Il giocatore 1 gioca D Il giocatore 2 gioca F se il giocatore 1 gioca C, gioca H se il

giocatore 1 gioca D, gioca K se il giocatore 1 gioca E.

Player 1

CD

Player 2

F G

1, 00, 1

Player 2

J K

1, 32, 2

Player 2

H I

2, 11, 1

E



SNE (E, FHK). Il giocatore 1 gioca E; Il giocatore 2 gioca F se il giocatore 1 gioca C, gioca H se il


Player 1

CD

Player 2

F G

1, 00, 1

Player 2

J K

1, 32, 2

Player 2

H I

2, 11, 1

E



SNE (D, FIK). Il giocatore 1 gioca D; Il giocatore 2 gioca F se il giocatore 1 gioca C, gioca I se il


Player 1

CD

Player 2

F G

1, 00, 1

Player 2

J K

1, 32, 2

Player 2

H I

2, 11, 1

E


Il modello di duopolio alla Stackelberg

Un prodotto omogeneo è prodotto solo da due imprese: firm 1 and firm 2. Le quantità sono indicate rispettivamente come q1 e q2.

La sequenza di questo gioco è come segue: Firm 1 sceglie una quantità q1 0. Firm 2 osserva q1 e quindi sceglie una quantità q2 0.

Il prezzo di mercato è P(Q)=a –Q, dove a è una costante e Q=q1+q2.

Il costo dell’impresa i di produrre la quantità qi è Ci(qi)=cqi.

Le funzioni di Payoff sono : u1(q1, q2)=q1(a–(q1+q2)–c) u2(q1, q2)=q2(a–(q1+q2)–c)



Trovare, per backward induction, il SNE Prima risolviamo il problema dell’impresa 2

per ogni q1 0 in modo da ottenre la funzione di risposta ottima dell’impresa 2 a q1 . Vale a dire, risolviamo tutti i sottogiochi che cominciano dalla mossa dell’impresa 2.

Fatto ciò, risolviamo il problema dell’impresa 1. Vale a dire, risolviamo il sottogioco che ha inizio dalla mossa dell’impresa 1



Risolvere il problema dell’impresa 2 per ogni q1 0 in modo da ottenere la risposta ottima dell’impresa 2 a ogni q1. Max u2(q1, q2)=q2(a–(q1+q2)–c)

s. a 0 q2 +∞

FOC: a – 2q2 – q1 – c = 0

La risposta ottima dell’impresa 2 sarà, R2(q1) = (a – q1 – c)/2 se q1 a– c

= 0 se q1 > a– c



Risolvere il problema dell’impresa 1. Notate che l’impresa 1 può risolvere anche il problema dell’impresa 2 (common knowledge). Vale a dire, l’impresa 1 conosce la risposta ottima dell’impresa 2 a ogni quantità 1 q1. Quindi, il problema dell’impresa 1 sarà: Max u1(q1, R2(q1))=q1(a–(q1+R2(q1))–c)

s. a 0 q1 +∞

Vale a dire,Max u1(q1, R2(q1))=q1(a–q1–c)/2s. a 0 q1 +∞

FOC: (a – 2q1 – c)/2 = 0 q1 = (a – c)/2



Equilibrio di Nash perfetto nei sottogiochi ( (a – c)/2, R2(q1) ), dove

R2(q1) = (a – q1 – c)/2 se q1 a– c = 0 if q1 > a– c

Vale a dire, l’impresa 1 sceglie una quantità (a – c)/2, l’impresa 2 sceglie una quantità R2(q1) se l’impresa 1 sceglierà una quantità q1.

Il risultato della backward induction è ( (a – c)/2, (a – c)/4 ).

L’impresa 1 sceglie una quantità (a – c)/2, l’impresa 2 sceglie una quantità (a – c)/4.



L’impresa 1 produrrà q1=(a – c)/2 e il suo profitto sarà q1(a–(q1+ q2)–c)=(a–c)2/8

L’impresa 3 produrrà q2=(a – c)/4 e il suo profitto sarà q2(a–(q1+ q2)–c)=(a–c)2/16

La quantità totale prodotta dalle due imprese sarà 3(a – c)/4.


Il modello di duopolio alla Cournot

L’impresa 1 produce q1=(a – c)/3 e il suo profitto sarà q1(a–(q1+ q2)–c)=(a–c)2/9

L’impresa 2 produce q2=(a – c)/3 e il suo profitto sarà q2(a–(q1+ q2)–c)=(a–c)2/9

La quantità totale prodotta dalle due imprese sarà 2(a – c)/3.


Il monopolio

Supponiate che ci sia una sola impresa, un monopolio, che produce il prodotto. Il monopolista, per decidere la quantità qm, deve risolvere il seguente problema:

Max qm (a–qm–c)s. a 0 qm +∞

FOC: a – 2qm – c = 0 qm = (a – c)/2

Il monopolista produce qm=(a – c)/2 e il suo profitto sarà qm(a–qm–c)=(a–c)2/4


Il modello di duopolio alla Bertrand: mosse successive e prodotti differenziati Due imprese: impresa 1 e impresa 2. Ogni impresa sceglie il prezzo per il proprio prodotto. I

prezzi sono rispettivamente indicati con p1 e p2. La sequenza di questo gioco è come segue:

L’impresa 1 sceglie un prezzo p1 0. L’impresa 2 osserva p1 e quindi sceglie p2 0.

La quantità domandata dai consumatori all’impresa 1: q1(p1, p2) = a – p1 + bp2.

La quantità domandata dai consumatori all’impresa 2: q2(p1, p2) = a – p2 + bp1.

I costi dell’impresa i di produrre la quantità qi sono: Ci(qi)=cqi.


Il modello di duopolio alla Bertrand: mosse successive e prodotti differenziati Risolvere il problema dell’impresa 2 per ogni

p1 0 per ottenere la funzione di risposta ottima ad ogni p1. Max u2(p1, p2)=(a – p2 + bp1 )(p2 – c)

s. a 0 p2 +∞

FOC: a + c – 2p2 + bp1 = 0 p2 = (a + c + bp1)/2

La risposta ottima dell’impresa 2 sarà, R2(p1) = (a + c + bp1)/2


Il modello di duopolio alla Bertrand: mosse successive e prodotti differenziati Risolvere il problema dell’impresa 1. Notate che

l’impresa 1 può risolvere il problema dell’impresa 2 (common knowledge). L’impresa 1 conosce quindi la funzione di risposta ottima dell’impresa 2 a p1. Quindi il problema dell’impresa 1 sarà: Max u1(p1, R2(p1))=(a – p1 + bR2(p1) )(p1 – c)

s. a 0 p1 +∞

Vale a dire,Max u1(p1, R2(p1))=(a – p1 + b(a + c + bp1)/2 )(p1 – c)s. a 0 p1 +∞

F.O.C.: a – p1 + b(a + c + bp1)/2+(–1+b2/2) (p1 – c) = 0 p1 = (a+c+(ab+bc–b2c)/2)/(2–b2)


Il modello di duopolio alla Bertrand: mosse successive e prodotti differenziati Equilibrio di Nash perfetto nei sottogiochi

((a+c+(ab+bc–b2c)/2)/(2–b2), R2(p1) ), dove R2(p1) = (a + c + bp1)/2

L’impresa 1 sceglie un prezzo (a+c+(ab+bc–b2c)/2)/(2–b2),

L’impresa 2 sceglie un prezzo R2(p1) se l’impresa 1 sceglie un prezzo p1.


Riassunto

Equilibrio di Nash perfetto nei sottogiochi Backward induction Modello di duopolio alla Stackelberg Modello di duopolio alla Bertrand a mosse

successive e prodotti differenziati

Prossimo argomento Giochi dinamici ad informazione completa ma

imperfetta


Giochi dinamici ad informazione completa ed imperfetta Informazione imperfetta

Un giocatore potrebbe non conoscere CHI ha fatto COSA nel momento in cui si trova a dover compiere una scelta.

Esempio: Il giocatore 2 fa la sua scelta dopo il giocatore 1. Il giocatore 2 ha bisogno di prendere la propria decisione senza sapere cosa ha fatto il giocatore 1.


Informazione imperfetta: esemplificazione Ognuno dei due giocatori ha un

penny. Il giocatore 1 sceglie se giocare

Head o Tail. Dopo ciò, il giocatore 2 sceglie

se giocare Head o Tail senza sapere la mossa del giocatore 1

Entrambi conoscono la regola di attribuzione dei payoffs: Se i due pennies sono

uguali allora vince il giocatore 2.

Se i due pennies sono diversi vince il giocatore 1.

Player 2

Player 1

Player 2

H T

-1, 1 1, -1

H T

H T

1, -1 -1, 1


Insieme informativo

Definizione del Gibbons: Un insieme informativo per un giocatore è una serie di nodi che soddisfa: Il giocatore ha la mossa ad ogni nodo dell’insieme

informativo, e Quando il gioco raggiunge un nodo in un insieme

informativo, il giocatore che deve muovere non sa quale nodo dell’insieme informativo è stato raggiunto.

Tutti i nodi di un insieme informativo appartengono allo stesso giocatore

Il giocatore deve avere lo stesso insieme di azioni possibili ad ogni nodo dell’insieme informativo.


Insieme informativo: esemplificazione

Player 1

L R

Player 2

L’ R’

2, 2, 3

Player 2

L’ R’

3

L” R”

3

L” R”

3

L” R”

3

L” R”

1, 2, 0 3, 1, 2 2, 2, 1 2, 2, 1 0, 1, 1 1, 1, 2 1, 1, 1

Un insieme informativo di player 3 contiene tre nodi

Un insieme informativo di player 3 contiene un nodo

singolo

Due insiemi informativi per player 2 ognuno dei quali contiene un nodo singolo



Tutti i nodi in un insieme informativo appartengono allo stesso giocatore

Player 1

C D

Player 2

E F

3, 0, 22, 1, 3

Player 3

G H

1, 3, 10, 2, 2

Questo NON è un insieme informativo

corretto



Il giocatore deve avere lo stesso insieme di azioni possibili ad ogni nodo dell’insieme informativo

Player 1

C D

Player 2

E F

3, 02, 1

Player 2

G H

1, 30, 2 1, 1

Un insieme informativo NON può contenere questi due nodi

K


Rappresentazione di un gioco statico ad albero: esemplificazione Il dilemma del prigioniero

Prigioniero 1

Prigioniero 2

Prigioniero 1

N C

-1, -1 0, -9

Nega Conf

N C

-9, 0 -6, -6


Esempio: distruzione mutualmente assicurata Fra le due superpotenze, 1 e 2, c’è stato un incidente

diplomatico. La sequenza è come segue: Il gioco comincia con la scelta della superpotenza 1 che può

ignorare l’incidente ( I ), ottenendo i payoffs (0, 0), o esasperare la situazione ( E ).

Se la superpotenza 1 esaspera, La superpotenza 2 può ritrattare ( B ), perdendo la faccia e ottenendo quindi un payoff negativo (1, -1), o può scegliere una risposta con attacco atomico ( A ). Su questa scelta, le due superpotenze giocano il seguente gioco a mosse simultanee.

Possono entrambe Ritrattare ( R ) o scegliere l’Attacco ( D ) nel qual caso il mondo è distrutto. Se entrambe scelgono di ritrattare entrambe hanno una piccola perdita e il payoff sarà (-0.5, -0.5). Se entrambe scelgono l’attacco atomico il payoff sarà (-K, -K), dove K è un numero molto grande.


Esempio: distruzione reciproca

1

I E

0, 0

2

B A

1, -11

2

R D

-0.5, -0.5 -K, -K

R D

R D

2

-K, -K -K, -K


Informazione perfetta e informazione imperfetta Un gioco dinamico nel quale ogni insieme

informativo contiene esattamente un nodo è chiamato gioco ad informazione perfetta.

Un gioco dinamico nel quale alcuni insiemi informativi contengono più di un nodo è chiamato gioco ad informazione imperfetta.


Strategia e payoff Una strategia è un

piano completo di azione.

Specifica una possibile azione per un giocatore in qualsiasi contingenza nella quale esso sia chiamato in causa.

Specifica cosa fa il giocatore ad ogni suo insieme informativo

Player 1

Player 2

H T

-1, 1 1, -1

H T

Player 2

H T

1, -1 -1, 1

La strategia per player 1: H

Una strategia per player 2: T

Il payoff del giocatore 1 è 1 e il payoff del giocatore 2 è -1 se il giocatore 1 gioca H e il giocatore 2 gioca T


Strategia e payoff: esemplificazione

1

I E

0, 0

2

B A

1, -11

2

R D

-0.5, -0.5 -K, -K

R D

R D

2

-K, -K -K, -K

Una strategia per il giocatore 1: E, e R se il giocatore 2 gioca A,

scritta come ER

Una strategia per il giocatore 2: A, R, se il giocatore 1 gioca E, scritta come AR


Il NE in un gioco dinamico

Possiamo usare anche la forma normale per rappresentare un gioco dinamico

L’insieme degli NE in un gioco dinamico ad informazione completa è l’insieme degli Nenella sua forma normale

Come trovare l’NE in un gioco dinamico ad informazione completa Costruite la forma normale del gioco dinamico

ad informazione completa Trovate l’NE nella forma normale


Rimuovere gli NE non ragionevoli

SNE è un NE raffinato Puo eliminare NE non ragionevoli o minacce

non credibili

Ma prima dobbiamo definire i sottogiochi


Sottogioco

Un sottogioco in un albero di gioco dinamico Comincia ad un insieme informativo singletone (che

contiene un nodo singolo), e Include tutti i nodi e segmenti che seguono il

singleton, e NON spezza nessun insieme informativo; vale a

dire, se un nodo di un insieme informativo appartiene a questo sottogioco allora tutti i nodi dell’insieme informativo devono anche appartenere al sottogioco.


Sottogioco: esemplificazione1

I E

0, 0

2

B A

1, -11

2

R D

-0.5, -0.5 -K, -K

R D

R D

2

-K, -K -K, -K

un sottogioco

un sottogioco

NON è un sottogioco


Equilibrio di Nash perfetto nei sottogiochi L’NE di un gioco dinamico è perfetto nei

sottogiochi se le strategie del NE costituiscono o inducono un NE in ogni sottogioco del gioco.

SNE è un NE.


Ricerca del SNE: backward induction1

I E

0, 0

2

B A

1, -11

2

R D

-0.5, -0.5 -K, -K

R D

R D

2

-K, -K -K, -K

Un sottogioco

un sottogioco

Iniziate con i sottogiochi più piccoliMuovete all’indietro fino a raggiungere la radice

Un SNE( IR, AR )


Ricerca del SNE: backward induction1

I E

0, 0

2

B A

1, -11

2

R D

-0.5, -0.5 -K, -K

R D

R D

2

-K, -K -K, -K

Un sottogioco

Un sottogioco

Un altro SNE( ED, BD )

Iniziate con i sottogiochi più piccoliMuovete all’indietro fino a raggiungere la radice


Investimento Bancario

Due investitori, 1 e 2, hanno ognuno un deposito di D con una banca.

La banca ha investito questi depositi in un progetto a lungo termine. Se la banca liquida gli investimenti prima che il progetto maturi, si ottiene un totale di 2r, dove D > r > D/2.

Se l’investimento bancario invece matura, il progetto pagherà un capitale pari a 2R, dove R>D.

Ci sono due date soltanto nelle quali gli investitori possono prelevare i soldi investiti nella banca.


Investimenti bancari: sequenza del gioco La sequenza del gioco è come segue Data 1 (prima che l’investimento bancario maturi)

I due investitori giocano un gioco a mosse simultanee Se entrambi prelevano alloro ognuno riceve r e il gioco finisce Se solo uno fa un prelievo allora lui riceve D, l’altro riceve 2r-D, e il

gioco finisce Se nessuno fa un prelevamento allora il progetto matura il

rendimento e il gioco continua alla Data 2.

Data 2 (dopo che l’investimento ha maturato rendimenti) Due investitori giocano un gioco a mosse simultanee Se entrambi fanno prelevamenti allora ognuno riceve R e il gioco

finisce Se solo uno preleva allora lui riceve 2R-D, l’altro riceve D, e il gioco

finisce Se nessuno preleva allora la banca restituisce R a ogni investitore

e il gioco finisce.


Investimenti bancari: l’albero1

W NW

2

W NW

1

2

W NW

W NW

W NW

2

Un sottogioco

Un SNE( NW W, NW W )

W

r, r

NWData 1

Data 2

W: prelevaNW: non preleva

2

D, 2r–D 2r–D, D

R, R D, 2R–D2R–D, D R, R


Investimenti bancari: l’albero1

W NW

2

W NW

1

2

W NW

W NW

W NW

2

Un altro SNE( W W, W W )

W

r, r

NWData 1

Data 2

W: prelevaNW: non preleva

2

D, 2r–D 2r–D, D

R, R D, 2R–D2R–D, D R, R

Un sottogioco


Dazi e concorrenza internazionale imperfetta Due nazioni identiche, 1 e 2, scelgono simultaneamente i propri

dazi, denotati rispettivamente da t1, t2. L’impresa 1 della nazione 1 e l’impresa 2 dalla nazione 2

producono un prodotto omogeneo sia per il consumo interno sia per esportarlo.

Dopo aver osservato i dazi scelti dalle due nazioni, l’impresa 1 e l’impresa w scelgono simultaneamente le quantità da destinare al consumo interno e all’esportazione, indicate rispettivamente con (h1, e1) e (h2, e2).

I prezzi di mercato nelle due nazioni sono Pi(Qi)=a–Qi, for i=1, 2. Q1=h1+e2, Q2=h2+e1.

Entrambe le imprese hanno costi marginali costanti c. Ogni impresa paga i dazi sulle esportazioni all’altra nazione.


Dazi e concorrenza internazionale imperfetta

Il payoff dell’impresa 1 e il suo profitto:

12111211212211211 )()]([)]([),,,,,( etehceheahehaehehtt

Il payoff dell’impresa 2 e il suo profitto:




Il payoff della nazione 1 è il suo benessere totale: somma dei surplus dei consumatori della nazione 1, il profitto dell’impresa 1 e il ricavo ottenuto dai dazi.

212211211212211211 ),,,,,(

2

1),,,,,( etehehttQehehttW

dove 211 ehQ .

Il payoff della nazione 2 è il suo benessere totale: somma dei surplus dei consumatori della nazione 2, il profitto dell’impresa 2 e il ricavo ottenuto dai dazi.

122211212222211212 ),,,,,(

2


dove 122 ehQ .


Backward induction: sottogioco tra le due impreseTroviamo l’equilibrio di Nash del sottogioco fra le due imprese per ogni coppia di dazi ) ,( 21 tt .

L’impresa 1 massimizza


FOC: )(

2

1 02

)(2

1 02

221221

2121

tchaetchea

ceahceha

L’impresa 2 massimizza


FOC: )(

2

1 02

)(2

1 02

112112

1212

tchaetchea

ceahceha


Backward induction: sottogioco tra le due imprese

Troviamo l’equilibrio di Nash del sottogioco fra le due imprese per ogni coppia di dazi ) ,( 21 tt .

Dato ) ,( 21 tt , un equilibrio di Nash ) ) ,( ), ,( ( *2

*2

*1

*1 eheh del sottogioco

deve soddisfare queste equazioni.

)(21

)(21

221

21

tchae

ceah

)(21

)(21

112

12

tchae

ceah

Risolvere queste equazioni ci porta alle soluzioni

)2(31

)(31

)2(31

)(31

1*22

*2

2*11

*1

tcaetcah

tcaetcah


Backward induction: l’intero gioco

Entrambi le nazioni possono calcolarsi a priori la risposta ottima delle due imprese a ) ,( 21 tt

L’impresa 1 massimizza ( 211 ehQ )

212211211212211211 ),,,,,(

2


Sostituendo quanto precedentemente ottenuto nella funzione obiettivo della nazione 1 otteniamo:

)2(3

1)2(

3

1))2(

3

1)(

3

2(

)2(3

1)

3

1)(

3

2()(

3

1)

3

1)(

3

2())(2(

18

1

112221

22112

1

tcattcatttcac

tcatcaatcatcaatca

FOC:

)(3

11 cat

Per simmetria, otteniamo anche )(3

12 cat



L’equilibrio di Nash perfetto nei sottogiochi

)2(3

1

)(3

1

,)2(

3

1

)(3

1

),(3

1 ),(

3

1

12

22

21

11*2

*1

tcae

tcah

tcae

tcahcatcat

Il risultato finale perfetto nei sottogiochi

)(9

1

)(9

4

,)(

9

1

)(9

4

),(3

1 ),(

3

1*2

*2

*1

*1

*2

*1

cae

cah

cae

cahcatcat


Generalizzazione del gioco dei dazi

Quattro giocatori: 1, 2, 3, 4. La sequenza del gioco è come segue:

Stadio 1: I giocatori 1 e 2 scelgono simultaneamente le azioni a1 e a2 dall’insieme delle azioni rispettivamente possibili A1 e A2.

Stadio 2:Dopo aver osservato il risultato (a1, a2) del primo stadio, I giocatori 3 e 4 scelgono simultaneamente le azioni a3 e a4 dall’insieme delle azioni rispettivamente possibili A3 e A4.

Il gioco finisce. I payoff sono ui(a1, a2, a3, a4), per i=1, 2, 3, 4


Albero informale del giocoGioc. 1

Stadio 1

Stadio 2

Gioc. 2

Gioc. 3

Insieme delle azioni del gioc. 2 A2



Gioc. 4

4 3, 2, ,1per ), , , ,( 4321 iaaaaui

a1

a2

a3

a4

Uno dei sottogiochi più piccoli a seguito di (a1, a2)



Backward induction: risolvete il sottogioco più piccoloIl sottogioco più piccolo che segue ogni coppia di (a1, a2) è un gioco a mosse simultanee giocato dai giocatori 3 e 4 con la seguente rappresentazione in forma normale:

Un insieme di giocatori: {gioc. 3, gioc. 4}

Insiemi di azioni: A3, A4

Payoffs: ) , , ,(

) , , ,(

43214

43213

aaaau

aaaau

Notate che a1, a2 possono essere considerate costanti quando risolviamo questo gioco simultaneo fra il giocatore 3 e 4.

Dopo aver fatto ciò, otterremo un NE ) ,( *4

*3 aa . Ciò è funzione di a1 e

a2, e possiamo scrivere quindi

) ,( ,) ,( 214*4213

*3 aaRaaaRa

Queste individuate sono le funzioni di risposta ottima ad (a1, a2).


Backward induction: ritornate alla radice

)) ,( ), ,( , ,(

)) ,( ), ,( , ,(

214213212

214213211

aaRaaRaau

aaRaaRaau

Gioc. 1

Stadio 1

Stadio 2

Gioc. 2

a1

a2

Sostituite i sottogiochi più piccoli con i payoffs dei giocatori 1 e 2.

I giocatori 1 e 2 sanno che se giocheranno rispettivamente a1 e a2, , allora i giocatori 3 e 4 giocheranno ) ,( ,) ,( 214

*4213

*3 aaRaaaRa .




Backward induction: ritornate alla radiceAdesso I giocatori 1 e 2 giocano un gioco a mosse simultaneecon la seguente rappresentazione in forma normale:

Un insieme di giocatori: {gioc. 1, gioc. 2}

Insiemi di azioni: A1, A2

Payoffs: )) ,( ), ,( , ,(

)) ,( ), ,( , ,(

214213212

214213211

aaRaaRaau

aaRaaRaau

Dopo aver risolto ciò, otteniamo un NE ) ,( *2

*1 aa .

L’SNE dell’intero gioco sarà

)) ,( ,) ,( , ,( 214213*2

*1 aaRaaRaa

Il risultato attuale del gioco sarà )) ,( ,) ,( , ,( *2

*14

*2

*13

*2

*1 aaRaaRaa .


Riassunto

Giochi dinamici ad informazione completa ed imperfetta

Equilibrio di Nash perfetto nei sottogiochi Backward induction

Prossimo argomento Giochi ripetuti

Teoria dei giochi - D'Orio - seconda parte1 Giochi dinamici ad informazione completa Corso di Teoria...

Documents

Transcript of Teoria dei giochi - D'Orio - seconda parte1 Giochi dinamici ad informazione completa Corso di Teoria...