Din teoria jocurilor se știe că, dacă jucătorul „A” își folosește strategia optimă, iar jucătorul „B” rămâne în strategiile sale active, atunci câștigul mediu rămâne neschimbat și egal cu prețul jocului. v indiferent de modul în care jucătorul „B” își folosește strategiile active. Și în cazul nostru, ambele strategii sunt active, altfel jocul ar avea o soluție în strategii pure. Prin urmare, dacă presupunem că jucătorul „B” va folosi strategia pură B 1 , atunci câștigul mediu v va fi:

k 11 p 1 + k 21 p 2 = v (1)

Unde: k ij - elemente ale matricei de plăți.

Pe de altă parte, dacă presupunem că jucătorul „B” va folosi strategia pură B 2 , atunci câștigul mediu va fi:

k 12 p 1 + k 22 p 2 \u003d v (2)

Echivalând părțile din stânga ale ecuațiilor (1) și (2) obținem:

k 11 p 1 + k 21 p 2 \u003d k 12 p 1 + k 22 p 2

Și ținând cont de faptul că p 1 + p 2 = 1 avem:

k 11 p 1 + k 21 (1 - p 1) \u003d k 12 p 1 + k 22 (1 - p 1)

În această sarcină:

Din teoria jocurilor se știe că, dacă jucătorul „B” își folosește strategia optimă, iar jucătorul „A” rămâne în strategiile sale active, atunci câștigul mediu rămâne neschimbat și egal cu prețul jocului. v indiferent de modul în care jucătorul „A” își folosește strategiile active. Prin urmare, dacă presupunem că jucătorul „A” va folosi strategia pură A 1 , atunci câștigul mediu v va fi:

k 11 q 1 + k 12 q 2 = v (4)

În această sarcină:

Răspuns:

Interpretare geometrică (soluție grafică):

Poza 1.
graficul profitului k din frecventa p 2 , când adversarul folosește strategia B1.

Să presupunem acum că jucătorul „B” va folosi strategia B 2 în forma sa cea mai pură. Apoi, dacă noi (jucătorul „A”) folosim strategia pură A 1 , atunci câștigul nostru va fi 5. Dacă folosim strategia pură A 2 , atunci câștigul nostru va fi 3/2 (vezi Fig. 2). În mod similar, dacă amestecăm strategiile A 1 și A 2 în proporții diferite, câștigul nostru se va schimba de-a lungul unei linii drepte care trece prin punctele cu coordonatele (0 , 5) și (1 , 3/2), să-i spunem linia strategiei. B 2 . Ca și în cazul precedent, abscisa oricărui punct de pe această dreaptă este egală cu probabilitatea cu care aplicăm strategia A 2 , iar ordonata este egală cu câștigul obținut în acest caz, dar numai pentru strategia B 2 (vezi Fig. 2).

Figura 2.
v si frecventa optima p 2 pentru jucător "A".

Într-un joc real, când un jucător rezonabil „B” își folosește toate strategiile, câștigul nostru se va schimba de-a lungul liniei întrerupte prezentate în Fig. 2 în roșu. Această linie definește așa-numitul limita inferioară a câștigului. Evident, cel mai înalt punct al acestei linii întrerupte corespunde strategiei noastre optime. În acest caz, acesta este punctul de intersecție al liniilor strategiilor B 1 și B 2 . Rețineți că dacă selectați o frecvență p 2 egal cu abscisa ei, atunci plata noastră va rămâne neschimbată și egală cu v pentru orice strategie a jucătorului „B”, în plus, va fi maximul pe care ni-l putem garanta. Frecvență (probabilitate) p 2 , în acest caz, este frecvența corespunzătoare strategiei noastre mixte optime. Apropo, Figura 2 arată și frecvența p 1 , strategia noastră mixtă optimă, este lungimea segmentului [ p 2 ; 1] pe axa x. (Este pentru că p 1 + p 2 = 1 )

Argumentând într-un mod complet similar, se pot găsi și frecvențele strategiei optime pentru jucătorul „B”, care este ilustrată în Figura 3.

Figura 3
Determinarea grafică a prețului jocului v si frecventa optima q2 pentru jucător "ÎN".

Numai pentru el ar trebui să construiască așa-numitul limita superioară a pierderii(linie roșie întreruptă) și căutați cel mai jos punct de pe el, pentru că pentru jucătorul „B” scopul este de a minimiza pierderea. În mod similar, valoarea frecvenței q 1 , este lungimea segmentului [ q 2 ; 1] pe axa x.

Secțiunea „Teoria jocurilor” este reprezentată de trei calculatoare online:

1. Strategii optime pentru jucători. În astfel de probleme, este dată o matrice a plăților. Este necesar să se găsească strategii pure sau mixte ale jucătorilor și, pretul jocului. Pentru a rezolva, trebuie să specificați dimensiunea matricei și metoda de soluție. Serviciul implementează următoarele metode pentru a rezolva un joc cu doi jucători:
   1. Minimax. Dacă trebuie să găsiți strategia pură a jucătorilor sau să răspundeți la întrebarea despre punctul de șa al jocului, alegeți această metodă de soluție.
   2. Metoda simplex. Este folosit pentru a rezolva jocul în strategii mixte folosind metode de programare liniară.
   3. Metoda grafică. Folosit pentru a rezolva jocuri de strategie mixte. Dacă există un punct de șa, soluția se oprește. Exemplu: pentru o anumită matrice a plăților, găsiți strategiile mixte optime ale jucătorilor și prețul jocului folosind metoda grafică de rezolvare a jocului.
   4. Metoda iterativă Brown-Robinson. Metoda iterativă este utilizată atunci când metoda grafică nu este aplicabilă și când metodele algebrice și matriceale nu sunt practic aplicabile. Această metodă oferă o aproximare a valorii jocului, iar valoarea adevărată poate fi obținută cu orice grad de acuratețe dorit. Această metodă nu este suficientă pentru a găsi strategii optime, dar vă permite să urmăriți dinamica unui joc pe rând și să determinați costul jocului pentru fiecare dintre jucători la fiecare pas.
   De exemplu, sarcina poate suna ca „indicați strategiile optime ale jucătorilor pentru joc date de matricea plăților”.
   Toate metodele aplică o verificare pentru rândurile și coloanele dominante.
2. Joc Bimatrix. De obicei, într-un astfel de joc, sunt stabilite două matrice de aceeași dimensiune a plăților primului și celui de-al doilea jucător. Rândurile acestor matrici corespund strategiilor primului jucător, iar coloanele matricelor corespund strategiilor celui de-al doilea jucător. În acest caz, prima matrice reprezintă plățile primului jucător, iar a doua matrice arată câștigurile celui de-al doilea.
3. Jocuri cu natura. Se utilizează atunci când este necesar să se aleagă o decizie de management după criteriile Maximax, Bayes, Laplace, Wald, Savage, Hurwitz.
   Pentru criteriul Bayes, va fi necesară și introducerea probabilităților de apariție a evenimentelor. Dacă nu sunt setate, lăsați valorile implicite (vor exista evenimente echivalente).
   Pentru criteriul Hurwitz, specificați nivelul de optimism λ . Dacă acest parametru nu este specificat în condiții, pot fi utilizate valorile 0, 0,5 și 1.

În multe probleme este necesară găsirea unei soluții cu ajutorul unui computer. Unul dintre instrumente este serviciile și funcțiile de mai sus

Teoria jocului - un set de metode matematice de rezolvare a situaţiilor conflictuale (coliziuni de interese). În teoria jocurilor, un joc este modelul matematic al unei situații conflictuale. Un subiect de interes deosebit în teoria jocurilor este studiul strategiilor de luare a deciziilor ale participanților la joc în condiții de incertitudine. Incertitudinea se datorează faptului că două sau mai multe părți urmăresc scopuri opuse, iar rezultatele oricărei acțiuni a fiecăreia dintre părți depind de mișcările partenerului. În același timp, fiecare dintre părți se străduiește să ia decizii optime care să realizeze obiectivele stabilite în cea mai mare măsură.

Teoria jocurilor este aplicată cel mai consistent în economie, unde apar situații conflictuale, de exemplu, în relațiile dintre un furnizor și un consumator, un cumpărător și un vânzător, o bancă și un client. Aplicarea teoriei jocurilor poate fi găsită și în politică, sociologie, biologie și artă militară.

Din istoria teoriei jocurilor

Istoria teoriei jocurilor ca disciplină independentă începe în 1944, când John von Neumann și Oscar Morgenstern au publicat cartea „Theory of Games and Economic Behavior” („Theory of Games and Economic Behavior”). Deși s-au mai întâlnit exemple de teorie a jocurilor: tratatul din Talmudul babilonian despre împărțirea bunurilor unui soț decedat între soțiile sale, jocurile de cărți în secolul al XVIII-lea, dezvoltarea teoriei șahului la începutul secolului al XX-lea, dovada a teoremei minimax a aceluiași John von Neumann în anul 1928, fără de care nu ar exista teoria jocurilor.

În anii 1950, Melvin Drescher și Meryl Flood din Rand Corporation Primul care a aplicat experimental dilema prizonierului, John Nash, în lucrarea sa despre starea de echilibru în jocurile cu două persoane, a dezvoltat conceptul de echilibru Nash.

Reinhard Salten a publicat în 1965 cartea „Oligopoly Processing in Game Theory on Demand” („Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit”), cu care aplicarea teoriei jocurilor în economie a primit un nou impuls. Un pas înainte în evoluția teoriei jocurilor este asociat cu lucrarea lui John Maynard Smith „Evolutionary Stable Strategy” („Evolutionary Stable Strategy”, 1974). Dilema prizonierului a fost popularizată în lucrarea lui Robert Axelrod, Evoluția cooperării, publicată în 1984. În 1994, John Nash, John Harsanyi și Reinhard Salten au primit Premiul Nobel pentru Teoria Jocurilor.

Teoria jocurilor în viață și în afaceri

Să ne oprim mai detaliat asupra esenței unei situații conflictuale (conflict de interese) în sensul în care aceasta este înțeleasă în teoria jocurilor pentru modelarea ulterioară a diferitelor situații din viață și afaceri. Lăsați individul să fie într-o poziție care duce la unul dintre mai multe rezultate posibile, iar individul are unele preferințe personale în legătură cu aceste rezultate. Dar, deși poate controla într-o oarecare măsură factorii variabili care determină rezultatul, el nu deține control complet asupra acestora. Uneori, controlul este în mâinile mai multor indivizi care, ca și el, au o oarecare preferință pentru posibilele rezultate, dar, în general, interesele acestor indivizi nu sunt de acord. În alte cazuri, rezultatul final poate depinde atât de accidente (uneori numite dezastre naturale în științe juridice), cât și de alți indivizi. Teoria jocurilor sistematizează observarea unor astfel de situații și formularea de principii generale care să ghideze acțiunea rezonabilă în astfel de situații.

În unele privințe, denumirea de „teoria jocurilor” este regretabilă, deoarece sugerează că teoria jocurilor se ocupă doar de coliziunile nesemnificative din punct de vedere social care apar în jocurile de societate, dar totuși această teorie are un sens mult mai larg.

Următoarea situație economică poate da o idee despre aplicarea teoriei jocurilor. Să presupunem că există mai mulți antreprenori, fiecare dintre aceștia cautând să maximizeze profiturile, având în același timp o putere limitată asupra variabilelor care determină acest profit. Antreprenorul nu are control asupra variabilelor care sunt controlate de un alt antreprenor, dar care pot afecta foarte mult veniturile primului. Interpretarea acestei situații ca un joc poate da naștere la următoarea obiecție. Modelul de joc presupune că fiecare antreprenor face o alegere din zona opțiunilor posibile, iar profiturile sunt determinate de aceste alegeri unice. Este evident că acest lucru este aproape imposibil în realitate, deoarece în acest caz nu ar fi necesare aparate administrative complexe în industrie. Există pur și simplu o serie de decizii și modificări ale acestor decizii care depind de alegerile făcute de alți participanți la sistemul economic (jucători). Dar, în principiu, se poate imagina că orice administrator anticipează toate eventualele neprevăzute și descrie în detaliu acțiunea care trebuie întreprinsă în fiecare caz, în loc să rezolve fiecare sarcină pe măsură ce apare.

Un conflict militar, prin definiție, este o ciocnire de interese în care niciuna dintre părți nu are control deplin asupra variabilelor care determină rezultatul, care este decis printr-o serie de bătălii. Puteți considera pur și simplu rezultatul ca o victorie sau o pierdere și să le atribuiți valori numerice 1 și 0.

Una dintre cele mai simple situații conflictuale care pot fi notate și rezolvate în teoria jocurilor este un duel, care este un conflict între doi jucători 1 și 2, având respectiv pȘi q lovituri. Pentru fiecare jucător, există o funcție care indică probabilitatea ca jucătorul să lovească i la momentul t va da o lovitură care se va dovedi fatală.

Ca urmare, teoria jocurilor ajunge la următoarea formulare a unei anumite clase de conflicte de interese: există n jucători, iar fiecare jucător trebuie să aleagă o posibilitate dintr-un anumit set de 100, iar atunci când face o alegere, jucătorul nu are nicio informație despre alegerile altor jucători. Zona de posibile alegeri a jucătorului poate conține elemente precum „deplasarea asului de pică”, „producerea de tancuri în loc de mașini” sau, în sens general, o strategie care definește toate acțiunile care trebuie întreprinse în toate circumstanțele posibile. Fiecare jucător se confruntă cu sarcina: ce alegere ar trebui să facă pentru ca influența sa privată asupra rezultatului să-i aducă cel mai mare câștig posibil?

Model matematic în teoria jocurilor și formalizarea problemelor

După cum am observat deja, jocul este un model matematic al unei situații conflictuale și necesită următoarele componente:

1. părțile interesate;
2. acțiuni posibile de fiecare parte;
3. interesele părților.

Părțile interesate de joc se numesc jucători. , fiecare dintre ei poate întreprinde cel puțin două acțiuni (dacă jucătorul are o singură acțiune, atunci nu participă efectiv la joc, deoarece se știe dinainte ce va întreprinde). Rezultatul jocului se numește victorie. .

O situație conflictuală reală nu este întotdeauna, dar jocul (în conceptul de teoria jocurilor) - întotdeauna - continuă anumite reguli , care definesc exact:

1. opțiuni pentru jucători;
2. cantitatea de informații pe care fiecare jucător o are despre comportamentul partenerului;
3. recompensa la care duce fiecare set de acțiuni.

Exemple de jocuri oficializate sunt fotbalul, jocul de cărți, șahul.

Dar în economie, un model de comportament al jucătorului apare, de exemplu, atunci când mai multe firme caută să ocupe un loc mai avantajos pe piață, mai mulți indivizi încearcă să împartă unele lucruri bune (resurse, finanțe) între ei, astfel încât toată lumea să obțină cât mai mult posibil. . Jucătorii aflați în situații conflictuale din economie care pot fi modelați ca un joc sunt firmele, băncile, persoanele fizice și alți agenți economici. La rândul său, în condiții de război, modelul de joc este folosit, de exemplu, în alegerea celei mai bune arme (dintre existente sau potențial posibile) pentru a învinge inamicul sau a se apăra împotriva atacurilor.

Jocul este caracterizat de incertitudinea rezultatului . Cauzele incertitudinii pot fi împărțite în următoarele grupuri:

1. combinatorie (ca la șah);
2. influența factorilor aleatori (ca în jocul „capete sau cozi”, zaruri, jocuri de cărți);
3. strategic (jucătorul nu știe ce acțiune va întreprinde adversarul).

Strategia jucătorului este un set de reguli care îi determină acțiunile la fiecare mișcare, în funcție de situație.

Scopul teoriei jocurilor este de a determina strategia optimă pentru fiecare jucător. A determina o astfel de strategie înseamnă a rezolva jocul. Optimitatea strategiei se realizează atunci când unul dintre jucători trebuie să obțină profitul maxim, în timp ce al doilea aderă la strategia sa. Iar al doilea jucător ar trebui să aibă o pierdere minimă dacă primul se ține de strategia lui.

Clasificarea jocurilor

1. Clasificare după numărul de jucători (joc de două sau mai multe persoane). Jocurile pentru două persoane sunt esențiale pentru toată teoria jocurilor. Conceptul de bază al teoriei jocurilor pentru jocurile pentru două persoane este o generalizare a ideii esențiale de echilibru, care apare în mod natural în jocurile pentru două persoane. Cât despre jocuri n persoane, atunci o parte a teoriei jocurilor este dedicată jocurilor în care cooperarea între jucători este interzisă. Într-o altă parte a teoriei jocurilor n persoane se presupune că jucătorii pot coopera în beneficiul reciproc (a se vedea mai târziu în acest paragraf despre jocurile non-cooperative și cooperative).
2. Clasificarea după numărul de jucători și strategiile acestora (numarul de strategii este de cel putin doua, poate fi infinit).
3. Clasificarea după cantitatea de informații privind mișcările trecute: jocuri cu informații complete și informații incomplete. Să fie jucătorul 1 - cumpărătorul și jucătorul 2 - vânzătorul. Dacă jucătorul 1 nu are informații complete despre acțiunile jucătorului 2, atunci jucătorul 1 poate să nu facă distincția între două alternative între care trebuie să aleagă. De exemplu, alegerea între două tipuri de un anumit produs și neștiind că, după unele caracteristici, produsul A mai rău decât bunurile B, este posibil ca jucătorul 1 să nu vadă diferența dintre alternative.
4. Clasificare după principiile împărțirii câștigurilor : cooperativă, coaliție pe de o parte și necooperativ, necooperativ pe de altă parte. ÎN joc non-cooperativ , sau altfel - joc non-cooperativ , jucătorii aleg strategii simultan fără să știe ce strategie va alege al doilea jucător. Comunicarea între jucători nu este posibilă. ÎN joc cooperativ , sau altfel - joc de coaliție , jucătorii pot forma coaliții și pot lua măsuri colective pentru a-și crește câștigurile.
5. Joc finit cu sumă zero pentru două persoane sau jocul antagonist este un joc de strategie cu informații complete, la care participă părți cu interese opuse. Jocurile antagoniste sunt jocuri de matrice.

Un exemplu clasic din teoria jocurilor este dilema prizonierului.

Cei doi suspecți sunt luați în arest și izolați unul de celălalt. Procurorul este convins că aceștia au săvârșit o infracțiune gravă, dar nu are suficiente probe pentru a-i pune sub acuzare la proces. El le spune fiecăruia dintre prizonieri că are două alternative: să mărturisească infracțiunea pe care poliția crede că a comis-o sau să nu mărturisească. Dacă amândoi nu mărturisesc, atunci procurorul districtual îi va acuza de o infracțiune minoră, cum ar fi furtul mic sau deținerea ilegală a unei arme, și amândoi vor primi o sentință mică. Dacă amândoi mărturisesc, vor fi supuși urmăririi penale, dar nu va necesita cea mai severă pedeapsă. Dacă unul mărturisește și celălalt nu, atunci cel mărturisit va avea o pedeapsă comutată pentru extrădarea unui complice, în timp ce cel încăpățânat va primi „la maxim”.

Dacă această sarcină strategică este formulată în termeni de concluzie, atunci se rezumă la următoarele:

Astfel, dacă ambii prizonieri nu se spovedesc, vor primi câte 1 an fiecare. Dacă ambii mărturisesc, atunci fiecare va primi 8 ani. Iar dacă unul mărturisește, celălalt nu, atunci cel care mărturisește va scăpa cu trei luni de închisoare, iar cel care nu se spovedește va primi 10 ani. Matricea de mai sus reflectă corect dilema prizonierului: toată lumea se confruntă cu întrebarea de a mărturisi sau a nu mărturisi. Jocul pe care procurorul îl oferă prizonierilor este joc non-cooperativ sau altfel - joc non-coaliție . Dacă ambii prizonieri ar fi putut coopera (de ex. jocul ar fi cooperant sau altfel joc de coaliție ), atunci amândoi nu s-au spovedit și au primit câte un an de închisoare fiecare.

Exemple de utilizare a mijloacelor matematice ale teoriei jocurilor

Ne întoarcem acum la luarea în considerare a soluțiilor la exemple de clase comune de jocuri pentru care există metode de investigare și soluție în teoria jocurilor.

Un exemplu de formalizare a unui joc non-cooperativ (non-cooperant) de două persoane

În paragraful anterior, am considerat deja un exemplu de joc necooperativ (necooperant) (dilema prizonierului). Să ne consolidăm abilitățile. Un complot clasic inspirat de Aventurile lui Sherlock Holmes a lui Arthur Conan Doyle este de asemenea potrivit pentru asta. Se poate, desigur, obiecta: exemplul nu este din viață, ci din literatură, dar Conan Doyle nu s-a impus ca scriitor de science-fiction! Clasic și pentru că sarcina a fost finalizată de Oscar Morgenstern, așa cum am stabilit deja - unul dintre fondatorii teoriei jocurilor.

Exemplul 1 Va fi oferit un fragment prescurtat din una dintre Aventurile lui Sherlock Holmes. Conform conceptelor binecunoscute ale teoriei jocurilor, creați un model al unei situații de conflict și scrieți în mod formal jocul.

Sherlock Holmes intenționează să plece de la Londra la Dover cu scopul suplimentar de a ajunge pe continent (european) pentru a scăpa de profesorul Moriarty, care îl urmărește. Urcându-se în tren, l-a văzut pe profesorul Moriarty pe peronul gării. Sherlock Holmes recunoaște că Moriarty poate alege un tren special și îl poate depăși. Sherlock Holmes are două alternative: să continue spre Dover sau să coboare la stația Canterbury, care este singura stație intermediară de pe traseul său. Presupunem că adversarul său este suficient de inteligent pentru a determina opțiunile lui Holmes, așa că are aceleași două alternative. Ambii adversari trebuie să aleagă o stație în care să coboare din tren, neștiind ce decizie va lua fiecare dintre ei. Dacă, în urma deciziei, ambii ajung la aceeași stație, atunci putem presupune cu siguranță că Sherlock Holmes va fi ucis de profesorul Moriarty. Dacă Sherlock Holmes ajunge în siguranță la Dover, el va fi salvat.

Soluţie. Eroii lui Conan Doyle pot fi considerați participanți la joc, adică jucători. La dispoziția fiecărui jucător i (i=1,2) două strategii pure:

• coborâți la Dover (strategie si1 ( i=1,2) );
• coborâți la o stație de drum (strategie si2 ( i=1,2) )

În funcție de care dintre cele două strategii alege fiecare dintre cei doi jucători, o combinație specială de strategii va fi creată ca pereche. s = (s1 , s 2 ) .

Fiecare combinație poate fi asociată cu un eveniment - rezultatul unei încercări de a-l ucide pe Sherlock Holmes de către profesorul Moriarty. Facem o matrice a acestui joc cu posibile evenimente.

Sub fiecare dintre evenimente este indicat un indice, ceea ce înseamnă dobândirea profesorului Moriarty, și se calculează în funcție de mântuirea lui Holmes. Ambii eroi aleg o strategie în același timp, neștiind ce va alege adversarul. Astfel, jocul este necooperant, pentru că, în primul rând, jucătorii sunt în trenuri diferite, iar în al doilea rând, au interese opuse.

Un exemplu de formalizare și soluție a unui joc de cooperare (coaliție). n persoane

În acest moment, partea practică, adică cursul rezolvării unei probleme exemplu, va fi precedată de o parte teoretică, în care ne vom familiariza cu conceptele de teoria jocurilor pentru rezolvarea jocurilor cooperative (necooperative). Pentru această sarcină, teoria jocurilor sugerează:

• funcția caracteristică (pentru a spune simplu, reflectă valoarea beneficiilor unirii jucătorilor într-o coaliție);
• conceptul de aditivitate (proprietatea cantităților, constând în faptul că valoarea cantității corespunzătoare întregului obiect este egală cu suma valorilor cantităților corespunzătoare părților sale, într-o anumită clasă de împărțire a obiectului în părți) și supraaditivitatea (valoarea cantității corespunzătoare întregului obiect este mai mare decât suma valorilor cantităților, corespunzătoare părților sale) a funcției caracteristice.

Supraadditivitatea funcției caracteristice indică faptul că coalițiile sunt benefice pentru jucători, deoarece în acest caz câștigul coaliției crește odată cu numărul de jucători.

Pentru a oficializa jocul, trebuie să introducem notația formală pentru conceptele de mai sus.

Pentru Joc n notează setul tuturor jucătorilor săi ca N= (1,2,...,n) Orice submulțime nevidă a mulțimii N notat ca T(inclusiv pe sine Nși toate submulțimile formate dintr-un element). Există o activitate pe site Seturi și operații pe platouri, care se deschide într-o fereastră nouă când dați clic pe link.

Funcția caracteristică se notează ca v iar domeniul său de definire constă din posibile submulţimi ale mulţimii N. v(T) - valoarea funcției caracteristice pentru un anumit subset, de exemplu, venitul primit de o coaliție, inclusiv, eventual, formată dintr-un jucător. Acest lucru este important deoarece teoria jocurilor necesită verificarea prezenței superaditității pentru valorile funcției caracteristice tuturor coalițiilor care nu se suprapun.

Pentru două coaliții nevide de subseturi T1 Și T2 aditivitatea funcției caracteristice a unui joc cooperativ (coalițional) se scrie după cum urmează:

Și superaditivitatea este așa:

Exemplul 2 Trei elevi ai unei școli de muzică câștigă bani în plus în cluburi diferite, își primesc veniturile de la vizitatorii clubului. Determinați dacă este profitabil pentru ei să își unească forțele (dacă da, în ce condiții), folosind conceptele de teoria jocurilor pentru a rezolva jocurile cooperative n persoane, cu următoarele date inițiale.

În medie, veniturile lor pe seară au fost:

• violonistul are 600 de unitati;
• chitaristul are 700 de unități;
• cantareata are 900 de unitati.

În încercarea de a crește veniturile, studenții au creat diverse grupuri timp de câteva luni. Rezultatele au arătat că, prin echipă, își pot crește veniturile de seară, după cum urmează:

• violonist + chitarist a câștigat 1500 de unități;
• violonist + cântăreț a câștigat 1800 de unități;
• chitarist + cântăreț a câștigat 1900 de unități;
• violonist + chitarist + cântăreț a câștigat 3000 de unități.

Soluţie. În acest exemplu, numărul de participanți la joc n= 3 , prin urmare, domeniul funcției caracteristice a jocului este format din 2³ = 8 subseturi posibile ale setului tuturor jucătorilor. Să enumerăm toate coalițiile posibile T:

• coaliții de un element, fiecare dintre ele constând dintr-un jucător - un muzician: T{1} , T{2} , T{3} ;
• coaliții de două elemente: T{1,2} , T{1,3} , T{2,3} ;
• coaliție de trei elemente: T{1,2,3} .

Atribuim un număr de serie fiecărui jucător:

• violonist - primul jucător;
• chitarist - al 2-lea jucător;
• cantareata este al 3-lea jucator.

În funcție de datele problemei, determinăm funcția caracteristică a jocului v:

v(T(1)) = 600; v(T(2)) = 700; v(T(3)) = 900; aceste valori ale funcției caracteristice sunt determinate pe baza câștigurilor primului, al doilea și, respectiv, al treilea jucători, atunci când aceștia nu sunt uniți în coaliții;

v(T(1,2)) = 1500; v(T(1,3)) = 1800; v(T(2,3)) = 1900; aceste valori ale funcției caracteristice sunt determinate de veniturile fiecărei perechi de jucători uniți în coaliții;

v(T(1,2,3)) = 3000; această valoare a funcţiei caracteristice este determinată de venitul mediu în cazul în care jucătorii au fost uniţi în triplete.

Astfel, am enumerat toate coalițiile posibile de jucători, sunt opt ​​dintre ele, așa cum ar trebui să fie, deoarece domeniul de definire a funcției caracteristice a jocului este format din exact opt ​​subseturi posibile ale setului tuturor jucătorilor. Ceea ce cere teoria jocurilor, deoarece trebuie să verificăm prezența superadditivității pentru valorile funcției caracteristice tuturor coalițiilor care nu se suprapun.

Cum sunt îndeplinite condițiile de supraaditivitate în acest exemplu? Să definim modul în care jucătorii formează coaliții care nu se suprapun T1 Și T2 . Dacă unii dintre jucători sunt într-o coaliție T1 , atunci toți ceilalți jucători sunt în coaliție T2 iar prin definiție această coaliție se formează ca diferență între setul total de jucători și setul T1 . Atunci dacă T1 - o coaliție de un jucător, apoi într-o coaliție T2 vor fi al doilea și al treilea jucător, dacă fac parte din coaliție T1 vor fi primul și al treilea jucător, apoi coaliția T2 va consta doar din al doilea jucător și așa mai departe.

Cuprins 1 Informații generale 2 1.1 Jocuri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Mișcări. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategii. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Jocul Matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Punct de urmărire. Strategii pure 7 2.1 Exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Exemplul 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Exemplul 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Strategii mixte 9 3.1 Joc 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Exemplul 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Exemplul 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Interpretarea geometrică. . . . . . . . . . . . . . . . . . . . 12 3.2 Jocuri 2×n și m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Exemplul 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Informaţii generale din teoria jocurilor 1.1. Jocuri Teoria jocurilor este o teorie matematică a situațiilor conflictuale, de ex. astfel de situații în care se ciocnesc interesele a două sau mai multe părți care urmăresc scopuri diferite. Un joc este o situație conflictuală reglementată de anumite reguli, care ar trebui să indice: posibilele opțiuni pentru acțiunile participanților, rezultatul cantitativ al jocului sau plata (câștig, pierdere) la care un anumit set de mișcări duce la suma de informațiile fiecărei părți despre comportamentul celeilalte. Joc de perechi - un joc la care participă doar două părți (doi jucători). Joc de perechi cu sumă zero - un joc de perechi în care valoarea plăților este zero, de exemplu. Pierderea unui jucător este egală cu câștigul celuilalt. În funcție de atitudinea fiecărui jucător față de valoarea funcției de plată, jocurile în pereche sunt subdivizate: Pierderea unui jucător este egală cu câștigul celuilalt. Un joc non-antagonist este un joc de pereche în care jucătorii urmăresc obiective diferite, dar nu direct opuse. 2 1.2. Mișcări Move - alegerea uneia dintre acțiunile prevăzute de regulile jocului, implementarea acestei alegeri Există două tipuri de mișcări: Mișcare personală - + alegerea conștientă a uneia dintre acțiunile prevăzute de regulile jocului + implementarea acestei alegeri Mișcare aleatorie - O mișcare aleatorie este o alegere dintr-un număr de posibilități, efectuată nu prin decizia jucătorului, ci printr-un mecanism de selecție aleatorie. Mai jos luăm în considerare jocurile perechi cu sumă zero care conțin doar mișcări personale. Fiecare parte nu are informații despre comportamentul celeilalte. 3 1.3. Strategii Strategia unui jucător este un set de reguli care determină alegerea acțiunilor pentru fiecare mișcare personală a acestui jucător, în funcție de situația care s-a dezvoltat în timpul jocului. În funcție de numărul de strategii posibile, jocurile sunt împărțite în finite și infinite. Un joc infinit este un joc în care cel puțin unul dintre jucători are un număr infinit de strategii. Un joc finit este un joc în care fiecare jucător are doar un număr finit de strategii. Numărul de mișcări consecutive pentru oricare dintre jucători determină împărțirea jocurilor în o singură mișcare și multi-mutare, sau pozițional. + Într-un joc cu o singură mișcare, fiecare jucător face o singură alegere dintre opțiunile posibile și apoi stabilește rezultatul jocului. + Un joc cu mai multe mișcări, sau pozițional, se dezvoltă în timp, reprezentând o serie de etape succesive, fiecare dintre ele vine după mutarea unuia dintre jucători și schimbarea corespunzătoare a situației. Într-un joc cu o singură mișcare, fiecare jucător face o singură alegere dintre opțiunile posibile și apoi stabilește rezultatul jocului. Strategia optimă a unui jucător este o strategie care, atunci când jocul este repetat de mai multe ori, oferă jucătorului dat câștigul mediu maxim posibil (sau, echivalent, pierderea medie minimă posibilă). În teoria jocurilor, toate recomandările sunt făcute pe baza presupunerii unui comportament rezonabil al jucătorilor. Greșelile de calcul și greșelile jucătorilor, inevitabile în orice situație conflictuală, precum și elementele de entuziasm și risc din teoria jocului nu sunt luate în considerare. 4 1.4. Jocul Matrix Jocul Matrix este un joc finit cu sumă zero cu o singură mișcare Jocul Matrix este un model teoretic al unei situații conflictuale în care adversarii fac o alegere (mișcare) dintr-un număr finit de moduri de acțiune posibile pentru a realiza obiective diametral opuse.În conformitate cu metodele de acţiune alese (strategiile) se determină rezultatul obţinut. Să ne uităm la un exemplu. Să fie doi jucători A și B, dintre care unul poate alege a i-a strategie din m dintre strategiile sale posibile A1 , A2 , ...Am , iar al doilea alege a j-a strategie din posibilele sale strategii B1 , B2 , .. .bm . Ca urmare, primul jucător câștigă aij și al doilea jucător pierde această valoare. Din numerele aij , compunem matricea   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. .. ..   . . . .  am1 am2 · · · amn Matricea A = (aij), i = 1, m, j = 1, n se numește matricea plăților sau matricea jocului m × n. În această matrice, rândurile sunt întotdeauna pentru strategiile jucătorului câștigător (maximizator) A, adică jucătorul care caută să-și maximizeze câștigul. Coloanele sunt rezervate strategiilor jucătorului care pierde B, adică jucătorului care urmărește să minimizeze criteriul de eficiență. Normalizarea jocului este procesul de reducere a unui joc pozițional la un joc matrice Un joc în formă normală este un joc pozițional redus la un joc matrice o alegere (mutare) dintr-un număr finit de moduri de acțiune posibile la fiecare etapă a dezvoltării acestui joc. situatie. Soluția jocului – găsirea strategiilor optime ale ambilor jucători și determinarea valorii jocului Valoarea jocului este câștigul (pierderea) așteptat al jucătorilor. Soluția jocului poate fi găsită fie în strategii pure – când jucătorul trebuie să urmeze o singură strategie, fie în cele mixte, când jucătorul trebuie să folosească două sau mai multe strategii pure cu anumite probabilități. Acestea din urmă în acest caz sunt numite active. 5 Strategia mixtă a unui jucător este un vector, fiecare componentă a căruia arată frecvența de utilizare de către jucător a strategiei pure corespunzătoare. Maximin sau preț mai mic al jocului - număr α = max min aij i j Maximin strategie (șir) - strategia aleasă de jucător pentru a-și maximiza profitul minim. Evident, atunci când alege cea mai prudentă strategie maximin, jucătorul A se asigură (indiferent de comportamentul adversarului) cu un profit garantat de cel puțin α. Maximin sau costul superior al jocului - numărul β = min max aij j i Strategia Minimax (coloană) - strategia aleasă de jucător pentru a-și minimiza pierderea maximă. Evident, atunci când alege cea mai prudentă strategie minimax, jucătorul B nu îi permite jucătorului A să câștige mai mult decât β în nicio circumstanță. Prețul inferior al jocului nu depășește întotdeauna prețul superior al jocului α = max min aij 6 min max aij = β i j j i Teorema 1 (teorema principală a teoriei jocurilor matriceale). Fiecare joc finit are cel puțin o soluție, poate în domeniul strategiilor mixte. 6 2. Jocuri cu un vârf de șa. Rezolvare în strategii pure Un joc cu un punct de șa este un joc pentru care α = max min aij = min max aij = β i j j i Pentru jocurile cu un punct de șa, găsirea unei soluții constă în alegerea strategiilor maximin și minimax care sunt optime. , Prețul net al jocului este valoarea totală a prețului inferior și superior al jocului α=β=ν 2.1. Exemple Exemplul 1 Găsiți o soluție în strategiile pure ale jocului date de matricea   8 4 7 A= 6 5 9  7 7 8 Rezolvare: determinați prețul superior și inferior al jocului. Pentru a face acest lucru, găsim minimul numerelor aij din i-lea rând αi = min aij j și maximul numerelor aij din j-a coloană βj = max aij i Scriem numerele αi (minimum rânduri) lângă matricea de plăți din dreapta ca o coloană suplimentară . Scriem sub matrice numerele βi (maxime de coloană) ca un rând suplimentar: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Aflați maximul numerelor αi α = max αi = 7 i și minimul numerelor βj β = min βj = 7 j α = β - jocul are un punct de șa. Strategia optimă pentru jucător este strategia A3, iar pentru jucătorul B - strategia B2, costul net al jocului ν = 7 Exemplul 2 Matricea de profit este dată: 1 1 2   1 2 1 1 2 Găsiți soluția jocului în strategii pure. Rezolvare: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Jocul are șase puncte de șa. Strategiile optime sunt: ​​A1 și B3 sau B4 A3 și B3 sau B4 A4 și B3 sau B4 8 3. Rezolvarea jocului în strategii mixte Pentru α ̸= β. În cazul în care, la alegerea strategiilor, ambii jucători nu au informații despre alegerea celuilalt, jocul are o soluție în strategii mixte. SA = (p1 , p2 , ..., pm) este strategia mixtă a jucătorului A în care strategiile A1 , A2 , ..., Am sunt aplicate cu probabilități ∑ m p1 , p2 , ..., pm , pi = 1, pi > 0, i = 1, m i=1 SB = (q1 , q2 , ..., qn) este o strategie mixtă a jucătorului B în care strategiile B1 , B2 , ..., Bm sunt aplicate cu probabilități ∑ n q1 , q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 = aij p∗i qi∗ j=1 i=1 2 × n, m × 2). Dacă unul dintre jucători folosește o strategie mixtă optimă, atunci câștigul său este egal cu prețul jocului ν, indiferent de probabilitățile cu care al doilea jucător va folosi strategiile incluse în cea optimă (inclusiv strategiile pure). 9 3.1. Joc 2 × 2 Să considerăm un joc 2 × 2 cu matricea: () a11 a21 a21 a22 Fie ca jocul să nu aibă soluție în strategii pure. Să găsim strategiile optime SA∗ și SB∗ . În primul rând, definim strategia SA∗ = (p∗1 , p∗2). Conform teoremei, dacă partea A aderă la strategia ν, atunci indiferent de cursul de acțiune al părții B, câștigul va rămâne egal cu prețul jocului ν. Prin urmare, dacă partea A aderă la strategia optimă SA∗ = (p∗1 , p∗2), atunci partea B poate aplica oricare dintre strategiile sale fără a modifica profitul. Apoi, atunci când jucătorul B aplică o strategie pură B1 sau B2, jucătorul va primi un câștig mediu egal cu prețul jocului: a11 p∗1 + a21 p∗2 = ν ← pentru strategia B1 rețineți că p∗1 + p ∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Valoare joc: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 În mod similar, se găsește strategia optimă a jucătorului B: SB∗ = (q1∗ , q2∗). Ținând cont că q1∗ + q2∗ = 1: q1∗ = a2 2 − a1 2 a11 + a22 − a12 − a21 q2∗ = a1 1 − a2 1 a11 + a22 − a12 − a21 3.1.1. Exemple Exemplul 3 Găsiți o soluție a jocului cu matricea () −1 1 A= 1 −1 10 Rezolvare: jocul nu are punct de șa, deoarece α= -1, β = 1, α ̸= β. Căutăm o soluție în strategii mixte. Folosind formulele pentru p∗ și q∗ obținem p∗1 = p∗2 = 0,5 și q1∗ = q2∗ = 0,5, ν = 0 Astfel, SA∗ = (0,5, 0,5) SB∗ = (0,5, 0,5) Exemplul 4 Găsiți o soluție la jocul cu matricea () 2 5 A= 6 4 Rezolvare: jocul nu are punct de șa, deoarece α= 4, β = 5, α ̸= β. Căutăm o soluție în strategii mixte. Prin formule pentru p∗ și q 0.8) 11 3.1.2. Interpretare geometrică Jocului 2×2 i se poate oferi o interpretare geometrică simplă. Să luăm o secțiune unitară a axei absciselor, fiecărui punct căruia îi asociem o strategie mixtă S = (p1 , p2) = (p1 , 1 − p1) p2 , strategii A2 - distanța până la capătul stâng. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ capătul drept al secțiunii (x = 1) - strategia A2 La capete ale secțiunii se refac două perpendiculare pe axa absciselor: axa I - I - se amână plata cu strategia A1 axa II - II - se amână câștigul cu strategia A2 Lăsăm jucătorul B să aplice strategia B1 ; dă pe axele I − I şi respectiv II − II punctele cu ordonatele a11 şi a21 . Tragem dreapta B1 − B1′ prin aceste puncte. Pentru orice strategie mixtă SA = (p1 , p2), profitul jucătorului este determinat de punctul N de pe linia B1 − B1′ , corespunzător punctului SA de pe axa x care împarte segmentul în raport cu p2: p1 . În mod evident, linia dreaptă B2 − B2′ , care determină profitul pentru strategia B2 , poate fi construită exact în același mod. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Este necesar să se găsească strategia optimă SA∗ , adică astfel încât câștigul minim al jucătorului A (cu cel mai prost comportament al jucătorului B pentru el) s-ar transforma într-un maxim. Pentru aceasta, o limită inferioară a plății jucătorului A este construită pentru strategiile B1 , B2 , i.e. linie întreruptă B1 N B2′ ;. Pe această limită se va afla câștigul minim al jucătorului A pentru oricare dintre strategiile sale mixte, punctul N , la care acest câștig atinge un maxim și determină soluția și prețul jocului. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ordonata punctului N nu este altceva decât valoarea jocului ν, abscisa sa este egală cu ∗2 , iar distanța până la capătul drept al segmentului este egală cu ∗1 , i.e. distanța de la punctul SA∗ până la capetele segmentului sunt egale cu probabilitățile ∗2 și ∗1 ale strategiilor A2 și A1 ale strategiei mixte optime a jucătorului A. În acest caz, soluția jocului a fost determinată de punctul de intersecție al strategiilor B1 și B2 . Mai jos este prezentat cazul în care strategia optimă a jucătorului este strategia pură A2 . Aici strategia A2 (pentru orice strategie a adversarului) este mai profitabilă decât strategia A1 , 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .v = a21 .B1 .v = a21 I. I I. I .I . .x .I . .X 2∗ P . A∗ S = A2 . 2∗ P . A∗ S = A2 În dreapta este prezentat cazul în care jucătorul B are o strategie deliberat neprofitabilă.Interpretarea geometrică face posibilă vizualizarea și prețul inferior al jocului α și cel superior β .y .I .I I .B2 .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P Pe același grafic se poate da și o interpretare geometrică a strategiilor optime ale jucătorului B . Este ușor de observat că ponderea q1∗ a strategiei B1 a strategiei mixte optime SB∗ = (q1∗ , q2∗) este egală cu raportul dintre lungimea segmentului KB2 și suma lungimilor segmentelor. KB1 și KB2 pe axa I − I: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 sau LB2′ q1∗ = LB2′ + LB1′ maximul limitei inferioare a plății considerați minimul limitei superioare. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. 2 × n și m × 2 jocuri Rezolvarea jocurilor 2 × n și m × 2 se bazează pe următoarea teoremă. Teorema 3. Orice joc finit m × n are o soluție în care numărul de strategii active ale fiecărei părți nu depășește cel mai mic dintre m și n. Conform acestei teoreme, un joc 2 × n are întotdeauna o soluție în care fiecare jucător are cel mult două strategii active. Trebuie doar să găsiți aceste strategii, iar jocul 2 × n se transformă într-un joc 2 × 2, care se rezolvă elementar. Găsirea strategiilor active se poate face grafic: 1) se construiește o interpretare grafică; 2) se determină limita inferioară a câștigului; 3) se disting două strategii ale celui de-al doilea jucător pe granița inferioară a plății, care corespund cu două linii care se intersectează în punctul cu ordonata maximă (dacă mai mult de două linii se intersectează la acesta, se ia orice pereche) - aceste strategii sunt active strategiile jucătorului B. Astfel, jocul 2 × n se reduce la jocul 2 × 2. Se poate rezolva și jocul m × 2, cu diferența că nu se construiește limita superioară a profitului și nu maximul, ci se cauta minim pe el. Exemplul 5 Găsiți o soluție la jocul () 7 9 8 A= 10 6 9 Rezolvare: folosind metoda geometrică, selectăm strategii active. Liniile B1 − B1′ , B2 − B2′ și B3 − B3′ corespund strategiilor B1 , B2 , B3 . Linia întreruptă B1 N B2 este limita inferioară a câștigului jucătorului. Jocul are o soluție S∗A = (23 , 31); S∗B = (0,5; 0,5; 0); v = 8,16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .X 2∗ P . A∗ S . 1∗ P 17 Joc index, 2 mișcare, 3 2 × 2, 10 personal, 3 2 × 2, 9 aleatoriu, 3 geometrie, 12 valoare joc pur, 7 exemple, 10 2 × n, 9, 16 m × 2, 9 , 16 infinit, 4 formă normală, 5 finită, 4 multidirecțională, 4 unidirecțională, 4 matrice, 5 duble, 2 cu sumă zero, 2 antagoniste, 2 neantagoniste, 2 soluție, 5 strategii mixte, 5, 9 strategii pure 5 teoria jocurilor, 2 18