Teoria jocului

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Teoria jocurilor este o disciplină care studiază modele matematice ale interacțiunii strategice între agenții raționali . [1] Teoria jocurilor are aplicații în diverse domenii ale științelor sociale, precum și în logică , teoria sistemelor și informatică . Deși se concentra inițial pe jocuri cu sumă zero , în care câștigurile sau pierderile fiecărui participant sunt perfect echilibrate cu cele ale celorlalți, teoria jocurilor contemporane se aplică unei game largi de relații comportamentale și indică acum generic știința. Deciziilor logice la oameni, animale , și calculatoare. [2] [3] [4]

Teoria modernă a jocurilor s-a născut cu ideea de echilibru în strategii mixte pentru jocuri cu doi jucători cu sumă zero și cu dovada corespunzătoare a existenței propusă de John von Neumann . [5] Dovada originală a lui Von Neumann folosește teorema punctului fix al lui Brouwer pentru hărți continue pe seturi convexe compacte; această metodă de probă a devenit standard în teoria jocurilor și economia matematică. Articolul lui Von Neumann a fost urmat de cartea sa din 1944, Teoria jocurilor și comportamentul economic , scrisă în colaborare cu Oskar Morgenstern , în care sunt luate în considerare și jocurile cooperative multiplayer. A doua ediție a acestei cărți a furnizat o teorie axiomatică a utilității așteptate, care a permis statisticienilor și economiștilor să modeleze și să analizeze comportamentele decizionale în situații de incertitudine. [6]

Teoria jocurilor a fost dezvoltată în anii 1950 de mulți cercetători. A fost aplicată în mod explicit evoluției naturale în anii 1970 , deși evoluții similare datează cel puțin din anii 1930 . [7] Teoria jocurilor a fost recunoscută ca un instrument important în multe domenii. Începând cu 2014, când Premiul Nobel pentru economie a fost acordat teoreticianului de joc Jean Tirole , unsprezece teoreticieni de joc au câștigat un premiu Nobel pentru economie. [8] John Maynard Smith a primit Premiul Crafoord pentru aplicarea teoriei jocurilor la evoluția naturală. [9]

Istorie

Cele mai vechi discuții despre matematica jocului datează cu mult înainte de nașterea teoriei moderne a jocului matematic. Girolamo Cardano elaborează un tratat despre jocuri de noroc în Liber de ludo aleae ( Carte despre jocurile de noroc ), scris în jurul anului 1564, dar publicat postum în 1663. În anii 1650, Pascal și Huygens au dezvoltat conceptul valorii așteptate prin argumentarea jocurilor de structură ale jocurilor de noroc. hazard, iar Huygens și-a publicat analiza jocurilor de noroc în De ratiociniis in ludo aleæ ( Despre raționamentul în jocurile de noroc ) în 1657.

În 1713, într-o scrisoare atribuită lui Charles Waldegrave, un jacobit , este analizat un joc de cărți numit le Her . [10] [11] În această scrisoare, Waldegrave oferă o soluție minimax în strategii mixte pentru o versiune cu doi jucători a acelui joc.

În 1838, în Recherches sur les principes mathématiques de la theorie des richesses ( Cercetări privind principiile matematice ale teoriei bogăției ), Antoine Augustin Cournot a considerat o situație de duopol și a prezentat o soluție care corespunde unui echilibru Nash al jocului.

În 1913 Ernst Zermelo a publicat Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels ( Despre o aplicație a teoriei seturilor la teoria jocului de șah ), în care arăta că jocul de șah este „strict determinat”, adică acest joc admite un echilibru strategic. [12]

Termenul „teoria jocurilor” a fost folosit pentru prima dată de Emil Borel în anii 1920 . Borel tratează în Théorie des jeux jocuri cu sumă zero cu doi jucători și încearcă să determine o soluție care mai târziu a devenit cunoscută sub numele de conceptul lui von Neumann al soluției unui joc cu sumă zero.

Nașterea teoriei jocurilor moderne poate fi urmărită de publicarea articolului lui John von Neumann Despre teoria jocurilor strategiei în 1928, [13] în care von Neumann demonstrează existența echilibrelor pentru jocurile cu sumă zero prin teorema punctului fix al lui Brouwer pentru hărți continue în seturi convexe compacte, dezvoltând o metodă care va deveni ulterior standard în teoria jocurilor și economia matematică. Articolul lui Von Neumann a fost urmat în 1944 de cartea Teoria jocurilor și comportamentul economic de John von Neumann și Oskar Morgenstern [14] . A doua ediție a acestei cărți oferă o teorie axiomatică a utilității , o reîncarnare a vechii teorii a utilității lui Daniel Bernoulli într-o nouă disciplină. Lucrarea seminală a lui von Neumann și Morgenstern include o metodă de determinare a soluțiilor reciproc consistente pentru jocurile cu suma zero pentru doi jucători.

În 1950, apar primele discuții despre dilema prizonierului , un scenariu investigat de matematicienii Merrill M. Flood și Melvin Dresher ca parte a investigațiilor RAND Corporation în teoria jocurilor. RAND a întreprins aceste studii pentru posibilele lor aplicații la strategiile nucleare globale. [15] Mai mult sau mai puțin simultan, John Nash elaborează un criteriu pentru consistența reciprocă a strategiilor jucătorilor, cunoscut sub numele de echilibru Nash, aplicabil unei game mai largi de jocuri decât criteriul propus de von Neumann și Morgenstern. Nash demonstrează că orice joc finit necooperativ, cu mai mulți jucători, chiar dacă nu cu suma zero, admite un așa-numit echilibru Nash în strategiile mixte.

Teoria jocurilor s-a dezvoltat foarte mult în anii 1950 , timp în care au fost dezvoltate conceptele de bază , joc extins , joc repetat și valoare Shapley . Anii 1950 au văzut și primele aplicații ale teoriei jocurilor în științe politice și filozofie.

Rezultate premiate

Unsprezece premii Nobel în economie au fost acordate cărturarilor care au studiat teoria jocurilor. Un premiu Crafoord a fost, de asemenea, acordat lui John Maynard Smith , un distins biolog și genetician, profesor de lungă durată la Universitatea din Sussex , pentru contribuțiile sale în acest domeniu.

În 1965, Reinhard Selten introduce conceptul de soluție cunoscut sub numele de echilibru perfect sub-joc , care rafinează în continuare conceptul de echilibru Nash. Mai târziu, Selten introduce și conceptul de „ echilibru tremurător al mâinilor ”. În 1994, Nash, Selten și Harsanyi au primit Premiul Nobel pentru economie pentru contribuțiile lor la teoria jocurilor.

În anii 1970 , teoria jocurilor a fost aplicată pe scară largă în biologie , în mare parte ca urmare a muncii lui John Maynard Smith și a conceptului său de strategii stabile din punct de vedere evolutiv . Au introdus, de asemenea, conceptele de echilibru corelat , echilibrul mâinii tremurate și cunoștințe comune (cunoștințe comune).

În 2005, teoreticienii jocurilor Thomas Schelling și Robert Aumann au primit, de asemenea, un premiu Nobel pentru economie. Schelling a lucrat la modele care anticipau teoria jocului evolutiv. Aumann a introdus conceptul de echilibru corelat și a dezvoltat o analiză formală extinsă a presupunerii cunoașterii comune și a consecințelor sale.

În 2007, Leonid Hurwicz , Eric Maskin și Roger Myerson au câștigat premiul Nobel pentru economie „pentru că au pus bazele teoriei mecanismelor proiectului (proiectarea mecanismelor)”. Contribuțiile lui Myerson includ noțiunea de echilibru adecvat și un important text monografic: Theory Game, Analysis of Conflict . [16] . Hurwicz a introdus și a oficializat conceptul de „ compatibilitate a stimulentelor ”.

În 2012, Alvin E. Roth și Lloyd S. Shapley au primit Premiul Nobel pentru economie „pentru teoria alocărilor stabile și pentru practica proiectării pieței”. În 2014, Premiul Nobel pentru economie i-a revenit teoreticianului de jocuri Jean Tirole .

In Italia

În Italia, o contribuție puternică la dezvoltarea teoriei jocurilor a fost dată de „Centrul interuniversitar pentru teoria jocurilor și aplicațiile sale” („CITG”), datorită organizării de conferințe naționale și internaționale, școli de vară și difuzării prin rețeaua de informații ( incluzând Listarea Pool-ului, o listă actualizată de pre-tipăriri pe acest subiect, editată anterior de Universitatea din Bielefeld și publicată în Jurnalul Internațional de Teorie de Jocuri). CITG, care fusese promovat de universitățile din Bergamo, Florența și Pavia, a fost creat în 1990 [17] și a fost închis în 2005 pentru că și-a atins obiectivele instituționale.

Descriere

Premise

În modelul teoriei jocurilor, premisa indispensabilă este că scopul este să câștigi; toată lumea trebuie să fie conștientă de regulile jocului și să fie conștienți de consecințele fiecărei mișcări. Miscarea sau setul de mișcări pe care intenționează să le facă un individ se numește „ strategie ”. În funcție de strategiile adoptate de toți jucătorii (sau agenții), fiecare primește o „plată” (care în engleză înseamnă: compensație, câștiguri, plată, dar și rezultat) în conformitate cu o unitate de măsură adecvată. Această compensare poate fi pozitivă, negativă sau nulă. Un joc se spune că este „sumă constantă” dacă pentru fiecare victorie a unui jucător există o pierdere corespunzătoare pentru alții. În special, un joc care este „sumă zero” între doi jucători reprezintă situația în care plata este plătită de un jucător către celălalt. Strategia care trebuie urmată este strict determinată dacă există una care să fie satisfăcătoare pentru toți jucătorii; în caz contrar, este necesar să se calculeze și să maximizeze speranța matematică a jucătorului sau valoarea așteptată, care este media ponderată a recompenselor posibile (atât pozitive, cât și negative), fiecare înmulțită (ponderată) cu probabilitățile respective de a fi asumate (adică de a apărea).

Descriere informală a jocurilor

Într-un joc există unul sau mai mulți concurenți care încearcă să câștige, adică să-și maximizeze câștigurile. Câștigarea este definită de o regulă ( funcție ) care stabilește cantitativ ceea ce câștigă concurenții în funcție de comportamentul lor. Această funcție se numește „funcția de plăți”. Fiecare jucător poate întreprinde un număr finit (sau infinit, în cel mai abstract caz posibil) de acțiuni sau decizii care determină o strategie. Fiecare strategie este caracterizată de o consecință pentru jucătorul care a adoptat-o ​​și care poate fi o recompensă sau o penalizare. Rezultatul jocului este în cele din urmă complet determinat de succesiunea strategiilor lor și de strategiile adoptate de ceilalți jucători.

Dar cum să caracterizezi rezultatul jocului pentru fiecare jucător? Dacă consecința unei strategii este măsurată în „termeni monetari”, fiecare strategie poate fi asortată cu o valoare: o valoare negativă va indica o plată către adversar, adică o penalitate; în timp ce o valoare pozitivă va indica un câștig, adică colectarea unui premiu. Câștigul sau pierderea datorată jucătorului generic asociat strategiei sale și strategiilor luate într-un moment dat de toți jucătorii rămași se exprimă prin valoarea monetară indicată de funcția de plată. Deciziile luate de un jucător se ciocnesc în mod natural sau sunt în acord cu deciziile luate de ceilalți jucători și din situații similare apar diferite tipuri de jocuri (de exemplu, jocuri cooperative sau necooperante).

Un instrument util pentru reprezentarea interacțiunilor dintre doi jucători, două firme sau doi indivizi este o matrice sau un tabel de decizie cu intrare dublă. Acest tabel de decizie este utilizat pentru a arăta strategiile și plățile unui joc cu doi jucători.

Matricea decizională este deci o reprezentare prin care catalogăm toate rezultatele posibile ale interacțiunilor dintre jucători și atribuim valoarea câștigului care în fiecare situație aparține fiecărui jucător. O altă formă de reprezentare se referă la secvența în care se iau fiecare decizie sau se desfășoară acțiunile. Această caracteristică a fiecărui joc poate fi descrisă prin intermediul unui grafic în arbore , reprezentând orice combinație posibilă de pariuri de către concurenți, de la o stare inițială la stările finale în care sunt împărțite câștigurile.

Tipuri de jocuri

Jocurile pot fi clasificate în funcție de diferite paradigme:

  • Cooperare;
  • Reprezentare;
  • Sumă.

Cooperare

Un joc cooperativ apare atunci când interesele jucătorilor nu sunt în opoziție directă între ele, dar există o comunitate de interese. Jucătorii urmăresc un obiectiv comun, cel puțin pe durata jocului, unii dintre ei ar putea tinde să se asocieze pentru a-și îmbunătăți „recompensa”. Garanția este dată de acorduri obligatorii.

Care este reprezentarea matematică a unei comune a intereselor? Conceptul unirii intereselor individuale individuale într-o coaliție sau alianță este exprimat prin definiția jocului esențial; în timp ce valoarea v a unei coaliții generice G este măsurată printr-o funcție numită funcție caracteristică. Notate cu R = setul de n jucători, aceștia pot exista subseturi arbitrare G⊆R reprezentând o coaliție astfel încât G să apară efectelor jocului ca un singur jucător. Funcția caracteristică este definită cu precizie pe setul de părți ale lui R, adică pe setul tuturor subgrupurilor G⊆R și asociază un număr fiecărei coaliții: V (G): = v. Bineînțeles, V (∅): = 0, deoarece plata pentru coaliția goală, cea formată din niciun jucător, este nulă. Se spune că un joc n-persoană este esențial dacă

cu k = 1, ..., Și pentru fiecare i ≠ j.

Practic, un joc esențial este intrinsec de natură cooperativă, atunci când toate coalițiile posibile care pot fi constituite între n jucători „văd” că există o valoare a jocului V (R) care domină uniunea simplă a plăților realizabile de către alianțe unice . În R toți jucătorii interacționează și din relațiile reciproce obțin avantajul reciproc V (R).

Există două subgenuri, jocurile NTU și jocurile TU .

Jocuri NTU

„Utilitate netransferabilă”: utilitate netransferabilă sau fără plăți secundare. În aceste cazuri, în domeniul economiei industriale, într-o situație de oligopol poate apărea fenomenul de coluziune .

VOI jocuri

„Utilitate transferabilă”: un utilitar transferabil sau cu plăți secundare, în care trebuie să existe un mijloc, bani sau altul, pentru transferul utilității.

Împărțirea câștigurilor are loc în raport cu rolul jucat de fiecare jucător, în funcție de strategia și acordurile sale (pentru "jocurile TU" trebuie adăugate plățile sau transferurile obținute în timpul jocului).

În jocurile de 2 persoane cu funcție de plată cu sumă constantă, prin definiție există două părți G și , aceasta din urmă fiind coaliția adversă față de G setul complementar de G. Jocurile cu două persoane sunt de așa natură încât pentru orice coaliție G⊆R pe care o avem

Prin urmare, jocurile de două persoane cu sumă constantă arată că nu sunt esențiale, adică adevărata lor natură nu este de natură cooperativă. Această ultimă afirmație este o teoremă matematică pentru a cărei dovadă formală ne referim la citirea teoremei 41 din E. Burger, Introducere în teoria jocurilor. În jocurile cu sumă constantă, dacă jucătorii au făcut echipă în R, ar obține același rezultat dacă ar juca separat: . În jocurile esențiale, pentru care se aplică zicala „unitatea este forța”, jucătorii care colaborează își garantează un venit mai mare decât ar obține jucând individual. În general, cooperarea poate fi cerută în mod explicit de regulile jocului: este cazul în care jocul impune alegerea unuia sau mai multor parteneri pentru fiecare jucător; sau cooperarea poate apărea deoarece funcția de plăți nu admite a priori o singură valoare. Funcția caracteristică descrie pur și simplu cât de mult primește o coaliție de la oponenții săi, dar nu spune nimic despre modul în care câștigurile sunt împărțite între aliații coaliției în sine. John von Neumann și Oskar Morgenstern au abordat problema jocurilor cooperative caracterizându-le prin faptul că o coaliție de indivizi are motive să existe dacă și numai dacă apar două condiții legate de distribuirea câștigurilor între membrii coaliției. Cele două condiții sunt:

1) fiecare diviziune a „câștigurilor” realizabile în rândul jucătorilor care nu aparțin coaliției este mai mică decât divizarea „câștigurilor” efectuată între jucătorii care aparțin coaliției;

2) nicio diviziune a câștigurilor în cadrul coaliției nu este superioară unei alte posibile distribuții a „câștigurilor” în cadrul coaliției.

Proprietatea 1) afirmă că coaliția câștigă, deoarece este mai profitabilă și, în concluzie, toată lumea ar dori să se alăture. Pe scurt, soluțiile jocurilor trebuie să fie eficiente: nu există alte soluții care să îmbunătățească rezultatele obținute de membrii coaliției.

Proprietatea 2) asigură faptul că încrederea adoptată în cadrul coaliției este liberă de contradicții interne care ar submina încrederea reciprocă între membri; pe scurt, câștigurile sunt distribuite în mod egal între toți membrii coaliției, fără preferințe sau favoritisme de orice fel.

Jocuri necooperante

În jocurile necooperante, numite și jocuri competitive, jucătorii nu pot încheia acorduri obligatorii (inclusiv cele de reglementare), indiferent de obiectivele lor. La această categorie răspunde soluția dată de John Nash cu Nash Equilibrium , probabil cea mai faimoasă noțiune pentru ceea ce privește întreaga teorie, grație vastului său domeniu de aplicabilitate. Criteriul comportamentului rațional adoptat în jocurile necooperante este de caracter individual și se numește strategie maximă.

O astfel de definiție a raționalității caracterizează comportamentul unui individ „optimist inteligent” prin aceea că își propune să fie obiectivul optimist de a lua întotdeauna decizia care atinge câștigul maxim posibil. Practic, comportamentul fiecărui jucător este de așa natură încât să urmărească întotdeauna cea mai avantajoasă strategie pentru sine. Dacă există o strategie în joc care prezintă câștigul maxim pentru toți jucătorii, se numește punct de echilibru.

Un punct de echilibru într-un joc în care strategia maximă este implementată exprimă faptul că toți jucătorii obțin câștigul maxim individual, dar și cel colectiv. Punctul de echilibru Nash exprimă într-un anumit sens un comportament rațional util social, deoarece toți jucătorii primesc o plată care prezintă convergența intereselor tuturor jucătorilor. John Nash a demonstrat că fiecare joc finit cu n jucători admite cel puțin un punct de echilibru în strategii mixte, această teoremă a făcut parte din teza sa de doctorat.

Jocuri repetate în timp

Pictogramă lupă mgx2.svg Același subiect în detaliu: Dilema prizonierului .

Unele tipuri de jocuri care îi determină pe agenți să joace de mai multe ori, transformând recompensele printr-o constrângere intertemporală, luând în considerare același tipar inițial de joc. În cazul jocurilor cu informații perfecte, acestea pot fi urmărite înapoi la forma normală a lui Borel, adică la jocuri fără dimensiunea timpului.

Un exemplu în acest sens este dilema prizonierului repetată mereu.

Jocuri cu informații perfecte și complete

Pictogramă lupă mgx2.svg Același subiect în detaliu: joc de informații complete .

În jocurile cu informații perfecte, istoria pieselor anterioare este cunoscută cu certitudine în orice moment. În termeni mai tehnici, acestea sunt jocuri în care în fiecare moment al jocului puteți înțelege în ce nod al reprezentării arborelui de joc (reprezentare extinsă) vă aflați. Un concept foarte similar este cel al unui joc de informații complete, în care fiecare jucător are o cunoaștere completă a contextului, dar nu neapărat a acțiunilor celorlalți jucători, de exemplu, pentru că mișcările diferiților jucători trebuie să aibă loc simultan (vezi prizonierul dilemă ).

Exemple de jocuri de informații perfecte:

Jocurile au luat sfarsit

Jocuri în care numărul posibilelor situații de joc este finit, dar numărul de situații poate fi foarte mare.

Exemple:

Reprezentare

Sumă

Jocuri cu sumă zero

Jocurile cu sumă zero sunt un caz special al jocurilor cu sumă constantă în care constanta este zero. Jocurile cu sumă zero modelează toate acele situații conflictuale în care opoziția celor doi jucători este totală: victoria unui jucător coincide exact cu pierderea celuilalt. Suma câștigurilor celor doi concurenți în funcție de strategiile utilizate este întotdeauna zero. În șah, de exemplu, înseamnă că singurele trei rezultate posibile (reprezentând victoria cu 1, înfrângerea cu -1 și egalarea cu 0) pot fi: 1, -1 dacă câștigă albul; -1,1 dacă câștigă negru; 0,0 dacă se leagă [18] . De exemplu, nu există niciun caz în care ambele câștigă sau ambele pierd.

Exemple cu informații perfecte

Exemple cu informații imperfecte

Un joc de strategie este descris de Von Neumann ca un anumit număr de alegeri și evenimente, fiecare determinând un număr finit de rezultate diferite. Evenimentele sunt fortuite, adică sunt rezultatul întâmplării și, ca atare, niciun individ nu este capabil să determine rezultatul sau mai degrabă să influențeze rezultatul. Cel mai mult indivizii cunosc probabilitățile cu care apar diferitele rezultate. Alegerile depind în schimb de libera voință a indivizilor, adică de deciziile luate în mod liber de către jucători. Teoria jocului se concentrează pe efectul pe care alegerea fiecărui jucător îl are asupra tuturor celorlalți, adică examinează efectul combinat al alegerilor individuale în care rațiunea din spatele fiecărei alegeri este urmărirea propriului avantaj. Soarta fiecărui jucător pare să depindă nu numai de propriile alegeri / acțiuni, ci influențează și este influențată de acțiunile altor indivizi atunci când toți jucătorii sunt ghidați în acțiunile lor numai de interesul propriu. Von Neumann consideră, de asemenea, inacceptabil să presupunem că un jucător, înainte de a face alegerea sa, poate cunoaște alegerile celorlalți jucători și rezultatul evenimentului aleatoriu. La luarea deciziei, jucătorul nu poate prezice sau spune care vor fi alegerile sale pe parcursul jocului în corespondență cu alegerile făcute de ceilalți jucători; în caz afirmativ, o astfel de eventualitate ar implica o restricție a propriului său arbitru. De fapt, un jucător care știa dinainte mișcările celorlalți, atunci când trebuia să facă alegerea, acest lucru ar fi condiționat de alegerile făcute de ceilalți și, prin urmare, jucătorul nu putea face altceva decât să sufere pasiv alegerile a jucătorilor rămași și a cazului. Acesta este motivul pentru care se presupune că alegerile jucătorilor sunt luate simultan. Numărul de evenimente care depind de caz este la număr ; indicat cu numărul numărul de rezultate posibile pentru fiecare eveniment, probabilitatea asociată fiecărui rezultat provenind din al-lea eveniment aleatoriu este cu și este astfel încât cu pentru fiecare . Rezultatele care pot apărea sunt număr finit : acest număr constituie toate combinațiile posibile de evenimente și este egal cu

conform regulii fundamentale a combinatoricii. Indicat cu probabilitatea cu care rezultatele aleatorii sunt realizate, Von Neumann simplifică descrierea jocurilor duce înapoi la acțiunea de separați evenimentele aleatorii la un singur eveniment aleatoriu pur și simplu prin combinarea evenimente în conformitate cu teoria probabilității și combinatorică. Luând în considerare un singur eveniment dependent de caz și indicat cu rezultatul său printre posibil, dacă jucătorii sunt n> 1 și fiecare are alegeri cu și indicat cu alegerea fiecărui jucător i, apoi jucătorul i primește de la ceilalți jucătorilor o anumită sumă (plată) care poate fi descrisă printr-o funcție de valoare reală a variabile

Dependența funcțională de variabilele exprimă astfel atât dependența reciprocă de alegerile făcute de jucătorii ca al efectului aleatoriu . Considerat coral jucătorii percep la unison următorul rezultat:

L'equazione a fondamento dei giochi a somma zero è la seguente identità

che viene assunta da Von Neumann valere per qualsiasi . 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 giocatori a seguito delle loro scelte e di un'azione casuale (invisibile) che determinano il pagamento che ogni giocatore fa all'altro. Si osservi che nessun giocatore è in grado di stabilire in anticipo il valore di in quanto il suo valore dipende dalle variabili di cui una sola, la , è determinata dal giocatore i-esimo: le restanti variabili dipendono dalla scelta dei restanti giocatori e dal risultato casuale . 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 risultati casuali accadono ciascuno con probabilità e sono stabilite le scelte dei giocatori allora il valore atteso del risultato per il giocatore generico risulta essere

Poiché ≡ implica ≡ allora restringersi a considerare solo le scelte degli 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 è

dove indica la scelta del giocatore 1 e la scelta del giocatore 2. Il giocatore 1 dispone di scelte chiamate strategie, il giocatore 2 di scelte anch'esse denominate strategie. Se si indica la funzione dei pagamenti per il giocatore 1 con

la funzione dei pagamenti per il giocatore 2 risulta essere

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 , mentre il giocatore 2 cerca di massimizzare e, dal momento che

,

il giocatore 2 cerca di minimizzare in riferimento alla funzione dei pagamenti dell'avversario. Il giocatore massimizzante 1 effettua una scelta e la sua perdita o il suo guadagno dipenderanno dalla scelta dell'avversario: in ogni caso può essere certo che

per qualsiasi scelta effettuata dal giocatore avverso. Il giocatore 1 se sceglie opportunamente , può essere certo del risultato seguente

indipendentemente dalla scelta compiuta dal giocatore 2. Il giocatore minimizzante 2 ragionando in modo analogo conclude che se sceglie opportunamente , può essere certo del risultato seguente

indipendentemente dalla scelta del giocatore 1. Dalla definizione di minimo si ha

per ogni

da cui si deduce che

Scelto tale che si può scrivere

per qualsiasi.

In particolare scelto risulta

Dalla definizione di massimo si ha

per ogni

da cui si deduce che

Scelto tale che si può scrivere

per qualsiasi.

In particolare scelto risulta

Per confronto si conclude che

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

il giocatore massimizzante 1 ed il giocatore minimizzante 2 conseguono il comune valore . 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 in modo tale che , il giocatore minimizzante sceglie tale che . L'eguaglianza implica che il giocatore 1 scegliendo percepirà la vincita

,

laddove il giocatore 2 scegliendo dovrà pagare la somma

.

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 , piuttosto specifica probabilità tali che , successivamente estrae da un'urna contenente i numeri 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à: . Il valore atteso per il giocatore 1 risulta dunque essere

ed il valore atteso per il giocatore 2 è

.

Naturalmente, nessuno proibisce ad un giocatore di compiere una scelta ben determinata, ossia di indirizzarsi verso una specifica strategia escludendo tutte le altre. In tale circostanza il giocatore porrà pari a 1 la probabilità di tale scelta e pari a 0 la probabilità di scelta di tutte le restanti . Una simile circostanza si rappresenta con vettori del tipo

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 esiste sempre un punto di equilibrio costituito da strategie miste:

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 ottimali sono pure e per queste ultime in generale vale

Un gioco a somma zero in forma normale a due giocatori si esprime come: + ≡ 0 ∀ ∧ ∀ dove e

Se il gioco è finito, le funzione dei pagamenti e 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

= e = -

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 è esattamente 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:

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 , 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 =

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" [19] 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 “ 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: = e = . 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 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:

soggetta ai vincoli:

Per il giocatore minimizzante (problema duale) si ha:

soggetta ai vincoli:

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 (non superiore a ).
  • 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 del giocatore 1 e le n strategie pure del giocatore 2 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

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

Esempi:

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 logica alla scienza dei sistemi , 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:

  • uguali
  • 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 venditore, le sue mosse possono essere: aumentare, diminuire o lasciare invariati i prezzi delle sue merci; le mosse di un acquirente possono invece essere: cambiare, restare fedeli a un prodotto oa 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

  1. ^ ( EN ) Myerson 1991 , p.1
  2. ^ ( EN ) Aumann 1987
  3. ^ Teoria dei giochi . Enciclopedia Treccani.
  4. ^ ( EN ) Game theory . Stanford Encyclopedia of Philosophy. Jan 25, 1997
  5. ^ ( EN ) von Neumann 1928
  6. ^ ( EN ) von Neumann e Morgenstern 1944
  7. ^ ( EN ) Fisher 1930
  8. ^ ( EN ) All Prizes in Economic Sciences . NobelPrize.org.
  9. ^ ( EN ) The Crafoord Prize 1999 .
  10. ^ ( EN ) David R. Bellhouse, The Problem of Waldegrave ( PDF ), in Journal Électronique d'Histoire des Probabilités et de la Statistique , vol. 3, n. 2, 2007.
  11. ^ ( EN ) David R. Bellhouse, Le Her and Other Problems in Probability Discussed by Bernoulli, Montmort and Waldegrave , in Statistical Science , vol. 30, n. 1, 2015, pp. 26–39, DOI : 10.1214/14-STS469 , arXiv : 1504.01950 .
  12. ^ ( DE ) Zermelo 1913
  13. ^ ( EN ) von Neumann 1928
  14. ^ ( EN ) von Neumann e Morgenstern 1944
  15. ^ ( EN ) Prisoner's Dilemma . Steven Kuhn, Stanford Encyclopedia of Philosophy. 2 Aprile 2019.
  16. ^ ( EN ) Myerson 1991
  17. ^ Breve cronistoria dei convegni italiani di Teoria dei Giochi
  18. ^ Ai fini delle classifiche dei tornei in caso di pareggio il punteggio è (1/2, 1/2) quindi entrambi i due giocatori pareggiando "vincono" qualcosa rispetto ad un altro giocatore del torneo che perde con un avversario
  19. ^ John von Neumann, Communication on the Borel notes , Econometrica - Vol. 21, 1953, p. 124-125.

Riferimenti bibliografici

Manuali in italiano

  • Robert Gibbons, Teoria dei giochi , Il Mulino, 2005, ISBN ‎ 8815108238 .
  • Ferdinando Colombo, Introduzione alla teoria dei giochi , Carocci, 2003, ISBN 8843027980 .

Testi di riferimento correnti

  • Roger B. Myerson , Game Theory, Analysis of Conflict ( PDF ), Harvard University Press, 1991, ISBN 0-674-34116-3 . URL consultato l'11 Luglio 2021 .
  • Drew Fudenberg e Jean Tirole, Game Theory , MIT Press, 1991, ISBN 0-262-06141-4 .
  • Ken Binmore, Fun and Games , DC Heath, 1991, ISBN 0-669-24603-4 .
  • Martin Osborne e Ariel Rubinstein, A Course in Game Theory , MIT Press, 1994, ISBN 0-262-65040-1 .
  • Robert Gibbons, Game Theory for Applied Economists , Princeton University Press, 1992, ISBN 0-691-00395-5 .
  • Peter Morris, Introduction to the Theory of Games , Springer, 1994, ISBN 3-540-94284-X .
  • Herbert Gintis, Game Theory Evolving , Princeton University Press, 2000, ISBN 0-691-00943-0 .
  • Guillermo Owen, Game Theory , 3ª ed., New York, Academic Press, 1995 [1968] .
  • Prajit K. Dutta, Strategies and Games: Theory and Practice , MIT Press, 1999.

Testi di importanza storica

Voci correlate

Altri progetti

Collegamenti esterni

Controllo di autorità Thesaurus BNCF 21854 · LCCN ( EN ) sh85052941 · GND ( DE ) 4056243-8 · BNF ( FR ) cb11941518c (data) · BNE ( ES ) XX4576411 (data) · NDL ( EN , JA ) 00574436
Matematica Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica