Teoria dei giochi: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Annullate le modifiche di 79.40.149.254 (discussione), riportata alla versione precedente di Fioravante Patrone |
m Annullata la modifica 146397282 di 79.41.169.12 (discussione) Etichetta: Annulla |
||
| (188 versioni intermedie di 86 utenti non mostrate) | |||
Riga 1:
{{NN|matematica|luglio 2013|}}
La '''teoria dei giochi''' è una disciplina che studia modelli [[matematica|matematici]] di interazione [[strategia|strategica]] tra [[agente intelligente|agenti razionali]].<ref>{{en}} {{Cita|Myerson 1991|p. 1.|Myerson}}</ref>
La teoria dei giochi ha applicazioni in vari campi delle scienze sociali, così come nella [[logica]], nella [[teoria dei sistemi]] e nell'[[informatica]]. Sebbene originariamente si sia focalizzata sui [[gioco a somma zero|giochi a somma zero]], in cui i guadagni o le perdite di ogni partecipante sono perfettamente bilanciati da quelli degli altri, la teoria dei giochi contemporanea si applica ad una vasta gamma di relazioni comportamentali e indica ormai genericamente la scienza delle decisioni logiche negli esseri umani, negli animali e nei calcolatori.<ref>{{en}} {{Cita|Aumann 1987||Aumann1987}}</ref><ref>[http://www.treccani.it/enciclopedia/teoria-dei-giochi/ ''Teoria dei giochi'']. Enciclopedia Treccani.</ref><ref>{{en}} [http://plato.stanford.edu/entries/game-theory/ ''Game theory'']. Stanford Encyclopedia of Philosophy. Jan 25, 1997</ref>
La teoria dei giochi moderna nasce con l'idea di equilibri in strategie miste per giochi a somma zero a due giocatori e con la corrispondente dimostrazione di esistenza proposta da [[John von Neumann]].<ref name="vonNeumann_1928">{{en}}{{Cita|von Neumann 1928||vonNeumann1928}}</ref> La dimostrazione originale di von Neumann utilizza il [[teorema del punto fisso di Brouwer]] per le mappe continue su [[insieme convesso|insiemi convessi]] compatti; questo metodo di dimostrazione è diventato standard nella teoria dei giochi e in [[economia]] matematica. L'articolo di von Neumann fu seguito dal suo libro del 1944, ''Theory of Games and Economic Behavior'', scritto in collaborazione con [[Oskar Morgenstern]], in cui vengono considerati anche [[gioco cooperativo|giochi cooperativi]] a più giocatori. La seconda edizione di questo libro ha fornito una teoria assiomatica dell'[[Utilità_(economia)|utilità]] attesa, che ha permesso a studiosi di statistica ed economia di modellare ed analizzare i comportamenti decisionali in situazioni di incertezza.<ref name="vonNeumannMorgenster">{{en}} {{Cita|von Neumann e Morgenstern 1944||vonNeumann}}</ref>
La teoria dei giochi è stata sviluppata negli [[anni 1950|anni cinquanta]] da molti studiosi. È stata esplicitamente applicata all'[[evoluzione|evoluzione naturale]] negli [[anni 1970|anni settanta]], sebbene sviluppi simili risalgano già almeno agli [[anni 1930|anni trenta]].<ref>{{en}} {{Cita|Fisher 1930||Fisher}}</ref> La teoria dei giochi è stata riconosciuta come uno strumento importante in molti campi. Alla data del 2014, anno in cui il [[premio Nobel per l'economia]] è stato assegnato al teorico dei giochi [[Jean Tirole]], undici teorici dei giochi hanno vinto un premio Nobel per l'economia.<ref>{{en}} [https://www.nobelprize.org/prizes/lists/all-prizes-in-economic-sciences/ ''All Prizes in Economic Sciences'']. NobelPrize.org.</ref>
[[John Maynard Smith]] è stato insignito del [[Premio Crafoord]] per la sua applicazione della teoria dei giochi all'evoluzione naturale.<ref>{{en}} [https://www.crafoordprize.se/press_release/the-crafoord-prize-1999 ''The Crafoord Prize 1999''].</ref>
== Storia ==
[[File:JohnvonNeumann-LosAlamos.gif|thumb|upright|[[John von Neumann]]]]
[[File:John f nash 20061102 3.jpg|thumb|upright|[[John Nash]]]]
:
Le prime discussioni sulla matematica dei giochi risalgono a ben prima della nascita della moderna teoria matematica dei giochi. [[Girolamo Cardano]] elabora un trattato sui giochi d'azzardo nel ''Liber de ludo aleae'' (''Libro sui giochi d'azzardo''), scritto nel 1564 circa ma pubblicato postumo nel 1663. Negli anni 1650, [[Blaise Pascal|Pascal]] e [[Christiaan Huygens|Huygens]] sviluppano il concetto di [[valore atteso]] ragionando sulla struttura dei giochi d'azzardo, e Huygens pubblica la sua analisi dei giochi d'azzardo nel ''De ratiociniis in ludo aleæ'' (''Sul ragionamento nei giochi d'azzardo'') nel 1657.
Nel 1713, in una lettera attribuita a Charles Waldegrave, un [[giacobitismo|giacobita]], viene analizzato un gioco di carte chiamato ''le Her''.<ref>{{en}}{{Cita pubblicazione |url=http://www.jehps.net/Decembre2007/Bellhouse.pdf |titolo=The Problem of Waldegrave |autore=David R. Bellhouse|rivista=Journal Électronique d'Histoire des Probabilités et de la Statistique|anno=2007 |volume=3 |numero=2}}</ref><ref>{{en}}{{Cita pubblicazione|autore=David R. Bellhouse|titolo=Le Her and Other Problems in Probability Discussed by Bernoulli, Montmort and Waldegrave |rivista=Statistical Science |volume=30 |pp=26-39 |anno=2015 |numero=1 |arxiv=1504.01950 |doi=10.1214/14-STS469}}</ref> In questa lettera, Waldegrave fornisce una soluzione [[minimax]] in [[strategia mista|strategie miste]] per una versione a due giocatori di tale gioco.
Nel 1838, nel suo ''Recherches sur les principes mathématiques de la théorie des richesses'' (''Ricerche sui principi matematici della teoria delle ricchezze''), [[Antoine Augustin Cournot]] considera una situazione di [[duopolio]] e ne presenta una soluzione che corrisponde ad un [[equilibrio di Nash]] del gioco.
Nel 1913 [[Ernst Zermelo]] pubblica ''Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels'' (''Su un'applicazione della teoria degli insiemi alla teoria del gioco degli scacchi''), in cui dimostra che il gioco degli scacchi è "strettamente determinato", cioè che tale gioco ammette un equilibrio strategico.<ref>{{de}}{{Cita|Zermelo 1913||Zermelo}}</ref>
L'espressione "teoria dei giochi" viene usata per la prima volta da [[Émile Borel|Emil Borel]] negli [[Anni 1920|anni venti]]. Borel si occupa nella ''Théorie des jeux'' di giochi a somma zero con due giocatori e cerca di determinare una soluzione poi divenuta nota come concetto di von Neumann di soluzione di un gioco a somma zero.
La nascita della moderna teoria dei giochi può essere fatta coincidere con la pubblicazione dell'articolo ''On the Theory of Games of Strategy'' di [[John von Neumann]] nel 1928,<ref name="vonNeumann_1928" /> in cui von Neumann dimostra l'esistenza di equilibri per giochi a somma zero attraverso il [[teorema del punto fisso di Brouwer]] per mappe continue in insiemi convessi compatti, mettendo a punto un metodo che sarebbe poi diventato standard in teoria dei giochi e in economia matematica. L'articolo di von Neumann fu seguito nel 1944 dal libro ''Theory of Games and Economic Behavior'' di [[John von Neumann]] e [[Oskar Morgenstern]]<ref name="vonNeumannMorgenster" />. La seconda edizione di questo libro fornisce una teoria assiomatica dell'[[Utilità_(economia)|utilità]], una reincarnazione della vecchia teoria dell'utilità di [[Daniel Bernoulli]] in una nuova disciplina. Il fondamentale lavoro di von Neumann e Morgenstern include un metodo per determinare soluzioni mutuamente consistenti per giochi a somma zero con due giocatori.
Nel 1950 appaiono le prime discussioni del [[dilemma del prigioniero]], uno scenario investigato dai matematici Merrill M. Flood e Melvin Dresher nell'ambito delle indagini della [[RAND Corporation]] sulla teoria dei giochi. La RAND intraprendeva questi studi per le loro possibili applicazioni alle strategie nucleari globali.<ref>{{en}}[http://plato.stanford.edu/entries/game-theory/ ''Prisoner's Dilemma'']. Steven Kuhn, Stanford Encyclopedia of Philosophy. 2 Aprile 2019.</ref> Più o meno contemporaneamente, [[John Nash]] elabora un criterio per la mutua consistenza delle strategie dei giocatori, noto come equilibrio di Nash, applicabile ad una gamma di giochi più ampia rispetto al criterio proposto da von Neumann e Morgenstern. Nash dimostra che ogni gioco non-cooperativo finito, con più giocatori, anche non a somma zero, ammette un cosiddetto equilibrio di Nash in strategie miste.
La teoria dei giochi si sviluppa grandemente negli [[anni cinquanta]], durante i quali vengono elaborati i concetti di [[Gioco_cooperativo#Il_nucleo_del_gioco|nucleo]], [[gioco in forma estesa]], [[gioco ripetuto]], e [[valore di Shapley]]. Gli anni cinquanta vedono anche le prime applicazioni della teoria dei giochi alle scienze politiche e alla filosofia.
=== Risultati premiati ===
Undici [[premio Nobel per l'economia|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 [[Università del Sussex|University of Sussex]] per lungo tempo, per il suo contributo in questo campo.
Nel 1965, [[Reinhard Selten]] introduce il concetto di soluzione noto come [[equilibrio perfetto nei sottogiochi]] (''subgame perfect equilibrium''), che raffina ulteriormente il concetto di equilibrio di Nash. Più tardi, Selten introduce anche il concetto di equilibrio "della mano tremolante" (''trembling hand equilibrium''). Nel 1994, Nash, Selten e [[John Harsanyi|Harsanyi]] ricevono il premio Nobel per l'economia per i loro contributi alla teoria dei giochi.
Negli [[anni settanta]], la teoria dei giochi è stata molto applicata in [[biologia]], in gran parte come risultato dei lavori di [[John Maynard Smith]] e del suo concetto di [[strategia evolutivamente stabile|strategie evolutivamente stabili]]. Vengono inoltre introdotti i concetti di [[equilibrio correlato]], [[equilibrio della mano tremolante]], e di [[conoscenza comune]] (''common knowledge'').
Nel 2005, anche i teorici dei giochi [[Thomas Schelling]] e [[Robert Aumann]] ricevono un premio Nobel per l'economia. Schelling si è occupato di modelli che anticipavano la teoria dei giochi evolutiva. Aumann ha introdotto il concetto di [[equilibrio correlato]] e ha sviluppato un'estesa analisi formale dell'assunzione della conoscenza comune e delle sue conseguenze.
Nel 2007, [[Leonid Hurwicz]], [[Eric Maskin]], e [[Roger Myerson]] hanno ricevuto il premio Nobel per l'economia "per aver gettato le basi della teoria del [[progetto di meccanismi]] (''mechanism design'')". I contributi di Myerson includono la nozione di [[equilibrio proprio]], e un importante testo monografico: ''Game Theory, Analysis of Conflict''.<ref>{{en}}{{Cita|Myerson 1991||Myerson}}</ref>. Hurwicz ha introdotto e formalizzato il concetto di "compatibilità con gli incentivi" (''incentive compatibility'').
Nel 2012, [[Alvin E. Roth]] e [[Lloyd Shapley|Lloyd S. Shapley]] hanno ricevuto il premio Nobel per l'economia "per la teoria delle allocazioni stabili e per la pratica della progettazione dei mercati".
Nel 2014, il premio Nobel per l'economia è andato al teorico dei giochi [[Jean Tirole]].
=== In Italia ===
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 e 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<ref>[https://congresos.ugr.es/sing16/about-sing/#about-sing-history ''Breve cronistoria dei convegni italiani di Teoria dei Giochi'']</ref> ed è stato chiuso nel 2005 per avere raggiunto i suoi scopi istituzionali.
== Descrizione ==
=== Premesse ===
Nel modello della teoria dei giochi la premessa indispensabile è che l'obiettivo sia vincere; 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 (teoria dei giochi)|strategia]]". In dipendenza poi delle 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. Tale compenso 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 che risulta ''"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 o valore atteso, che è la media ponderata dei possibili compensi (sia positivi sia negativi), ciascuno moltiplicato (pesato) per le rispettive probabilità di essere assunto (ossia di verificarsi).
=== Descrizione informale dei giochi ===
In un gioco esistono uno o più contendenti che cercano di vincere, ovvero di massimizzare la propria vincita. La vincita è definita da una regola ([[Funzione (matematica)|funzione]]) che stabilisce quantitativamente qual è la vincita dei contendenti in funzione del loro comportamento. Tale funzione è detta "funzione dei pagamenti". Ogni giocatore può intraprendere un numero finito (o infinito, nel caso più astratto possibile) di azioni o decisioni che determinano una strategia. Ogni strategia è caratterizzata da una conseguenza per il giocatore che l'ha adottata e che può essere un premio o una penalità. Il risultato del gioco è completamente determinato infine dalla sequenza delle loro strategie e dalle strategie adottate 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 valore: un valore negativo indicherà un pagamento all'avversario, ossia una penalità; mentre un valore positivo indicherà una vincita, ossia la riscossione di un premio. Il guadagno o la perdita spettante al generico giocatore 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 e da simili situazioni nascono varie tipologie di giochi (ad es.: giochi cooperativi o non-cooperativi).
Uno strumento utile per rappresentare le interazioni tra due giocatori, due imprese o due individui è una [[matrice]] o tabella delle decisioni a doppia entrata. Questa tabella delle decisioni serve a mostrare le strategie e le vincite di un gioco condotto da due giocatori.
La matrice delle decisioni è quindi una rappresentazione attraverso la quale cataloghiamo tutti i possibili risultati delle interazioni fra giocatori e assegniamo il valore della vincita che in ciascuna situazione compete a ciascun giocatore. Altra forma di rappresentazione riguarda la sequenza con la quale ogni decisione viene assunta o le azioni vengono condotte. Questa caratteristica di ogni gioco può essere descritta mediante un [[albero (grafo)|grafo ad albero]], rappresentando ogni possibile combinazione di giocate dei contendenti da uno stato iniziale sino agli stati finali dove vengono ripartite le vincite.
== 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 <math>2^{n}-1</math> 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
<math>V(G_1) + V(G_2) + ...+ V(G_k) < V(R)</math> con k=1,...,<math>2^{n-1}</math> e <math>G_i \cap\ G_j= \emptyset\ </math> 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 <math>V(G_i)</math>. 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 ====
Riga 49 ⟶ 84:
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 <math>R \cap\ G^c</math>, quest'ultima è la coalizione avversa a G essendo <math>G^c</math> l'insieme complementare di G. I giochi a due persone sono tali per cui per ogni coalizione G⊆R si ha
Riga 55 ⟶ 89:
<math>V(G) + V(R \cap\ G^c) = V(R)</math>
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: <math>V(G) + V(R \cap\ G^c)</math>. 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]] verificano 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.
Riga 68 ⟶ 100:
=== 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 se 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.
{{interprogetto|nolik=si|nowikidata=si|preposizione=sui|v=Giochi non cooperativi|v_etichetta=Giochi non cooperativi}}
=== Giochi ripetuti nel tempo ===
{{Vedi anche|Dilemma del prigioniero}}
Alcuni tipi di gioco che portano gli agenti a giocare più di una volta, trasformando i pay off tramite un vincolo intertemporale, pur considerando lo stesso schema di gioco iniziale. Nel caso di giochi ad informazione perfetta essi possono essere ricondotti alla forma normale di Borel, ossia a giochi sprovvisti della dimensione temporale.
Un esempio di questi è il dilemma del prigioniero ripetuto infinite volte.
=== Giochi a informazione perfetta e completa ===
{{Vedi anche|Gioco a informazione completa}}
Esempi di giochi a informazione perfetta:
* [[Scacchi]]
* [[Dama]]
* [[Nim]]
* [[Hex (gioco)|Hex]]
* [[Go (gioco)|Go]]
=== Giochi finiti ===
Giochi in cui il numero delle situazioni di gioco possibili è finito
Esempi:
* [[tris (gioco)|tris]]
* [[
* [[gioco del cento]]
* [[scacchi]]
* [[dama]]
* [[morra cinese]] (o sasso, carta, forbice)
=== Rappresentazione ===
{{...|matematica}}
== Somma ==
Riga 108 ⟶ 145:
=== 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
Esempi a informazione perfetta
* [[scacchi]]
Esempi a informazione imperfetta
Riga 117 ⟶ 154:
* [[poker]]
Un [[gioco di strategia]] viene descritto da Von Neumann come un certo numero di scelte ed eventi ognuno dei quali determina un numero finito di risultati diversi. Gli eventi sono fortuiti, ossia sono frutto del caso e come tale nessun individuo è in grado di determinarne il risultato o meglio di influenzarne l’esito. Al più gli individui conoscono le probabilità con le quali i diversi risultati appaiono. Le scelte invece dipendono dal [[libero arbitrio]] degli individui, ossia dalle decisioni prese liberamente dai giocatori. La teoria dei giochi si concentra sull'effetto che la scelta di ogni giocatore ha su tutti gli altri, ossia esamina l’effetto congiunto originato da scelte individuali laddove la ratio dietro ogni scelta è la ricerca del proprio vantaggio. Il destino di ogni giocatore appare così dipendere non solo dalle proprie scelte/azioni, ma influenza ed è influenzato dalle azioni degli altri individui allorquando tutti i giocatori sono guidati nel proprio agire unicamente dall'interesse personale. Von Neumann inoltre ritiene inaccettabile ipotizzare che un giocatore, prima di compiere la propria scelta, possa conoscere le scelte dei restanti giocatori ed il risultato dell’evento casuale.
Al momento di prendere la decisione il giocatore non può prevedere o dire quali saranno le sue scelte nel corso del gioco in corrispondenza delle scelte prese dagli altri giocatori; se così fosse tale eventualità implicherebbe una restrizione al suo stesso libero arbitrio. Un giocatore infatti che conoscesse in anticipo le mosse degli altri, nel momento in cui dovesse effettuare la propria scelta, questa risulterebbe condizionata dalle scelte compiute dagli altri ed in ultima analisi dunque il giocatore non potrebbe fare altro che subire passivamente le scelte dei restanti giocatori e del caso. Ecco dunque motivata la ragione per cui si ipotizza che le scelte dei giocatori vengano prese simultaneamente.
Il numero di eventi che dipendono dal caso sia in numero <math> l=1,2,..., m </math>; indicato con il numero <math> M_l </math> il numero di esiti possibili per ciascun evento, la probabilità associata a ciascun risultato originato dall'evento casuale l-esimo è <math> \alpha_{l,1},\alpha_{l,2},...,\alpha _{l, M_l} </math>
con <math> l=1,2,..., m </math> ed è tale che <math>\alpha_{l,1}+...+\alpha_{l, M_l} = 1</math> con <math>\alpha_{l,k}\ge0</math> per ogni <math> k=1,2,..., M_l </math>.
I risultati che possono verificarsi sono in numero finito <math> M </math>: tale numero costituisce tutte le combinazioni possibili degli <math>M_l</math> eventi ed è pari a
: <math> M = \prod_{l=1}^{m} M_{l} </math>
in accordo alla regola fondamentale del [[calcolo combinatorio]].
Indicato con <math> \alpha_{1},\alpha_{2},...,\alpha_{M} </math> la probabilità con cui gli <math> M </math> risultati casuali si realizzano, Von Neumann semplifica la descrizione dei giochi riconduce l’azione degli <math> M </math> eventi separati casuali ad un singolo evento aleatorio <math> y </math> semplicemente combinando gli <math> M </math> eventi in accordo alla [[Teoria della probabilità|teoria delle probabilità]] e del calcolo combinatorio.
Considerando un unico evento dipendente dal caso ed indicato con <math> y </math> il suo risultato tra gli <math> M </math> possibili, se i giocatori sono in numero n>1 e ciascuno dispone di <math> 1,2,..., N_i </math> scelte con <math> i=1,2,..., n </math> ed indicato con <math> s_{1},s_{2},..., s_{n} </math> la scelta di ogni giocatore i-esimo, allora il giocatore i-esimo ottiene dagli altri <math> n-1 </math> giocatori un certo ammontare (pagamento) che può essere descritto da una funzione a valori reali di <math> n+1 </math> variabili
: <math> f_{i}\left(y,s_{1},s_{2},..., s_{n}\right)</math>
La dipendenza funzionale dalle <math> n+1 </math> variabili esprime dunque sia la reciproca dipendenza dalle scelte compiute dagli <math> n </math> giocatori che dell’effetto casuale <math>y</math>.
Considerati coralmente gli <math> n </math> giocatori percepiscono all’unisono il seguente risultato:
: <math> f_{1}\left(y,s_{1},s_{2},..., s_{n}\right) + f_{2}\left(y,s_{1},s_{2},..., s_{n}\right) + ... + f_{n}\left(y,s_{1},s_{2},..., s_{n}\right)</math> ≡ <math>0</math>
L’equazione a fondamento dei giochi a somma zero è la seguente identità
: <math>f_{1} + f_{2} + ... + f_{n}</math> ≡ <math>0</math>
che viene assunta da Von Neumann valere per qualsiasi <math>y,s_{1},s_{2},..., s_{n}</math>.
La sua validità esprime la circostanza che i giocatori effettuano dei pagamenti l’uno all’altro, ma come collettivo non guadagnano né perdono nulla. Ciò che avviene non è né creazione né distruzione di ricchezza, ma una sua semplice ridistribuzione tra gli <math> n </math> giocatori a seguito delle loro scelte e di un’azione casuale (invisibile) <math>y</math> che determinano il pagamento che ogni giocatore fa all’altro.
Si osservi che nessun giocatore è in grado di stabilire in anticipo il valore di <math> f_{i} </math> in quanto il suo valore dipende dalle <math> n+1 </math> variabili <math> y,s_{1},s_{2},..., s_{n} </math> di cui una sola, la <math> s_{i}</math>, è determinata dal giocatore i-esimo: le restanti variabili dipendono dalla scelta dei restanti <math>n-1</math> giocatori e dal risultato casuale <math>y</math>. In sintesi ogni giocatore effettua la propria scelta senza conoscere la scelta effettuata dagli altri partecipanti o dall’azione del caso o come si dice adottano le proprie decisioni simultaneamente. Von Neumann ricorrendo al concetto probabilistico di valore atteso è in grado di “eliminare” dalla struttura del gioco la nozione di evento aleatorio: se <math> M </math> risultati casuali <math> y_{1},y_{2},..., y_{M} </math> accadono ciascuno con probabilità <math> \alpha_{1},\alpha_{2},...,\alpha_{M} </math> e sono stabilite le <math>n</math> scelte <math> s_{1},s_{2},..., s_{n} </math> dei giocatori allora il valore atteso del risultato per il giocatore generico <math> i </math> risulta essere
: <math> g_{i}\left(s_{1},s_{2},..., s_{n}\right) = \alpha_{1}\cdot f_{i}\left(y_{1},s_{1},s_{2},..., s_{n}\right) + ... + \alpha_{M} \cdot f_{i}\left(y_{M},s_{1},s_{2},..., s_{n}\right)</math>
Poiché <math> f_{1} + f_{2} + ... + f_{n} </math> ≡ <math>0</math> implica <math> g_{1} + g_{2} + ... + g_{n}</math> ≡ <math>0</math> allora restringersi a considerare solo le scelte <math> s_{1},s_{2},..., s_{n} </math> degli <math> n </math> giocatori non altera la struttura del gioco che continua ad essere a somma zero.
==== Giochi a due persone, n=2 ====
Per definizione di gioco a somma zero è
:<math> g_{1}\left(s_{1},s_{2}\right) + g_{2}\left(s_{1},s_{2}\right)</math> ≡ <math>0</math>
dove <math> s_{1} </math> indica la scelta del giocatore 1 e <math> s_{2} </math> la scelta del giocatore 2.
Il giocatore 1 dispone di <math> i=1,2, ..., m </math> scelte chiamate strategie, il giocatore 2 di <math> j=1,2, ..., n </math> scelte anch’esse denominate strategie. Se si indica la funzione dei pagamenti per il giocatore 1 con
:<math> g\left( i,j \right) </math> ≡ <math> g_{1}\left( i,j \right) </math>
la funzione dei pagamenti per il giocatore 2 risulta essere
:<math> g_{2}\left( i,j \right) </math> ≡ <math> - g\left( i,j \right) </math>
pertanto un gioco a due persone a somma zero caratterizza un gioco in cui gli esiti per i due giocatori sono opposti: la perdita per uno corrisponde esattamente al guadagno per l’altro. Von Nuemann immagina che entrambi i giocatori agiscano unicamente in base ai propri interessi personali: il giocatore 1 e 2 perseguono l’obiettivo di massimizzare il proprio guadagno. Il giocatore cerca di massimizzare <math> g_{1}\left( i,j \right) </math>, mentre il giocatore 2 cerca di massimizzare <math> g_{2}\left( i,j \right) </math> e, dal momento che
:<math> max_j g_2 \left( i,j \right) = max_j \left[ - g \left( i,j \right) \right] = min_j g \left( i,j \right) </math>,
il giocatore 2 cerca di minimizzare <math> g\left( i,j \right) </math> in riferimento alla funzione dei pagamenti dell’avversario.
Il giocatore massimizzante 1 effettua una scelta <math>\tilde i</math> e la sua perdita o il suo guadagno dipenderanno dalla scelta <math>j</math> dell’avversario: in ogni caso può essere certo che
:<math> g \left( \tilde i ,j \right) \ge min_j g \left( \tilde i ,j \right) </math>
per qualsiasi scelta <math>j</math> effettuata dal giocatore avverso.
Il giocatore 1 se sceglie opportunamente <math>i</math>, può essere certo del risultato seguente
:<math> max_i g \left( i ,j \right) = g \left( \tilde i ,j \right) \ge max_i min_j g \left( i ,j \right) </math>
indipendentemente dalla scelta compiuta dal giocatore 2.
Il giocatore minimizzante 2 ragionando in modo analogo conclude che se sceglie opportunamente <math>j</math>, può essere certo del risultato seguente
:<math> min_j g \left( i ,j \right) = g \left(i , \tilde j \right) \le min_j max_i g \left( i ,j \right) </math>
indipendentemente dalla scelta del giocatore 1.
Dalla definizione di minimo si ha
:<math> min_j g \left( i ,j \right) \le g \left( i ,j \right) </math> per ogni <math>i,j</math>
da cui si deduce che
:<math> max_i min_j g \left( i ,j \right) \le max_i g \left( i ,j \right) </math>
Scelto <math>i=\tilde i</math> tale che <math> max_i g \left( i ,j \right) = g \left( \tilde i ,j \right) </math> si può scrivere
:<math> max_i min_j g \left( i ,j \right) = min_j g \left( \tilde i ,j \right) \le g \left( \tilde i , j \right) </math> per <math>j</math> qualsiasi.
In particolare scelto <math>j=\tilde j</math> risulta
:<math> max_i min_j g \left( i ,j \right) \le g \left( \tilde i , \tilde j \right) </math>
Dalla definizione di massimo si ha
:<math> max_i g \left( i ,j \right) \ge g \left( i ,j \right) </math> per ogni <math>i,j</math>
da cui si deduce che
:<math> min_j max_i g \left( i ,j \right) \ge min_j g \left( i ,j \right) </math>
Scelto <math>j=\tilde j</math> tale che <math> min_j g \left( i ,j \right) = g \left(i , \tilde j \right) </math> si può scrivere
:<math> min_j max_i g \left( i ,j \right) = max_i g \left(i, \tilde j \right) \ge g \left(i, \tilde j \right) </math> per <math>i</math> qualsiasi.
In particolare scelto <math>i=\tilde i</math> risulta
:<math> min_j max_i g \left( i ,j \right) \ge g \left( \tilde i, \tilde j \right) </math>
Per confronto si conclude che
:<math> max_i min_j g \left( i ,j \right) \le g \left( \tilde i , \tilde j \right) \le min_j max_i g \left( i ,j \right) </math>
Tutte le volte che vige la diseguaglianza appena scritta i due giocatori non sono certi di conseguire un risultato che costituisca il migliore risultato per sé stessi. Von Neumann conclude così che è impossibile per ognuno dei due giocatori agire in modo più intelligente dell’avversario in quanto l’esito del gioco risulta per entrambi imprevedibile.
Nei giochi invece per cui si abbia
:<math> max_i min_j g \left( i ,j \right) = min_j max_i g \left( i ,j \right) </math>
il giocatore massimizzante 1 ed il giocatore minimizzante 2 conseguono il comune valore <math> v = g \left( \tilde i , \tilde j \right) </math>. L’esito del gioco risulta quindi essere determinato dal momento che il criterio del massimo adottato dal giocatore 1 ed il criterio del minimo adottato dal giocatore 2 conducono ad un risultato comune che viene ritenuto razionale da entrambi i giocatori. Il giocatore massimizzante sceglie <math>i=\tilde i</math> in modo tale che
<math> max_i g \left( i , \tilde j \right) = g \left( \tilde i , \tilde j \right) </math>, il giocatore minimizzante sceglie <math>j=\tilde j</math> tale che <math> min_j g \left( \tilde i , j \right) = g \left( \tilde i , \tilde j \right) </math>.
L’eguaglianza <math> max_i min_j g \left( i ,j \right) = min_j max_i g \left( i ,j \right) = v </math> implica che il giocatore 1 scegliendo <math>\tilde i</math> percepirà la vincita
:<math> v = g \left( \tilde i , \tilde j \right) </math> ≡ <math> g_{1}\left( \tilde i , \tilde j \right) </math>,
laddove il giocatore 2 scegliendo <math>\tilde j</math> dovrà pagare la somma
:<math> g_{2}\left( \tilde i , \tilde j \right) </math> ≡ <math> - g \left( \tilde i , \tilde j \right) = -v </math>.
In sintesi se vige l’eguaglianza, i giocatori, adottando la scelta ritenuta più razionale, fanno sì che l’esito del gioco sia determinato: qualora ripetano il gioco moltissime volte il risultato del gioco è e sarà sempre lo stesso indipendentemente da chi tra i due giocatori sia il miglior psicologo o stratega. Allorquando il gioco venga ripetuto diverse volte risulta chiara la ragione per cui un giocatore non voglia compiere sempre la medesima scelta: il giocatore avverso infatti potrebbe accorgersi e avvantaggiarsi del fatto che l’avversario effettui sempre la medesima scelta. In una lunga sequenza di giochi ripetuti un giocatore pertanto desidererà giocare irregolarmente, ossia compiere diverse scelte con diverse frequenze (probabilità). Von Neumann con il proposito di matematizzare questo modo di giocare introduce il concetto di strategia mista, ossia una ''strategia statistica'' che consiste nel mischiare i diversi modi di giocare selezionando le strategie con assegnate probabilità scelte dal giocatore. Sebbene il caso sia stato oscurato nei giochi mediante l’introduzione della nozione di valor atteso nell’esito delle decisioni, la dipendenza dei giochi dal caso riappare invero nelle vesti di strategia mista, ossia nel modo con cui i giocatori si affidano al caso per selezionare la propria scelta e nel mettersi così al riparo dall'eventualità che la propria strategia venga scoperta dall'avversario. Il giocatore 1 non sceglie più uno dei numeri <math> i=1,2, ..., m </math>, piuttosto specifica <math> m </math> probabilità <math> p_{1}, p_{2}, ..., p_{m} </math> tali che <math> p_{1} + p_{2} + ... + p_{m} =1 </math>, successivamente estrae da un’urna contenente i numeri <math> i=1,2, ..., m </math> con le probabilità associate ed appena specificate ed adotta come scelta il numero effettivamente estratto. Altrettanto fa l’altro giocatore associando a ciascuna scelta una probabilità: <math> q_{1}, q_{2}, ..., q_{n} </math>.
Il valore atteso per il giocatore 1 risulta dunque essere
:<math> h_{1} \left( \mathbf p , \mathbf q \right) = \sum_{i=1}^m \sum_{j=1}^n g_1 \left( i,j \right) p_{i} \cdot q_{j} </math>
ed il valore atteso per il giocatore 2 è
:<math> - h_{1} \left( \mathbf p , \mathbf q \right) </math>.
Naturalmente, nessuno proibisce ad un giocatore di compiere una scelta ben determinata, ossia di indirizzarsi verso una specifica strategia <math> k </math> escludendo tutte le altre. In tale circostanza il giocatore porrà pari a 1 la probabilità di tale scelta <math> p_{k} = 1 </math> e pari a 0 la probabilità di scelta di tutte le restanti <math> m-1 </math>. Una simile circostanza si rappresenta con vettori del tipo
:<math> s_k = \left( 0, ..., 1, ..., 0 \right) </math>
che vengono appellati come strategie pure. La libertà di scelta in mano ai giocatori risiede dunque nella possibilità di affidarsi o meno al caso per prendere decisioni. Il [[teorema del minimax]] garantisce che in tutti i giochi a due persone per la forma bilineare <math> h \left( \mathbf p , \mathbf q \right) </math> esiste sempre un punto di equilibrio costituito da strategie miste:
: <math>\max_{ \mathbf p}\min_{\mathbf q} h(\mathbf p ,\mathbf q)=v^*=\min_{\mathbf q}\max_{\mathbf p} h(\mathbf p,\mathbf q)</math>
i due giocatori dispongono così di strategie miste che li proteggono completamente dall'eventualità che la loro strategia venga scoperta dall'avversario; si osservi che non tutte le strategie miste <math> \mathbf p, \mathbf q </math> ottimali sono pure <math> \mathbf s </math> e per queste ultime in generale vale
:<math> \max_{ \mathbf s_{1}}\min_{\mathbf s_{2}} h \left( \mathbf s_{1} , \mathbf s_{2} \right) \le \min_{ \mathbf s_{2}}\max_{\mathbf s_{2}} h \left( \mathbf s_{1} , \mathbf s_{2} \right) </math>
Un gioco a somma zero in forma normale a due giocatori si esprime come:
<math>g_1\left(s_{1,i}, s_{2,j}\right)</math> + <math>g_2\left(s_{1,i}, s_{2,j}\right)</math> ≡ 0 ∀ <math>s_{1,i}</math> ∈ <math>S_1</math> ∧ ∀ <math>s_{2,j}</math> ∈ <math>S_2</math> dove <math>S_1=\left\{s_{1,1},..., s_{1,m}\right\}</math> e <math>S_2=\left\{s_{2,1},..., s_{2,n}\right\}</math>
Se il gioco è finito, le
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 <math>s_{k,i}</math> ∈ <math>S_k</math> senza conoscere la scelta dell'altro.
Riga 130 ⟶ 250:
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
Il desiderio del giocatore 2 sarà pertanto di minimizzare il pagamento dovuto al giocatore 1, ovvero il giocatore 2 volendo massimizzare <math>A_2</math> = - <math>A</math> cercherà di minimizzare <math>A</math>.
Il desiderio del giocatore 1 sarà invece di massimizzare il pagamento ricevuto dal giocatore 2, ovvero il giocatore 1 volendo massimizzare <math>A_1</math> = <math>A</math> cercherà di massimizzare <math>A</math>. In sostanza il comportamento dei due giocatori è
A questo punto
Il giocatore 1 cerca di massimizzare <math>A</math>, ma il suo controllo è limitato solo alla scelta di una riga. Idem per il giocatore 2 che cerca di minimizzare <math>A</math>:
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
<math>max_i \left(min_j
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
<math>min_j \left(max_i a_{i,j} \right)</math>
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 <math>s_1^e</math>, <math>s_2^e</math>
1)
2)
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 <math>s_1^e</math>, <math>s_2^e</math> rappresenta ovvero la convergenza degli interessi dei due avversari e pertanto si è soliti riferirsi alle strategie di equilibrio come alle strategie ottimali.
Riga 161 ⟶ 280:
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
<math>max_i \left[ min_j
J. von Neumann agli arbori della sua ricerca si era promesso di determinare se per un gioco qualsiasi esistesse una strategia/decisione migliore in riferimento ad un criterio di ottimalità prefissato. Nell'articolo "Communication on the Borel notes"<ref>{{Cita libro|autore = John von Neumann|titolo = Communication on the Borel notes|anno = 1953|editore = Econometrica - Vol. 21|città = |pp = 124-125|ISBN = }}</ref> J. von Neumann riconobbe ad Emile Borel il merito di essere stato il primo autore ad aver introdotto il principio di scelta del maximin ed a sviluppare il concetto di strategia sia pura che mista; tuttavia nello stesso articolo J. von Neumann fece osservare che il matematico francese analizzò solo il caso dei giochi simmetrici a due persone e che la rilevanza del principio di scelta del maximin ebbe impatto limitato in quanto nel 1921 E. Borel pensò che il “[[minimax|teorema del minimax]]” fosse falso o possibilmente falso per un numero elevato di giocatori, maggiore di sette.
Dunque senza il [[teorema del minimax]] non ci sarebbe la teoria dei giochi come oggi è conosciuta.
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 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: <math>g_1</math> = <math> g</math> e <math> g_2</math> = <math> -g</math>.
Diviene allora lecito scrivere:
<math>
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:
<math>-
ovvero
<math>
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 <math>z^*</math> dei due problemi corrisponde al valore del gioco V*.
Sia
Riga 184 ⟶ 305:
la matrice dei pagamenti rappresentativa di un gioco a somma zero a due giocatori: <math>A_1+A_2=0</math> avendo indicato con <math>A=A_1</math>
Per il giocatore massimizzante si ha il seguente problema primale:
<math>z^*= max
soggetta ai vincoli:
:<math> \left\{ \begin{array}{l}
\begin{matrix} \sum_{i=1}^m s_{1,i}a_{i,j} \end{matrix} \begin{matrix} \sum_{i=1}^m s_{1,i} \end{matrix} = 1 \\
s_{1,i} \ge 0 \forall i=1,...,m \\
\end{array} \right.</math>
Per il giocatore minimizzante (problema duale) si ha:
<math>z^*= min
soggetta ai vincoli:
:<math> \left\{ \begin{array}{l}
\begin{matrix} \sum_{j=1}^n s_{2,j}a_{i,j} \end{matrix} \begin{matrix} \sum_{j=1}^n s_{2,j} \end{matrix} = 1 \\
s_{2,j} \ge 0 \forall j=1,...,n \\
\end{array} \right.</math>
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 <math>v</math> (non superiore a <math>v</math>).
* Il vincolo che pone uguale ad 1 la somma delle strategie fa sì che la somma delle probabilità delle strategie sia pari a 1 in quanto si riferiscono ad alternative disgiunte ed esaustive.
* Le m strategie pure <math>s_{1,i}</math> del giocatore 1 e le n strategie pure del giocatore 2 <math>s_{2,i}</math> si esprimono come variabili booleane nelle componenti.
==== Giochi a tre o più persone, n>2 ====
I giochi a più di 2 giocatori presentano una natura diversa dai giochi a due giocatori dove si ha una pura opposizione negli interessi dei due giocatori; nei giochi a tre persone può invece emergere la cooperazione tra i partecipanti. La scelta di un giocatore infatti potrebbe essere svantaggiosa per entrambi gli altri due giocatori, ma potrebbe anche risultare vantaggiosa per uno e svantaggiosa per l’altro. La possibilità di un “parallelismo” nelle scelte conduce alla formazione di coalizioni o alleanze.
=== Giochi a somma non zero ===
Riga 224 ⟶ 345:
* [[gioco del pollo]]
* [[dilemma del viaggiatore]]
*[[Il gioco del coniglio|gioco del coniglio]]
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 [[economia|economico]] e [[finanza|finanziario]] a quello [[Strategia militare|strategico-militare]], dalla [[politica]] alla [[sociologia]], dalla [[logica]] alla [[scienza dei sistemi]], dalla [[psicologia]] all'[[informatica]], dalla [[biologia]] allo [[sport]], introducendo l'azione del caso, connessa
*uguali
* comuni, ma non identici
* differenti
Riga 240 ⟶ 362:
Ecco alcuni esempi di situazioni che possono essere analizzate utilizzando la teoria dei giochi.
Se il giocatore è un
Un altro esempio di situazioni conflittuali è il celebre [[dilemma del prigioniero]].
Riga 248 ⟶ 370:
== Bibliografia ==
=== Manuali in italiano ===
* {{Cita libro|cid=GibbonsIT|autore=Robert Gibbons|titolo=Teoria dei giochi|editore=Il Mulino|anno=2005|ISBN=8815108238}}
* {{Cita libro|cid=Colombo|autore=Ferdinando Colombo|titolo=Introduzione alla teoria dei giochi|editore=Carocci|anno=2003|ISBN= 8843027980}}
=== Testi di riferimento correnti ===
* {{Cita libro|cid=Myerson|autore=Roger B. Myerson|wkautore=Roger Myerson|titolo=Game Theory, Analysis of Conflict|editore=Harvard University Press|anno=1991|ISBN=0-674-34116-3|url=http://www.ru.ac.bd/wp-content/uploads/sites/25/2019/03/405_06_Myerson_Game-Theory_-Analysis-of-Conflict-Harvard-University-Press-1997.pdf|accesso=11 Luglio 2021|dataarchivio=11 luglio 2021|urlarchivio=https://web.archive.org/web/20210711090038/http://www.ru.ac.bd/wp-content/uploads/sites/25/2019/03/405_06_Myerson_Game-Theory_-Analysis-of-Conflict-Harvard-University-Press-1997.pdf|urlmorto=sì}}
* {{Cita libro|cid=Fudenberg|autore=Drew Fudenberg
* {{Cita libro|cid=Binmore|autore=Ken Binmore
* {{Cita libro|cid=Osborne|autore=Martin Osborne|autore2=Ariel Rubinstein|titolo=A Course in Game Theory|url=https://archive.org/details/courseingametheo0000osbo|editore=MIT Press|anno=1994|ISBN=0-262-65040-1}}
* {{Cita libro|cid=Gibbons|autore=Robert Gibbons|titolo=Game Theory for Applied Economists|url=https://archive.org/details/nlsiu.330.01.gib.22059|editore=Princeton University Press|anno=1992|ISBN=0-691-00395-5}}
* {{Cita libro|cid=Morris|autore=Peter Morris|anno=1994|titolo=Introduction to the Theory of Games|editore=Springer|ISBN=3-540-94284-X}}
* {{Cita libro|cid=Gintis|autore=Herbert Gintis|anno=2000|titolo=Game Theory Evolving|url=https://archive.org/details/gametheoryevolvi0000gint|editore=Princeton University Press|ISBN=0-691-00943-0}}
* {{Cita libro|cid=Owen|autore=Guillermo Owen|titolo=Game Theory|edizione=3|annooriginale=1968|editore=Academic Press|città=New York|anno=1995}}
* {{Cita libro|cid=Dutta|autore=Prajit K. Dutta|titolo=Strategies and Games: Theory and Practice|url=https://archive.org/details/strategiesgamest0000dutt|editore=MIT Press|anno=1999}}
=== Testi di importanza storica ===
* {{Cita conferenza|cid=Zermelo|autore=Ernst Zermelo | titolo=Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels | conferenza=Proceedings of the Fifth International Congress of Mathematicians |url=https://archive.org/details/proceedingsfifth00hobs_774/page/n502/mode/1up|lingua=de|anno=1913|volume=2|pp=501-504}}
* {{Cita pubblicazione|cid=vonNeumann1928|autore=John von Neumann|wkautore=John von Neumann|titolo=Zur Theorie der Gesellschaftsspiele|url=https://archive.org/details/sim_mathematische-annalen_1928_100/page/295|rivista= Mathematische Annalen|volume=100|anno=1928|pp=295-320|doi=10.1007/BF01448847|lingua=de}}
* {{Cita libro|cid=Fisher|autore=Ronald Fisher|wkautore=Ronald Fisher|titolo=The Genetical Theory of Natural Selection|editore=Oxford Clarendon Press|anno=1930|url=https://archive.org/details/geneticaltheoryo031631mbp/page/n12/mode/1up}}
* {{Cita libro|cid=vonNeumann|autore=John von Neumann|wkautore=John von Neumann|autore2=Oskar Morgenstern|wkautore2=Oskar Morgenstern|titolo=Theory of Games and Economic Behavior|editore=Princeton University Press|edizione=3|anno=1953|annooriginale=1944|url=https://archive.org/details/in.ernet.dli.2015.215284}}
* {{Cita pubblicazione|cid=Nash1950a|autore=John Forbes Nash|wkautore=John Forbes Nash|titolo=Equilibrium points in n-person games|rivista= Proceedings of the National Academy of the USA|volume=36|numero=1|anno=1950|pp=48-49|doi=10.1073/pnas.36.1.48|url=https://www.pnas.org/content/pnas/36/1/48.full.pdf|accesso=10 Luglio 2021}}
* {{Cita pubblicazione|cid=Nash1950b|autore=John Forbes Nash|wkautore=John Forbes Nash|titolo=The bargaining problem|rivista=Econometrica|volume=18|anno=1950|pp=155-162|url=http://www.rasmusen.org/GI/reader/12a.nash.bargaining.1950.pdf|accesso=10 Luglio 2021}}
* {{Cita pubblicazione|cid=Nash1951|autore=John Forbes Nash|wkautore=John Forbes Nash|titolo=Non-cooperative games|rivista= Annals of Mathematics|volume=54|anno=1951|pp=289-295|url=http://lcm.csa.iisc.ernet.in/gametheory/Classics/NCG.pdf|accesso=10 Luglio 2021}}
* {{Cita pubblicazione|cid=Shapley1953a|autore=Lloyd Shapley|wkautore=Lloyd Stowell Shapley|titolo=Stochastic games|rivista= Proceedings of the National Academy of Sciences of the USA|volume=39|anno=1953|pp=1095-1100|doi=10.1073/pnas.39.10.1095|url=https://www.pnas.org/content/pnas/39/10/1095.full.pdf|accesso=10 Luglio 2021}}
* {{Cita pubblicazione|cid=Shapley1953b|autore=Lloyd Shapley|wkautore=Lloyd Stowell Shapley|titolo=A value for n-person games|rivista=Contributions to the theory of games|curatore=W. Harold Kuhn|curatore2=Albert W. Tucker|editore=Princeton University Press|anno=1953|pp=307-317|url=http://library.fa.ru/files/Roth2.pdf#page=39|accesso=10 Luglio 2021}}
* {{Cita libro|cid=Luce|autore=Duncan Luce|autore2=Howard Raiffa|titolo=Games and Decisions|editore=Dover|anno=1957|ISBN=0-486-65943-7|url=http://index-of.es/Varios-2/Games%20and%20Decisions.pdf|accesso=10 Luglio 2021|dataarchivio=14 giugno 2021|urlarchivio=https://web.archive.org/web/20210614045225/http://index-of.es/Varios-2/Games%20and%20Decisions.pdf|urlmorto=sì}}
* {{Cita pubblicazione|autore=David Schmeidler|titolo=The nucleolus of a characteristic function game|rivista=SIAM Journal of Applied Mathematics|volume=17|anno=1969|pp=1163-1170|doi=10.1137/0117107}}
* {{Cita pubblicazione|autore=John C. Harsanyi|wkautore=John Harsanyi|titolo=Games with incomplete information played by "Bayesian" players, I-III|rivista=Management Science|volume=14|anno=1967|pp=159-182|url=http://www.dklevine.com/archive/refs41175.pdf|accesso=10 Luglio 2021|doi=10.1287/mnsc.14.3.159}}
* {{Cita pubblicazione|autore=Robert J. Aumann|wkautore=Robert Aumann|titolo=Subjectivity and correlation in randomized strategies|rivista=Journal of Mathematical Economics|volume=1|anno=1974|pp=67-96|url=http://dklevine.com/archive/refs4389.pdf|accesso=10 Luglio 2021|doi=10.1016/0304-4068(74)90037-8}}
* {{Cita libro|autore=John Maynard Smith|wkautore=John Maynard Smith|titolo=Evolution and the Theory of Games|url=https://archive.org/details/evolutiontheoryo0000mayn|editore=Cambridge University Press|anno=1982}}
* {{Cita pubblicazione|autore=Ariel Rubinstein|titolo=A perfect equilibrium in a bargaining model|rivista= Econometrica|volume=50|anno=1982|pp=97-109|url=https://arielrubinstein.tau.ac.il/papers/11.pdf|accesso=10 Luglio 2021}}
* {{Cita pubblicazione|autore=Abraham Neyman|titolo=Bounded complexity justifies cooperation in the finitely repeated prisoner's dilemma|url=https://archive.org/details/sim_economics-letters_1985_18_2-3/page/227|rivista=Economics Letters|volume=19|anno=1985|pp=227-230|doi=10.1016/0165-1765(85)90026-6}}
* {{Cita pubblicazione|autore=Ariel Rubinstein|titolo=Finite automata play the repeated prisoner's dilemma|rivista=Journal of Economic Theory|volume=39|anno=1986|pp=83-96|url=https://arielrubinstein.tau.ac.il/papers/21.pdf|accesso=10 Luglio 2021|doi=10.1016/0022-0531(86)90021-9}}
* {{Cita pubblicazione|cid=Aumann1987|autore=Robert J. Aumann|wkautore=Robert Aumann|titolo=Game Theory|rivista=The New Palgrave: A Dictionary of Economics|curatore=John Eatwell|curatore2=Murray Milgate|curatore3=Peter Newmann|editore=MacMillan|città=Londra|anno=1987|pp=460-482|doi=10.1057/978-1-349-95121-5_942-2}}
== Voci correlate ==
* [[
* [[
* [[Equilibrio di Nash]]
* [[John Nash]]
* [[John von Neumann]]
* [[Lloyd Stowell Shapley]]
* [[
* [[Oskar Morgenstern]]
* [[Ottimizzazione (matematica)]]
* [[Ricerca operativa]]
* [[Teoria delle aste]]
* [[Tit for tat]]
* [[
== Altri progetti ==
{{interprogetto|preposizione=sulla}}
== Collegamenti esterni ==
* {{Collegamenti esterni}}
* [http://www.fioravante.patrone.name/mat/TdG/DRI/ Decisori (razionali) interagenti] appunti, videolezioni, software on line, link di teoria dei giochi, a cura di Fioravante Patrone
* [http://www.galenotech.org/strategie.htm Teoria dei giochi] breve introduzione a cura di Marcello Guidotti
* [http://www.socialcapitalgateway.org/ita-gametheory.htm Social Capital Gateway] siti web in inglese su teoria dei giochi e interazioni sociali, a cura di Fabio Sabatini
*
* {{en}} [http://www.gametheory.net/ Risorse di teoria dei giochi] a cura di Mike Shor
{{Teoria dei giochi}}
{{Controllo di autorità}}
{{Portale|matematica}}
[[Categoria:Teoria dei giochi| ]]
| |||