Teoria dei Giochi

Dario Celotto

Liceo scientifico e classico Ettore Majorana – Classe 5° D

A.S. 2006/2007

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 del prigioniero”, si presenta, in forma strategica, così:

I/II C NC

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

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

Soluzioni