Teoria dei giochi
3. Forma Strategica e ricerca
dell’equilibrio
Slides di Teoria dei Giochi,
Vincenzo Cutello
1
Incrocio di strategie
 Se A ha a disposizione le strategie A1, A2, A3
 B ha a disposizione le strategie B1, B2, B3
 Possiamo studiare il gioco costruendo la tavola dei
payoff
B1 B2 B3
A1 ?
A2 ?
A3 ?
?
?
?
?
?
?
Slides di Teoria dei Giochi,
Vincenzo Cutello
2
Matrice dei pagamenti:
giochi a somma zero
B
A
B1
B2
A1
A2
1
0
2
-1
 A sceglie la riga
 B la colonna
 Il valore indica quanto B deve
pagare ad A
Slides di Teoria dei Giochi,
Vincenzo Cutello
3
Ricordiamo: Assioma di razionalità
Un giocatore sceglie l’azione che gli consente di ottenere
i risultati migliori, qualunque sia la mossa
dell’avversario


Che succede in questo caso ?
Situazione di equilibrio oppure no ?
B
A
B1
B2
A1
A2
1
0
2
-1
Slides di Teoria dei Giochi,
Vincenzo Cutello
4
Esempio 1


Che succede in questo caso ?
Situazione di equilibrio oppure no ?
B
A
B1
B2
B3
A1
2
4
6
A2
1
7
0
A3
1
0
7
Slides di Teoria dei Giochi,
Vincenzo Cutello
5
Esempio 2


Che succede in questo caso ?
Situazione di equilibrio oppure no ?
B
A
B1
B2
B3
A1
1
2
3
A2
2
5
0
A3
4
0
0
Slides di Teoria dei Giochi,
Vincenzo Cutello
6
Riduzione: esempio 1


Che succede in questo caso ?
Ha senso per B scegliere B3 ? No, perché B1 è migliore
in tutti i casi.
B
A
B1
B2
B3
A1
2
3
4
A2
0
7
1
A3
1
0
5
Slides di Teoria dei Giochi,
Vincenzo Cutello
7
Riduzione: esempio 1, cont.

Ha senso per A scegliere A3 ? No, perché A1 è migliore in
tutti i casi.
B
A
B1
B2
A1
2
3
A2
0
7
A3
1
0
Slides di Teoria dei Giochi,
Vincenzo Cutello
8
Riduzione: esempio 1, cont.

Ha senso per B scegliere B2 ? No, perché B1 è migliore
in tutti i casi.
B
A
B1
B2
A1
2
3
A2
0
7
Slides di Teoria dei Giochi,
Vincenzo Cutello
9
Riduzione: esempio 1, cont.

Ha questo punto B ha una sola strategia. Quindi A sceglie A1. ? No,
perché B1 è migliore in tutti i casi.
B
A
B1
A1
2
A2
0
B
Soluzione del
gioco
Equilibrio
Slides di Teoria dei Giochi,
Vincenzo Cutello
A
B1
A1
2
10
Riduzione: esempio 1

Ricapitoliamo
B
A
B1
B2
B3
A1
2
3
4
A2
0
7
1
A3
1
0
5
Max-min
Min-max
Slides di Teoria dei Giochi,
Vincenzo Cutello
11
Equilibrio con max-min e min-max: esempio 1


Che succede in questo caso ?
Studiamo il gioco
B
A
B1
B2
B3
A1
2
4
6
A2
1
7
0
A3
1
0
7
Slides di Teoria dei Giochi,
Vincenzo Cutello
12
Equilibrio con max-min e min-max: esempio 2


Che succede in questo caso ?
Studiamo il gioco
B
A
B1
B2
B3
A1
1
2
3
A2
2
5
0
A3
4
0
7
Slides di Teoria dei Giochi,
Vincenzo Cutello
13
Esistenza dell’equilibrio


Se Max-min= Min-Max
Ricordiamo:
–
–
Max-min = quanto A è in grado di garantirsi giocando contro B
Min-max = quanto B è disposto a pagare giocando contro A
Slides di Teoria dei Giochi,
Vincenzo Cutello
14
Minimax
 Giocatori perfetti per giochi deterministici ad informazione perfetta
 Idea: scegli la mossa che porta alla posizione con il più alto minimax
value = miglior risultato raggiungibile contro il miglior avversario
Per esempio, gioco a 2 giocatori:
MAX
3
A1
2
3
MIN
A11
3
A12
12
A3
A2
A21
A13
8
2
A22
2
A23
4
Slides di Teoria dei Giochi,
Vincenzo Cutello
6
A31
14
A32
5
A33
2
15
Strategie miste: es. pari e dispari


Utilità del gioco pari-dispari. A vince se esce pari.
Nessun equilibrio. Nessuna informazione ulteriore.
B
A
P
D
P
1
-1
D
-1
1
Slides di Teoria dei Giochi,
Vincenzo Cutello
16
Strategie miste: es. pari e dispari



Che succede se A sceglie pari il 30% delle volte e B
sceglie dispari il 40% delle volte ?
Strategia mista.
Definizione di utilità attesa?
B
A
P: q
D: 1-q
P: p
1
-1
D: 1-p -1
1
Slides di Teoria dei Giochi,
Vincenzo Cutello
17
Attenzione!
Nel seguito dovremo usare un po’ di
Matematica
Slides di Teoria dei Giochi,
Vincenzo Cutello
18
Lotterie e Preferenze
Un giocatore sceglie tra premi (A, B, etc.) e
lotterie, cioè, situazioni con premi incerti
A
p
Lotteria L = [p, A; (1-p), B]
L
Notazione :
A B
A è preferito a B
A B
A e B sono indifferen ti
A  B
B non è preferito ad A
Slides di Teoria dei Giochi,
Vincenzo Cutello
1-p
B
19
Preferenze razionali
Idea: le preferenze di un giocatore razionale devono obbedire a vincoli.
Preferenze razionali  comportamento descrivibile come
massimizzazione dell’utilità attesa
Vincoli :
Ordinabili tà
( A  B )  ( B  A)  ( A  B )
Transitivi tà
( A  B)  ( B  C )  ( A  C )
Continuità
A  B  C  p [ p, A;1  p, C ]  B
Sostituibi lità
A  B  [ p, A;1  p, C ]  [ p, B;1  p, C ]
Monotonici tà
A  B  ( p  q  [ p, A;1  p, B ]   [q, A;1  q, B ])
Slides di Teoria dei Giochi,
Vincenzo Cutello
20
Preferenze razionali (cont.)
 La violazione dei vincoli conduce a evidenti contraddizioni
 Per esempio: un giocatore con preferenze intransitive può essere
indotto a dare via tutto il suo denaro
Se B C, allora un giocatore che possiede C pagherebbe
(diciamo) 1 centesimo per ottenere B
Se A B, allora un giocatore che possiede B pagherebbe
(diciamo) 1 centesimo per ottenere A
Se C B, allora un giocatore che possiede A pagherebbe
(diciamo) 1 centesimo per ottenere C

Slides di Teoria dei Giochi,
Vincenzo Cutello
21
Massimizzando l’utilità attesa
Teorema (Ramsey, 1931; von Neumann e Morgenstern, 1944):
Date le preferenze soddisfacenti i vincoli esiste una funzione a valori reali
U tale che
U ( A)  U ( B)  A  B
U ([ p1 , S1;...; pn , S n ])  i piU ( Si )
Principio MEU: Scegliere l’azione che massimizza l’utilità attesa
Nota: un giocatore può essere interamente razionale (consistente con MEU)
senza mai rappresentare o manipolare utilità e probabilità
Slides di Teoria dei Giochi,
Vincenzo Cutello
22
Utilità
 L’utilità associa gli stati a numeri reali. Quali numeri ?
 Approccio standard per stabilire l’utilità umana:
– Comparare un dato stato A con una lotteria standard Lp che ha:
– “miglior premio possibile” u^ con probabilità p
– “peggiore catastrofe possibile” u^ con probabilità (1-p)
 Aggiustare la probabilità della lotteria p fino a quando A è indifferente
rispetto a Lp
Continua come prima
0.999999
Pagare 30 €
è indifferente a
L
0.000001
Slides di Teoria dei Giochi,
Vincenzo Cutello
Morte istantanea
23
Denaro
 Il denaro non si comporta come una funzione di utilità
 Data una lotteria L con valore monetario atteso di EMV(L),
solitamente U(L) < U(EMV(L)), cioè, le persone sono avverse
al rischio
 Curva di utilità: per quale probabilità p sono indifferente tra un
premio fisso x e una lotteria [p, € 1M; (1-p), € 0] ?
 I dati si possono (o debbono estrapolare sperimentalmente)
Slides di Teoria dei Giochi,
Vincenzo Cutello
24
Paradosso di S. Pietroburgo



Vi viene chiesto di partecipare ad un gioco in cui una moneta viene
lanciata in aria sino a quando il risultato non è “testa”.
Se “testa” compare al lancio “n” , il giocatore vince € 2n .
Quanto paghereste per giocare ?

EMV(S.P.)=  P(Ti ) MV (Ti )  
i
i
1 i
2 
2i

Disposto a pagare qualunque cifra ? Assurdo. Bernoulli (1738) propose
di misurare l’utilità del denaro su scala logaritmica:
1
2 3 4
i
P
(
T
)
MV
(
T
)

log
2

1

   ...  2
i i
i 2i 2
i
4 8 16

Quindi per giocare un giocatore razionale paga sino a € 4 !
Slides di Teoria dei Giochi,
Vincenzo Cutello
25
Valore dell’informazione
 Problema calcolare il valore di acquisire nuovi elementi
decisionali.
 Esempio: comperare dei diritti petroliferi
– n blocchi A1, …, An, solo in uno è presente il petrolio,
valore stimato k
– Probabilità a priori 1/n ognuno, mutuamente esclusivi
– Il prezzo corrente di ogni blocco è allora k/n
– Il consulente offre una perizia sul blocco A1. Costo della
consulenza ?
Slides di Teoria dei Giochi,
Vincenzo Cutello
26
Valore dell’informazione
 Soluzione: calcolare il valore atteso dell’informazione =
– valore atteso della miglior azione data l’informazione
meno il
– valore atteso della miglior azione senza l’informazione
 Potremmo dire “petrolio in A1” o “niente petrolio in A1”, con
probabilità rispettivamente 1/n e (n-1)/n,
– [1/n * valore di “comprare A1” dato “petrolio in A1” +
– (n-1)/n * valore di “comprare un altro lotto” dato “niente
petrolio in A1” ] – 0
– =
1 (n  1)
n 1 k
k
 k/n
n n
n n(n  1)
Slides di Teoria dei Giochi,
Vincenzo Cutello
27
Giochino probabilistico
 A tre amici condannati a morte, A, B, C è comunicata la
decisione del re di graziare due di loro
 A questo punto A si rende conto di avere una probabilità su 3
di salvarsi.
 Quando arriva la guardia per portargli da mangiare (A è
isolato dai suoi amici), A chiede di sapere il nome di uno dei
suoi due amici che sicuramente sarà graziato.
 La guardia ci pensa su un attimo, capisce che non c’è niente
di illegale e gli comunica che B sarà graziato.
 Qual è la probabilità che A sarà condannato ? (o se volete
quanto vale questa informazione della guardia ?)
Slides di Teoria dei Giochi,
Vincenzo Cutello
28
Giochino logico
 C’era una volta un isola lontana popolata da fanti e cavalieri
– I Fanti mentivano sempre
– I Cavalieri dicevano sempre la verità
 Aristotele arrivato nell’isola, vuole sapere se il suo allievo
Alessandro si trova lì.
 Il capo delle guardie lo sa di sicuro
 Aristotele gli chiede se Alessandro è nell’isola.
– La risposta è solamente un “Si” oppure un “No”
 Aristotele gli chiede quindi se lui ha visto Alessandro
nell’isola.
– La risposta è di nuovo solamente un “Si” oppure un “No”.
 Aristotele non sa se il capo delle guardie è un fante o un
cavaliere. Però a questo punto Aristotele è in grado di
dedurre se Alessandro si trova nell’isola.
Slides di Teoria dei Giochi,
Vincenzo Cutello
29