Teoria dei giochi - D'Orio - I parte1 Giochi statici (o a mosse simultanee) con informazione...

Teoria dei giochi - D'Orio - I parte 1

Giochi statici (o a mosse simultanee) con informazione completa

Corso di Teoria dei Giochi

Laurea specialistica in Economia Applicata

Docente: Giovanni D’Orio

E-mail: [email protected]


Prospetto di sintesi dei giochi statici ad informazione completa Introduzione ai giochi Rappresentazione in forma Normale (o

strategica) Eliminazione iterata delle strategie

strettamente dominate Equilibrio di Nash Ripasso delle funzioni concave,

ottimizzazione Applicazione dell’equilibrio di Nash Equilibrio di Nash in strategie miste


Agenda

Che cosa è la teoria dei giochi Esempi

Dilemma del prigioniero La battaglia dei sessi Matching pennies

Giochi statici ad informazione completa (o a mosse simultanee)

Rappresentazione in forma Normale o strategica


Che cosa è la teoria dei giochi?

Noi ci concentreremo su giochi dove: Ci sono almeno due giocatori razionali Ogni giocatore ha più di una scelta Il risultato finale dipende dalle strategie scelte da tutti i

giocatori; c’è interazione strategica.

Esempio: Sei persone vanno ad un ristorante. Ogni persona paga il proprio pasto – un problema

semplice di decisione Prima del pranzo, ogni persona è d'accordo a dividere

il conto fra tutti i partecipanti – un gioco


Che cosa è la teoria dei giochi?

La Teoria dei Giochi è un modo formale di analizzare l’interazione strategica tra un gruppo di giocatori (o agenti) razionali che si comportano strategicamente

La teoria dei giochi ha applicazioni Economiche Politiche etc.


Esempio Classico: Il Dilemma del prigioniero Due sospetti detenuti in celle separate sono accusati di un crimine

rilevante. Non ci sono però prove sufficienti. Ad entrambi I sospetti viene comunicata la seguente regola:

Se nessuno confessa allora entrambi saranno accusati di un crimine minore e condannati ad un mese di carcere.

Se entrambi confessano allora entrambi saranno condannati a sei mesi di carcere.

Se uno confessa ma l’altro nega, allora chi confessa sarà rilasciato ma l’altro sconterà nove mesi di carcere.

-1 , -1 -9 , 0

0 , -9 -6 , -6Prigioniero 1

Prigioniero 2

Confessa

Nega

Confessa

Nega


Esempio: La battaglia dei sessi

In posti separati, Chris e Pat devono scegliere di passare la serata all’opera o a un combattimento di boxe.

Sia Chris che Pat sanno quanto segue: Entrambi vorrebbero passare la serata insieme. Ma Chris preferisce l’opera. Pat preferisce la boxe.

2 , 1 0 , 0

0 , 0 1 , 2Chris

Pat

Boxe

Opera

Boxe

Opera


Esempio: Matching pennies Ognuno dei due giocatori ha una monetina. I due giocatori devono scegliere simultaneamente se mostrare

Testa o Croce. Entrambi i giocatori conoscono le seguenti regole:

Se le due monetine hanno entrambi lo stesso esito (entrambe testa or entrambe croce) allora il giocatore 2 vince la moneta del giocatore 1.

In caso diverso, il giocatore 1 vince la moneta del giocatore 2.

-1 , 1 1 , -1

1 , -1 -1 , 1Giocatore 1

Giocatore 2Croce

Testa

Croce

Testa


Gioco statico (o a mosse simultanee) con informazione completa

Un insieme di giocatori (almeno 2)

Per ogni giocatore, un insieme di strategie/azioni

Payoffs ottenuti da ogni giocatore data la combinazione delle strategie, o preferenze per ogni giocatore sulle combinazioni delle strategie

{Giocat. 1, Giocat. 2, ... Giocat. n}

S1 S2 ... Sn

ui(s1, s2, ...sn), per ogni s1S1, s2S2, ... snSn.

Un gioco statico consiste di:


Gioco statico (o a mosse simultanee) con informazione completa Mosse simultanee

Ogni giocatore sceglie la propria strategia senza conoscere la scelta degli altri.

Informazione completa Ogni strategia possibile di ogni giocatore e la funzione dei

payoff sono conoscenza comune fra tutti I giocatori. Assunzioni sui giocatori

Razionalità• I giocatori vogliono massimizzare il proprio payoffs• I giocatori sono dei calcolatori perfetti (no errori)

Ogni giocatore sa che gli altri giocatori sono razionali


Gioco statico (o a mosse simultanee) con informazione completa I giocatori cooperano?

No. Questi sono giochi non cooperativi Il timing (la sequenza degli eventi)

Ogni giocatore i sceglie la propria strategia si senza conoscere la scelta altrui.

Solo adesso ogni giocatore i riceve il proprio payoff ui(s1, s2, ..., sn).

Il gioco finisce


Definizione: Rappresentazione in forma normale o strategica La rappresentazione in forma normale (o

strategica) di un gioco G specifica: Un insieme finito di giocatori {1, 2, ..., n}, Lo spazio delle strategie dei giocatori S1

S2 ... Sn e

Le funzioni di pay-off u1 u2 ... un dove ui : S1 × S2 × ...× Sn→R.


Rappresentazione in forma normale: gioco a 2 giocatori

Rappresentazione Bi-matriciale 2 giocatori: Player 1 e Player 2 Ogni giocatore ha un numero finito di strategie

Esempio:S1={s11, s12, s13} S2={s21, s22}

Player 2

s21 s22

Player 1

s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)

s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)

s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)


Esempio Classico: Rappresentazione “normale” del Dilemma del Prig. Insieme di giocatori:{Prigioniero 1, Prigioniero 2} Insieme delle strategie: S1 = S2 = {Nega, Confessa} Funzioni di Payoff :

u1(N, N)=-1, u1(N, C)=-9, u1(C, N)=0, u1(C, C)=-6;u2(N, N)=-1, u2(N, C)=0, u2(C, N)=-9, u2(C, C)=-6

-1 , -1 -9 , 0

0 , -9 -6 , -6Prig. 1

Prig. 2

Confessa

Nega

Confessa

NegaGiocat.

Strateg.

Payoffs



Rappresentazione in forma Normale: Insieme giocatori:{ Chris, Pat } (={Player 1, Player 2}) Insieme strategie: S1 = S2 = { Opera, Boxe}

Funzioni di Payoff : u1(O, O)=2, u1(O, B)=0, u1(B, O)=0, u1(B, B)=1; u2(O, O)=1, u2(O, B)=0, u2(B, O)=0, u2(B, B)=2

2 , 1 0 , 0

0 , 0 1 , 2Chris

Pat

Boxe

Opera

Boxe

Opera


Esempio: Matching pennies

Rappresentazione in forma normale: Insieme giocatori: {Player 1, Player 2} Insieme strategie: S1 = S2 = { Testa, Croce }

Funzioni di Payoff : u1(T, T)=-1, u1(T, C)=1, u1(C, T)=1, u1(C, C)=-1; u2(T, T)=1, u2(T, C)=-1, u2(C, T)=-1, u2(C, C)=1

-1 , 1 1 , -1

1 , -1 -1 , 1Player 1

Player 2

Croce

Testa

Croce

Testa


Esempio: Turisti e Nativi

Solo due bars (bar 1, bar 2) in città Si può applicare un prezzo di $2, $4, o $5 6000 turisti scelgono un bar casualmente 4000 nativi scelgono il bar con il prezzo minore

Esempio 1: Entrambi fissano $2 Ognuno guadagna 5,000 clienti e $10,000

Esempio 2: Il Bar 1 fissa $4, Il Bar 2 fissa $5 Bar 1 prende 3000+4000=7,000 clienti e $28,000 Bar 2 prende 3000 clienti e $15,000


Esempio: Il modello di duopolio di Cournot Un prodotto è prodotto solo da 2 imprese: impresa 1

e impresa 2. Le quantità sono rispettivamente q1 e q2,. Ogni impresa sceglie la quantità senza conoscere la quantità scelta dall’altra..

Il prezzo di mercato è P(Q)=a-Q, dove Q=q1+q2. Il costo dell’impresa i di produrre qi è Ci(qi)=cqi.

Rappresentazione in forma normale: Insieme giocatori: { Firm 1, Firm 2} Insieme strategie: S1=[0, +∞), S2=[0, +∞) Funzione di Payoff :

u1(q1, q2)=q1(a-(q1+q2)-c), u2(q1, q2)=q2(a-(q1+q2)-c)


Ancora un esempio

Ognuno di n giocatori seleziona un numero tra 0 e 100 simultaneamente. Sia xi il numero selezionato dal giocatore i.

Sia y la media di questi numeri Il payoff del giocatore i sia = xi – 3y/5

La rappresentazione in forma normale:


Risolvere il Dilemma del Prigioniero

Confessare dà sempre un risultato migliore indipendentemente dalla scelta dell’altro

Strategia dominata Esiste un’altra strategia che dà sempre risultati migliori

indipendentemente dalla scelta degli altri.

-1 , -1 -9 , 0

0 , -9 -6 , -6Prigion. 1

Prisoner 2

Confessa

Nega

Confessa

NegaGiocatori

Strategie

Payoffs


Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un}, siano si', si" Si strategie possibili per I giocatori i. La strategia si' è strettamente dominata dalla strategia si" se

ui(s1, s2, ... si-1, si', si+1, ..., sn) < ui(s1, s2, ... si-1, si", si+1, ..., sn)

Per ogni s1 S1, s2 S2, ..., si-1Si-1, si+1 Si+1, ..., sn Sn.

Definizione: strategie strettamente dominate

-1 , -1 -9 , 0

0 , -9 -6 , -6Prig. 1

Prig. 2

Confessa

Nega

Confessa

NegaIndipend. Scelta altrui

si” è strettamente meglio di si’


Riassunto

Giochi statici ad informazione completa Rappresentazione normale o strategica

Prossimo argomento Strategie dominate Eliminazione iterata di strategie strettamente

dominate Equilibrio di Nash


Ripasso veloce

La forma normale di un gioco G specifica: Un insieme finito di giocatori {1, 2, ..., n}, Lo spazio delle strategie dei giocatori S1 S2 ... Sn e

Le loro funzioni di payoff u1 u2 ... un dove ui : S1 × S2 × ...× Sn→R.

Prig. 2

Nega Confessa

Prig. 1Nega -1 , -1 -9 , 0

Confessa 0 , -9 -6 , -6

Tutte le combinazioni delle strategie.

Una combinazione di strategie è un insieme di strategie, una per ogni giocatore


Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un}, siano si', si" Si strategie possibili per I giocatori i. La strategia si' è strettamente dominata dalla strategia si" se

ui(s1, s2, ... si-1, si', si+1, ..., sn) < ui(s1, s2, ... si-1, si", si+1, ..., sn)

Per ogni s1 S1, s2 S2, ..., si-1Si-1, si+1 Si+1, ..., sn Sn.

Definizione: strategie strettamente dominate

-1 , -1 -9 , 0

0 , -9 -6 , -6Prig. 1

Prig. 2

Confessa

Nega

Confessa

NegaIndipend. Scelta altrui

si” è strettamente meglio di si’


Esempio

Due imprese, Reynolds e Philip, si dividono il mkt. Ogni impresa guadagna $60 milioni dalla propria

clientela se nessuna fa pubblicità (Ad) La pubblicità costa all’impresa $20 milioni La pubblicità attrae $30 milioni di fatturato dell’altro

concorrente

Philip

No Ad Ad

ReynoldsNo Ad 60 , 60 30 , 70

Ad 70 , 30 40 , 40


Gioco a 2 con strategie finite

S1={s11, s12, s13} S2={s21, s22} s11 è strettamente dominata da s12 se

u1(s11,s21)<u1(s12,s21) e u1(s11,s22)<u1(s12,s22). s21 è strettamente dominata da s22 se

u2(s1i,s21) < u2(s1i,s22), per i = 1, 2, 3

Player 2

s21 s22

Player 1

s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)

s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)

s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)


Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un}, siano si', si" Si strategie possibili per il giocatore i. La strategia si' è debolmente dominata dalla strategia si" se

ui(s1, s2, ... si-1, si', si+1, ..., sn) (ma non sempre =) ui(s1, s2, ... si-1, si", si+1, ..., sn)

per tutte s1 S1, s2 S2, ..., si-1Si-1, si+1 Si+1, ..., sn Sn.

Definizione: strategie debolmente dominate

1 , 1 2 , 0

0 , 2 2 , 2Player 1

Player 2

R

U

B

LQualsiasi sia la scelta altrui

si” è almeno tanto buono quanto si’


Strategie dominate in modo stretto o in modo debole Un giocatore razionale non sceglie mai

strategie strettamente dominate. Quindi ogni strategia strettamente dominata può essere eliminata.

Un giocatore razionale può scegliere una strategia debolmente dominata.


Eliminazione iterata di strategie strettamente dominate Se una strategia è strettamente dominata,

eliminatela La dimensione e complessità del gioco

risulterà ridotta Eliminate ogni strategia strettamente

dominata dal gioco ridotto Continuate le eliminazioni finchè non ci

saranno più strategie strettam. dominate


Eliminazione iterata di strategie strettamente dominate: un esempio

1 , 0 1 , 2 0 , 1

0 , 3 0 , 1 2 , 0Player 1

Player 2

Centro

Su

Giù

Sinistra

1 , 0 1 , 2

0 , 3 0 , 1Player 1

Player 2

Centro

Su

Giù

Sinistra

Destra



Solo due bar (bar 1, bar 2) in una città Si possono fissare prezzi di $2, $4, o $5 6000 turisti scelgono un bar casualmente 4000 nativi selezionano il bar con il prezzo inferiore

Esempio 1: Entrambi fissano $2 Ognuno attrae 5,000 clienti e $10,000

Esempio 2: Bar 1 fissa $4, Bar 2 fissa $5 Bar 1 attrae 3000+4000=7,000 clienti e $28,000 Bar 2 attrae 3000 clienti e $15,000



Bar 2

$2 $4 $5

Bar 1

$2 10 , 10 14 , 12 14 , 15

$4 12 , 14 20 , 20 28 , 15

$5 15 , 14 15 , 28 25 , 25

Payoffs sono in migliaia di dollari

Bar 2

$4 $5

Bar 1$4 20 , 20 28 , 15

$5 15 , 28 25 , 25


Ancora un esempio

Ognuno di n giocatori seleziona un numero tra 0 e 100 simultaneamente. Sia xi il numero selezionato dal giocatore i.

Sia y la media di questi numeri Il payoff del giocatore I sarà = xi – 3y/5


Un esempio ulteriore

La rappresentazione in forma normale: Giocatori: {player 1, player 2, ..., player n} Strategie: Si =[0, 100], per i = 1, 2, ..., n.

Funzione di payoff:

ui(x1, x2, ..., xn) = xi – 3y/5

Ci sono strategie dominate?

Quali numeri dovrebbero essere selezionati?


Un nuovo concetto di soluzione: l’equilibrio di Nash

Giocat. 2

L C R

Giocat. 1

T 0 , 4 4 , 0 5 , 3

M 4 , 0 0 , 4 5 , 3

B 3 , 5 3 , 5 6 , 6

La combinazione di strategie (B, R) ha la seguente proprietà:

Il Giocatore 1 NON PUO’ fare meglio scegliendo una strategia diversa da B, dato il fatto che giocatore 2 sceglie R.

Il Giocatore 2 NON PUO’ fare meglio scegliendo una strategia diversa da R, dato il fatto che il giocatore 1 sceglie B.


Un nuovo concetto di soluzione: l’equilibrio di Nash

Giocat. 2

L’ C’ R’

Giocat. 1

T’ 0 , 4 4 , 0 3 , 3

M’ 4 , 0 0 , 4 3 , 3

B’ 3 , 3 3 , 3 3.5 , 3.6

La combinazione di strategie (B’, R’) ha la seguente proprietà:

Il giocatore 1 NON PUO’ fare meglio scegliendo una strategia diversa da B’, dato il fatto che il giocatore 2 sceglie R’.

Il giocatore 2 NON PUO’ fare meglio scegliendo una strategia diversa da R’, dato il fatto che il giocatore 1 sceglie B’.


Equilibrio di Nash : l’idea

L’equilibrio di Nash Un insieme di strategie, una per ogni

giocatore, tale che la strategia di ogni giocatore sia la migliore risposta possibile nel momento in cui gli altri giocatori stanno giocando le loro strategie di equilibrio.

BR to BR= Best response to a best response


Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 ,

u2 , ..., un}, una combinazione di strategie ),...,( **1 nss è

un equilibrio di Nash se, per ogni giocat. i,

),...,,,,...,(

),...,,,,...,(

**1

*1

*1

**1

**1

*1

niiii

niiii

sssssu

sssssu

per tutte ii Ss . Ciò implica che, *is solve

Max ),...,,,,...,( **1

*1

*1 niiii sssssu

soggetto a ii Ss

Definizione: L’equilibrio di Nash

Data la scelta altrui, il giocat. i non può migliorare se devia da si*

Prig. 2

Nega Confessa

Prig. 1Nega -1 , -1 -9 , 0

Confessa 0 , -9 -6 , -6


Gioco a 2 giocatori con strategie finite

S1={s11, s12, s13} S2={s21, s22} (s11, s21)è un equilibrio di Nash se u1(s11,s21) u1(s12,s21), u1(s11,s21) u1(s13,s21) eu2(s11,s21) u2(s11,s22).

Giocatore 2

s21 s22

Gioc. 1

s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)

s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)

s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)


Ricerca dell’equilibrio di Nash: ispezione cella a cella

1 , 0 1 , 2 0 , 1

0 , 3 0 , 1 2 , 0Player 1

Player 2

Middle

Up

Down

Left

1 , 0 1 , 2

0 , 3 0 , 1Player 1

Player 2

Middle

Up

Down

Left

Right


Riassunto

Strategie dominate Eliminazione iterata Equilibrio di Nash

Prossimo argomento Equilibrio di Nash Funzione di risposta ottima


Equilibrio di Nash : idea

Equilibrio di Nash Un insieme di strategie, una per ogni giocatore, tale

che la strategia di ogni giocatore sia la sua migliore possibile considerato che tutti gli altri giocatori stanno giocando la loro migliore strategia o

Una situazione stabile nella quale nessun giocatore vuole deviare se gli altri confermano la propria posizione

Prig. 2

Nega Confessa

Prig. 1Nega -1 , -1 -9 , 0

Confessa 0 , -9 -6 , -6

(Confessa, Confessa) è un equilibro di Nash.



Bar 2

$2 $4 $5

Bar 1

$2 10 , 10 14 , 12 14 , 15

$4 12 , 14 20 , 20 28 , 15

$5 15 , 14 15 , 28 25 , 25

Payoffs sono in migliaia di dollari

Bar 2

$4 $5

Bar 1$4 20 , 20 28 , 15

$5 15 , 28 25 , 25


Ancora quell’esempio

Rappresentazione in forma normale: Giocatori: {player 1, player 2, ..., player n} Strategie: Si =[0, 100], for i = 1, 2, ..., n.

Funzioni di Payoff :

ui(x1, x2, ..., xn) = xi – 3y/5

Quale è l’equilibrio di Nash?


Funzione di risposta ottima: esempio

Se Player 2 sceglie L’ allora la strategia ottima di Player 1 è M’ Se Player 2 sceglie C’ allora la strategia ottima di Player 1 è T’ Se Player 2 sceglie R’ allora la strategia ottima di Player 1 è B’ Se Player 1 sceglie B’ allora la strategia ottima di Player 2’ è R’

Risposta ottima: la migliore strategia giocabile da un giocatore, data la strategia scelta da altri giocatori

Player 2

L’ C’ R’

Player 1

T’ 0 , 4 4 , 0 3 , 3

M’ 4 , 0 0 , 4 3 , 3

B’ 3 , 3 3 , 3 3.5 , 3.6



Quale è la risposta ottima del Bar 1 alle strategie di Bar 2 pari a $2, $4 o $5?

Quale è la risposta ottima del Bar 2 alle strategie di Bar 1 pari a $2, $4 or $5?

Bar 2

$2 $4 $5

Bar 1

$2 10 , 10 14 , 12 14 , 15

$4 12 , 14 20 , 20 28 , 15

$5 15 , 14 15 , 28 25 , 25

Payoffs in migliaia di dollari


Gioco a 2 giocatori con strategie finite

S1={s11, s12, s13} S2={s21, s22} La strategia di Player 1 s11 è la migliore risposta alla

strategia di Player 2 s21 se u1(s11,s21) u1(s12,s21) eu1(s11,s21) u1(s13,s21).

Player 2

s21 s22

Player 1

s11 u1(s11,s21), u2(s11,s21) u1(s11,s22), u2(s11,s22)

s12 u1(s12,s21), u2(s12,s21) u1(s12,s22), u2(s12,s22)

s13 u1(s13,s21), u2(s13,s21) u1(s13,s22), u2(s13,s22)


Utilizzo delle funzioni di risposta ottima per trovare l’equilibrio di Nash In un gioco a due giocatori, ( s1, s2 ) è un

equilibrio di Nash se e solo se la strategia di player 1’ s1 è la migliore risposta alla strategia di player 2 s2, e la strategia di player 2 s2 è la migliore risposta alla strategia di player 1 s1.

-1 , -1 -9 , 0

0 , -9 -6 , -6Prisoner 1

Prisoner 2

Confess

Mum

Confess

Mum


Utilizzo delle funzioni di risposta ottima per trovare l’equilibrio di Nash : esempio

M’ è la risposta ottima di Player 1 alla strategia L’ di Player 2 T’ è la risposta ottima di Player 1 alla strategia C’ di Player 2 B’ è la risposta ottima di Player 1 alla strategia R’ di Player 2 L’ è la risposta ottima di Player 2 alla strategia T’ di Player 1 C’ è la risposta ottima di Player 2 alla strategia M’ di Player 1 R’ è la risposta ottima di Player 2 alla strategia B’ di Player 1

Player 2

L’ C’ R’

Player 1

T’ 0 , 4 4 , 0 3 , 3

M’ 4 , 0 0 , 4 3 , 3

B’ 3 , 3 3 , 3 3.5 , 3.6



Bar 2

$2 $4 $5

Bar 1

$2 10 , 10 14 , 12 14 , 15

$4 12 , 14 20 , 20 28 , 15

$5 15 , 14 15 , 28 25 , 25

I Payoffs sono in migliaia di dollari

Usate la funzione di rsposta ottima per trovare l’equilibrio di Nash.



Opera è la risposta ottima di Player 1 alla strategia di Player 2 Opera Opera è la risposta ottima di Player 2 alla strategia di Player 1 Opera

Quindi, (Opera, Opera) è un Equilibrio di Nash

Fight è la risposta ottima di Player 1 alla strategia di Player 2 Fight Fight è la risposta ottima di Player 2 alla strategia di Player 1 Fight

Quindi, (Fight, Fight) è un Equilibrio di Nash

2 , 1 0 , 0

0 , 0 1 , 2Chris

Pat

Prize Fight

Opera

Prize Fight

Opera


Esempio: Matching pennies

Head è la risposta ottima di Player 1 alla strategia di Player 2 Tail Tail è la risposta ottima di Player 2 alla strategia di Player 1 Tail

Tail è la risposta ottima di Player alla strategia di Player 2 Head Head è la risposta ottima di Player 2 alla strategia di Player 1 Head

Quindi, NON c’è equilibrio di Nash

-1 , 1 1 , -1

1 , -1 -1 , 1Player 1

Player 2

Tail

Head

Tail

Head


Nel gioco in forma normale {S1 , S2 , ..., Sn , u1 , u2 , ..., un},

Se i giocat. 1, 2, ..., i-1, i+1, ..., n scelgono rispettivamente

nii ssss ,...,,,..., 111 , strategie, Allora la funzione di risposta ottima del giocatore i è

definita da } le per tutte ),,...,,,,...,(

),...,,,,...,(:{

) ,...,,,..., (

111

111

111

iiniiii

niiiiii

niii

Sssssssu

sssssuSs

ssssB

Definizione: funzione di risposta ottima

La risposta ottima di Player i

Date le strategie degli altri


Una definizione alternativa: La strategia di Player i ),...,,...,( 111 niiii ssssBs se e solo se risolve (o è soluzione d’ottimo)

Max ),...,,,,...,( 111 niiii sssssu oggetto a ii Ss dove nii ssss ..., , , ..., , 111 sono date.

Definizione: funzione di risposta ottima

La risposta ottima di Player 1 alle strategie altrui è una soluzione d’ottimo di


Utilizzo delle funzioni di risposta ottima per la definizione degli equilibri di Nash

Insieme di strategie, una per giocatore, tale che la strategia di ogni giocatore è per lui la migliore, assunto che gli altri stanno giocando le loro strategie ottime, o

Una situazione stabile che nessun giocatore vuole cambiare se gli altri non cambiano

Nel gioco in forma normale {S1, ..., Sn , u1, ..., un}, una combinazione di strategie ),...,( **

1 nss è un equilibrio di Nash se per ogni giocatore i,

) ..., , , ,..., ( **1

*1

*1

*niiii ssssBs


Riassunto

Equilibrio di Nash Funzione di risposta ottima Utilizzo della funzione di risposta ottima per la

definizione dell’equilibrio di Nash Utilizzo della funzione di risposta ottima per la

determinazione dell’equilibrio di Nash

Prossimo argomento Funzioni concave e ottimizzazione Applicazioni


Riassunto

In un gioco a n-giocatori in forma normale, se l’eliminazione iterata di strategie strettamente dominate elimina tutte le strategie tranne ( s1*, s2*, ..., sn*), allora (s1*, s2*, ..., sn*) è l’unico equilibrio di Nash.

In un gioco a n-giocatori in forma normale, se le strategie ( s1*, s2*, ..., sn*) è un equilibrio di Nash allora esse sopravvivono all’eliminazione iterata di strategie strettamente dominate. Male strategie che superano l’eliminazione iterata di strategie strettamente dominate non necessariamente sono equilibri di Nash.


Il modello del duopolio di Cournot

Un prodotto è realizzato solo da due imprese: impresa 1 e impresa 2. Le quantità sono denotate rispettivamente da q1 e q2,. Ogni impresa sceglie la propria quantità senza conoscere la scelta dell’altra.

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

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



La rappresentazione in forma normale: Insieme dei giocatori: { Impresa 1, Impresa 2} Insieme delle strategie: S1=[0, +∞), S2=[0, +∞)

Funzioni di payoff: u1(q1, q2)=q1(a-(q1+q2)-c)u2(q1, q2)=q2(a-(q1+q2)-c)



Come trovare l’equilibrio di Nash: Trovate la coppia di quantità (q1*, q2*) tale che q1* sia

la risposta ottima dell’impresa 1 alla quantità q2* dell’impresa 2 e q2* sia la risposta ottima dell’impresa 2 alla quantità q1* dell’impresa 1

Ciò significa che, q1* risolve Max u1(q1, q2*)=q1(a-(q1+q2*)-c)soggetto a 0 q1 +∞

e q2* risolveMax u2(q1*, q2)=q2(a-(q1*+q2)-c)soggetto a 0 q2 +∞


Una funzione )(xf è concava se, per ogni x e y, )()1()())1(( yfxfyxf

per tutti 10 .

Funzioni concave

x

f(x)

0


Una funzione )(xf è convessa se, per ogni x e y, )()1()())1(( yfxfyxf

per tutti 10 .

Funzioni convesse

x

f(x)

0


Alcuni risultati utili: Una funzione )(xf è concava se e solo se

.0)( xf

Una funzione )(xf è convessa se e solo se .0)( xf

)(xf è concava se e solo se )(xf è convessa.

Concavità e convessità


Esempio 1: 463)( 2 xxxf , 66)( xxf , 06)( xf . Quindi, )(xf è concava.

Esempio 2: xexf )( , 0)()( xexfxf . Quindi, )(xf è convessa. Esempio 3: 22 342),( yxyxyyxf Per ogni dato y, ),( yxf è concava in x perchè

02),( e 22),( yxfxyyxf xx Per ogni dato x, ),( yxf è convessa in y perchè

06),( e 642),( yxfyxyxf yy

Concavità e convessità


Un massimo di )(xf è un punto x' tale che )()( xfxf per ogni x.

Un minimo di )(xf è un punto x* tale che )(*)( xfxf per ogni x.

Massimi e minimi

x

f(x)

0 x* x’


Condizioni di primo ordine (FOC): se un punto x è un massimo o minimo allora x soddisfa le condizioni di primo ordine (FOC): 0)( xf .

Se )(xf è concave e x soddisfa le FOC, allora x è un massimo.

Se )(xf è convessa e *x soddisfa le FOC, allora *x è un minimo.

Massimo e minimo

x

f(x)

0 x

f(x)

0x’ x*


Trovare il max di una funzione concava )(xf Calcolate )(xf Calcolate )(xf e controllate se 0)( xf Se 0)( xf allora risolvete 0)( xf . La soluzione è un massimo

Esempio 1: 463)( 2 xxxf , 66)( xxf , 06)( xf . Quindi, )(xf è concava.

Risolvendo 0)( xf da x=1, il massimo. Esempio 3: 22 342),( yxyxyyxf Per ogni y fisso, ),( yxf è concava in x. Per ogni y fisso, trovate il massimo di ),( yxf

Trovare il massimo di una funzione concava


Un massimo di )(xf nel dominio [x1, x2] è un punto x' in [x1, x2] tale che )()( xfxf per ogni ] ,[ 21 xxx . Un minimo di )(xf nel dominio [x1, x2] è un punto x* in [x1, x2] ale che )(*)( xfxf per ogni ] ,[ 21 xxx .

Massimo e minimo

x

f(x)

0x1 x2x* x’


Trovare il massimo di una )(xf concava nel dominio ] ,[ 21 xx Trovate il max x di )(xf senza vincoli Se x è in ] ,[ 21 xx allora x è anche un max per il

problema vincolato Altrimenti,

a. se )()( 21 xfxf o 1xx allora 1x è un massimo; b. se )()( 21 xfxf o 2xx allora 2x è un massimo; c. se )()( 21 xfxf allora ogni punto in ] ,[ 21 xx è un

massimo.

Trovare il massimo di una funzione concava con vincoli


Esempio 4:

22 a s.

463)(Max 2

x

xxxf

Risolvere il problema senza vincolo dà come soluzione x=1. Dato che 1 è nel dominio, 1 è anche il punto di massimo del problema vincolato. Esempio 5:

463)( Max 2

2

xxxf

x




x

f(x)=-3x2+6x-4


Utilizzo della funzione di risposta ottima per la ricerca dell’equilibrio di Nash

In un gioco a due gioc., ( s1, s2 ) è un equilibrio di Nash se e solo se la strategia s1 del gioc.1 è la rsipsota ottima alla strategia s2 del gioc. 2, e se la strategia s2 del giocatore 2 è la risposta ottima alla strategia s1 del giocatore 1

-1 , -1 -9 , 0

0 , -9 -6 , -6Prig. 1

Prig. 2

Confessa

Nega

Confessa

Nega



Come trovare l’equilibrio di Nash: Trovate la coppia di quantità (q1*, q2*) tale che q1* sia

la risposta ottima dell’impresa 1 alla quantità q2* dell’impresa 2 e q2* sia la risposta ottima dell’impresa 2 alla quantità q1* dell’impresa 1

Ciò significa che, q1* risolve Max u1(q1, q2*)=q1(a-(q1+q2*)-c)soggetto a 0 q1 +∞

e q2* risolveMax u2(q1*, q2)=q2(a-(q1*+q2)-c)soggetto a 0 q2 +∞



Ricerca dell’equilibrio di Nash Risolvete

Max u1(q1, q2*)=q1(a-(q1+q2*)-c)s. a 0 q1 +∞

FOC: a - 2q1 - q2*- c = 0 q1 = (a - q2*- c)/2



Ricerca dell’equilibrio di Nash Risolvete

Max u2(q1*, q2)=q2(a-(q1*+q2)-c)s. a 0 q2 +∞

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



Ricerca dell’equilibrio di Nash La coppia (q1*, q2*) è un equilibrio di Nash se

q1* = (a – q2* – c)/2 q2* = (a – q1* – c)/2

Risolvere queste due equazioni ci dà: q1* = q2* = (a – c)/3


Il modello del duopolio di Cournot Funzione di risposta ottima

La funzione di risposta ottima dell’impresa 1 alla quantità q2 dell’impresa 2R1(q2) = (a – q2 – c)/2 if q2 < a– c; 0 negli altri casi, e

La funzione di risposta ottima dell’impresa 2 alla quantità q1 dell’impresa 1

R2(q1) = (a – q1 – c)/2 if q1 < a– c; 0 negli altri casi

q1

q2

(a – c)/2

(a – c)/2

a – c

a – c

Equilibrio diNash


Il modello del duopolio di Cournot a n imprese Un prodotto è realizzato da n imprese:

dall’impresa 1 all’impresa n. La quantità dell’impresa i sia qi.Ogni impresa effettua la propria scelta senza sapere ciò che fanno le altre.

Il prezzo di mkt. è P(Q)=a-Q, dove a è una costante e Q=q1+q2+...+qn.

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



La rappresentazione in forma normale: Insieme dei giocatori: { Impresa 1, ...

Impresa n} Insieme delle strategie: Si=[0, +∞),

per i=1, 2, ..., nFunzioni di payoff:

ui(q1 ,..., qn)=qi(a-(q1+q2 +...+qn)-c)for i=1, 2, ..., n



Come trovare l’equilibrio di Nash Trovate le quantità (q1*, ... qn*) tali che qi* e la risposta

ottima dell’impresa i alle quantità delle altre imprese. Ciò significa che q1* risolve

Max u1(q1, q2*, ..., qn*)=q1(a-(q1+q2* +...+qn*)-c)s. a 0 q1 +∞

e q2* risolveMax u2(q1*, q2 , q3*, ..., qn*)=q2(a-(q1*+q2+q3*+ ...+ qn*)-c)s. a 0 q2 +∞

.......


Riassunto

Equilibrio di Nash Funzioni concave e massimizzazione Il modello del duopolio e dell’oligopolio di

Cournot

Prossimo argomento Il modello del duopolio di Bertrand

Teoria dei giochi - D'Orio - I parte1 Giochi statici (o a mosse simultanee) con informazione...

Documents

Transcript of Teoria dei giochi - D'Orio - I parte1 Giochi statici (o a mosse simultanee) con informazione...