Teoria dei giochi tesina (2)

Liceo Scientifico Statale

“Francesco Vercelli”

Asti

Classe V E

Anno scolastico 2013/2014

Esame di Stato

Competizione e cooperazione

Un tuffo nella teoria matematica dei giochi

Di

Federico Miceli

Competizione e cooperazione tesina di Federico Miceli

Indice

• Introduzione 2
• Giochi 4
• Cenni storici (parte 1) 5
• Struttura ad albero 6
• Matrici 8
• Teorema di Zermelo 10
• Invarianti 11
• Simmetria 12
• MinMax 13
• Cenni storici (parte 2) 15
• John Nash VS Adam Smith 16
• Andrea Camilleri 17
• Gradi di informazione 20
• Rand Corporation 22
• Crisi missilistica di Cuba 24
• Indice di Shapley 28
• Equiprobabilità 31
• Il gioco del matrimonio 34
• Un giornale “onesto” 35
• Nineteen eighty-four 36
• Bibliografia - Sitografia 39

Competizione e cooperazione tesina di Federico Miceli

Introduzione

“I matematici hanno vinto la guerra. I matematici hanno decifrato i codici segreti giapponesi e fabbricato la bomba atomica. I matematici.”

Questa è la frase con cui si apre “A beautiful mind”, un film uscito nel 2001 la cui trama descrive la vita di uno dei massimi matematici dello scorso secolo, John Nash.

La matematica negli ultimi decenni è entrata sempre più nei massimi sistemi.

Si è scoperto che non sono soltanto i fenomeni fisici a seguirne le leggi, bensì anche l’andamento dell’economia, i risultati delle elezioni politiche e addirittura gli esiti delle guerre.

Questi fenomeni possono essere ben descritti, e quindi previsti, da tali leggi e schemi.

In quanto appassionato di matematica (all’università intendo appunto iscrivermi a tale disciplina) mi è parso doveroso fare una scelta un po’ controcorrente e incentrare il mio lavoro sulla matematica tralasciando in gran parte tutte le altre discipline.

Soltanto altre tre materie (italiano, storia e inglese) compaiono infatti in questo breve testo, e comunque come puri collegamenti decorativi, utili per approfondire le applicazioni della teoria e catturare, almeno in parte, l’attenzione dei vari docenti della commissione.

Ad alcuni potrà sembrare controversa la scelta di un argomento matematico per questo tipo di lavoro.

Ci si chiederà: “perché incentrare una tesina su un tema esclusivamente matematico?”.

Credo che la risposta sia in stretta relazione con un’altra questione, la definizione stessa di matematica e la sbagliata opinione che spesso si ha di essa.

Non è un segreto il fatto che la matematica sia generalmente una disciplina poco apprezzata.

Ritengo che questo dipenda principalmente dal modo in cui viene presentata in ambito scolastico.

La matematica studiata almeno fino al secondo anno di superiori essenzialmente non è matematica. In essa infatti non è richiesto alcun ragionamento, non serve un’idea originale.

Basta svolgere meccanicamente dei calcoli e applicare pedestremente regole studiate.

Chi potrebbe gradire un simile compito?

Non uno studente di certo, e così neppure un matematico.

Così l’opinione comune riduce i matematici a “uomini che passano la vita a svolgere calcoli complicati”. Nulla di più sbagliato!

Chi si sognerebbe di ridurre un poeta a “uno che scrive parole” o un pittore a “uno che usa un pennello”?

Il matematico, come il poeta, come il pittore, ricerca innanzitutto un’idea originale.

Lo scopo di un artista poi sarà esprimere tale idea, quello del matematico sarà cercare di comprenderla più a fondo, nella sua essenza e nelle sue implicazioni ed applicazioni.

La matematica è una disciplina interessante fatta di idee sempre nuove e bizzarre.

Ogni grande rivoluzione in campo matematico (come d’altronde in ogni campo del sapere scientifico) non è derivata dalla semplice evoluzione di studi precedenti, bensì da un approccio del tutto nuovo a un problema o alla disciplina stessa. In tale modo nel XVI secolo Tartaglia definì i numeri complessi per risolvere le equazioni di terzo grado. Essi non derivavano da studi precedenti, che comunque c’erano stati, ma soltanto da una visione del tutto nuova del problema.

2

Competizione e cooperazione tesina di Federico Miceli

Introduzione

Ritengo interessante a questo proposito un’intervista a Camillo De Lellis, matematico italiano vincitore del premio Fermat e oggi professore di matematica all’Università di Zurigo, che alla domanda “Cosa diresti per motivare un giovane a fare matematica?” rispose:

“Direi che è bello. È bello. È bello. È bello fare matematica. È interessante. Si capiscono le cose. Non so come dirlo, ma il piacere che provo quando capisco una cosa è proprio la soddisfazione di averla capita. È impagabile. E ovviamente è anche una cosa utile. Certo, a un ragazzo di 18 o 19 anni, se lo vuoi incoraggiare a fare matematica o più in generale a fare scienza, gli puoi spiegare che ci sono le applicazioni. Ma insomma, alla fine se sono queste che veramente lo interessano, allora potrebbe anche andare a fare l’ingegnere. Invece secondo me uno deve battere sul chiodo del genuino interesse estetico nel fare matematica. Uno fa cose belle. E in questo invidio i miei colleghi che fanno scienze umanistiche che non devono mai giustificare il motivo per studiare le loro materie. Studi italiano o storia dell’arte perché sono belle. E così dovrebbe essere per la matematica. Perché la matematica è bella e divertente, più di quanto uno non pensi.”

Dunque non paia strano alla commissione di trovare un testo in parte specifico, in cui si tratterà di matematica e poco altro. In essa c’è tutto il rigore delle materie scientifiche, la bellezza estetica dell’arte, l’utilità della filosofia e della grande letteratura.

Si vuole infine fare una precisazione tecnica.

La teoria dei giochi è un ramo della combinatoria, una delle grandi parti in cui è divisa la matematica (insieme ad altri rami più o meno ampi).

Io di certo amo tutta la matematica, ma la mia passione si è sempre incentrata in particolare sulla combinatoria (anche per questo la scelta della teoria dei giochi anziché altri possibili argomenti).

Tale disciplina è difficile da formalizzare e ardua da comprendere in forma astratta.

Dunque il mio lavoro sarà ricco di esempi e di problemi proposti per spiegare concetti e teoremi.

Essi talvolta avranno la funzione di chiarire dei concetti, altre di presentarli.

Non è possibile ometterli se si vuole essere compresi da chi non si occupa in prima persona di matematica (comunque questa tesina vuole rifarsi al metodo dei testi di divulgazione scientifica).

Spero comunque che essi possano risultare stimolanti e che le loro risoluzioni possano servire per comprendere la teoria di fondo prima ancora che i problemi stessi.

Inoltre si presenteranno alcuni problemi che non possono essere considerati a tutti gli effetti parte della teoria dei giochi ma che ritengo interessanti per mostrare diversi approcci che si possono avere a un problema e come alcuni quesiti entrino nella nostra società senza che noi ce ne accorgiamo. Dunque oltre a problemi più astratti verranno anche presentati problemi utili a spiegare alcune dinamiche del mondo che ci circonda.

Molti degli esercizi presentati, seppur non tutti, sono tratti da “Di duelli, scacchi e dilemmi”, un testo divulgativo di Roberto Lucchetti con cui l’autore punta a presentare la teoria dei giochi da un punto di vista matematico anche a chi non si occupa direttamente di matematica.

Questa scelta deriva dal semplice fatto che si tratta della miglior raccolta cartacea in lingua italiana di quesiti attinenti a tale materia, ed effettivamente vi ho trovato moltissimi esempi utili per il mio lavoro.

Detto ciò auguro a tutti buona lettura. 3

Competizione e cooperazione tesina di Federico Miceli

Giochi

Per parlare di teoria dei giochi serve innanzitutto definire il concetto matematico di gioco.

Esso non coinvolge né la fantasia né la creatività, si tratta di una definizione profondamente diversa da quella usuale.

Un gioco in senso matematico è dato da uno scontro di interessi fra due o più giocatori (che in realtà possono anche collaborare se è possibile il perseguimento di un fine comune).

Questi giocatori non sono necessariamente individui, possono essere partiti, eserciti, nazioni, società industriali…

Ogni giocatore ha a disposizione delle scelte e in base a queste tenta di massimizzare il proprio guadagno (o minimizzare la propria perdita, il che algebricamente ha lo stesso significato).

A questo proposito è importante osservare che l’interesse di un giocatore non è necessariamente in conflitto con quello degli avversari, dipende essenzialmente dalla tipologia di gioco.

Sono poi presenti molti altri fattori che ci consentono di distinguere diversi tipi di giochi che vanno dunque approcciati in modi diversi.

Contano la durata del gioco (finito o infinito?), il numero di giocatori, l’intervento del caso, il grado di consapevolezza dei giocatori (conosco le mosse fatte del mio avversario?), la contemporaneità delle scelte (si sceglie in successione o tutti insieme?)…..

Questi e altri fattori creano una grande varietà di giochi che vanno dunque analizzati secondo schemi differenti.

Dunque in senso matematico non è un gioco il nascondino, né il gioco dello sparviero.

Sono invece giochi i conflitti economici fra aziende, le elezioni politiche e gli andamenti bellici.

La teoria dei giochi è la teoria matematica che studia i comportamenti dei vari giocatori.

Lo scopo di questa disciplina è scoprire le strategie vincenti, con cui ogni giocatore può massimizzare il proprio guadagno, e determinare dunque gli esiti del gioco.

Robert Aumann, uno dei massimi studiosi di teoria dei giochi, definì tale teoria come segue:

“La teoria dei giochi è la scienza delle interazioni strategiche tra entità che si battono al meglio per raggiungere i propri scopi. Le entità non devono essere necessariamente persone: possono essere nazioni, corporazioni, sindacati, ma anche animali o piante. E gli scopi possono anche essere opposti, ma non è necessario che lo siano.”

In tutto ciò la teoria si serve del postulato di razionalità.

Questo postulato sostiene che tutti i giocatori puntano effettivamente a massimizzare il proprio guadagno (non è razionale un giocatore che si accontenta del risultato ottenuto se certo di poter migliorare tale risultato) e che agiscano in maniera razionale (cioè prendendo in ogni situazione la scelta ottimale). Senza tale postulato ogni risultato in teoria dei giochi risulta errato.

Chiaramente se un giocatore non segue il postulato di razionalità lo fa a proprio danno, nel senso che se invece gli avversari agiranno razionalmente allora egli subirà perdite maggiori di quelle che avrebbe subito comportandosi razionalmente. 4

Competizione e cooperazione tesina di Federico Miceli

Cenni storici (parte 1)

Nell’agosto del 1900 a Parigi si tenne il Secondo Congresso Internazionale di Matematica.

In questa occasione David Hilbert, uno dei massimi matematici del periodo, espose i suoi intenti in una conferenza intitolata “I Problemi della Matematica” che si apriva con le parole:

“Chi di noi non sarebbe felice di sollevare il velo dietro cui si nasconde il futuro; di gettare uno sguardo ai prossimi sviluppi della nostra scienza e ai segreti del suo sviluppo nei secoli a venire? Quali saranno le mete verso cui tenderà lo spirito delle future generazioni di matematici? Quali metodi, quali fatti nuovi schiuderà il nuovo secolo nel vasto e ricco campo del pensiero matematico?”.

Alla conferenza erano presenti alcuni dei massimi matematici dell’epoca. Hilbert voleva che questi si impegnassero nella sua battaglia di unificazione e riorganizzazione dei fondamenti di tutta la matematica. Fra i presenti compariva un nome destinato a entrare nella storia, Ernst Zermelo.

Zermelo lavorò sulla congettura di Cantor, proposta da Hilbert, ed elaborò con successo diverse teorie.

La più nota è quella ricordata come “teorema di Zermelo” dimostrata nel 1913.

Con questo teorema (su cui tornerò nelle pagine successive) si era giunti al primo risultato in quella che solo successivamente avrebbe preso il nome di teoria dei giochi.

All’ambizioso progetto di Hilbert lavorò fino al 1927 anche un giovane brillante matematico, John von Neumann. Nel 1928 von Neumann pubblicò sulla rivista Mathematische Annalen un articolo intitolato Zur Theorie der Gesellschaftspiele (Sulla teoria dei giochi di società).

In questo articolo von Neumann presentava il teorema di minmax, di cui si parlerà in seguito.

Ma il ruolo di von Neumann nello scenario della teoria dei giochi non era ancora volto al termine.

Nel 1944 infatti pubblicò insieme a Oskar Morgenstern, professore di economia, un testo destinato a fare storia, Theory of Games and Economic Behavior (Teoria dei giochi e comportamenti economici).

Questo testo è considerato l’origine formale della teoria dei giochi.

In esso infatti per la prima volta veniva formalizzata la teoria dei giochi a cui si dava dignità matematica.

Solo a partire da questa data è possibile parlare ufficialmente di teoria dei giochi.

Nel testo inoltre comparivano innumerevoli riferimenti alle situazioni di applicazione della teoria, prima di tutte riguardanti l’economia.

Furono soprattutto tali applicazioni a contribuire alla notorietà del testo, e della teoria stessa e che avrebbero portato le future generazioni di matematici a impegnarsi in tale campo. 5

Competizione e cooperazione tesina di Federico Miceli

Struttura ad albero

Esistono due metodi essenziali per rappresentare, e dunque risolvere, i giochi più semplici.

Le strutture ad albero sono adatte per i giochi in cui i giocatori giocano a turno, conoscono tutte le mosse precedenti, hanno mosse limitate e il gioco termina dopo un numero finito di mosse.

Una struttura ad albero si presenta nella forma seguente

In questo albero ci immaginiamo un gioco che termina dopo tre mosse e in cui ogni giocatore (supponiamo che ci siano due giocatori) ha due possibilità per ogni mossa, schematizzabili sull’albero come: destra e sinistra.

Il primo giocatore deciderà dove orientare il gioco al nodo 1, il secondo giocatore dovrà decidere al nodo 2, poi ancora il primo giocatore sceglierà al nodo 3.

Le lettere a fine albero rappresentano i payoffs, ovvero i risultati del gioco.

Supponiamo che il primo giocatore voglia una lettera più vicina possibile alla A, mentre il secondo giocatore voglia una lettera più vicina possibile alla H. In altre parole proviamo a vedere l’esito del gioco se per il primo giocatore i payoffs sono ordinati in ordine decrescente (A è il migliore) mentre per il secondo giocatore i payoffs sono in ordine crescente (H è il migliore).

Allora il primo giocatore al primo nodo sceglierà di andare a sinistra.

Poi il secondo giocatore sceglierà al secondo nodo di andare a destra.

Infine il primo giocatore al terzo nodo sceglierà di andare a sinistra.

Rappresentato nello schema si ottiene dunque la situazione seguente:

Questo schema ad albero mostra dunque l’andamento di questo semplice gioco e il suo risultato (supponendo ovviamente il postulato di razionalità).

È significativo che se fosse il secondo giocatore a iniziare si giungerebbe con ragionamenti analoghi al payoff F. Questo mostra l’importanza dell’ordine in cui i giocatori fanno le loro mosse.

In maniera analoga è possibile rappresentare giochi più complessi.

Ovviamente gli alberi risultanti avranno più diramazioni, più payoffs e non risulterà subito evidente quali siano le scelte ottimali di ogni giocatore a ciascun nodo. 6

Competizione e cooperazione tesina di Federico Miceli

Vediamo dunque un problema risolvibile tramite struttura ad albero:

Due giocatori, diciamo Alberto e Barbara, giocano come segue:

Dispongono 4 fiammiferi in 2 gruppi da 2 fiammiferi l’uno.

Una mossa consiste nel togliere 1 o 2 fiammiferi da un gruppo (si possono togliere due fiammiferi dallo stesso gruppo ma non si può togliere un fiammifero da ciascun gruppo).

Si procede a turno (prima gioca Alberto, poi Barbara, poi ancora Alberto…).

Chi toglie l’ultimo fiammifero perde il gioco.

Ovviamente ciascun giocatore vuole obbligare l’avversario a togliere l’ultimo fiammifero.

Per capire l’esito del gioco è opportuno tracciarne il diagramma ad albero:

Il pallino blu indica la vittoria di Alberto, il pallino rosso indica la vittoria di Barbara.

Analizziamo i possibili andamenti del gioco per capire se Alberto abbia una strategia vincente.

Se al primo nodo Alberto gioca 1 → 2 allora Barbara giocherà 2 → 6 ottenendo dunque la vittoria.

Dunque se Alberto gioca 1 → 2 mette Barbara nella situazione di assicurarsi la vittoria.

Se invece Alberto gioca 1 → 3 la situazione risulta analoga.

Infatti Barbara giocherà 3 → 7 e ancora si garantirà la vittoria.

Dunque se Barbara è una giocatrice razionale il gioco potrà seguire solo uno dei seguenti due andamenti:

• 1 → 2 → 6 → 12 vince Barbara
• 1 → 3 → 7 → 13 vince Barbara

Dunque Barbara ha una strategia vincente per qualunque mossa di Alberto e risulta dunque vincitrice del gioco.

Con questo esempio si è voluto mostrare l’efficacia delle strutture ad albero nella rappresentazione di giochi finiti, con giocatori finiti aventi mosse finite, che giocano a turno con totale consapevolezza delle mosse precedenti e in cui non interviene il caso.