Teoria dei giochi
Università degli
Studi di Parma
Parma,
15 giugno 2011
I.I.S. “B. Pascal”
Reggio Emilia
1
Cos’ è la teoria dei giochi
“La vita ci costringe a fare continue scelte ad ogni
livello (famigliare, personale, sociale) e in ogni campo
(morale, economico, politico), in situazioni di
conoscenza imperfetta della situazione, del
comportamento altrui e degli effetti delle varie scelte.
Nonostante la sua complessità, il processo decisionale
può comunque essere modellato con strumenti
matematici: la branca della matematica che si
interessa di tali problemi si chiama teoria dei giochi.”
[P. Odifreddi – “Giochi pericolosi”]
2
Il gioco delle mani:
 In che cosa consiste: due giocatori, Arianna e Bruno,
tirano su CONTEMPORANEAMENTE una o entrambe le
mani.
 Regole del gioco: se A e B tirano su lo stesso numero di
mani, B deve dare ad A 10$; se il numero di mani è
diverso, A deve dare a B 10$ se B ha tirato su una sola
mano, 20$ se B ha tirato su 2 mani.
Si tratta di un gioco competitivo, a informazione
completa, simultaneo a somma nulla perché A e B
giocano contemporaneamente e ciò che vince uno è
uguale a quanto l’altro perde.
3
Studio del gioco
 Strategie possibili: A, una mano/due mani; B, una
mano/due mani.
 Situazioni possibili:
1. A, una mano; B, due mani
2. A, due mani; B, una mano
3. A, una mano; B, una mano
4. A, due mani; B, due mani
Situazione
iniziale
1-2
2-2
2-1
1-1
4
Il gioco delle mani:
ricerca della soluzione
 Per rappresentare i pagamenti si usano le tabelle dei
pagamenti. Ad esempio questo gioco è rappresentato
dalla seguente tabella.
Strategie
B1
B2
A1
10
-20
A2
-10
10
 Soluzione: unisce la strategia ottimale per A e quella
ottimale per B, individuando l’equilibrio del gioco.
5
NIM 2-2
Stato iniziale: ci sono due pile di due
fiammiferi ciascuna.
Regole del gioco:
1. si sorteggia il giocatore che inizia.
2. a turno i giocatori scelgono una pila e
prelevano almeno un fiammifero.
3. chi toglie l’ultimo fiammifero perde.
Si tratta di un gioco competitivo, a
informazione completa, non simultaneo.
6
NIM 2-2: Albero degli stati
|| ||
|
||
|
||
||
|
|
|
|
|
Si vede che, qualunque sia la mossa del primo giocatore, il secondo
giocatore ha la vittoria sicura se gioca “razionalmente”
7
Il dilemma del prigioniero
 In che cosa consiste: Rick e Carl, sospettati di un
reato, vengono arrestati e interrogati
separatamente:
1. se uno dei due denuncia l’altro e questo non
confessa, il primo sarà liberato, mentre il complice
sarà condannato alla pena intera (3 anni);
2. se entrambi si denunciano a vicenda, saranno
condannati tutti e due ad una pena ridotta (2 anni);
3. se invece nessuno dei due confessa, entrambi
vengono condannati ad una pena di 1 anno;
8
Studio del gioco
 Tipologia di gioco: si tratta di un gioco a
informazione completa, a somma non nulla, non
cooperativo
 Tabella dei pagamenti:
Strategie
Confessa
Non confessa
Confessa
2-2
0-3
Non confessa
3-0
1-1
Soluzione e applicazioni
Soluzione:La strategia “non confessa” è
strettamente dominata dalla strategia “confessa”,
quindi l’equilibrio si trova in Rick confessa e Carl
confessa. Il risultato migliore per ciascuno dei due
sarebbe Rick non confessa e Carl non confessa, ma
questo non è un equilibrio.
L’equilibrio non sempre coincide con il risultato migliore
Applicazione: il dilemma del prigioniero può essere
usato come modello semplificato per descrivere:
1. problemi di tipo militare,
2. i motivi delle guerre economiche,
3. i comportamenti sociali.
10
Modello per la guerra fredda
• Giocatori : Stati Uniti e URSS
• Confessione = armamento con l’atomica
• Non confessione = non armamento
Secondo il modello del dilemma del prigioniero era
inevitabile la corsa agli armamenti, anche se la
situazione più auspicabile sarebbe stata quella del
non armamento di entrambi.
La corsa del coniglio
 In che cosa consiste: due amici Gianni e Paolo si
sfidano in auto. La sfida consiste nel correre a tutta
velocità l’uno contro l’altro e vince chi non vira. Il
primo che si sposta viene considerato un “coniglio”.
Le possibilità sono:
1. uno si sposta e l’altro no (e viceversa);
2. si spostano entrambi;
3. nessuno dei due si sposta.
La corsa del coniglio
 Matrice dei pagamenti:
M=
(2-2)
(1-3)
(3-1)
(0-0)
Ci sono due equilibri di Nash: (1,3), cioè si sposta Gianni
e non si sposta Paolo; (3,1), cioè si sposta Paolo e non si
sposta Gianni.
Non esiste una strategia razionale adottabile da
entrambi i giocatori, anche se “virano entrambi” è
meno rischioso di “nessuno dei due vira”.
13
La “deterrenza”
• La “corsa del coniglio” si presta a descrivere la
“deterrenza”, cioè la credibilità di una minaccia.
Durante la guerra fredda entrambe le superpotenze
sarebbero state disposte a scatenare una guerra
nucleare piuttosto che fare la figura del “coniglio”
con l’avversario.
La caccia al cervo
 In che cosa consiste: due amici Andrea e Mario
stanno partecipando ad una caccia al cervo,
quando Andrea vede una lepre che potrebbe
cacciare da solo e deve decidere se:
1. continuare a cacciare il cervo insieme all’amico;
2. cacciare la lepre e lasciare solo l’amico;
La caccia al cervo
 Matrice dei pagamenti:
(3-3)
(2-0)
(0-2)
(1-1)
M=
In questo caso ci sono due equilibri di Nash: (3–3) cioè
entrambi continuano a cacciare il cervo e (1–1) cioè
entrambi abbandonano la caccia al cervo e
cacciano la lepre.
16
Classificazione dei giochi
Nel caso di giocatori razionali (ricercano SEMPRE la strategia migliore
per ottenere il massimo risultato), i giochi si dividono in:
deterministici
Strategici: il cui risultato è
influenzato dal giocatore
(scacchi, tris…);
stocastici
Aleatori: il cui risultato è influenzato solo dal “caso”(il
gioco dell’oca...).
Cooperativi: nel caso in cui due o più giocatori si
accordino e giochino come se fossero uno solo.
Non Cooperativi: il meccanismo delle decisioni riguarda
il singolo giocatore sulla base di ragionamenti individuali
Competitivi: ogni giocatore segue una strategia
indipendente volta al massimo profitto.
17
La strategia
 Definizione: piano d’azione preparato a priori in base
alle regole del gioco, cioè specificazione teorica
completa delle mosse che il giocatore farà ogni volta
che dovrà prendere una decisione.
accordi
 Come viene scelta: in base alla
massimizzazione del risultato
(vincere il massimo possibile
e perdere il minimo possibile)
indipendente
Come posso schematizzarla: attraverso l’albero degli stati,
con il quale analizzo tutte le singole situazioni teoriche
che possono verificarsi nel corso del gioco.
18
La strategia:
pura e mista
 Strategia pura: piano d’azione preparato secondo
le regole del gioco che descrive le mosse del
giocatore per ciascuna delle situazioni teoriche che
possono presentarsi.
 Strategia mista: ciascun giocatore segue una
strategia globale che gli permetta di variare e
mischiare le varie strategie pure date dal gioco Se
le strategie vengono “mischiate”, ciò sarà fatto in
modo aleatorio per impedire all’avversario di
capire lo schema seguito.
In ogni caso, ogni gioco a due persone, a somma
nulla, ha una soluzione in termini di strategia pura o di
strategia mista.
19
Equilibri
 Equilibrio in strategie dominanti:
1.
2.
io faccio meglio che posso indipendentemente da
ciò che fai tu;
tu fai meglio che puoi indipendentemente da ciò
che faccio io.
Equilibrio di Nash:
Coppia di strategie rispetto alle quali nessuno dei due giocatori
ha interesse ad essere l’unico a cambiare
1.
io faccio meglio che posso dato ciò che fai tu;
2.
tu fai meglio che puoi dato ciò che faccio io.