Beautiful Minds - John Nash racconta "La teoria dei giochi"

A volte mi piace riportare in alto alcuni post che a mio giudizio non sono stati sufficientemente letti o che meritano di essere letti di più, o magari che meritano di essere riletti. Questo è uno di quelli. Con l'occasione vorrei estrarre una piccola parte del pensiero di Nash in cui contrappone l'Equilibrio "delle sue teorie " a quello delle "teorie di Smith" in cui dice che Smith sbaglia quando dice che l'uomo ottiene il massimo dei risultati quando fa i suoi interessi, bensì quando fa i suoi interessi e quelli del gruppo a cui appartiene.

Personalmente aggiungerei una cosa: un gruppo fa i suoi interessi, e dei suoi leader o seguendone le linee guida, ma quando fa anche gli interessi degli individui che lo compongono, pena una prematura disgregazione interna. Qualsiasi cosa si intenda fare insieme ad altri ritengo sia difficile prescindere da questi concetti.

In modo semplice e comprensibile con traduzione simultanea

Teoria dei giochi

Da Wikipedia, l'enciclopedia libera.

La teoria dei giochi è la scienza matematica che analizza situazioni di conflitto e ne ricerca soluzioni competitive e cooperative tramite modelli, ovvero uno studio delle decisioni individuali in situazioni in cui vi sono interazioni tra due o più soggetti, tali per cui le decisioni di un soggetto possono influire sui risultati conseguibili da parte di un rivale secondo un meccanismo di retroazione, e sono finalizzate al massimo guadagno del soggetto. La teoria dei giochi trova applicazione anche nello studio delle relazioni nei gruppi umani.

Cenni storici

La nascita della moderna teoria dei giochi può essere fatta coincidere con l'uscita del libro "Theory of Games and Economic Behavior" di John von Neumann e Oskar Morgenstern nel 1944 anche se altri autori (quali Ernst Zermelo, Armand Borel e von Neumann stesso) avevano scritto, ante litteram, di teoria dei giochi. I due erano, nell'ordine, un matematico e un economista.

Si può descrivere informalmente l'idea di questi due studiosi come il tentativo di descrivere matematicamente ("matematizzare") il comportamento umano in quei casi in cui l'interazione fra uomini comporta la vincita, o lo spartirsi, di qualche tipo di risorsa.

Il più famoso studioso ad essersi occupato successivamente della Teoria dei giochi, in particolare per quel che concerne i "giochi non cooperativi", è il matematico John Forbes Nash jr., al quale è dedicato il film di Ron Howard "A Beautiful Mind".

Otto Premi Nobel per l'economia sono stati assegnati a studiosi che si sono occupati di teoria dei giochi. Anche un Premio Crafoord è stato assegnato a John Maynard Smith, illustre biologo e genetista, professore alla University of Sussex per lungo tempo, per il suo contributo in questo campo.

LOGO del CITG

In Italia, un forte contributo allo sviluppo della teoria dei giochi è stato dato dal "Centro Interuniversitario per la Teoria dei Giochi e le sue Applicazioni" ("CITG"), grazie all'organizzazione di convegni nazionali ed internazionali, scuole estive e diffusione via rete di informazioni (tra cui il Pool Listing, elenco aggiornato di preprint in tema, precedentemente curato dalla Università di Bielefeld e pubblicato sullo International Journal of Game Theory). Il CITG , che era stato promosso dagli atenei di Bergamo, Firenze e Pavia, è stato creato nel 1990 ed è stato chiuso nel 2005 per avere raggiunto i suoi scopi istituzionali.

Premesse

Nel modello della teoria dei giochi la premessa indispensabile è che tutti devono essere a conoscenza delle regole del gioco, ed essere consapevoli delle conseguenze di ogni singola mossa. La mossa, o l'insieme delle mosse, che un individuo intende fare viene chiamata "strategia". In dipendenza dalle strategie adottate da tutti i giocatori (o agenti), ognuno riceve un "pay-off" (che in inglese significa compenso, vincita, pagamento, ma anche esito) secondo un'adeguata unità di misura, che può essere positivo, negativo o nullo. Un gioco si dice "a somma costante" se per ogni vincita di un giocatore vi è una corrispondente perdita per altri. In particolare, un gioco "a somma zero" fra due giocatori rappresenta la situazione in cui il pagamento viene corrisposto da un giocatore all'altro. La strategia da seguire è strettamente determinata, se ne esiste una che è soddisfacente per tutti i giocatori; altrimenti è necessario calcolare e rendere massima la speranza matematica del giocatore, che si ottiene sommando tutti i possibili compensi (sia positivi sia negativi) moltiplicati (pesati) per le rispettive probabilità.

Descrizione informale dei giochi

In un gioco esistono uno o più contendenti che cercano di vincere il gioco, ovvero, di massimizzare la propria vincita. Esiste inoltre una regola (funzione) che stabilisce quantitativamente qual è la vincita dei contendenti in funzione del loro comportamento, tale funzione si chiama funzione dei pagamenti. Ogni giocatore può prendere un numero finito (o infinito nel caso più astratto possibile) di decisioni o strategie. Ogni strategia è caratterizzata da una conseguenza per il giocatore che l'ha presa, la conseguenza della strategia può essere un premio o una penalità. Il risultato del gioco è completamente determinato dalla sequenza delle loro strategie e dalle strategie prese dagli altri giocatori. Ma come caratterizzare il risultato del gioco per ogni giocatore? Se si misura la conseguenza di una strategia in "termini monetari", ogni strategia può essere messa in corrispondenza con un numero: un numero negativo indicherà un pagamento all'avversario, ossia una penalità; mentre un numero positivo indicherà una vincita, ossia la riscossione di un premio. Il guadagno o la perdita spettante al generico giocatore k-esimo associata alla sua strategia e alle strategie prese in un dato istante da tutti i restanti giocatori è espresso dal valore monetario indicato dalla funzione dei pagamenti. Le decisioni prese da un giocatore naturalmente si scontrano o sono in accordo con le decisioni prese dagli altri giocatori; da simili situazioni nascono i giochi cooperativi o non-cooperativi.

Almeno in linea di principio, si può descrivere ogni gioco mediante la forma estesa. Ovvero lo si può rappresentare con un grafo ad albero rappresentando ogni possibile combinazione di giocate dei contendenti sino agli stati finali dove vengono ripartite le vincite. Un'altra possibile rappresentazione è quella matriciale (a matrice).

Tipi di giochi

I giochi possono essere classificati in base a diversi paradigmi:

Cooperazione

Rappresentazione

Somma.

Cooperazione

Un gioco cooperativo si presenta quando gli interessi dei giocatori non sono in opposizione diretta tra loro, ma esiste una comunanza di interessi. I giocatori perseguono un fine comune, almeno per la durata del gioco, alcuni di essi possono tendere ad associarsi per migliorare il proprio "pay-off". La garanzia è data dagli accordi vincolanti. Qual è la rappresentazione matematica di una comunanza di interessi? Il concetto di unione di singoli interessi individuali in una coalizione o alleanza è espresso dalla definizione di gioco essenziale; mentre il valore v di una generica coalizione G è misurato da una funzione detta funzione caratteristica. Indicato con R= l'insieme degli n giocatori, possono esistere

arbitrari sottoinsiemi G⊆R che rappresentano una coalizione tali per cui G appaia agli effetti del gioco come un unico giocatore. La funzione caratteristica è proprio definita sull'insieme delle parti di R, ossia sull'insieme di tutti i sottoinsiemi G⊆R ed associa ad ogni coalizione un numero: V(G):= v. Naturalmente V(∅):= 0 in quanto è nullo il pagamento per la coalizione vuota, quella costituita da nessun giocatore. Un gioco ad n-persone è detto essenziale se

con k=1,...,

per ogni i≠j.

In sostanza un gioco essenziale è intrinsecamente di natura cooperativa quando tutte le possibili coalizioni costituibili tra gli n giocatori "vedono" che esiste un valore del gioco V(R) che domina la semplice unione dei pagamenti conseguibili dalle singole alleanze

. In R tutti i giocatori interagiscono e dalle reciproche relazioni traggono il mutuo vantaggio V(R).

Si possono avere due sottogeneri, i giochi NTU ed i giochi TU.

Giochi NTU

"Non Transferable Utility": a utilità non trasferibile o senza pagamenti laterali. In questi casi, nel campo dell'economia industriale, in una situazione di oligopolio può insorgere il fenomeno della collusione.

Giochi TU

"Transferable Utility": a utilità trasferibile o con pagamenti laterali, nei quali deve esistere un mezzo, denaro o altro, per il trasferimento dell'utilità.

La suddivisione della vincita avviene in relazione al ruolo svolto da ciascun giocatore, secondo la sua strategia ed i suoi accordi (per i "giochi TU" vanno aggiunti i pagamenti o i trasferimenti ottenuti durante il gioco).

Nei giochi a 2 persone con funzione dei pagamenti a somma costante, per definizione esistono due schieramenti G ed

, quest'ultima è la coalizione avversa a G essendo

l'insieme complementare di G. I giochi a due persone sono tali per cui per ogni coalizione G⊆R si ha

I giochi a due persone a somma costante mostrano quindi di non essere essenziali, ovvero la loro vera natura non è di carattere cooperativo. Quest'ultima asserzione è un teorema matematico per la cui dimostrazione formale si rimanda alla lettura del teorema 41 in E.Burger, Introduction to the Theory of Games. Nei giochi a somma costante se i giocatori si coalizzassero in R conseguirebbero il medesimo risultato se giocassero separatamente:

. Nei giochi essenziali, per i quali vale l'adagio "l'unione fa la forza", i giocatori collaborando si garantiscono un guadagno superiore a quello che otterrebbero giocando individualmente. In generale la cooperazione può essere richiesta esplicitamente dalle regole del gioco: è il caso in cui è il gioco stesso ad imporre per ogni giocatore la scelta di uno o più partner; oppure la cooperazione può sorgere in quanto la funzione dei pagamenti non ammette a priori un valore unico. La funzione caratteristica descrive semplicemente quanto una coalizione ottenga dai propri avversari, ma non dice nulla di come i guadagni vengano divisi tra gli alleati della coalizione stessa. John von Neumann e Oskar Morgenstern si sono avvicinati al problema dei giochi cooperativi caratterizzandoli per il fatto che una coalizione di individui ha ragione di esistere se e solo se verifica due condizioni relative alla distribuzione delle vincite tra i membri della coalizione. Le due condizioni sono:

1) ogni spartizione dei "guadagni" conseguibili tra i giocatori non appartenenti alla coalizione è inferiore alla spartizione dei "guadagni" effettuata tra i giocatori appartenenti alla coalizione;

2) nessuna spartizione dei guadagni all'interno della coalizione è superiore a qualche altra possibile distribuzione dei "guadagni" all'interno della coalizione.

La proprietà 1) afferma che la coalizione è vincente perché è più remunerativa e, in conclusione, tutti vorrebbero entrarvi.In sintesi le soluzioni dei gioco devono essere efficienti: non esistono altre soluzioni che migliorano i risultati conseguibili dai membri della coalizione.

La proprietà 2) assicura che il credo (trust) adottato all'interno della coalizione è libero da contraddizioni interne che minerebbero la fiducia reciproca tra i membri; in poche parole le vincite vengono distribuite equamente tra tutti i membri della coalizione senza preferenze o favoritismi di sorta.

Giochi non cooperativi

Nei giochi non cooperativi, detti anche giochi competitivi, i giocatori non possono stipulare accordi vincolanti (anche normativamente), indipendentemente dai loro obiettivi. A questa categoria risponde la soluzione data da John Nash con il suo Equilibrio di Nash, probabilmente la nozione più famosa per quel che riguarda l'intera teoria, grazie al suo vastissimo campo di applicabilità. Il criterio di comportamento razionale adottato nei giochi non-cooperativi è di carattere individuale ed è chiamato strategia del massimo. Una definizione di razionalità siffatta caratterizza il comportamento di un individuo “intelligente ottimista” in quanto si prefigge l’obiettivo ottimista di prendere sempre la decisione che consegue il massimo guadagno possibile. In sostanza il comportamento di ogni giocatore è tale da perseguire sempre la strategia più vantaggiosa per sé stesso. Qualora nel gioco esista una strategia che presenta il massimo guadagno per tutti i giocatori si parla di punto di equilibrio. Un punto di equilibrio in un gioco in cui si attua la strategia del massimo esprime il fatto che tutti i giocatori conseguono sì il massimo guadagno individuale, ma anche quello collettivo. Il punto di equilibrio di Nash esprime in un certo senso un comportamento razionale socialmente utile dal momento che tutti i giocatori ottengono un pagamento che presenta la convergenza degli interessi di tutti i giocatori. John Nash ha dimostrato che ogni gioco finito ad "n" giocatori ammette almeno un punto di equilibrio in strategie miste, tale teorema faceva parte della sua tesi di dottorato.

Giochi ripetuti nel tempo

Per approfondire, vedi la voce dilemma del prigioniero.

Alcune tipologie di gioco che portano gli agenti a giocare più di una volta, trasformando i pay off tramite un vincolo intertemporale, possono via via produrre risultati finali diversi pur considerando lo stesso schema di gioco iniziale.

Un esempio di questi è il dilemma del prigioniero ripetuto infinite volte.

Rappresentazione

Giochi a informazione perfetta e completa

Per approfondire, vedi la voce Gioco a informazione completa.

I giochi a informazione perfetta, in ogni momento, si conosce con certezza la storia delle giocate precedenti. In termini più tecnici, si tratta di giochi in cui in ogni momento del gioco si può capire in quale nodo della rappresentazione ad albero del gioco (rappresentazione estesa) ci si trova. Un concetto molto simile è quello di gioco a informazione completa, in cui ogni giocatore ha una conoscenza completa del contesto ma non necessariamente delle azioni degli altri giocatori, per esempio perché le mosse dei diversi giocatori devono avvenire simultaneamente (vedi il dilemma del prigioniero).

Esempi:

Scacchi

Dama

Nim

Hex

Giochi finiti

Giochi in cui il numero delle situazioni di gioco possibili è finito. Ma il numero delle situazioni può essere assai elevato.

Esempi:

tris (o tic tac toe)

Othello (o reversi)

Somma

Giochi a somma zero

I giochi a somma zero sono un caso particolare dei giochi a somma costante in cui la costante è pari a zero. I giochi a somma zero modellano tutte quelle situazioni conflittuali in cui la contrapposizione dei due giocatori è totale: la vincita di un giocatore coincide esattamente con la perdita dell’altro. La somma delle vincite dei due contendenti in funzione delle strategie utilizzate è cioè sempre zero. Negli scacchi ad esempio significa che i soli tre risultati possibili (rappresentando la vittoria con 1, la sconfitta con -1 e il pareggio con 0) possono essere: 1,-1 se vince il bianco; -1,1 se vince il nero; 0,0 se pareggiano. Non esiste ad esempio il caso in cui vincono entrambi o perdono entrambi.

Esempi a informazione perfetta

scacchi

Esempi a informazione imperfetta

briscola

poker

Formalmente un gioco a somma zero in forma normale a due giocatori si esprime come:

≡ 0 ∀

∈

∧ ∀

∈

dove

Se il gioco è finito, le funzione dei pagamenti

possono essere rappresentate per mezzo di una matrice costituita da m righe ed n colonne. I due giocatori 1 e 2 conoscono il contenuto della matrice dei pagamenti ed il gioco consiste per ogni giocatore k nello scegliere una strategia

∈

senza conoscere la scelta dell'altro.

In riferimento alla matrice dei pagamenti del giocatore 1 si pone

= -

La scelta di una strategia da parte del giocatore 1 corrisponde alla scelta di una riga, mentre per il giocatore 2 corrisponde alla scelta di una colonna. Il giocatore 2 verserà al giocatore 1 la somma indicata all’intersezione della riga scelta dal giocatore 1 con la colonna scelta dal giocatore 2. Il desiderio del giocatore 2 sarà pertanto di minimizzare il pagamento dovuto al giocatore 1, ovvero il giocatore 2 volendo massimizzare

= -

cercherà di minimizzare

. Il desiderio del giocatore 1 sarà invece di massimizzare il pagamento ricevuto dal giocatore 2, ovvero il giocatore 1 volendo massimizzare

cercherà di massimizzare

. In sostanza il comportamento dei due giocatori è esattamante opposto: il giocatore 1 si dice giocatore massimizzante, mentre il giocatore 2 si dice giocatore minimizzante. In modo simmetrico se si desse al giocatore 2 la matrice dei pagamenti che lui dovrebbe ricevere dal giocatore 1,

, allora il giocatore 1 diverrebbe il giocatore minimizzante ed il giocatore 2 quello massimizzante.

A questo punto l’attenzione dei due giocatori si rivolge al medesimo oggetto: la matrice

. Il giocatore 1 cerca di massimizzare

, ma il suo controllo è limitato solo alla scelta di una riga. Idem per il giocatore 2 che cerca di minimizzare

: il suo controllo è limitato solo alla scelta di una colonna. Quale sarà il criterio di scelta dei due giocatori antagonisti?

John von Neumann ha risposto a tale quesito mediante il seguente criterio: il giocatore 1 rileva dapprima il numero più piccolo di ogni riga e decide di scegliere la riga che contiene il più grande dei valori monetari considerati: in questo modo egli è certo che la sua vincita non sarà inferiore al valore

qualunque sia la scelta del giocatore 2. Il giocatore 2 da parte sua considera il numero più grande di ogni colonna e decide di scegliere la colonna che contiene il più piccolo dei numeri considerati: così egli è certo che la sua perdita non sarà superiore al valore

qualunque sia la scelta del giocatore 1. Quanto appena descritto rappresenta la definizione di comportamento razionale data da John von Neumann e ad essa comunemente ci si riferisce come principio della scelta minimax.

La coppia di strategie

costituiscono un punto di equilibrio, punto di sella, nel senso di Von Neumann se valgono le due condizioni:

∀

∈

∀

∈

La condizione 1) si riferisce al giocatore massimizzante, la 2) al giocatore minimizzante. Il punto di equilibrio in un gioco fondato sul principio minimax per la scelta delle strategia rappresenta il fatto che entrambi i giocatori attuano decisioni compatibili con i fini che entrambi si erano proposti di raggiungere: il punto di equilibrio

rappresenta ovvero la convergenza degli interessi dei due avversari e pertanto si è soliti riferirsi alle strategie di equilibrio come alle strategie ottimali. Von Neumann ha dimostrato che ogni gioco a somma zero a due persone a informazione completa e con albero del gioco finito ammette strategie ottimali per entrambi i giocatori. Alla luce del teorema appena menzionato il principio del minimax risulta essere giustificatamente a fondamento della teoria del comportamento razionale nei giochi a somma zero in quanto introduce in modo rigoroso le strategie minimax e queste si dimostrano essere le strategie ottimali in corrispondenza delle quali il gioco presenta un valore ottimale per entrambi

=V*=

avendo scelto arbitrariamente

In ultimo si fa osservare che la definizione di equilibrio secondo Von Neumann data nei giochi a somma zero è la traduzione del concetto di equilibrio nel senso di Nash data in termini più generali per i giochi non-cooperativi. Nel seguito si illustra come passare dal concetto di equilibrio di Von Neumann al concetto di equilibrio di Nash: basta ricordare che per un gioco a somma zero si ha:

. Diviene allora lecito scrivere:

∀

∈

La prima condizione di equilibrio nel senso di Von Neumann pertanto è la prima condizione di equilibrio nel senso di Nash riferita al giocatore 1. Per il giocatore 2 invece diviene:

∀

∈

ovvero

∀

∈

Per concludere nel campo della programmazione matematica si ricorda che un gioco a somma zero a due giocatori può sempre essere ricondotto a una coppia di programmi lineari mutuamente duali, il cui valore ottimale z* dei due problemi corrisponde al valore del gioco V*.

Sia

la matrice dei pagamenti rappresentativa di un gioco a somma zero a due giocatori:

avendo indicato con

Per il giocatore massimizzante si ha il seguente problema primale:

z*=max V

soggetta ai vincoli:

≥ V per ogni j=1,...,n

= 1

∈ {0;1} per ogni i=1,...,m

Per il giocatore minimizzante (problema duale) si ha:

z*=min V

soggetta ai vincoli:

≤ V per ogni i=1,...,m

= 1

∈ {0;1} per ogni j=1,...,n

Osservazioni sui vincoli

I primi n vincoli per il giocatore massimizzante (m per il giocatore minimizzante) indicano che la strategia da scegliere dovrà conseguire un guadagno (una perdita) non inferiore a V (non superiore a V).

Il vincolo che pone uguale ad 1 la somma delle strategie afferma che una ed una sola strategia deve essere scelta, si osservi comunque che se il gioco dovesse ammettere più di un punto di equlibrio il valore del gioco V* rimarrebbe immutato.

Le m strategie

del giocatore 1 e le n strategie del giocatore 2

sono state espresse come variabili booleane: queste assumono il valore 1 in corrispondenza della scelta del giocatore, mentre assumono il valore 0 quando la strategia corrispondente non viene scelta.

L'insieme dei vincoli costituiscono un poliedro. La soluzione dei rispettivi problemi, se esiste, si identifica con un vertice del poliedro.

Giochi a somma non zero

In cui la somma di cui al punto precedente non è zero almeno in un caso.

Esempi:

gioco del pollo

dilemma del viaggiatore

I giochi a somma non costante sono implicitamente giochi a somma non nulla; mentre tutti i giochi a somma costante sono riconducibili a giochi a somma zero senza alterare l'esito del gioco.

Applicazioni

Le applicazioni e le interazioni della teoria sono molteplici: dal campo economico e finanziario a quello strategico-militare, dalla politica alla sociologia, dalla psicologia all'informatica, dalla biologia allo sport, introducendo l'azione del caso, connessa con le possibili scelte che gli individui hanno a disposizione per raggiungere determinati obiettivi, che possono essere:

comuni

comuni, ma non identici

differenti

individuali

individuali e comuni

contrastanti.

Possono essere presenti anche aspetti aleatori.

Esempi

Ecco alcuni esempi di situazioni che possono essere analizzate utilizzando la teoria dei giochi.

Se il giocatore è un commerciante, le sue mosse possono essere: aumentare, diminuire o lasciare invariati i prezzi dei suoi prodotti; le mosse di un acquirente possono invece essere: cambiare, restare fedeli a un prodotto o a un fornitore; le mosse di un responsabile di logistica militare possono essere: inviare un convoglio lungo un certo percorso, piuttosto che lungo un altro. Per esempio, i convogli possono essere inviati periodicamente, per il 30% dei viaggi su un percorso e per il 70% su un altro; i prezzi dei prodotti possono essere variati in rotazione e così via.

Un altro esempio di situazioni conflittuali è il celebre dilemma del prigioniero.

Note

Breve cronistoria dei convegni italiani di TdG

Bibliografia

Testi di importanza storica

Ronald Fisher (1930): The Genetical Theory of Natural Selection Oxford Clarendon Press

Duncan Luce, Howard Raiffa (1957) Games and Decisions: Introduction and Critical Survey, Dover, ISBN 0-486-65943-7

John Maynard Smith (1982): Evolution and the Theory of Games, Cambridge University Press

John von Neumann, Oskar Morgenstern (1944): Theory of Games and Economic Behavior, Princeton University Press; terza ed. 1953.

John Forbes Nash (1950): Equilibrium points in n-person games, Proceedings of the National Academy of the USA, 36(1) pp. 48-49

Testi di riferimento correnti

Roger B. Myerson (1991): Game Theory, Analysis of Conflict, Harvard University Press, ISBN 0-674-34116-3

Drew Fudenberg e Jean Tirole (1991): Game Theory, MIT Press, ISBN 0-262-06141-4

Ken Binmore (1992): Fun and Games, D. C. Heath, ISBN 0-669-24603-4

Robert Gibbons (1992) Game Theory for Applied Economists, Princeton University Press, ISBN 0-691-00395-5 - Pubblicato in Europa da Harvester Wheatsheaf con il titolo A primer in game theory

Peter Morris (1994): Introduction to the Theory of Games, Springer, ISBN 3-540-94284-X

Herbert Gintis (2000) Game Theory Evolving, Princeton University Press, ISBN 0-691-00943-0

Martin Osborne, Ariel Rubinstein: A Course in Game Theory, MIT Press, 1994, ISBN 0-262-65040-1

R.Duncan Luce e Howard Raiffa: Games and Decisions, Wiley, New York, 1957.

Guillermo Owen: Game Theory, terza edizione (prima edizione: 1968), Academic Press, New York, 1995.

Prajit K. Dutta: Strategies and Games: Theory and Practice, MIT Press, 1999.

Ewald Burger: Introduction to the Theory of Games, United States of America: Prentice-Hall, Inc., 1963

Voci correlate