Teoria dei Giochi

Sommario

Introduzione ....................................................................................................................... 3

Sistemi di classificazione dei giochi ............................................................................ 4

Metodi di rappresentazione dei giochi non cooperativi .......................................... 4

Soluzioni di giochi ............................................................................................................ 6

Eliminazione iterata di strategie strettamente dominate.................................................... 6

Il metodo MaxMin/MinMax.............................................................................................. 8

MinMax con strategie miste .............................................................................................. 9

Equilibrio di Nash............................................................................................................ 11

Teoria delle aste .............................................................................................................. 11

Giochi con strategie complesse ................................................................................... 13

Applicazione di un algoritmo MinMax ........................................................................... 13

La potatura alfa-beta........................................................................................................ 14

Studio di giochi ............................................................................................................... 15

Il tris................................................................................................................................. 15

Forza 4 ............................................................................................................................. 16

Go-moku semplificato ..................................................................................................... 16

Go-moku.......................................................................................................................... 17

Appendice ......................................................................................................................... 19

Teorema di Nash.............................................................................................................. 19

Scacchi e dama ................................................................................................................ 19

Bibliografia ....................................................................................................................... 20

La presente relazione è il frutto di un lavoro condotto nel corso di quest’anno scolastico da parte di

un gruppo di quattro studenti di diverse quinte (oltre a me, Davide Pignataro di 5° C, Jacopo

Scalise e Davide Fossati di 5° I), svolto con la supervisione del prof. D. Ciceri.

Mentre lo scritto è integralmente opera mia, le idee che hanno permesso lo sviluppo dell’ultimo

capitolo (“Studio di giochi”) sono frutto del lavoro di tutti e quattro. 2

Introduzione

La teoria dei giochi è una branca della matematica nata molto recentemente, dato che il

primo scritto sistematico sull’argomento, “Theory of Games and Economic Behaviour” di

von Neumann e Morgenstern, risale solamente al 1944. Tuttavia i primi studi in proposito

si devono a Cournot nella prima metà dell’Ottocento. Il matematico che ha dato

un’ulteriore spinta alla teoria dei giochi è stato, nel 1951, John Nash, che con la sua tesi di

sole 30 pagine (“Non-cooperative games”) compie un passo in avanti, generalizzando i

teoremi di von Neumann. Dopo un iniziale periodo di entusiasmo la Teoria dei Giochi

cadde in disgrazia fino agli anni ’80, quando divenne uno strumento fondamentale per

l’analisi economica, tanto da valere il Nobel per l’economia a Nash nel 1994. Oltre che in

economia la Teoria dei Giochi - e specialmente alcuni teoremi di Nash - venne utilizzata

per l’analisi di situazioni di tipo militare durante la guerra fredda, e ultimamente i suoi

campi di applicazione arrivano addirittura alla biologia.

La parola “giochi” in realtà è molto riduttiva, in quanto questa teoria si propone di

analizzare ogni situazione di interazione strategica tra decisori. I giochi in senso letterale

(scacchi, carte, ecc.) vengono usati come “palestre” per imparare a modellizzare interazioni

economiche e sociali. Usualmente i giocatori sono considerati intelligenti e razionali. Per

intelligenti si intende individui che comprendono la situazione in cui si trovano e in grado

di fare ragionamenti logici di complessità indefinitamente elevata, mentre per razionali si

intende che hanno preferenze coerenti (transitive) sugli esiti finali e che hanno l’obiettivo

di massimizzare queste preferenze.

Essendo coinvolti più decisori l’esito finale di un gioco è determinato dalle scelte operate

da ogni decisore.

Il problema delle preferenze dei decisori ci porta a una riflessione sul concetto di utilità.

Nella Teoria dei Giochi l’utilità è intesa come una caratteristica intrinseca dei soggetti e

delle loro preferenze. L’utilità quindi è considerata una funzione definita sull’insieme degli

esiti del gioco. Non importa quali siano le preferenze dei giocatori, basta che esse siano

quantificabili. La funzione di utilità quindi non è necessariamente uguale per tutti i

decisori, e può cambiare a seconda delle situazioni di gioco (ad esempio si pensi a un gioco

in cui si desidera far vincere qualcun altro per farlo felice). 3

Sistemi di classificazione dei giochi

Prima di iniziare la trattazione vera e propria dei giochi è opportuno trovare dei criteri

formali di classificazione.

1) Giochi cooperativi e giochi non cooperativi

La prima classificazione possibile è quella tra i giochi definiti cooperativi e quelli non

cooperativi. Questa distinzione non implica il fatto che i decisori di giochi cooperativi

siano più propensi ad atteggiamenti altruistici, infatti l’altruismo è già preso in

considerazione nelle funzioni di utilità dei singoli. La cooperazione sta nella possibilità di

stringere accordi vincolanti, ovvero accordi il cui rispetto è garantito (ad es. le leggi

possono essere interpretate come accordi vincolanti tra individui, il potere giudiziario

funge da garante per il rispetto delle leggi stesse). Al contrario i giochi non cooperativi

sono quelli in cui non è possibile stringere accordi vincolanti.

2) Giochi a somma zero

Questo criterio di classificazione è applicato ai giochi a due giocatori. Un gioco è definito

a somma zero se in ogni possibile risultato l’utilità di un giocatore è opposta a quella

dell’altro.

3) Giochi a informazione completa

Un gioco è detto a informazione completa se le regole del gioco e le funzioni di utilità di

ogni giocatore sono conoscenza comune di tutti i giocatori.

Metodi di rappresentazione dei giochi non cooperativi

Per operare una descrizione formale dei giochi non cooperativi si è soliti ricorrere a due

modalità rappresentative: la forma estesa e la forma strategica.

Un gioco è descritto in forma estesa quando è rappresentato con un grafo ad albero, che

partendo dalla situazione iniziale proceda mossa per mossa, fino a presentare ogni

possibile situazione finale.

La forma strategica invece precisa il numero dei giocatori, le loro strategie e funzioni di

utilità, essa si presenta sotto forma di bimatrice, che presenta i payoff (risultati) a seconda

della strategia utilizzata da ogni giocatore. Per risalire alla forma strategica bisogna spesso

partire dalla forma estesa, che, rappresentando ogni possibile configurazione, precisa le

possibili mosse dei decisori e, di conseguenza, le strategie.

Ecco un esempio di gioco presentato in forma estesa. 4

a b

A B C D E

c d e f g

F G

Ci sono due mucchietti di due fiammiferi ciascuno. Due giocatori a turno tolgono un certo

numero (>0) di fiammiferi tutti dallo stesso mucchietto. Chi toglie l’ultimo fiammifero

perde.

Il primo giocatore (I) può o togliere uno o due fiammiferi da uno dei due mucchietti,

formalmente può scegliere tra le mosse:

a) togliere un fiammifero da un mucchietto,

b) togliere due fiammiferi da un mucchietto.

A questo punto se I ha giocato la strategia (a), il secondo giocatore (II) può:

A) togliere un fiammifero dallo stesso mucchietto di I,

B) togliere un fiammifero dall’altro mucchietto,

C) togliere due fiammiferi dall’altro mucchietto.

se invece I ha giocato (b), può

D) togliere un fiammifero dal mucchietto rimanente,

E) togliere due fiammiferi dal mucchietto rimanente (e quindi vince I)

Per finire ecco cosa possono fare I e II per concludere il gioco (in proposito si guardi il

grafo sottostante):

c) togliere uno dei due fiammiferi dal mucchietto rimanente

d) togliere entrambi i fiammiferi dal mucchietto rimanente (vince II)

e) togliere l’ultimo fiammifero da uno dei due mucchietti

f-g) togliere l’ultimo fiammifero (vince II)

F-G) togliere l’ultimo fiammifero (vince I)

(come per le prime due mosse le lettere minuscole descrivono le mosse di I, mentre le

maiuscole quelle di II) 5

Si può inoltre evidenziare che questo gioco, giocato tra decisori intelligenti e razionali,

porta invariabilmente II a vincere, infatti se I gioca (a), II può giocare (C) e vincere quando

I fa la mossa (f), se invece I gioca (b), II gioca (D), vincendo il turno successivo.

Evidentemente è più facile lavorare su un gioco in forma strategica, ma è molto più

difficile essere in grado di rappresentarlo (poiché spesso non si conoscono le strategie dei

giocatori). Un celebre gioco di cui parlerò presto, il cosiddetto “Dilemma de prigioniero”,

si presenta, in forma strategica, così:

I/II C NC

C (-5,-5) (-1,-6)

NC (-6,-1) (-2,-2)

Soluzioni di giochi

Per soluzione di un gioco si intende trovare l’esito a cui questo gioco porta. Si ricorda che

bisogna considerare razionali ed intelligenti i due (o più) decisori, altrimenti gli esiti

sarebbero i più disparati.

Qui sono esposti i metodi più efficaci di risoluzione dei giochi a due giocatori.

Eliminazione iterata di strategie strettamente dominate

Se i decisori si trovano davanti a strategie che per qualunque scelta dell’avversario portano

a un payoff minore si dice che quelle strategie sono strettamente dominate, ovvero il

giocatore non ha nessun interesse a seguire tale strategia. Eliminando via via tali strategie

si arriva ad un’unica soluzione, come negli esempi che seguono.

Questo gioco (rappresentato in forma strategica) è a somma zero, quindi è inutile scrivere i

payoff del secondo giocatore, che saranno evidentemente di segno opposto rispetto a quelli

del primo. Le strategie che può scegliere I verranno da qui in avanti indicate con s , s , …,

1 2

s ; le strategie di II invece saranno t , t , …, t .

i 1 2 i t t

I/II t 1 2 3

s 8 3 4

1

s 5 2 -2

2

s 9 -1 3

3

Poiché l’assunto è che i giocatori siano razionali il primo non ha nessun motivo per usare

la sua strategia s , che può essere eliminata. La matrice quindi si presenterà così:

2 6

t t

I/II t 1 2 3

s 8 3 4

1

s 9 -1 3

3 (tenendo conto che l’obiettivo de

Analogamente il secondo può eliminare la colonna t 1

secondo giocatore è minimizzare i guadagni del primo)

I/II t t

2 3

s 3 4

1

s -1 3

3

Continuando così I può eliminare s e II t , quindi (s , t ) è la soluzione.

3 3 1 2

Ecco il “Dilemma del prigioniero” (il gioco citato poco sopra), probabilmente il gioco più

famoso per l’esito inaspettato a cui porta questo metodo di soluzione. Formalmente questo

è considerato un gioco non cooperativo a due giocatori non a somma zero.

Due individui I e II vengono arrestati per lo stesso reato e vengono interrogati

separatamente dal giudice. Ognuno può scegliere indipendentemente dall’altro di

confessare (C) o di non confessare (NC). Se entrambi confessano vengono condannati a 5

anni di prigione ciascuno, se nessuno dei due confessa vengono condannati per reati minori

a due anni ciascuno, infine se uno dei due confessa e l’altro no, quello che confessa ha uno