Soluție de joc Matrix. Concepte de bază ale teoriei jocurilor Jocul matriceal este cu sumă zero

Teste pentru controlul final

1. Jocul antagonist poate fi setat:

a) un set de strategii atât pentru jucători, cât și pentru un punct de șa.

b) setul de strategii ale ambilor jucători și funcția de plată a primului jucător.

2. Prețul jocului există întotdeauna pentru jocurile matrice în strategii mixte.

a) da.

3.Dacă toate coloanele din matricea plăților sunt aceleași și au forma (4 5 0 1), atunci ce strategie este optimă pentru primul jucător?

a) mai întâi.

b) al doilea.

c) oricare dintre cele patru.

4. Fie ca într-un joc matrice una dintre strategiile mixte ale primului jucător să aibă forma (0,3, 0,7), iar una dintre strategiile mixte ale celui de-al doilea jucător să aibă forma (0,4, 0, 0,6). Care este dimensiunea acestei matrice?

a) 2*3.

c) o altă dimensiune.

5. Principiul dominanței vă permite să eliminați din matrice într-un singur pas:

a) linii întregi.

b) numere individuale.

6. În metoda grafică de rezolvare a jocurilor de 2*m se găsește direct din grafic:

a) strategiile optime ale ambilor jucători.

b) prețul jocului și strategiile optime ale celui de-al 2-lea jucător.

c) prețul jocului și strategiile optime ale primului jucător.

7. Graficul plicului inferior pentru metoda grafică de rezolvare a jocurilor de 2*m este în cazul general:

a) spart.

b) drept.

c) parabolă.

8. Într-un joc cu matrice 2*2 există două componente ale strategiei mixte a jucătorului:

a) determinați reciproc valorile.

b) independent.

9. Într-un joc de matrice, elementul aij este:

a) câștigurile primului jucător când folosește strategia i-a, iar al 2-lea - strategia j-a.

b) strategia optimă a primului jucător când adversarul folosește strategia i-a sau j-a.

c) pierderea primului jucător când folosește strategia j-a, iar al 2-lea - strategia i-a.

10.Elementul de matrice aij corespunde punctului de șa. Sunt posibile următoarele situații:

a) acest element este strict cel mai mic dintre toate din linie.

b) acest element este al doilea în ordine în linie.

11. În metoda Brown-Robinson, fiecare jucător, atunci când alege o strategie la pasul următor, este ghidat de:

a) strategiile inamicului la etapele anterioare.

b) strategiile tale în pașii anteriori.

c) altceva.

12. După criteriul așteptării matematice, fiecare jucător pornește din faptul că:

a) se va întâmpla cea mai proastă situație pentru el.

c) toate sau unele situații sunt posibile cu unele probabilități date.

13. Fie un joc de matrice dat de o matrice în care toate elementele sunt negative. Pretul jocului este pozitiv:

b) nu.

c) nu există un răspuns clar.

14. Pretul jocului este:

un număr.

b) vector.

c) matricea.

15.Care este numărul maxim de puncte de șa care poate fi într-un joc de dimensiunea 5*5 (matricea poate conține orice numere):

16. Să fie într-un joc matrice de dimensiunea 2*3 una dintre strategiile mixte ale primului jucător să aibă forma (0,3, 0,7), iar una dintre strategiile mixte ale celui de-al doilea jucător să aibă forma (0,3, x, 0,5) . Care este numărul x?

c) un alt număr.

17. Pentru ce dimensiune a matricei de joc se transformă criteriul Wald în criteriul Laplace?

c) numai în alte cazuri.

18. Prețul superior al jocului este întotdeauna mai mic decât prețul inferior al jocului.

b) nu.

b) întrebarea este incorectă.

19. Ce strategii există într-un joc de matrice:

a) curat.

b) mixt.

c) ambele.

20. Într-un joc antagonist, valorile funcției de plată a ambilor jucători pot fi egale cu 1 pentru unele valori ale variabilelor?

a) întotdeauna.

b) uneori.

c) niciodată.

21. Într-un joc cu matrice, una dintre strategiile mixte ale primului jucător să fie de forma (0,3, 0,7), iar una dintre strategiile mixte ale celui de-al doilea jucător să fie de forma (0,4, 0,1,0,1,0,4) . Care este dimensiunea acestei matrice?

c) o altă dimensiune.

22. Principiul dominanței vă permite să eliminați din matrice într-un singur pas:

a) coloane întregi,

b) numere individuale.

c) submatrice de dimensiuni mai mici.

23. Într-un joc cu matrice 3*3 există două componente ale strategiei mixte a jucătorului:

a) determinați a treia.

b) nu definesc.

24. Într-un joc cu matrice, elementul aij este:

a) pierderea celui de-al 2-lea jucător când folosește strategia j-a, iar al 2-lea - strategia i-a.

b) strategia optimă a celui de-al 2-lea jucător când adversarul folosește strategia i-a sau j-a,

c) câștigurile primului jucător când folosește strategia j-a, iar al 2-lea - i-a strategie,

25. Elementul de matrice aij corespunde punctului de șa. Sunt posibile următoarele situații:

a) acest element este cel mai mare din coloană.

b) acest element este strict cel mai mare în ordine din linie.

c) șirul conține elemente atât mai mari, cât și mai mici decât acest element.

26. Conform criteriului Wald, fiecare jucător presupune că:

a) se va întâmpla cea mai proastă situație pentru el.

b) toate situațiile sunt la fel de posibile.

c) toate situaţiile sunt posibile cu anumite probabilităţi date.

27. Prețul mai mic este mai mic decât prețul superior al jocului:

b) nu întotdeauna.

c) niciodată.

28. Suma componentelor unei strategii mixte pentru un joc matrice este întotdeauna:

a) este egal cu 1.

b) nenegativ.

c) pozitiv.

d) nu întotdeauna.

29. Fie ca într-un joc de matrice de dimensiunea 2*3 una dintre strategiile mixte ale primului jucător să aibă forma (0,3, 0,7), iar una dintre strategiile mixte ale celui de-al doilea jucător să aibă forma (0,2, x, x) . Care este numărul x?

Luați în considerare un joc finit de perechi cu sumă zero. Să notăm prin A câștigurile jucătorului A, și prin b– câștigurile jucătorului B. Deoarece A = –b, atunci când analizați un astfel de joc nu este nevoie să luați în considerare ambele numere - este suficient să luați în considerare câștigurile unuia dintre jucători. Să fie, de exemplu, A. În cele ce urmează, pentru comoditatea prezentării, A vom numi condiționat " Noi„și lateral B – "dusman".

Să avem m strategii posibile A 1 , A 2 , …, A.m, și inamicul n strategii posibile B 1 , B 2 , …, Bn(un astfel de joc se numește joc m×n). Să presupunem că fiecare parte a ales o anumită strategie: noi am ales A i, adversar B j. Dacă jocul constă doar din mișcări personale, atunci alegerea strategiilor A iȘi B j determină în mod unic rezultatul jocului - câștigurile noastre (pozitive sau negative). Să notăm acest câștig prin a ij(câștigul atunci când alegem o strategie A i, iar inamicul – strategii B j).

Dacă jocul conține, pe lângă mișcări personale, aleatorii, atunci câștigurile cu o pereche de strategii A i, B j este o valoare aleatoare care depinde de rezultatele tuturor mișcărilor aleatoare. În acest caz, o estimare naturală a profitului așteptat este așteptarea matematică a unei victorii aleatorii. Pentru comoditate, vom nota prin a ij atât câștigul în sine (într-un joc fără mișcări aleatorii), cât și așteptarea sa matematică (într-un joc cu mișcări aleatorii).

Să presupunem că știm valorile a ij pentru fiecare pereche de strategii. Aceste valori pot fi scrise ca o matrice, ale cărei rânduri corespund strategiilor noastre ( A i), iar coloanele arată strategiile adversarului ( B j):

B j A i	B 1	B 2	…	Bn
A 1	A 11	A 12	…	A 1n
A 2	A 21	A 22	…	A 2n
…	…	…	…	…
A.m	a m 1	a m 2	…	un mn

O astfel de matrice se numește matricea de plată a jocului sau pur și simplu matricea jocului.

Rețineți că construirea unei matrice a plăților pentru jocuri cu un număr mare de strategii poate fi o sarcină dificilă. De exemplu, pentru un joc de șah, numărul de strategii posibile este atât de mare încât construirea unei matrice a plăților este practic imposibilă. Cu toate acestea, în principiu, orice joc finit poate fi redus la formă de matrice.

Sa luam in considerare exemplu 1 joc antagonist 4x5. Avem patru strategii la dispoziție, inamicul are cinci strategii. Matricea jocului este următoarea:

B j A i	B 1	B 2	B 3	B 4	B 5
A 1
A 2
A 3
A 4

Ce strategie ar trebui să avem (adică jucătorul A) profită? Indiferent de strategia pe care o alegem, un adversar inteligent va răspunde cu o strategie pentru care câștigul nostru va fi minim. De exemplu, dacă alegem strategia A 3 (ispitit de a câștiga 10), adversarul va răspunde prin alegerea unei strategii B 1, iar câștigul nostru va fi doar 1. Evident, pe baza principiului precauției (și este principiul de bază al teoriei jocurilor), trebuie să alegem strategia în care câștigurile noastre minime sunt maxime.

Să notăm prin αi valoarea minimă de câștig pentru strategie A i:

și adăugați o coloană care conține aceste valori la matricea jocului:

B j A i	B 1	B 2	B 3	B 4	B 5	minim în rânduri αi
A 1
A 2
A 3
A 4							maximin

Atunci când alegem o strategie, ar trebui să o preferăm pe cea pentru care valoarea αi maxim. Să notăm această valoare maximă cu α :

Magnitudinea α numit cel mai mic preț al jocului sau maximin(câștig minim minim). Strategia jucătorului A, corespunzător maximinului α , numit strategia maximin.

În acest exemplu, maximin α este egal cu 3 (celula corespunzătoare din tabel este evidențiată cu gri), iar strategia maximin este A 4 . Alegând această strategie, putem fi siguri că pentru orice comportament al inamicului vom câștiga nu mai puțin de 3 (și poate mai mult dacă comportamentul inamicului este „nerezonabil”).Această valoare este minimul nostru garantat, pe care îl putem asigura singuri. prin aderarea la cea mai prudentă strategie („reasigurare”).

Acum haideți să facem un raționament similar pentru inamic B B A B 2 – îi vom răspunde A .

Să notăm prin β j A B) pentru strategie A i:

β j β :

7. CE SE NUMINE JOC DE VALOARE SUPERIOR Acum haideți să facem un raționament similar pentru adversar B. Este interesat să ne minimizeze câștigurile, adică să ne ofere mai puțin, dar trebuie să conteze pe cel mai rău comportament al nostru pentru el. De exemplu, dacă alege strategia B 1, atunci îi vom răspunde cu o strategie A 3 și ne va da 10. Dacă alege B 2 – îi vom răspunde A 2, iar el va da 8 etc. Evident, un adversar prudent ar trebui să aleagă strategia în care câștigurile noastre maxime vor fi minime.

Să notăm prin β j valorile maxime în coloanele matricei de plăți (câștiguri maxime ale jucătorului A, sau, ceea ce este același lucru, pierderea maximă a jucătorului B) pentru strategie A i:

și adăugați un rând care conține aceste valori la matricea jocului:

Atunci când alege o strategie, inamicul o va prefera pe cea pentru care are valoare β j minim. Să o notăm prin β :

Magnitudinea β numit pret de top joc sau minimax(câștiguri minime maxime). Strategia inamicului (jucătorului) corespunzătoare minimaxului B), numit strategia minimax.

Minimax este valoarea câștigului, peste care un adversar rezonabil cu siguranță nu ne va oferi (cu alte cuvinte, un adversar rezonabil nu va pierde mai mult de β ). În acest exemplu, minimax β este egal cu 5 (celula corespunzătoare din tabel este evidențiată cu gri) și se realizează folosind strategia inamicului B 3 .

Așadar, pe principiul precauției („întotdeauna să-ți asumi ce e mai rău!”), trebuie să alegem o strategie A 4, iar inamicul - strategie B 3. Principiul precauției este fundamental în teoria jocurilor și se numește principiul minimax.

Sa luam in considerare exemplu 2. Lasă jucătorii AȘi ÎN simultan și independent unul de celălalt, notați unul dintre cele trei numere: fie „1”, fie „2”, fie „3”. Dacă suma numerelor scrise este pară, atunci jucătorul B plătește jucătorul A această sumă. Dacă suma este impară, atunci jucătorul plătește această sumă A către jucător ÎN.

Să notăm matricea de plată a jocului și să găsim prețurile inferioare și superioare ale jocului (numărul strategiei corespunde numărului scris):

Jucător A trebuie să adere la strategia maximin A 1 pentru a câștiga cel puțin -3 (adică pentru a pierde cel mult 3). Minimax Player Strategie B– oricare dintre strategii B 1 și B 2, care garantează că nu va da mai mult de 4.

Același rezultat îl obținem dacă scriem matricea plăților din punctul de vedere al jucătorului ÎN. De fapt, această matrice se obține prin transpunerea matricei construite din punctul de vedere al jucătorului A, și schimbarea semnelor elementelor la opus (de la data câștigului jucătorului A– aceasta este pierderea jucătorului ÎN):

Pe baza acestei matrice, rezultă că jucătorul B trebuie să urmeze oricare dintre strategii B 1 și B 2 (și atunci el nu va pierde mai mult de 4), și jucătorul A– strategii A 1 (și atunci nu va pierde mai mult de 3). După cum puteți vedea, rezultatul coincide exact cu cel obținut mai sus, așa că atunci când analizăm, nu contează din punctul de vedere al cărui jucător îl conducem.

8 CE SE NUMINE JOC DE VALOARE.

9. CARE ESTE PRINCIPIUL MINIMAX. 2. Prețul mai mic și mai mare al jocului. Principiul Minimax

Luați în considerare un joc de matrice de tipul cu o matrice de profit

Dacă jucătorul A va alege o strategie A i, atunci toate beneficiile sale posibile vor fi elemente i al-lea rând al matricei CU. Cel mai rău pentru jucător A caz când jucătorul ÎN aplică o strategie adecvată minim element al acestei linii, câștigul jucătorului A va fi egal cu numărul .

Prin urmare, pentru a obține cel mai mare câștig, jucătorul A trebuie să alegeți strategia pentru care numărul maxim.

Scopul serviciului. Folosind serviciul online puteți:

• determinați prețul unui joc matrice (limitele inferioare și superioare), verificați prezența unui punct de șa, găsiți o soluție pentru o strategie mixtă, găsiți o strategie minimax a jucătorilor;
• scrieți un model matematic al unei perechi de probleme de programare liniară duală, rezolvați un joc matriceal folosind următoarele metode: minimax, metoda simplex, metoda grafică (geometrică), metoda lui Brown.

Instrucțiuni. Selectați dimensiunea matricei, faceți clic pe Următorul. În noua casetă de dialog, selectați o metodă pentru rezolvarea jocului matrice. Exemplu de umplere. Rezultatele calculului sunt prezentate într-un raport în format Word.

Un joc este un model matematic al unei situații conflictuale reale. O situație de conflict între doi jucători se numește joc de dublu. Este convenabil să studiezi un joc de perechi cu sumă zero dacă este descris sub forma unei matrice. Acest joc se numește matrice; o matrice compusă din numere a ij se numește plată. Tabelul prezintă opțiunile de rezolvare a jocului specificate de matricea de plată A.

Descrierea algoritmului:

1. Pe baza analizei matricei de plată, este necesar să se determine dacă există strategii dominate în aceasta și să le elimine.
2. Găsiți prețurile superioare și mai mici ale jocului și stabiliți dacă acest joc are un punct de șa (prețul inferior al jocului trebuie să fie egal cu prețul superior al jocului).
3. Dacă există un punct de șa, atunci strategiile optime ale jucătorilor, care sunt soluția jocului, vor fi strategiile lor pure corespunzătoare punctului de șa. Prețul jocului este egal cu prețurile superioare și mai mici ale jocului, care sunt egale între ele.
4. Dacă jocul nu are un punct de șa, atunci soluția jocului ar trebui căutată în strategii mixte. Pentru a determina strategiile mixte optime în m × n jocuri, ar trebui să folosiți metoda simplex, reformuland mai întâi problema jocului într-o problemă de programare liniară.

Să prezentăm grafic algoritmul pentru rezolvarea unui joc matriceal.

Figura - Schema de rezolvare a unui joc de matrice.

Metode de rezolvare a jocurilor matriceale în strategii mixte

Deci, dacă nu există un punct de șa, jocul este rezolvat folosind strategii mixte și rezolvat folosind următoarele metode:

1. Rezolvarea jocului printr-un sistem de ecuații.
   Dacă este dată o matrice pătrată nxn (n=m), atunci vectorul probabilității poate fi găsit prin rezolvarea sistemului de ecuații. Această metodă nu este întotdeauna utilizată și este aplicabilă numai în anumite cazuri (dacă matricea este 2x2, atunci soluția jocului este aproape întotdeauna obținută). Dacă soluția produce probabilități negative, atunci acest sistem este rezolvat folosind metoda simplex.
2. Rezolvarea grafică a jocului.
   În cazurile în care n=2 sau m=2, jocul matriceal poate fi rezolvat grafic.
3. Rezolvarea unui joc matriceal folosind metoda simplex.
   În acest caz, jocul matricei se reduce la

Institutul Energetic din Moscova

(Universitate tehnica)

Raport de laborator

în teoria jocurilor

„Un program pentru găsirea strategiilor optime pentru un joc cu sumă zero pereche dat sub formă de matrice”

Completat de elevi

grupa A5-01

Ashrapov Daler

Ashrapova Olga

Concepte de bază ale teoriei jocurilor

Teoria jocurilor este concepută să rezolve situatii conflictuale , adică situații în care se ciocnesc interesele a două sau mai multe părți, care urmăresc scopuri diferite.

Dacă scopurile partidelor sunt direct opuse, atunci ele vorbesc despre conflict antagonic .

Joc numit model simplificat formalizat al unei situaţii conflictuale.

O singură joacă a unui joc de la început până la sfârșit este numită parte . Rezultatul petrecerii este plată (sau câștiguri ).

Partidul este format din mișcări , adică alegeri ale jucătorilor dintr-un anumit set de alternative posibile.

Mișcările pot fi personalȘi Aleatoriu.Mișcare personală , Spre deosebire de Aleatoriu , implică alegerea conștientă de către jucător a unei opțiuni.

Sunt apelate jocuri în care există cel puțin o mișcare personală strategic .

Sunt numite jocuri în care toate mișcările sunt aleatorii jocuri de noroc .

Când fac o mișcare personală, vorbesc și despre strategii jucător, adică despre o regulă sau un set de reguli care determină alegerea unui jucător. În același timp, strategia trebuie să fie cuprinzătoare, adică. alegerea trebuie determinată pentru orice situație posibilă din timpul jocului.

Problema de teoria jocurilor– găsirea strategiilor optime pentru jucători, de ex. strategii care le oferă un câștig maxim sau o pierdere minimă.

Clasificarea modelelor teoretice de joc

Joc n persoanele sunt de obicei notate ca, unde
- set de strategii ale celui de-al i-lea jucător,
- plata pentru joc.

În conformitate cu această denumire, se poate propune următoarea clasificare a modelelor teoretice de joc:

Discret (strategii multiple discret)

Final

Fără sfârşit

Continuu (strategii multiple continuu)

Fără sfârşit

n persoane (
)

Coaliție (cooperativă)

Non-coaliție (non-cooperant)

2 persoane (perechi)

Antagoniste (jocuri cu sumă zero)

(interesele părților sunt opuse, adică pierderea unui jucător este egală cu câștigul celuilalt)

Neantagonist

Cu informații complete (dacă jucătorul care face o mișcare personală cunoaște întregul fundal al jocului, adică toate mișcările adversarului)

Cu informatii incomplete

Cu suma zero (plata totală este egală cu zero)

Sumă diferită de zero

O singură mișcare (loterie)

Multi-pass

Reprezentarea matriceală a unui joc cu sumă zero pereche

În acest tutorial ne vom uita la jocuri antagoniste pentru două persoane , dat sub formă de matrice. Aceasta înseamnă că știm multe strategii ale primului jucător (jucător A){ A i }, i = 1,…, mși o varietate de strategii pentru al doilea jucător (jucător B){ B j }, j = 1,..., n, și, de asemenea, având în vedere matricea A = || A ij || câștigurile primului jucător. Întrucât vorbim de un joc antagonist, se presupune că câștigul primului jucător este egal cu pierderea celui de-al doilea. Presupunem că elementul matricei A ij– câștigurile primului jucător atunci când alege o strategie A iși răspunsul celui de-al doilea jucător la el cu o strategie B j. Vom desemna un astfel de joc ca
, Unde m - numărul de strategii ale jucătorilor A,n - numărul de strategii ale jucătorilor ÎN.În general, acesta poate fi reprezentat prin următorul tabel:

	B 1		B j		B n
A 1
A i
A m

Exemplul 1

Ca exemplu simplu, luați în considerare un joc în care un joc constă din două mișcări.

prima mutare: Jucător A alege unul dintre numere (1 sau 2) fără a-i spune adversarului despre alegerea sa.

a 2-a mutare: Jucător ÎN selectează unul dintre numere (3 sau 4).

Concluzie: Alegerile jucătorilor AȘi ÎN pliază în sus. Dacă suma este egală, atunci ÎNîși plătește valoarea jucătorului A, dacă este impar - invers, A plătește suma jucătorului ÎN.

Acest joc poate fi prezentat sub formă
in felul urmator:

	(alegerea 3)	(alegerea 4)
(alegerea 1)
(alegerea 2)

Este ușor de observat că acest joc este antagonic; în plus, este un joc cu informații incomplete, deoarece către jucător ÎN, făcând o mișcare personală, nu se știe ce alegere a făcut jucătorul A.

După cum s-a menționat mai sus, sarcina teoriei jocurilor este de a găsi strategiile optime ale jucătorilor, de exemplu. strategii care le oferă un câștig maxim sau o pierdere minimă. Acest proces se numește soluție de joc .

Când rezolvați un joc în formă de matrice, ar trebui să verificați jocul pentru prezență punct de șa . Pentru a face acest lucru, sunt introduse două valori:

– estimare mai mică a prețului jocului și

– estimarea superioară a prețului jocului.

Cel mai probabil primul jucător va alege strategia în care primește câștigul maxim dintre toate răspunsurile posibile ale celui de-al doilea jucător, iar al doilea jucător, dimpotrivă, o va alege pe cea care își minimizează propria pierdere, adică. posibilă câștigare a primului.

Se poate dovedi că α ≤ V ≤ β , Unde V–pretul jocului , adică câștigul probabil al primului jucător.

Dacă relația se menține α = β = V, atunci ei spun asta jocul are un punct de șa
, Și poate fi rezolvată în strategii pure . Cu alte cuvinte, există câteva strategii
, dând jucătorului AV.

Exemplul 2

Să revenim la jocul pe care l-am considerat în Exemplul 1 și să verificăm prezența unui punct de șa.

	(alegerea 3)	(alegerea 4)
(alegerea 1)
(alegerea 2)

Pentru acest joc
= -5,
= 4,
, prin urmare, nu are un punct de șa.

Să atragem încă o dată atenția asupra faptului că acest joc este un joc cu informații incomplete. În acest caz, putem doar să sfătuim jucătorul A alege o strategie , deoarece în acest caz, el poate obține cel mai mare câștig, totuși, în funcție de alegerea jucătorului ÎN strategii .

Exemplul 3

Să facem câteva modificări regulilor jocului din exemplul 1. Îi vom oferi jucătorul ÎN informații despre selecția jucătorului A. Atunci au ÎN vor apărea două strategii suplimentare:

- o strategie benefica pentru A. Dacă alegerea A - 1, Acea ÎN alege 3 dacă alege A - 2, Acea ÎN alege 4;

- o strategie care nu este benefică pentru A. Dacă alegerea A - 1, Acea ÎN alege 4 dacă alege A - 2, Acea ÎN alege 3.

	(alegerea 3)	(alegerea 4)
(alegerea 1)
(alegerea 2)

Acest joc este cu informații complete.

În acest caz
= -5,
= -5,
, prin urmare, jocul are un punct de șa
. Acest punct de șa corespunde două perechi de strategii optime:
Și
. Pretul jocului V= -5. Este evident că pt A un astfel de joc este neprofitabil.

Exemplele 2 și 3 sunt o ilustrare bună a următoarei teoreme, dovedite în teoria jocurilor:

Teorema 1

Fiecare joc antagonist pereche cu informații complete poate fi rezolvat în strategii pure.

Acea. Teorema 1 spune că orice joc pentru doi jucători cu informații complete are un punct de șa și există o pereche de strategii pure
, dând jucătorului A câștiguri durabile egale cu prețul jocului V.

În cazul absenței unui punct de șa, așa-numitul strategii mixte :, Unde p i Șiq j– probabilităţile de alegere a strategiilor A i Și B j primul și, respectiv, al doilea jucător. Soluția jocului în acest caz este o pereche de strategii mixte
, maximizând așteptările matematice ale prețului jocului.

Următoarea teoremă generalizează teorema 1 în cazul unui joc cu informații incomplete:

Teorema 2

Orice joc antagonist pereche are cel puțin o soluție optimă, adică o pereche de strategii mixte în cazul general
, dând jucătorului A câștiguri durabile egale cu prețul jocului V, și α ≤ V ≤ β .

În cazul special, pentru un joc cu un punct de șa, soluția în strategii mixte arată ca o pereche de vectori în care un element este egal cu unu și restul sunt egali cu zero.

Cel mai simplu caz, dezvoltat în detaliu în teoria jocurilor, este un joc finit de perechi cu sumă zero (un joc antagonic de două persoane sau două coaliții). Luați în considerare acest joc G, la care participă doi jucători AȘi ÎN, având interese opuse: câștigul unuia este egal cu pierderea celuilalt. De la recompensa jucătorului A egal cu câștigurile jucătorului B cu semnul opus, nu ne poate interesa decât să câștigăm A jucător A. Natural, A vrea să maximizeze și IN - minimiza A. Pentru simplitate, haideți să ne identificăm mental cu unul dintre jucători (să fie A)și îl vom numi „noi”, și jucătorul IN -„inamic” (desigur, fără avantaje reale pentru A nu rezultă din aceasta). Să avem T strategii posibile A 1 , A 2 , ..., A m, iar inamicul - n strategii posibile ÎN 1 , IN 2 , ..; ÎN n(un astfel de joc se numește joc T × n). Denota A ij câștigul nostru dacă folosim strategia A i , iar inamicul prin strategie B j .

Tabelul 26.1

A i B j	B 1	B 2		B n
A 1 A 2 A m	A 11 A 21 A m1	A 21 A m		A 1 n A 2 n A mn

Să presupunem că pentru fiecare pereche de strategii L<, ÎN, câștig (sau câștig mediu) A, j noi stim. Apoi, în principiu, este posibil să se construiască o masă dreptunghiulară (matrice) care să enumere strategiile jucătorilor și câștigurile corespunzătoare (vezi Tabelul 26.1).

Dacă un astfel de tabel este compilat, atunci se spune că jocul este G redusă la o formă matriceală (în sine, aducerea jocului într-o astfel de formă poate fi deja o sarcină dificilă, și uneori aproape imposibilă, datorită varietății imense de strategii). Rețineți că, dacă jocul este redus la formă de matrice, atunci jocul cu mai multe mișcări este de fapt redus la un joc cu o singură mișcare - jucătorul trebuie să facă o singură mișcare: să aleagă o strategie. Vom desemna pe scurt matricea jocului ( A ij).

Să ne uităm la un exemplu de joc G(4x5) sub formă de matrice. Avem patru strategii la dispoziție (din care să alegem), în timp ce inamicul are cinci strategii. Matricea jocului este dată în tabelul 26.2

Să ne gândim la ce strategie avem (jucătorul A) profită? În Matrix 26.2 există o răsplată tentantă de „10”; suntem tentați să alegem o strategie A 3 , în care vom obține acest „gust”. Dar stai: nici inamicul nu este un prost! Dacă alegem o strategie A 3 , pentru a ne ciudă, va alege o strategie ÎN 3 , și vom obține un câștig jalnic „1”. Nu, alege o strategie A 3 este interzis! Cum să fii? Evident, pe baza principiului precauției (și acesta este principiul de bază al teoriei jocurilor), trebuie să alegem

Tabelul 26.2

B j A i	B 1	B 2	B 3	B 4	B 5
A 1 A 2 A 3 A 4

strategia în care câștigurile noastre minime sunt maxime. Acesta este așa-numitul „principiu minimax”: acționează în așa fel încât să obții câștigul maxim în cazul celui mai rău comportament al inamicului pentru tine.

Să rescriem tabelul 26.2 și în coloana suplimentară din dreapta notăm valoarea minimă câștigătoare în fiecare rând (minimum rând); să o notăm pt i al-lea rând α i(vezi tabelul 26.3).

Tabelul 26.3

B j A i	B 1	B 2	B 3	B 4	B 5
A 1 A 2 A 3 A 4
β j

Dintre toate valorile α i(coloana din dreapta) este evidențiată cea mai mare (3). Strategia îi corespunde A 4 . Alegând această strategie, noi, în orice caz, putem fi siguri că (pentru orice comportament al inamicului) vom câștiga nu mai puțin de 3. Această valoare este câștigul nostru garantat; Comportându-ne cu grijă, nu putem obține mai puțin decât atât (și poate vom obține mai mult). Acest câștig se numește prețul mai mic al jocului (sau „maximin” - maximul câștigurilor minime). O vom nota A.În cazul nostru α = 3.

Acum să luăm punctul de vedere al inamicului și motivul pentru el. Nu este un fel de pion, dar este și inteligent! Atunci când alege o strategie, ar dori să dea mai puțin, dar trebuie să conteze pe cel mai rău comportament al nostru pentru el. Dacă alege o strategie ÎN 1 , îi vom răspunde A 3 , iar el va da 10; dacă el alege B 2 - îi vom răspunde A 2 , și el va da 8 etc. Să adăugăm o linie de jos suplimentară la Tabelul 26.3 și să notăm maximele coloanelor β în el j. Evident, un adversar prudent ar trebui să aleagă strategia în care această valoare este minimă (valoarea corespunzătoare 5 este evidențiată în Tabelul 26.3). Această valoare β este valoarea câștigului, mai mult decât un adversar rezonabil cu siguranță nu ne va oferi. Se numește prețul superior al jocului (sau „minimax” - minimul câștigurilor maxime). În exemplul nostru, β = 5 și se realizează cu strategia adversarului B 3 .

Deci, pe baza principiului prudenței (regula de reasigurare „întotdeauna să-ți asumi ce este mai rău!”), trebuie să alegem o strategie A 4 , iar inamicul – strategia ÎN 3 . Astfel de strategii se numesc „minimax” (în baza principiului minimax). Atâta timp cât ambele părți din exemplul nostru țin de strategiile lor minimax, câștigul va fi A 43 = 3.

Acum imaginați-vă pentru o clipă că am aflat că inamicul urmărește o strategie ÎN 3 . Haide, să-l pedepsim pentru asta și să alegem o strategie A 1 - vom primi 5, ceea ce nu este prea rău. Dar nici inamicul nu este un eșec; anunță-i că strategia noastră A 1 ; se va grăbi și el să aleagă ÎN 4 , reducerea câștigurilor noastre la 2 etc. (partenerii „s-au grăbit cu strategii”). Pe scurt, strategii minimax în exemplul nostru instabil în raport cu La informații despre comportamentul celeilalte părți; aceste strategii nu au proprietatea de echilibru.

Este întotdeauna cazul? Nu, nu întotdeauna. Luați în considerare exemplul cu matricea dată în tabelul 26.4.

În acest exemplu, prețul inferior al jocului este egal cu cel mai mare: α = β = 6. Ce rezultă din aceasta? Strategii pentru jucători Minimax AȘi ÎN va fi durabil. Atâta timp cât ambii jucători se țin de ei, câștigul este 6. Să vedem ce se întâmplă dacă (A) aflăm că inamicul (ÎN)

Tabelul 26.4

Bj A i	B 1	B 2	B 3	B 4
A 1 A 2 A 3
β j

se tine de strategie B 2 ? Și exact nimic nu se va schimba. Pentru că orice abatere de la strategie A 2 nu poate decât să ne înrăutățească situația. La fel, informațiile primite de inamic nu îl vor determina să se retragă din strategia sa. ÎN 2 . Câteva strategii A 2 , B 2 posedă proprietatea echilibrului (o pereche echilibrată de strategii), iar profitul (în cazul nostru, 6) realizat cu această pereche de strategii se numește „punctul de șa al matricei” 1). Un semn al prezenței unui punct de șa și a unei perechi echilibrate de strategii este egalitatea prețurilor inferioare și superioare ale jocului; valoarea comună a α și β se numește prețul jocului. O vom nota v:

α = β = v

Strategii A i , B j(în acest caz A 2 , IN 2 ), la care se realizează acest câștig se numesc strategii pure optime, iar totalitatea lor se numește soluție a jocului. În acest caz, se spune că jocul în sine este rezolvat prin strategii pure. Ambele părți AȘi ÎN se pot indica strategiile lor optime, în care poziţia lor este cea mai bună posibilă. Ce este un jucător Aîn acest caz 6 câștigă, iar jucătorul IN - pierde 6, - ei bine, acestea sunt conditiile jocului: sunt benefice pt A si dezavantajos pentru ÎN

1) Termenul „punct de șa” este preluat din geometrie - acesta este numele unui punct de pe suprafață în care se realizează simultan un minim într-o coordonată și un maxim într-o alta.

Cititorul poate avea o întrebare: de ce strategiile optime sunt numite „pure”? Privind puțin în perspectivă, vom răspunde la această întrebare: există strategii „mixte”, care constau în faptul că jucătorul folosește nu doar o singură strategie, ci mai multe, intercalându-le la întâmplare. Deci, dacă permitem strategii mixte pe lângă cele pure, fiecare joc finit are o soluție - un punct de echilibru. Dar vom vorbi despre atomi care urmează să vină.

Prezența unui punct de șa într-un joc este departe de a fi o regulă; mai degrabă, este o excepție. Majoritatea jocurilor nu au un punct de șa. Cu toate acestea, există un tip de joc care are întotdeauna un punct de șa și, prin urmare, se rezolvă în strategii pure. Acestea sunt așa-numitele „jocuri cu informații complete”. Un joc cu un raft de informații este un joc în care fiecare jucător, cu fiecare mișcare personală, cunoaște întregul fundal al dezvoltării sale, adică rezultatele tuturor mișcărilor anterioare, atât personale, cât și aleatorii. Exemple de jocuri cu informații complete includ: dame, șah, tic-tac-toe etc.

În teoria jocurilor este dovedit că fiecare joc cu informații complete are un punct de șa,și deci pot fi rezolvate în strategii pure. În fiecare joc cu informații complete, există o pereche de strategii optime care oferă un profit stabil egal cu valoarea jocului v. Dacă un astfel de joc constă numai din mișcări personale, atunci când fiecare jucător își folosește strategia optimă, ar trebui să se încheie într-un mod foarte definit - cu un câștig egal cu costul jocului. Aceasta înseamnă că dacă se cunoaște soluția jocului, jocul în sine își pierde sensul!

Să luăm un exemplu elementar de joc cu informații complete: doi jucători plasează alternativ nichel pe o masă rotundă, alegând aleatoriu poziția centrului monedei (suprapunerea reciprocă a monedelor nu este permisă). Câștigă cel care pune ultimul nichel (când nu mai este loc pentru alții). Este ușor de observat că rezultatul acestui joc este, în esență, predeterminat. Există o anumită strategie care asigură că jucătorul care plasează primul moneda câștigă. Și anume, trebuie să plaseze mai întâi un nichel în centrul mesei și apoi să răspundă la mișcarea fiecărui adversar cu o mișcare simetrică. Evident, indiferent de modul în care se comportă inamicul, el nu poate evita să piardă. Situația este exact aceeași cu șahul și jocurile în general cu informații complete: oricare dintre ele, scris în formă de matrice, are un punct de șa și, prin urmare, soluția este în strategii pure și, prin urmare, are sens doar atâta timp cât acest lucru solutie nu a fost gasita. Să spunem un joc de șah sau Mereu se termină cu câștigul alb, sau Mereu - negru câștigând, sau Mereu - o remiză, dar încă nu știm ce anume (din fericire pentru iubitorii de șah). Să mai adăugăm un lucru: cu greu vom ști în viitorul apropiat, deoarece numărul de strategii este atât de mare încât este extrem de dificil (dacă nu imposibil) să reducem jocul la o formă de matrice și să găsim un punct de șa în el.

Acum să ne întrebăm ce să facem dacă jocul nu are un punct de șa: α ≠ β? Ei bine, dacă fiecare jucător este forțat să aleagă una - singura strategie pură, atunci nu este nimic de făcut: trebuie să te ghidezi după principiul minimax. Un alt lucru este dacă este posibil să „amesteci” un set de strategii, alternate aleatoriu cu unele probabilități. Utilizarea strategiilor mixte este concepută astfel: jocul se repetă de multe ori; înainte de fiecare joc al jocului, când jucătorului i se dă o mișcare personală, acesta „își încredințează” alegerea întâmplării, „aruncă la sorți” și ia strategia care a căzut (știm deja să organizăm lotul din capitolul anterior). ).

Strategiile mixte în teoria jocurilor sunt un model de tactici flexibile, schimbătoare, când niciunul dintre jucători nu știe cum se va comporta adversarul într-un anumit joc. Această tactică (deși de obicei fără nicio justificare matematică) este adesea folosită în jocurile de cărți. Să remarcăm în același timp că cea mai bună modalitate de a-ți ascunde comportamentul de inamic este să îi dai un caracter aleatoriu și, prin urmare, să nu știi dinainte ce vei face.

Deci, să vorbim despre strategii mixte. Vom desemna strategiile mixte ale jucătorilor AȘi ÎN respectiv S A = ( p 1 , R 2 , ..., p m), S B = (q 1 , q 2 , …, q n), Unde p 1 , p 2 , …, p m(formând un total de unu) - probabilitățile de utilizare a jucătorului A strategii A 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n- probabilitățile de utilizare de către jucător ÎN strategii ÎN 1 , ÎN 2 , ..., ÎN n . Într-un caz particular, când toate probabilitățile, cu excepția uneia, sunt egale cu zero, iar aceasta este egală cu unu, strategia mixtă se transformă într-una pură.

Există o teoremă de bază a teoriei jocurilor: orice joc finit de două persoane cu sumă zero are cel puțin o soluție - pereche de strategii optime, în general mixte
si pretul corespunzator v.

Pereche de strategii optime
formarea soluției jocului are următoarea proprietate: Dacă unul dintre jucători aderă la strategia sa optimă, atunci nu poate fi benefic pentru celălalt să se abată de la a lui. Această pereche de strategii formează o anumită poziție de echilibru în joc: un jucător dorește să transforme câștigurile într-un maxim, celălalt - într-un minim, fiecare trage în propria sa direcție și, cu un comportament rezonabil al ambelor, echilibrul și câștigurile stabile sunt stabilit v. Dacă v > 0, atunci jocul este profitabil pentru noi dacă v< 0 - pentru inamic; la v= 0 jocul este „corect”, la fel de benefic pentru ambii participanți.

Să luăm în considerare un exemplu de joc fără un punct de șa și să dăm (fără dovezi) soluția acestuia. Jocul este următorul: doi jucători AȘi ÎN simultan și fără să scoată un cuvânt, arată unul, două sau trei degete. Numărul total de degete decide câștigul: dacă este par, câștigă A si primeste de la ÎN o sumă egală cu acest număr; dacă este ciudat, atunci invers A plătește ÎN o sumă egală cu acest număr. Ce ar trebui să facă jucătorii?

Să creăm o matrice de joc. Într-un joc, fiecare jucător are trei strategii: arată unul, două sau trei degete. Matricea 3x3 este dată în Tabelul 26.5; coloana suplimentară din dreapta arată minimele rândului, iar rândul suplimentar de jos arată maximele coloanei.

Prețul mai mic al jocului este α = - 3 și corespunde strategiei A 1 . Aceasta înseamnă că, cu un comportament rezonabil, atent, garantăm că nu vom pierde mai mult de 3. Mică consolare, dar totuși mai bună decât, să zicem, un câștig de 5, găsit în unele celule ale matricei. E rău pentru noi, jucătorii. A... Dar haideți să ne consolem:

poziția inamicului pare să fie și mai rea: prețul mai mic al jocului este β = 4, adică, cu un comportament rezonabil, el ne va oferi cel puțin 4. În general, situația nu este foarte bună - pentru niciuna dintre părți. Dar să vedem: se poate îmbunătăți? Se dovedește că este posibil. Dacă fiecare parte aplică nu o singură strategie pură, ci una mixtă, în care

Tabelul 26.5

Bj A i	B 1	B 2	B 3
A 1 A 2 A 3
β j

primul și al treilea sunt incluse cu probabilități de 1/4, iar al doilea cu probabilitate de 1/2, i.e.

atunci câștigul mediu va fi constant egal cu zero (ceea ce înseamnă că jocul este „corect” și la fel de benefic pentru ambele părți). Strategii
formează o soluție pentru joc și prețul acestuia v= 0. Cum am găsit această soluție? Aceasta este o întrebare diferită. În paragraful următor vom arăta cum se rezolvă jocurile finite în general.