Route Map
► Ripasso Lezione 2.
Economia dell’
dell’azienda in rete
Lezione 3: Teoria dei giochi
► Definizioni
► Giochi in forma normale
► Concetti di equilibrio
► Giochi in forma estesa
► Sottogiochi ed equilibrio perfetto nei sottogiochi
► Equilibrio undercut-proof
Corso di Laurea in Informatica (DM 509)
Docente: Annamaria Fiore
A.A. 2009/2010
Lezione 3
Ec. azienda in rete - Annamaria
Fiore
Nota
2
Teoria dei giochi
►La teoria dei giochi è una teoria matematica che
analizza situazioni conflittuali (giochi), in cui due o
più decisori (giocatori) interagiscono, controllando
una o più variabili che influiscono non solo sul loro
benessere/profitto, ma anche su quello degli altri,
determinando congiuntamente il risultato
dell’interazione.
►Il materiale presentato in questa lezione è
basato sul testo di Oz Shy, The Economics of
Network Industries , Cambridge University
Press, in particolare:
Appendice A
Appendice B
Appendice C.
► Scopo: prescrivere che cosa ogni giocatore
dovrebbe fare, al fine di trarre il massimo beneficio
dalla propria (parziale) influenza sul gioco.
► J. Von Neumann e O. Morgenstern, Teoria dei
giochi e comportamento economico, 1944.
Ec. azienda in rete - Annamaria
Fiore
3
Ec. azienda in rete - Annamaria
Fiore
Utilità della teoria dei giochi
4
Classificazione dei giochi
►Si distringuono:
•
giochi cooperativi:
cooperativi sono fattibili accordi vincolanti fra i
giocatori;
• giochi non cooperativi:
cooperativi o gli accordi sono fattibili solo per
certi sottoinsiemi di giocatori (coalizioni ammissibili) o ogni
giocatore agisce in modo autonomo.
►La teoria dei giochi è particolarmente utile quando
il numero dei soggetti che interagiscono fra loro è
non elevato.
► Per
questo, la teoria dei giochi è stata soprattutto
applicata all’analisi di settori composti da un
numero limitato di imprese – i.e., oligopolio.
Ec. azienda in rete - Annamaria
Fiore
• Giochi oneone-shot:
shot l’interazione fra i giocatori avviene una sola
volta;
• giochi ripetuti:
ripetuti vi è un’interazione fra i giocatori ripetuta nel
tempo, un numero finito (giochi finiti) o infinito (giochi
infiniti) di volte.
5
►In questo corso, ci occuperemo solo di giochi non cooperativi
Ec. azienda in rete - Annamaria
6
e one-shot.
Fiore
1
Rappresentazione giochi non
cooperativi
Importanza dell’informazione
►I giochi non cooperativi possono essere rappresentati:
• in forma normale:
normale tutti i giocatori agiscono
simultaneamente (giochi statici);
• in forma estesa:
estesa i giocatori possono agire anche in
diversi momenti del tempo (giochi dinamici).
► Generalmente, si suppone che i giocatori conoscano
del gioco:
• struttura;
• regole;
• pay-off.
►Inoltre, i giocatori possono optare per due tipi di
azioni:
• azioni pure:
pure quando giocano una singola azione dal
loro spazio delle azioni possibili;
• azioni miste:
miste quando assegnano una distribuzione di
probabilità a ciascuna azione contenuta nello spazio
delle azioni possibili.
► Inoltre, i giochi esaminati sono giochi con
informazione perfetta,
perfetta ossia i giocatori conoscono la
storia del gioco, i.e., ogni giocatore conosce tutta
l’informazione riguardante le azioni scelte
precedentmente dagli altri giocatori.
Ec. azienda in rete - Annamaria
Fiore
7
Gioco in forma normale: definizione
(1/2)
Ec. azienda in rete - Annamaria
Fiore
8
Gioco in forma normale: definizione
(2/2)
(b) Ogni giocatore i, con i ℮ I, ha uno spazio delle
azioni Ai, che è l’insieme di tutte le ki azioni possibili
per il giocatore i. ai ℮ Ai denota una particolare
azione scelta dal giocatore i, Ai ≡ {a1i, a2i, …, akii}.
► Un gioco in forma normale si compone
necessariamente di tre elementi:
• giocatori;
• spazio delle azioni;
• funzione dei pay-off.
Si definisca con a ≡ (a1, a2, …, aN) la lista delle azioni
scelte da ciascun giocatore. Questa lista di azioni
scelte da ciascun giocatore costituisce un risultato del
gioco.
gioco
(a) Un insieme di N giocatori definito nello spazio I ≡
{1, 2, …, N}.
(c) Ogni giocatore ha una funzione di payoff,
payoff πi, la quale
assegna un numero reale ,πi(a), ad ogni risultato del
gioco.
Ec. azienda in rete - Annamaria
Fiore
9
Alcune precisazioni
10
Esempio 1
► E’
importante:
• distinguere fra lo spazio delle azioni Ai – ossia,
l’insieme delle azioni possibili per un particolare
giocatore i ex ante, ed un risultato del gioco a, che è la
lista delle azioni scelte effettivamente da tutti i
giocatori ex post;
• notare che la notazione fra parentesi graffe è usata
quando l’elenco degli elementi è irrilevante, mentre
la notazione fra parentesi tonde quando l’ordine è
rilevante;
• notare che, mentre per i giochi in forma normale
usare il termine strategia o azione è indifferente, ciò
non sarà vero nella trattazione dei giochi in forma
estesa.
Ec. azienda in rete - Annamaria
Fiore
Ec. azienda in rete - Annamaria
Fiore
11
►In questo gioco, noto in letteratura anche come
“dilemma del prigioniero”, vi sono:
• i giocatori: due imprese (mercato di oligopolio o,
rectius, un duopolio);
• ogni impresa ha due azioni possibili: aumentare o
ridurre la produzione da offrire sul mercato;
• i pay-off conseguibili dalle due imprese in
corrispondenza di ogni coppia di strategie sono
profitti.
Ec. azienda in rete - Annamaria
Fiore
12
2
Rappresentazione in forma matriciale
Azioni, risultati e payoff
►Se entrambe le imprese scelgono di aumentare la
produzione, l’offerta complessiva aumenta, il prezzo
diminuisce ed entrambe conseguono un profitto pari ad
1.
► Se entrambe le imprese scelgono di restringere la
produzione, l’offerta complessiva diminuisce, il prezzo
aumenta ed il profitto complessivo è pari a 4, ossia 2 per
ciascuna.
► Ognuna delle due imprese ottiene il profitto maggiore
di 3, se sceglie di aumentare la produzione, mentre
l’altra la riduce, in modo tale che l’offerta complessiva
non aumenti così tanto da far abbassare troppo il
prezzo.
Ec. azienda in rete - Annamaria
Fiore
Impresa B
Impresa A
Aumentare
Restringere
Aumentare
1; 1
3; 0
Restringere
0; 3
2; 2
► Verificare
che la matrice contiene tutti gli elementi
necessari per definire un gioco in forma normale
13
Ec. azienda in rete - Annamaria
Fiore
14
Azione dominante
Concetti di equilibrio
►Scopo: prescrivere che cosa ogni giocatore dovrebbe
fare, al fine di trarre il massimo beneficio dalla propria
(parziale) influenza sul gioco.
► Per fare previsioni sul gioco, è necessario fare
riferimento a dei concetti di equilibrio.
equilibrio
►Una particolare azione ãi ℮ Ai è detta azione
dominante per il giocatore i, se, qualunque sia
l’azione scelta da tutti gli altri giocatori, scegliere di
giocare l’azione ãi permette al giocatore i di
massimizzare sempre il proprio payoff.
► E’ necessario quindi sviluppare metodologie e definire
algoritmi che permettono di restringere l’insieme dei
possibili risultati del gioco in modo da pervenire ai
risultati di equilibrio.
► Un risultato del gioco ã ≡ (ã1, ã2, …, ãN) è detto
equilibrio in azioni dominanti se ãi è un’azione
dominante per ogni giocatore i.
►E’ importante anche che i risultati di equilibrio
soddisfino delle proprietà desiderabili, e.g., unicità
dell’equilibrio.
Ec. azienda in rete - Annamaria
Fiore
15
Ec. azienda in rete - Annamaria
Fiore
Equilibrio in azioni dominanti
► Il gioco rappresentato è un gioco simmetrico.
Esempio 2
►Non sempre un equilibrio in azioni dominanti esiste.
Impresa B
Aumentare
Impresa A
Restringere
Aumentare
Restringere
1; 1
3; 0
0; 3
Impresa B
Impresa A
2; 2
► Sia l’impresa A, sia l’impresa B hanno un’azione
dominante da scegliere: Aumentare. Quindi, il
risultato (aA, aB) = (Aumentare, Aumentare) è
l’equilibrio in azioni dominanti di questo gioco.
Ec. azienda in rete - Annamaria
Fiore
16
Standard α
Standard β
Standard α
2; 1
0; 0
Standard β
0; 0
1; 2
►In letteratura, il gioco di coordinazione
rappresentato è noto come “battaglia dei sessi”.
17
Ec. azienda in rete - Annamaria
Fiore
18
3
Equilibrio di Nash
Equilibrio in azioni dominanti ed
equlibrio di Nash
► Un risultato del gioco â ≡ (â 1, â2, …, â N) è detto
equilibrio di Nash se nessun giocatore trova
profittevole deviare, a condizione che tutti gli altri
giocatori non deviino dalla strategia giocata
nell’equilibrio di Nash.
► Un equilibrio in azioni dominanti è anche un
equlibrio di Nash, ma non vale il viceversa, i.e., un
equilibrio di Nash non necessariamente è un
equilibrio in azioni dominanti.
► L’equilibrio di Nash è self-enforcing o ad attuazione
spontanea, i.e., fintanto che gli altri seguono le
raccomandazioni prescritte in equilibrio, non è
nell’interesse di alcuno deviare da quelle.
► Si è in presenza di un equilibrio di Nash
oqniqualvolta nessun giocatore può beneficiare da
una deviazione unilaterale da un dato risultato.
Ec. azienda in rete - Annamaria
Fiore
19
► Purtroppo, non solo l’equilibrio di Nash non sempre
è unico, riducendone così il potere predittivo, ma
anch’esso non sempre esiste.
Ec. azienda in rete - Annamaria
Fiore
20
Funzioni di risposta ottima
Esempio 3
►In un gioco con 2 giocatori, la funzione di risposta
ottima del giocatore i è la funzione Ri(aj) che, per
ogni data azione aj del giocatore j, assegna un’azione
ai = Ri(aj) che massimizza il payoff del giocatore i
πi(ai, aj).
► Per definizione, ogni giocatore, in un equilibrio di
Nash, si trova sulla sua funzione di risposta ottima.
►Non sempre un equilibrio di Nash esiste,
perlomeno in azioni pure.
Impresa B
Impresa A
► Infatti, nell’esempio 2, ci sono due equilibri di Nash,
ma nessun equilibrio in azioni dominanti.
Standard α
Standard β
Standard α
2; 0
0; 2
Standard β
0; 1
1; 0
►In un equilibrio di Nash, ogni giocatore sceglie
un’azione che è una risposta ottima alle azioni scelte
dagli altri giocatori in un equilibrio di Nash.
► Quindi, in un equilibrio di Nash, le strategie dei
giocatori sono reciprocamente risposte ottime.
Ec. azienda in rete - Annamaria
Fiore
21
22
Gioco in forma estesa: definizione
Gioco in forma estesa
►In un gioco in forma estesa i giocatori possono
muovere in stadi differenti del gioco e possono
giocare anche più di una volta.
► Un gioco in forma estesa è:
► I giochi in forma estesa sono rappresentati da un
grafo ad albero con un nodo decisionale iniziale,
altri nodi decisionali e dei nodi finali.
► Diversi rami congiungono i diversi nodi decisionali.
►Ogni nodo decisionale descrive le azioni disponibili
per il relativo giocatore in quel particolare nodo.
Ec. azienda in rete - Annamaria
Fiore
Ec. azienda in rete - Annamaria
Fiore
23
(a)Un grafo ad albero contenente un nodo iniziale, alcuni
nodi decisionali, nodi finali e rami congiungenti ogni
nodo decisionale con i nodi successivi.
(b) Un insieme di N ≥ 1 giocatori,
giocatori indicizzato con i = 1, 2,
…, N.
(c) Per ogni nodo decisionale, il nome del giocatore che
può effettuare la mossa.
(d) Per ogni giocatore i, la specificazione dell’insieme
delle azioni in ogni nodo decisionale in cui i può
giocare.
(e) La specificazione del payoff per ogni giocatore ad ogni
nodo terminale.
Ec. azienda in rete - Annamaria
Fiore
24
4
Descrizione del gioco
Esempio
►Il gioco rappresentato ha due stadi.
I (muove A)
Entra
► Nello stadio 1, l’impresa A decide se entrare
(sopportando un costo irrecuperabile di 1) o meno.
Non Entra
IIE (muove B)
Resta
► Nello stadio 2, l’impresa B già sul mercato può
ritrovarsi o a dover concorrere con l’impresa A
(nodo IIE), o a mantenere il suo potere
monopolistico (nodo IIN).
πA =
-2
πB = -2
IIN (muove B)
Esce Resta
πA =
3
πA =
Esce
πA = 0
0
πB = -1 πB = 3
πB = -1
► In ognuno di questi nodi, l’impresa B ha uno
specifico insieme delle azioni.
Ec. azienda in rete - Annamaria
Fiore
25
Ec. azienda in rete - Annamaria
Fiore
Strategie in un gioco in forma estesa
26
Risultati in un gioco in forma estesa
► Nei giochi in forma estesa, un giocatore può essere
chiamato a scegliere un’azione per più di una volta, ed
ogni volta il giocatore deve scegliere un’azione
dall’insieme di azioni disponibili in quel particolare
nodo.
► Nei giochi in forma estesa, il risultato per un gioco è la
lista di tutte le azioni prese da ogni giocatore in ogni
possibile nodo in cui il giocatore ha diritto di effettuare
una mossa.
► Una strategia per il giocatore i (indicata con si) è un
piano completo di azioni, un’azione per ogni nodo
decisionale in cui il giocatore può effettuare una mossa.
► Importante: la strategia non è ciò che il giocatore
effettivamente fa in ogni singolo nodo, ma una lista di
ciò che il giocatore fa in ogni nodo in cui può effettuare
la mossa. Ec. azienda in rete - Annamaria
27
Ec. azienda in rete - Annamaria
Fiore
Fiore
Rappresentazione in forma normale
di un gioco in forma estesa
Rappresentazione in forma normale
►Dopo aver definito un gioco in forma estesa, ciò che
interessa è fare alcune predizioni sul gioco, i.e., cercare
un equilibrio per quel gioco.
►In molti casi, può essere utile trasformare un un gioco in
forma estesa in un gioco rappresentato in forma
normale (operazione che, tuttavia, non sempre è
possibile fare).
Ec. azienda in rete - Annamaria
Fiore
29
Impresa B
Impresa A
►L’equilibrio più naturale da cercare è un equilibrio di
Nash,
Nash ossia un equilibrio in strategie in cui ogni
giocatore non può aumentare il proprio payoff per
mezzo di una deviazione unilaterale dalla strategia
giocata in un equilibrio di Nash dato.
28
Entra
No
(Resta, Resta) (Resta, Esce)
-2; -2
-2; -2
(Esce, Resta)
3; -1
(Esce, Esce)
3; -1
0; 3
0; 3
0; -1
0; -1
►In questo gioco, vi sono 3 equilibri di Nash, il che riduce
di molto il suo potere predittivo.
► Per questo, si introducono dei raffinamenti
dell’
dell’equilibrio di Nash:
Nash concetto di equilibrio che restringe
l’insieme degli equilibri di Nash.
Ec. azienda in rete - Annamaria
Fiore
30
5
Limitazioni equilibrio di Nash
►Raffinamenti: questi concetti di equilibrio soddisfano
tutte le condizioni per un equilibrio di Nash, oltre ad
ulteriori restrizioni.
►Permettono quindi di eliminare alcuni equilibri di Nash
“non desiderabili”.
►L’equilibrio di Nash, infatti, a volte è “limitato”, poiché
non riesce a catturare l’abilità da parte dei giocatori di
anticipare le mosse degli altri.
►Infatti, alcune mosse da parte di alcuni giocatori sono
minacce non credibili, nel senso che non verrebbero
comunque attuate in risposta all’azione dell’altro
giocatore.
Ec. azienda in rete - Annamaria
Fiore
-2
πB = -2
►Un gioco è chiamato sottogioco proprio se differisce
dal gioco originale.
► Un risultato è detto equilibrio perfetto nei sottogiochi
se induce un equilibrio di Nash in ogni sottogioco del
gioco originale o, alternativamente,
un equilibrio di Nash è perfetto nei sottogiochi se le
strategie dei giocatori costituiscono un equilibrio di
Nash in ogni sottogioco.
31
Ec. azienda in rete - Annamaria
Fiore
32
Soluzione - 2
I (muove A)
► Il gioco proposto ha due sottogiochi propri.
Entra
Resta
►Un sottogioco è un nodo decisionale del gioco
originale assieme ai nodi decisionali ed ai nodi
terminali che seguono direttamente tale nodo.
Soluzione - 1
Non Entra
IIE (muove B)
πA =
Sottogiochi ed equilibrio perfetto
nei sottogiochi
► Ogni sottogioco proprio ha solo un EN.
IIN (muove B)
Esce Resta
πA =
3
πA =
0
πB = -1 πB = 3
IIE (muove B)
Resta
Esce
πA =
πA =
0
πB = -1
-2
πB = -2
IIN (muove B)
Esce Resta
πA =
3
πA =
0
πB = -1 πB = 3
Esce
πA = 0
πB = -1
► Un equilibrio perfetto dei sottogiochi deve essere un EN in ogni
sottogioco: gli altri risultati non possono, quindi, più essere considerati.
► Il risultato (Entra, (Esce, Resta)) è l’equilibrio cercato: è un EN per il
gioco originale e la strategia (Esce, Resta) è associata con l’unico EN in
ogni sottogioco proprio.
Ec. azienda in rete - Annamaria
Fiore
33
Backward induction
34
Equilibrio undercut-proof
►La metodologia solitamente utilizzata per trovare
l’equilibrio perfetto nei sottogiochi è la backward
induction (induzione all’indietro): si inizia a cercare
gli EN nei sottogiochi che conducono ai nodi
terminali, considerando date le azioni giocate in NE
giocate nei sottogiochi precedenti l’ultimo.
► Si procede così a risolvere il gioco a ritroso, giungendo
al nodo iniziale e selezionando l’azione che
massimizza il profitto del giocatore che muove per
primo, dati gli EN di tutti i sottogiochi propri.
►Tale metodologia si rivela molto utile soprattutto nel
caso di giochi molto lunghi.
Ec. azienda in rete - Annamaria
Fiore
Ec. azienda in rete - Annamaria
Fiore
35
►Nell’equilibrio
equilibrio undercutundercut-proof ogni impresa,
producente un bene differenziato, sceglie il proprio
prezzo in modo da massimizzare il profitto,
assicurandosi che quel prezzo sia sufficientemente basso
in modo da evitare che un'impresa rivale possa trovare
conveniente fissare un prezzo ancora più basso e
prendere per sé tutto il mercato.
► In un equilibrio undercut-proof, ogni impresa
considera le rivali “sofisticate” abbastanza da essere
pronte a ridurre il loro prezzo ogniqualvolta ciò sia
conveniente.
L’intuizione dietro il concetto di equilibrio undercut-proof è considerarlo, in
qualche modo, "a prova di riduzione del prezzo da parte del proprio
concorrente".
Ec. azienda in rete - Annamaria
Fiore
36
6
Esempio
Utilità dei consumatori
► Vi sia un mercato composto da due imprese A e B;
► beni differenziati: di tipo A e di tipo B;
► per semplicità di analisi, costo di produzione pari a 0;
► due gruppi di consumatori: un gruppo di consumatori
“orientati al prodotto A” e un gruppo di consumatori
“orientati al prodotto B”;
►i consumatori di tipo A sono ηA > 0, e i consumatori di
tipo B, ηB >0;
► ogni consumatore acquista un’unità del bene o
dall’impresa A o dall’impresa B;
►pA e pB i prezzi fissati dalle due imprese;
► δ ≥ 0 la disutilità che il consumatore ottiene acquistando
il bene verso cui non è orientato.
Ec. azienda in rete - Annamaria
Fiore
37
Distribuzione dei consumatori
0
se pB > pA + δ
qB ≡ η B
se pA - δ ≤ pB ≤ pA + δ
ηA+ ηB se pB < pA - δ
► Il numero dei consumatori che acquistano dall’impresa
A e dall’impresa B è determinato endogenamente
(all’interno del modello).
► Si dimostra che in questo gioco non c’è un equilibrio di
Nash-Bertrand in strategie pure.
39
-pB -δ se compra il bene di tipo B
-pA -δ se compra il bene di tipo A
UB ≡
-pB
se compra il bene di tipo B
Ec. azienda in rete - Annamaria
Fiore
38
Undercutting ed equilibrio
undercut-proof
► L’equilibrio undercut-proof è costituito da una coppia
di prezzi (pUA, pUB) che soddisfa le seguenti
condizioni:
(a) per pUB e qUB dati, l’impresa A sceglie il prezzo più
alto possibile pUA tale che:
πUB= pUBq UB ≥ (pA − δ)(ηA + ηB)
(b) per pUA e qU A dati, l’impresa B sceglie il prezzo più
alto possibile pUB tale che:
πUA = pUAq UA ≥ (pB − δ)(ηA + ηB)
(c) La distribuzione dei consumatori tra le due imprese è
determinati come nella slide relativa.
Ec. azienda in rete - Annamaria
Fiore
40
Proprietà
Prezzi di equilibrio
►In un equilibrio undercut-proof, l’impresa A fissa il
prezzo più alto possibile evitando, al contempo, che
l’impresa B faccia undercutting e le sottragga i clienti,
ossia, evitando che il profitto di B sia più basso del
profitto che B otterrebbe fissando pB < pUA – δ
(=undercutting).
► Dalle due disuguaglianze che valgono come
uguaglianzesi possono ottenere i prezzi di equilibrio:
(η + η )(η + 2η B )δ
pUA = A 2 B A
> δ In questo modo,
entrambe le imprese
(η A ) + η Aη B + (η B ) 2
conservano una quota
(η A + η B )( 2η A + η B )δ
U
pB =
> δ di mercato positiva
(η A ) 2 + η Aη B + (η B ) 2
Ec. azienda in rete - Annamaria
Fiore
se compra il bene di tipo A
► L’impresa i fa undercutting all’impresa j, se pi ≤ pj – δ.
0
se pA > pB + δ
qA ≡ η A
se pB - δ ≤ pA ≤ pB + δ
ηA+ ηB se pA < pB - δ
Ec. azienda in rete - Annamaria
Fiore
-pA
UA ≡
41
1. I prezzi aumentano con la disutilità (δ), mentre tendono a
zero se la disutilità dall’acquistare il bene non preferito
tende a zero, finché i due beni possono considerarsi
omogenei.
2. In un equilibrio undercut-proof, l’impresa con la quota di
mercato maggiore chiede un prezzo inferiore (“effetto
supermercato”).
3. L’impresa con la quota di mercato maggiore, ottiene un
profitto maggiore, anche se pratica un prezzo più basso.
4. Se le due imprese hanno la stessa quota di mercato (ηA =
ηB), i prezzi praticati dalle due imprese sono uguali, pari a
due volte la disutilità: pA = pB = 2δ.
Ec. azienda in rete - Annamaria
Fiore
42
7