INFORMATICA PER IL
COMMERCIO ELETTRONICO
MATTEO CRISTANI
AGENDA




GIOCHI
STORIA DELLA TEORIA DEI GIOCHI
RISULTATI TEORICI SUI GIOCHI
CLASSIFICAZIONE DEI GIOCHI
GIOCHI


I lucidi qui presentati sono tratti dalla presentazione della
teoria dei giochi del Dott. Francesco Del Fabbro,
dell’Università di Udine
http://fadest.uniud.it/socind/giochi.ppt
GIOCHI

CHE COS’E’ LA TEORIA DEI GIOCHI

Esamina le situazioni in cui due o più agenti, detti
giocatori agiscono secondo regole stabilite, allo scopo di
ottenere una vincita (payoff) di qualche genere.

L’insieme di regole che ogni singolo giocatore segue nel
determinare le mosse da effettuare (da non confondere
con le regole del gioco) è detto strategia.
STORIA





Teorema di Zermelo (1913)
Teorema del minimax (von Neumann 1928)
The Theory of Games and Economic Behavior (von
Neumann e Morgenstern 1944)
Equilibrio di Nash (1950)
Negli anni ’60-’70, l’equilibrio di Nash viene raffinato,
vengono studiati i giochi dinamici e quelli con
informazione incompleta.
TEOREMA DI ZERMELO

Un gioco (finito) ad informazione perfetta ha un equilibrio
di Nash in strategie pure.

OVVERO

Ogni gioco finito può essere vinto da un giocatore se è
l’unico a giocare in modo perfetto.

ESEMPIO: TRIS
TEOREMA DEL MINIMAX

Il teorema del minimax (o del maximin) stabilisce che
ogni gioco finito a somma costante possiede almeno un
punto di equilibrio di minimax in strategie pure o miste.

OVVERO

Ogni gioco finito a somma costante ammette una
strategia vincente.

ESEMPIO: BRIDGE
EQUILIBRIO DI NASH

Equilibrio di Nash (Nash, 1950, 1951). Basato sul teorema
del punto fisso di Kakutani (1941), è un concetto di
soluzione valido per qualsiasi gioco non cooperativo. Di
fatto, si può considerare come la generalizzazione del
minimax ai giochi a somma variabile.
CLASSIFICAZIONE DEI GIOCHI


Giochi a 2 oppure ad n (n≥2) giocatori
Cooperativi e competitivi:






Cooperativi: i giocatori agiscono in vista del bene comune
Non cooperativi: i giocatori non possono concertare una strategia comune
Competitivi: alla vincita di uno corrisponde la perdita dell’altro
A informazione completa: se ogni giocatore possiede tutta
l’informazione sullo stato attuale del gioco (es. scacchi)
Deterministici: non ci sono elementi casuali. Il gioco si dice non
deterministico se il caso fa parte delle regole del gioco
A somma costante: qualunque sia lo stato finale del gioco, la somma
delle vincite e delle perdite dei giocatori (considerate vincite negative) è
costante.
MATRICE DI GIOCO



Supponiamo gioco deterministico a somma nulla con
due giocatori. Le strategie a loro disposizione siano:
A={A1,A2,…,Am} e B={B1,B2,…,Bn}
Il gioco si può rappresentare come una matrice mxn,
in cui le righe corrispondono alle m strategie del
primo giocatore, le colonne alle n strategie del
secondo.
Gli elementi della matrice sono valori che
quantificano la vincita del primo giocatore. L’elemento
vij è la vincita del primo giocatore se sceglie la
strategia Ai in risposta alla Bj del secondo
MATRICE DI GIOCO: ESEMPIO
B1
B2
…
Bn
A1
V11
V12
…
V1n
A2
V21
V22
…
V2n
…
…
…
…
…
Am
Vm1
Vm2
…
Vmn
PARI E DISPARI
0
1
2
0
1
-1
1
1
-1
1
-1
2
1
-1
1
GIOCHI NON COOPERATIVI



Non sempre il giocatore, pur cercando il massimo profitto per
se, è costretto a farlo a spese dell’altro giocatore.
Ossia, non tutti i giochi sono a somma costante o nulla
È possibile che le strategie dei giocatori non determinino solo
come vengono tagliate le fette, ma anche quanto è grande la
torta.
DILEMMA DEL PRIGIONIERO

Due criminali vengono accusati di aver commesso un
reato. Gli investigatori li arrestano entrambi e li chiudono
in due celle diverse impedendo loro di comunicare. Ad
ognuno di loro vengono date due scelte: confessare
l'accaduto, oppure non confessare. Viene inoltre spiegato
loro che:



se solo uno dei due confessa, chi ha confessato evita la pena;
l'altro viene però condannato a 7 anni di carcere.
se entrambi confessano, vengono entrambi condannati a 6 anni.
se nessuno dei due confessa, entrambi vengono condannati a 1
anno.
DILEMMA DEL PRIGIONIERO
B nega
B confessa
A nega
(A=-1, B=-1)
(A=-7, B=0)
A confessa
(A=0, B=-7)
(A=-6, B=-6)
EQUILIBRIO


Il gioco si dice in equilibrio quando i giocatori hanno
adottato una combinazione di strategie tale che nessuno
di loro riuscirebbe a guadagnare cambiando la propria
strategia.
Nei giochi cooperativi i giocatori devono cooperare per
raggiungere il loro obiettivo comune
ESEMPIO: WAR GAMES
Missili si
Missili no
Missili si
(A=10, B=10)
(A=200, B=0)
Missili no
(A=0, B=200)
(A=100, B=100)