Principi rješavanja matričnih antagonističkih igara. Matrix igre: primjeri rješavanja problema

Svrha usluge. Korištenjem online usluge možete:

• odrediti cijenu matrične igre (donje i gornje granice), provjeriti prisutnost sedlaste točke, pronaći rješenje za mješovitu strategiju, pronaći minimax strategiju igrača;
• napisati matematički model para problema dualnog linearnog programiranja, riješiti matričnu igru ​​koristeći metode: minimaks, simpleks metoda, grafička (geometrijska) metoda, Brownova metoda.

upute. Odaberite dimenziju matrice, kliknite Dalje. U novom dijaloškom okviru odaberite metodu za rješavanje igre matrice. Primjer popunjavanja. Rezultati izračuna prezentiraju se u izvješću u Word formatu.

Igra je matematički model stvarne konfliktne situacije. Konfliktna situacija između dva igrača naziva se igra parova. Pogodno je proučavati igru ​​parova s ​​nultim zbrojem ako je opisana u obliku matrice. Ova igra se zove matrica; matrica sastavljena od brojeva a ij naziva se plaćanje. U tablici su prikazane opcije za rješavanje igre zadane matricom plaćanja A.

Opis algoritma:

1. Na temelju analize platne matrice potrebno je utvrditi postoje li u njoj dominantne strategije te ih eliminirati.
2. Nađite gornju i donju cijenu igre i odredite ima li ova igra sedlu točku (donja cijena igre mora biti jednaka gornjoj cijeni igre).
3. Ako postoji sjedište, tada će optimalne strategije igrača, koje su rješenje igre, biti njihove čiste strategije koje odgovaraju sjedištu. Cijena igre jednaka je gornjoj i donjoj cijeni igre koje su međusobno jednake.
4. Ako igra nema sedlu točku, tada rješenje igre treba tražiti u mješovitim strategijama. Da bi se odredile optimalne mješovite strategije u m × n igrama, treba se koristiti simpleks metodom, nakon što se prvo problem igre preformulira u problem linearnog programiranja.

Predstavimo grafički algoritam za rješavanje matrične igre.

Slika - Shema rješavanja matrične igre.

Metode rješavanja matričnih igara u mješovitim strategijama

Dakle, ako nema sedla, igra se rješava pomoću mješovitih strategija i rješava se pomoću sljedećih metoda:

1. Rješavanje igre kroz sustav jednadžbi.
   Ako je dana kvadratna matrica nxn (n=m), tada se vektor vjerojatnosti može pronaći rješavanjem sustava jednadžbi. Ova metoda se ne koristi uvijek i primjenjiva je samo u određenim slučajevima (ako je matrica 2x2, tada se gotovo uvijek dobiva rješenje igre). Ako rješenje daje negativne vjerojatnosti, tada se ovaj sustav rješava pomoću simpleks metode.
2. Grafičko rješavanje igre.
   U slučajevima kada je n=2 ili m=2, matrična igra se može riješiti grafički.
3. Rješavanje matrične igre simpleks metodom.
   U ovom slučaju igra matrice se svodi na

Pristup rješavanju matričnih igara može se generalizirati na slučaj igara s nultim zbrojem u kojima je dobitak igrača zadan kao kontinuirana funkcija (beskonačna igra s nultim zbrojem).

Ova igra je predstavljena kao igra za dva igrača u kojoj igrač 1 bira broj x od mnogih X, igrač 2 bira broj y iz skupa 7, a nakon toga igrači 1 i 2 dobivaju dobitke redom U(x, y) i -U(x, y). Odabir određenog broja od strane igrača znači primjenu njegove čiste strategije koja odgovara tom broju.

Po analogiji s matričnim igrama može se nazvati neto niža cijena igre v (= max min U(x, y), i najvišu neto cijenu igre -v 2 =

min maks U(x, y). Tada, analogno, možemo pretpostaviti da ako za neke

na *

ili beskrajna antagonistička igra veličina V I v 2 postoje i jednaki su jedni drugima (“tj =v 2 =v), onda takva igra ima rješenje u čistim strategijama, tj. Optimalna strategija igrača 1 je odabrati broj x° e X, a igrač 2 - brojevi y 0 e 7, za koje Psst ( y 0) -v.

U ovom slučaju v naziva se neto cijena igre, a (x°, y 0) je sjedište beskonačne igre s nultim zbrojem.

Za matrične igre veličine v x I v 2 uvijek postoje, ali u beskonačnim antagonističkim igrama možda i ne postoje, tj. beskonačna igra s nultim zbrojem nije uvijek rješiva.

Kada se stvarna situacija formalizira u obliku beskrajne antagonističke igre, obično se odabire jedan strateški interval - jedan interval iz kojeg igrači mogu napraviti izbor (X - broj (strategija) po izboru igrača 1; -

broj (strategija) po izboru igrača 2). Tehnički, ovo pojednostavljuje rješenje, jer se jednostavnom transformacijom bilo koji interval može pretvoriti u jedinični interval i obrnuto. Ova igra se zove antagonistička igra na jediničnom kvadratu.

Na primjer, recimo da igrač 1 izabere broj x od mnogih X=, igrač 2 bira broj y iz skupa Y=. Nakon toga, igrač 2 plaća igraču 1 iznos Shchh, y) -2x 2 -y 2. Budući da igrač 2 nastoji minimizirati isplatu igrača 1, on određuje min ( 2x 2 - y 2) = 2x 2- 1, tj. u ovom slučaju = 1. Igrač 1 nastoji napraviti mtag

Simulirajte svoje plaćanje, stoga određuje maksimalni min Pssst, y)1 =

xGX y npr

- max (2x 2 - 1) = 2- 1 = 1, što se postiže kada x = 1.

Dakle, niža neto cijena igre v x - 1. Gornji čist

cijena igrev 2 =min - min (2 - y 2) = 2 - 1 = 1, tj. u ovome

>nprheh ti ej

igra v l =v 2 =l. Stoga je neto cijena igre v= 1, i sedla (x° = 1; y° = 1).

Pretpostavimo sada da Chi Y- otvorene intervale, tj. igrač 1 bira xeA"=(0; 1), igrač 2 bira ue 7= (0; 1). U ovom slučaju, odabir X, dovoljno blizu 1, igrač 1 bit će uvjeren da će dobiti isplatu ne manju od broja blizu "=1; odabirom y blizu 1, igrač 2 neće dopustiti da isplata igrača 1 značajno premaši neto trošak igre v= 1.

Stupanj blizine cijeni igre može se okarakterizirati brojem?>0. Stoga se u opisanoj igri može govoriti o optimalnosti čistih strategija x°= 1, 0 = 1 odnosno igrači 1 i 2 do proizvoljnog broja?>0. Točka (X", y E), gdje je x e e X, y (. eY, u beskonačnoj igri s nultim zbrojem zove se z-točka ravnoteže (s.-sjedlasta točka), ako za bilo koju strategiju xTiger 1, ue Tiger 2 vrijedi nejednakost Pssst, u.) - ? Š x r , u (.) U(x t ., u) + ?. U ovom slučaju, strategije x k. i u. se zovu s,-optimalnim strategijama. Jesu li ove strategije optimalne do? u smislu da ako odstupanje od optimalne strategije ne može donijeti nikakvu korist igraču, tada njegovo odstupanje od c-optimalne strategije može povećati njegov dobitak za najviše e.

Ako igra nema sedlu točku (c-saddle point), tj. rješenja u čistim strategijama, tada se optimalne strategije mogu tražiti među mješovitim strategijama, koje se koriste kao funkcije distribucije vjerojatnosti igrača koji koriste čiste strategije.

Neka F(x) je funkcija distribucije vjerojatnosti korištenja čistih strategija od strane igrača 1. Ako je broj E čista strategija igrača 1, tada F(x) = P(q gdje je P(q -X)- vjerojatnost da nasumično odabrana čista strategija E neće premašiti X. Funkcija distribucije vjerojatnosti korištenja čistih strategija r| razmatra se na sličan način. igrač 2: Q(y) = P(g .

Funkcije F(x) I Q(y) se zovu mješovite strategije odnosno igrači 1 i 2. Ako Fx) I Q(y) su diferencijabilne, tada postoje njihove derivacije, označene redom sa f(x) I q(y)(funkcije gustoće distribucije).

Općenito, diferencijal funkcije distribucije dF(x) izražava vjerojatnost da strategija S, je između x E, Isto tako za igrača 2: dQ(y) znači vjerojatnost da je njegova strategija p u intervalu y g| y+dy. Tada će isplata igrača 1 biti Shx, y) dF(x), a isplata igrača 2 je Shx, y) dQ(y).

Prosječna isplata igrača 1 s obzirom na to da igrač 2 koristi svoju čistu strategiju y, može se dobiti integracijom plaćanja preko svih mogućih vrijednosti X, oni. na jediničnom intervalu:

Prosječna isplata igrača 1, pod pretpostavkom da oba igrača koriste svoje mješovite strategije F(x) I Q(y), bit će jednaki

Analogno matričnim igrama određuju se optimalne mješovite strategije igrača i cijena igre: ako je par mješovitih strategija F*(x) I Q*(y) optimalne za igrače 1 i 2, zatim za sve mješovite strategije F(x) I Q(y) vrijede sljedeće relacije:

Ako igrač 1 odstupi od svoje strategije F*(x), tada se njegova prosječna isplata ne može povećati, ali se može smanjiti zbog racionalnih postupaka igrača 2. Ako se igrač 2 povuče iz svoje mješovite strategije Q*(y), onda se prosječna isplata igrača 1 može povećati, ali ne i smanjiti, zbog razumnijih postupaka igrača 1. Prosječna isplata E(F*, Q*), koju prima igrač 1 kada igrači primjenjuju optimalne mješovite strategije, odgovara cijeni igre.

Tada se donja cijena beskonačne igre s nultim zbrojem riješene u mješovitim strategijama može definirati kao v x= provjeriti

min E(FQ), a najviša cijena igrice je kao v 2 = min maks E(F, Q).

Q Q f

Ako takve mješovite strategije postoje F* (x) I Q*(y) redom za igrače 1 i 2, za koje se donja i gornja cijena igre podudaraju, tada F*(x) I Q*(y) Prirodno je nazvati optimalne mješovite strategije odgovarajućih igrača, a v=v x = v 2- po cijeni igre.

Za razliku od matričnih igara, rješenje igre s beskonačnim nultim zbrojem ne postoji za svaku funkciju Ššš, uh). Ali teorem je dokazan da svaka beskonačna igra s nultim zbrojem s kontinuiranom funkcijom isplate Ššš, uh) na jediničnom kvadratu ima rješenje (igrači imaju optimalne mješovite strategije), iako ne postoje opće metode za rješavanje beskonačnih igara s nultim zbrojem, uključujući kontinuirane igre. Međutim, antagonističke beskonačne igre s konveksnim i konkavnim kontinuiranim funkcijama isplate (zovu se respektivno konveksan I konkavne igre).

Razmotrimo rješenje igara s konveksnom isplatnom funkcijom. Rješenje igara s konkavnom isplatnom funkcijom je simetrično.

Konveksan funkcija/varijabla x na intervalu ( A; b) je funkcija za koju vrijedi nejednakost

Gdje Xx I x 2 - bilo koje dvije točke iz intervala (a; b);

X.1, A.2 > 0 i +X.2= 1.

Ako je za / h * 0 D 2 * 0, striktna nejednakost uvijek vrijedi

tada se poziva funkcija/ strogo konveksan na (a; b).

Geometrijski konveksna funkcija prikazuje luk čiji se graf nalazi ispod tetive koja ga spaja. Analitički, konveksnost dva puta diferencijabilne funkcije odgovara nenegativnosti (i u slučaju striktne konveksnosti, pozitivnosti) njezine druge derivacije.

Za konkavne funkcije svojstva su suprotna; za njih vrijedi nejednakost /(/4X1 +A.2X2) > Kf(xi) +)-ako(x 2) (> sa strogom konkavnošću), a druga derivacija / "(x)

Dokazano je da kontinuirana i strogo konveksna funkcija na zatvorenom intervalu ima minimalnu vrijednost samo u jednoj točki intervala. Ako Pssst, y) je kontinuirana funkcija isplata igrača 1 na jediničnom kvadratu i strogo konveksan duž na za bilo koji x, tada postoji jedinstvena optimalna čista strategija y=y° e za igrača 2, cijena igre određena je formulom

i značenje y 0 definira se kao rješenje sljedeće jednadžbe:

Ako funkcija Pssst, y) nije striktno konveksan u y, tada igrač 2 neće imati jedinu optimalnu čistu strategiju.

Svojstvo simetrije vrijedi i za strogo konkavne funkcije. Ako funkcija Pssst, y) kontinuirano u oba argumenta i strogo konkavno u x za bilo koji y, tada igrač 1 ima jedinstvenu optimalnu strategiju.

Cijena igre određena je formulom

a neto optimalna strategija x 0 igrača 1 određena je iz jednadžbe

Na temelju ovih svojstava beskonačnih igara s nultim zbrojem s konveksnim ili konkavnim funkcijama isplate, konstruirana je opća shema za rješavanje takvih igara na jediničnom kvadratu (he, ue). Ovu shemu prikazujemo samo za konveksne igre, budući da je za konkavne igre simetrična.

1. Provjerite funkciju Pssst, y) za konveksnost u y (druga parcijalna derivacija mora biti veća ili jednaka 0).

2. Iz relacije odredite y 0 v- min maks Ššš, uh) kao značenje

y, pri kojoj se postiže minimaks.

3. Pronađite rješenje jednadžbe v = U(x, y 0) i sastavite parove njegovih rješenja x I x 2, za koji

4. Pronađite parametar A iz jednadžbe

Parametar A određuje optimalnu strategiju igrača 1 i ima značenje vjerojatnosti njegovog izbora njegove čiste strategije x x. Vrijednost 1 - a ima značenje vjerojatnosti da igrač 1 izabere svoju čistu strategiju x 2.

Poslužimo se primjerom da demonstriramo korištenje ove sheme za rješavanje igre ove vrste. Neka je funkcija isplate u beskonačnoj igri s nultim zbrojem dana na jediničnom kvadratu i neka je jednaka Shchh, y) = =(x - y) 2 = x 2 - 2 xy ch-y 2.

1. Ova funkcija je kontinuirana u x I y, i stoga ova igra ima rješenje. Funkcija Ššš, uh) strogo konveksno duž y, jer

Prema tome, igrač 2 ima jedinu čistu optimalnu strategiju 0.

2. Imamo v= min max (x - y) 2. Za određivanje max (x 2 - 2xy Ch-y 2)

Nađimo redom prvu i drugu parcijalnu derivaciju funkcije plaćanja u odnosu na x:

Dakle funkcija U ima minimum za bilo koji y na x=y. To znači da kako xy - raste, tako da njegov maksimum treba postići u jednoj od krajnjih točaka x = 0 ili x = 1. Odredimo vrijednosti funkcije U na ovim točkama:

Zatim provjerite (x - y) 2 = max (y 2; 1 - 2y + y 2). Uspoređujući "interno"

maksimuma u vitičastim zagradama, to je lako vidjeti u 2 > 1 - - 2y+y 2, Ako y >*/ 2 i y 2 1 - 2 y+y 2, Ako y "/ 2. To je jasnije prikazano grafom (Sl. 2.5).

Riža. 2.5. Interni maksimumi funkcije plaćanja U(x, y) = (x- na) 2

Stoga je izraz (x - y) 2 dostiže maksimum pri x=0 ako y > 7 2, i na x= 1 ako na U 2:

Stoga, v= min ( min y 2 ; min (1 - y) 2 ). Svaki od

jutarnji minimumi dostižu se na y=*/ 2 i uzima vrijednost Y 4. Dakle, cijena igre r = Y 4, a optimalna strategija igrača 2:

3. Iz jednadžbe odredite optimalnu strategiju igrača 1 U(x, y 0)= v, oni. za ovu igru ​​(x - Y 2) 2 = Y 4. Rješenje ove jednadžbe SU X| =0, x 2 = 1.

Za njih su ispunjeni uvjeti

4. Odredimo parametar a, t.j. vjerojatnost da igrač 1 koristi svoju čistu strategiju X] = 0. Napravimo jednadžbu a-1 + (1 - a) (-1) = 0, iz koje je a = Y 2. Dakle, optimalna strategija igrača 1 je da s vjerojatnošću izabere svoje čiste strategije 0 i 1 1 / 2 svaki. Problem je riješen.

Najjednostavniji slučaj, detaljno razrađen u teoriji igara, je igra parova s ​​konačnim nultim zbrojem (antagonistička igra dviju osoba ili dviju koalicija). Razmotrimo igru ​​G u kojoj sudjeluju dva igrača A i B, koji imaju suprotne interese: dobitak jednog jednak je gubitku drugog. Budući da je dobitak igrača A jednak dobitku igrača B sa suprotnim predznakom, može nas zanimati samo dobitak igrača a. Naravno, A želi maksimizirati, a B želi minimizirati a.

Radi jednostavnosti, mentalno se identificirajmo s jednim od igrača (neka to bude A) i nazovimo ga "mi", a igrača B "protivnik" (naravno, iz ovoga ne proizlaze nikakve stvarne prednosti za A). Neka nam budu moguće strategije i protivnik - moguće strategije (takva igra se zove igra). Označimo naše dobitke ako mi koristimo strategiju i protivnik koristi strategiju

Tablica 26.1

Pretpostavimo da nam je isplata (ili prosječna isplata) a poznata za svaki par strategija. Tada je, u načelu, moguće konstruirati pravokutnu tablicu (matricu) koja ispisuje strategije igrača i odgovarajuće isplate (vidi tablicu 26.1).

Ako se sastavi takva tablica, onda kažu da je igra G svedena na matrični oblik (dovođenje igre u takav oblik samo po sebi već može biti težak zadatak, a ponekad i gotovo nemoguć, zbog goleme raznolikosti strategija ). Imajte na umu da ako je igra svedena na matrični oblik, tada je igra s više poteza zapravo svedena na igru ​​s jednim potezom - od igrača se traži samo jedan potez: odabrati strategiju. Ukratko ćemo označiti matricu igre

Pogledajmo primjer igre G (4X5) u matričnom obliku. Imamo četiri strategije na raspolaganju (na izbor), dok neprijatelj ima pet strategija. Matrica igre data je u tablici 26.2

Razmislimo koju bi strategiju mi ​​(igrač A) trebali koristiti? U Matrixu 26.2 postoji primamljiva isplata od "10"; dolazimo u iskušenje da odaberemo strategiju u kojoj ćemo dobiti ovu “slacicu”.

Ali čekaj: ni neprijatelj nije budala! Ako mi izaberemo strategiju, on će, nama u inat, izabrati strategiju, a mi ćemo dobiti neku jadnu “1”. Ne, ne možete birati strategiju! Kako biti? Očito, na temelju načela opreza (a to je osnovno načelo teorije igara), moramo odabrati strategiju pri kojoj je naš minimalni dobitak maksimalan.

Tablica 26.2

Ovo je takozvani “mini-max princip”: ponašajte se na takav način da, s obzirom na najgore ponašanje vašeg protivnika za vas, dobijete maksimalnu pobjedu.

Prepišimo tablicu 26.2 iu desnom dodatnom stupcu zapišimo minimalnu vrijednost dobitka u svakom retku (minimum retka); označimo ga za liniju a (vidi tablicu 26.3).

Tablica 26.3

Od svih vrijednosti (desni stupac), najveća (3) je istaknuta. Strategija tome odgovara. Odabirom ove strategije u svakom slučaju možemo biti sigurni da (za bilo koje ponašanje neprijatelja) nećemo pobijediti manje od 3. Ova vrijednost je naša zajamčena pobjeda; Pažljivo, ne možemo dobiti manje od ovoga, možda ćemo dobiti više).

Ovaj dobitak naziva se niža cijena igre (ili "maximin" - najveći od minimalnih dobitaka). Označit ćemo ga kao a. U našem slučaju

Sada uzmimo neprijateljevo gledište i razlog za njega. Nije on nekakav pijun, ali je i pametan! Pri odabiru strategije želio bi dati manje, ali mora računati na naše najgore ponašanje prema njemu. Ako odabere strategiju, mi ćemo mu odgovoriti i on će dati 10; ako odabere, mi ćemo mu odgovoriti i on će dati, itd. Dodat ćemo dodatni donji redak tablici 26.3 i zapisati maksimume stupaca u njemu. Očito, oprezan protivnik treba odabrati strategiju u kojoj je ta vrijednost minimalna (odgovarajuća vrijednost 5 istaknuta je u tablici 26.3) . Ova vrijednost P je vrijednost dobitka, više od koje nam razuman protivnik sigurno neće dati. Zove se gornja cijena igre (ili "mi-nimax" - minimum od maksimalnih dobitaka). U našem primjeru, i postiže se neprijateljskom strategijom

Dakle, temeljem načela opreza (pravilo reosiguranja “uvijek računaj na najgore!”) moramo odabrati strategiju A, a neprijatelja - strategiju. Takve strategije nazivamo “minimax” (iz principa minimax). Sve dok se obje strane u našem primjeru drže svojih minimax strategija, dobit će biti

Sada zamislimo na trenutak da smo saznali da neprijatelj slijedi strategiju. Ajde, kaznimo ga za ovo i izaberi strategiju, dobit ćemo 5, a to i nije tako loše. Ali neprijatelj također nije neuspjeh; dajte mu do znanja da je naša strategija , on će također požuriti s odabirom, smanjujući naše dobitke na 2, itd. (partneri su “navalili sa strategijama”). Ukratko, minimaks strategije u našem primjeru su nestabilne u odnosu na informacije o ponašanju druge strane; te strategije nemaju svojstvo ravnoteže.

Je li to uvijek slučaj? Ne, ne uvijek. Razmotrimo primjer s matricom danom u tablici 26.4.

U ovom primjeru, donja cijena igre jednaka je gornjoj cijeni: . Što iz ovoga slijedi? Minimaks strategije igrača A i B će biti stabilne. Sve dok ih se oba igrača pridržavaju, isplata je 6. Da vidimo što se događa ako (A) saznamo da se protivnik (B) pridržava strategije B?

Tablica 26.4

Ali neće se promijeniti apsolutno ništa, jer svako odstupanje od strategije može samo pogoršati našu situaciju. Isto tako, informacije koje primi protivnik neće ga natjerati da odstupi od svoje strategije.Par strategija ima svojstvo ravnoteže (uravnoteženi par strategija), a dobit (u našem slučaju 6) postignuta ovim parom strategija naziva se "sjedla točka matrice". Znak prisutnosti sedlaste točke i uravnoteženog para strategija je jednakost donje i gornje cijene igre; ukupna vrijednost naziva se cijena igre. Označit ćemo ga

Strategije (u ovom slučaju) kod kojih se taj dobitak ostvaruje nazivaju se optimalne čiste strategije, a njihova se ukupnost naziva rješenjem igre. U ovom slučaju za samu igru ​​kažu da je riješena u čistim strategijama. Obje strane A i B mogu dobiti svoje optimalne strategije, u kojima je njihov položaj najbolji mogući. I ako igrač A osvoji 6, a igrač B izgubi, pa, ovo su uvjeti igre: oni su korisni za A, a nepovoljni za B.

Čitatelj može imati pitanje: zašto se optimalne strategije nazivaju "čistim"? Gledajući malo unaprijed, odgovorit ćemo na ovo pitanje: postoje "mješovite" strategije, koje se sastoje u činjenici da igrač ne koristi samo jednu strategiju, već nekoliko, nasumično ih ispreplićući. Dakle, ako uz čiste dopustimo i mješovite strategije, svaka konačna igra ima rješenje - točku ravnoteže. Ali o tome će se tek raspravljati.

Prisutnost sedla u igri daleko je od toga da je pravilo, to je iznimka. Većina igara nema sedlo. Međutim, postoji vrsta igre koja uvijek ima sedlo i stoga se rješava u čistim strategijama. To su takozvane “igre s potpunom informacijom”. Igra s potpunom informacijom je igra u kojoj svaki igrač sa svakim osobnim potezom zna cjelokupnu pozadinu svog razvoja, odnosno rezultate svih prethodnih poteza, osobnih i slučajnih. Primjeri igara s potpunim informacijama uključuju: dame, šah, tic-tac-toe, itd.

U teoriji igara je dokazano da svaka igra s potpunom informacijom ima sedlišnu točku, te se stoga rješava u čistim strategijama. U svakoj igri s potpunim informacijama postoji par optimalnih strategija koje daju stabilnu isplatu jednaku cijeni igre i. Ako se takva igra sastoji samo od osobnih poteza, onda kada svaki igrač koristi svoju optimalnu strategiju, ona bi trebala završiti na vrlo određen način - s pobjedom jednakom cijeni igre. To znači da ako se zna rješenje igre, sama igra gubi smisao!

Uzmimo elementarni primjer igre s potpunom informacijom: dva igrača naizmjenično stavljaju novčiće na okrugli stol, nasumično birajući položaj središta novčića (međusobno preklapanje novčića nije dopušteno). Pobjeđuje onaj koji uloži zadnji novčić (kada nema mjesta za druge). Lako je vidjeti da je ishod ove igre, u biti, unaprijed određen. Postoji određena strategija koja osigurava pobjedu igrača koji prvi stavi novčić.

Naime, on prvo mora postaviti cent u središte stola, a zatim na svaki protivnikov potez odgovoriti simetričnim potezom. Očito, kako god se neprijatelj ponašao, ne može izbjeći gubitak. Potpuno je ista situacija sa šahom i igrama općenito s potpunom informacijom: bilo koja od njih, zapisana u matričnom obliku, ima sedlišnu točku, što znači da je rješenje u čistim strategijama, pa stoga ima smisla samo dok to rješenje ne nalazi. Recimo da šahovska partija ili uvijek završi pobjedom bijelog, ili uvijek pobjedom crnog, ili uvijek remijem, ali još ne znamo čime točno (na sreću ljubitelja šaha). Dodajmo i to: teško da ćemo to znati u dogledno vrijeme, jer je broj strategija toliki da je izuzetno teško (ako ne i nemoguće) dovesti igru ​​u matrični oblik i pronaći u njemu sedlišnu točku.

Sada se zapitajmo što učiniti ako igra nema sedlu točku: Pa, ako je svaki igrač prisiljen odabrati jednu jedinu čistu strategiju, onda nema što učiniti: moramo se voditi načelom minimaksa. Druga je stvar ako možete "miješati" svoje strategije, izmjenjivati ​​ih nasumično s nekim vjerojatnostima. Upotreba mješovitih strategija zamišljena je na sljedeći način: igra se ponavlja mnogo puta; prije svake partije u igri, kada igrač dobije osobni potez, on svoj izbor "povjerava" slučaju, "baca ždrijeb" i uzima strategiju koja se pojavila (već znamo kako organizirati ždrijeb iz prethodnog poglavlja ).

Mješovite strategije u teoriji igara model su promjenjivih, fleksibilnih taktika kada nitko od igrača ne zna kako će se protivnik ponašati u datoj igri. Ova se taktika (iako obično bez ikakvog matematičkog opravdanja) često koristi u kartaškim igrama. Napomenimo u isto vrijeme da je najbolji način da sakrijete svoje ponašanje od neprijatelja da mu date nasumičan karakter i, prema tome, ne znate unaprijed što ćete učiniti.

Dakle, razgovarajmo o mješovitim strategijama. Označit ćemo mješovite strategije igrača A i B, redom, gdje (tvoreći ukupno jedan) - vjerojatnost da igrač A koristi strategije - vjerojatnost da igrač B koristi strategije

U posebnom slučaju kada su sve vjerojatnosti osim jedne jednake nuli, a ova je jednaka jedinici, mješovita strategija prelazi u čistu.

Postoji temeljni teorem teorije igara: svaka konačna igra s nultim zbrojem za dvije osobe ima barem jedno rješenje - par optimalnih strategija, općenito izmiješanih, i odgovarajuću cijenu

Par optimalnih strategija koje tvore rješenje igre ima sljedeće svojstvo: ako se jedan od igrača pridržava svoje optimalne strategije, drugome ne može biti isplativo odstupiti od svoje. Ovaj par strategija tvori određenu ravnotežnu poziciju u igri: jedan igrač želi dobitak pretvoriti u maksimum, drugi - u minimum, svaki vuče u svom smjeru i, uz razumno ponašanje obojice, ravnoteža i stabilan dobitak v su uspostavljeni. Ako je onda igra korisna za nas, ako - za neprijatelja; kada je igra “poštena”, jednako korisna za oba sudionika.

Razmotrimo primjer igre bez sedla i dajmo (bez dokaza) njezino rješenje. Igra je sljedeća: dva igrača A i B istovremeno i bez riječi pokazuju jedan, dva ili tri prsta. Ukupan broj prstiju odlučuje o dobitku: ako je paran, A pobjeđuje i od B dobiva iznos jednak tom broju; ako je neparan, tada, naprotiv, A plaća B-u iznos jednak tom broju. Što bi igrači trebali učiniti?

Kreirajmo matricu igre. U jednoj igri svaki igrač ima tri strategije: pokaži jedan, dva ili tri prsta. Matrica 3x3 data je u tablici 26.5; dodatni desni stupac prikazuje minimume retka, a dodatni donji red prikazuje maksimume stupca.

Niža cijena igre odgovara strategiji. To znači da razumnim, pažljivim ponašanjem jamčimo da nećemo izgubiti više od 3. Mala utjeha, ali ipak bolja od, recimo, dobitka od 5, koji se nalazi u nekim ćelijama matrice. Loše je za nas, igrač L... Ali tješimo se: čini se da je položaj neprijatelja još gori: niža cijena igre je na. razumno ponašanje dat će nam najmanje 4.

Problem odlučivanja, razmatran u okviru sistemskog pristupa, sadrži tri glavne komponente: razlikuje sustav, upravljački podsustav i okolinu. Sada prelazimo na proučavanje problema odlučivanja u kojima na sustav utječe ne jedan, već više upravljačkih podsustava, od kojih svaki ima svoje ciljeve i mogućnosti djelovanja. Ovaj pristup donošenju odluka naziva se teorijskim, a matematički modeli odgovarajućih interakcija nazivaju se igre. Zbog razlika u ciljevima upravljačkih podsustava, kao i određenih ograničenja mogućnosti razmjene informacija među njima, ove interakcije su konfliktne prirode. Stoga je svaka igra matematički model sukoba. Ograničimo se na slučaj kada postoje dva upravljačka podsustava. Ako su ciljevi sustava suprotni, sukob se naziva antagonističkim, a matematički model takvog sukoba naziva se antagonistička igra..

U terminologiji teorije igara, 1. upravljački podsustav naziva se igrač 1, 2. upravljački podsustav - igrač 2, setovi

nazivaju se njihove alternativne radnje skupovi strategija ovi igrači. Neka x- mnoge strategije za igrača 1, Y- mnoge strategije

igrača 2. Stanje sustava jednoznačno je određeno izborom upravljačkih akcija podsustava 1 i 2, odnosno izborom strategija

x∈x I g∈Y. Neka F(x,g) - procjena korisnosti za igrača 1 tog stanja

sustav u koji ulazi kada igrač odabere 1 strategiju x I

strategija igrača 2 na. Broj F(x,g) Zove se pobijediti igrač 1 u situaciji ( x,g), i funkcija F- funkcija isplate igrača 1. Dobici igrača

1 je istovremeno i gubitak igrača 2, odnosno vrijednost koju prvi igrač želi povećati, a drugi – smanjiti. To je ono što je

manifestacija antagonističke prirode sukoba: interesi igrača su potpuno suprotni (što jedan dobije, drugi izgubi).

Antagonističku igru ​​prirodno definira sustav G=(X, Y, F).

Imajte na umu da je formalno igra s nultim zbrojem postavljena na gotovo isti način kao i zadatak donošenja odluke u uvjetima nesigurnosti - ako

identificirati upravljački podsustav 2 s okolinom. Sadržajna razlika između upravljačkog podsustava i okoline je ta

ponašanje prvog je svrhovito. Ako pri izradi matematičkog modela stvarnog sukoba imamo razloga (ili namjeru) okolinu smatrati neprijateljem čiji je cilj donijeti

maksimalnu štetu za nas, onda se takva situacija može prikazati u obliku antagonističke igre. Drugim riječima, igra nultog zbroja može se tumačiti kao ekstremni slučaj ZPR-a u uvjetima neizvjesnosti,

karakterizira tretiranje okoline kao protivnika s ciljem. U isto vrijeme, moramo ograničiti vrste hipoteza o ponašanju okoline.

Ovdje je najopravdanija hipoteza krajnjeg opreza, kada pri donošenju odluke računamo na najgore moguće postupanje okoline za nas.

Definicija. Ako x I Y konačne, tada se antagonistička igra naziva matrična igra. U matričnoj igri možemo pretpostaviti da x={1,…,n},

Y={1,…,m) i stavite aij=F(i J). Dakle, matrična igra je u potpunosti određena matricom A=(aij),i=1,…,n, j=1,…,m.

Primjer 3.1. Igra s dva prsta.

Dvije osobe istovremeno pokazuju jedan ili dva prsta i nazivaju broj 1 ili 2, što po mišljenju govornika znači broj

prste pokazane drugima. Nakon što se pokažu prsti i imenuju brojevi, dobitak se raspoređuje prema sljedećim pravilima:

ako su obojica pogodila ili obojica nisu pogodila koliko je prstiju protivnik pokazao, svačiji dobitak je nula; ako je samo jedan pogodio, tada protivnik plaća pogađaču iznos novca proporcionalan ukupno prikazanom broju

Ovo je igra matrice s nultim zbrojem. Svaki igrač ima četiri strategije: 1- pokaži 1 prst i pozovi 1, 2- pokaži 1 prst i pozovi 2, 3-

pokaži 2 prsta i pozovi 1, 4 - pokaži 2 prsta i pozovi 2. Zatim matrica isplate A=(aij), i= 1,…, 4, j= 1,…, 4 definira se na sljedeći način:

a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 u ostalim slučajevima.

Primjer 3.2. Igra tipa diskretnog dvoboja.

Problemi tipa duela opisuju, na primjer, tučnjavu između dva igrača,

od kojih svaki želi izvršiti neku jednokratnu radnju (puštanje serije robe na tržište, prijava za kupnju na aukciji) i odabire vrijeme za to. Neka se igrači kreću jedan prema drugom n korake. Nakon svakog poduzetog koraka, igrač može odabrati hoće li pucati ili ne pucati na neprijatelja. Svaka osoba može imati samo jedan udarac. Vjeruje se da je vjerojatnost da pogodite neprijatelja ako napredujete k n =5 ima oblik

Pošaljite svoj dobar rad u bazu znanja jednostavno je. Koristite obrazac u nastavku

Studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit će vam vrlo zahvalni.

Uvod

1. Teorijski dio

1.3 Redoslijed igre 2x2

1.4 Algebarska metoda

1.5 Grafička metoda

1.6 Igre 2xn ili mx2

1.7 Rješavanje igara matričnom metodom

2. Praktični dio

2.2 Igre 2xn i mx2

2.3 Metoda matrice

2.4 Brownova metoda

Analiza rezultata

Uvod

Igra s nultim zbrojem je igra s nultim zbrojem. Igra s nultim zbrojem je nekooperativna igra koja uključuje dva igrača čiji su isplate suprotni.

Formalno, antagonistička igra može biti predstavljena trojkom , gdje su X i Y skupovi strategija prvog i drugog igrača, F je funkcija isplate prvog igrača, koja svakom paru strategija dodjeljuje (x,y), gdje realni broj odgovara korisnosti prvi igrač u realizaciji date situacije.

Budući da su interesi igrača suprotni, funkcija F istovremeno predstavlja i gubitak drugog igrača.

Povijesno gledano, igre s nultim zbrojem su prva klasa matematičkih modela teorije igara kojima je kockanje opisano. Vjeruje se da je po ovom predmetu proučavanja teorija igara dobila svoje ime. Danas se antagonističke igre smatraju dijelom šire klase nekooperativnih igara.

1. Teorijski dio

1.1 Osnovne definicije i odredbe igre

Igru karakterizira sustav pravila koji određuju broj sudionika u igri, njihove moguće radnje i raspodjelu dobitaka ovisno o njihovom ponašanju i ishodima. Igračem se smatra jedan sudionik ili grupa sudionika igre koji imaju neke zajedničke interese koji se ne poklapaju s interesima drugih grupa. Stoga se svaki sudionik ne smatra igračem.

Pravila ili uvjeti igre određuju moguća ponašanja, izbore i poteze igrača u bilo kojoj fazi razvoja igre. Napraviti izbor za igrača znači odabrati jednu od njegovih opcija ponašanja. Igrač tada odabire potezima. Povući potez znači u određenoj fazi igre napraviti cijeli ili dio izbora odjednom, ovisno o mogućnostima koje daju pravila igre. Svaki igrač u određenoj fazi igre povlači potez prema svom izboru. Drugi igrač, znajući ili ne znajući za izbor prvog igrača, također povlači potez. Svaki igrač nastoji uzeti u obzir podatke o dosadašnjem razvoju igre, ako je takva mogućnost dopuštena pravilima igre.

Skup pravila koja jasno pokazuju igraču kakav izbor mora napraviti pri svakom potezu, ovisno o situaciji koja nastaje kao rezultat igre, naziva se igračeva strategija. Strategija u teoriji igara znači određeni cjeloviti plan akcije za igrača, koji pokazuje kako bi on trebao djelovati u svim mogućim slučajevima razvoja igre. Strategija znači ukupnost svih uputa za bilo koje stanje informacija dostupnih igraču u bilo kojoj fazi razvoja igre. Iz ovoga je već jasno da strategije mogu biti dobre i loše, uspješne i neuspješne itd.

Igra s nultim zbrojem bit će kada je zbroj dobitaka svih igrača u svakoj od njegovih igara jednak nuli, tj. u igri s nultim zbrojem ukupni kapital svih igrača se ne mijenja, već se preraspodjeljuje između igrača ovisno o rezultirajućim ishodima. Stoga se mnoge ekonomske i vojne situacije mogu promatrati kao igre s nultom sumom.

Konkretno, igra s nultim zbrojem između dva igrača naziva se antagonističkom, budući da su ciljevi igrača u njoj izravno suprotni: dobitak jednog igrača događa se samo na račun gubitka drugog.

1.1.1 Definicija, primjeri i rješenja matričnih igara u čistim strategijama

Matrična igra za dva igrača s nultim zbrojem može se smatrati sljedećom apstraktnom igrom za dva igrača.

Prvi igrač ima t strategija i =1, 2,…, t, drugi ima n strategija j = 1, 2,…, p. Svakom paru strategija (i, j) pridružen je broj a ij , izražavajući dobitak prvog igrača zbog drugog igrača ako prvi igrač koristi svoju i-tu strategiju, a drugi igrač koristi svoju j-tu strategiju.

Svaki igrač čini jedan potez: prvi igrač bira svoju i-tu strategiju (i = 1, 2,..., m), drugi bira svoju j-tu strategiju (j = 1, 2,..., n) , nakon čega prvi igrač dobiva dobitak a ij na račun drugog igrača (ako je ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Svaka strategija igrača i = 1, 2,…, t; j = 1, 2,…, n se često naziva čistom strategijom.

Matrična igra za dva igrača s nultim zbrojem od sada će se jednostavno zvati matrična igra. Očito matrična igra spada u antagonističke igre. Iz njezine definicije slijedi da je za definiranje matrične igre dovoljno zadati matricu A = (a ij) reda isplata prvog igrača.

Ako uzmemo u obzir matricu isplate

tada se igranje svake igre matrične igre s matricom A svodi na izbor prvog igrača i-tog retka i drugog igrača j-tog stupca, a prvi igrač prima (na račun drugog ) dobitak koji se nalazi u matrici A na sjecištu i-tog retka i j-tog stupca.

Da bi se stvarna konfliktna situacija formalizirala u obliku matrične igre, potrebno je identificirati i prenumerirati čiste strategije svakog igrača i stvoriti matricu isplate.

Sljedeća faza je određivanje optimalnih strategija i dobitaka igrača.

Glavna stvar u proučavanju igara je koncept optimalnih strategija igrača. Ovaj koncept intuitivno ima sljedeće značenje: strategija igrača je optimalna ako mu korištenje te strategije osigurava najveću zajamčenu pobjedu za sve moguće strategije drugog igrača. Na temelju ovih pozicija, prvi igrač ispituje matricu A svojih dobitaka pomoću formule (1.1) kako slijedi: za svaku vrijednost i (i = 1, 2,..., t) minimalna vrijednost dobitka se određuje ovisno o strategije koje koristi drugi igrač

(i = 1, 2,..., m) (1.2)

tj. određena je minimalna isplata za prvog igrača, pod uvjetom da on primijeni svoju i -tu čistu strategiju, zatim se iz tih minimalnih isplata pronađe strategija i = i 0 za koju će ta minimalna isplata biti maksimalna, tj.

Definicija. Broj b, određen formulom (1.3), naziva se donja neto cijena igre i pokazuje koji minimalni dobitak prvi igrač može zajamčiti za sebe primjenom svojih čistih strategija za sve moguće akcije drugog igrača.

Drugi igrač svojim optimalnim ponašanjem treba nastojati, ako je moguće, svojim strategijama minimizirati dobitke prvog igrača. Stoga, za drugog igrača kojeg nalazimo

tj. određuje se maksimalni dobitak prvog igrača, pod uvjetom da drugi igrač primijeni svoju j-tu čistu strategiju, zatim drugi igrač pronalazi svoju j = j 1 strategiju prema kojoj će prvi igrač dobiti minimalni dobitak, tj. pronalazi

Definicija. Broj b, određen formulom (1.5), naziva se neto gornja cijena igre i pokazuje koji najveći dobitak prvi igrač može zajamčiti za sebe kroz svoje strategije. Drugim riječima, primjenom svojih čistih strategija, prvi igrač može osigurati isplatu ne manju od b, a drugi igrač, primjenom svojih čistih strategija, može spriječiti prvog igrača da dobije više od b.

Definicija. Ako se u igri s matricom A donja i gornja neto cijena igre poklapaju, tj. b = c, tada se za ovu igru ​​kaže da ima sjedište u čistim strategijama i neto cijenu igre:

n = b = v (1.6)

Sjedište je par čistih strategija () prvog i drugog igrača, redom, na kojima se postiže jednakost

Koncept sedla ima sljedeće značenje: ako se jedan od igrača pridržava strategije koja odgovara sedlu, tada drugi igrač ne može učiniti ništa bolje nego da se pridržava strategije koja odgovara sedlu. Imajući na umu da najbolje ponašanje igrača ne bi trebalo dovesti do smanjenja njegovih dobitaka, a najgore ponašanje može dovesti do smanjenja njegovih dobitaka, ovi se uvjeti mogu matematički napisati u obliku sljedećih odnosa:

gdje su i, j bilo koje čiste strategije prvog i drugog igrača; (i 0 , j 0) su strategije koje tvore sedlo. U nastavku ćemo pokazati da je definicija sedlaste točke ekvivalentna uvjetima (1.8).

Prema tome, na temelju (1.8), sedlasti element je minimalan u i 0. retku i maksimalan u j 0. stupcu u matrici A. Pronalaženje sedlaste točke matrice A je jednostavno: u matrici A, minimalni element se sukcesivno nalazi u svaki red i provjerite je li taj element maksimum u svom stupcu. Ako je takav, onda je to sedlasti element, a njemu odgovarajući par strategija čini sedlastu točku. Par čistih strategija (i 0 , j 0) prvog i drugog igrača koji tvore sedlo i sedlasti element naziva se rješenjem igre.

Čiste strategije i 0 i j 0 koje tvore sedlo nazivaju se optimalne čiste strategije prvog i drugog igrača.

Teorem 1. Neka je f (x, y) realna funkcija dviju varijabli x A i y B i postoji

tada je b = c.

Dokaz. Iz definicije minimuma i maksimuma proizlazi da

Kako je na lijevoj strani (1.11) x proizvoljan, onda

Na desnoj strani nejednakosti (1.12) y je, dakle, proizvoljno

Q.E.D.

Konkretno, matrica () je poseban slučaj funkcije f (x, y), tj. ako stavimo x = i, y = j, = f (x, y), tada iz teorema 1 dobivamo da je donja mreža cijena ne premašuje gornju neto cijenu igranja u matrix igri.

Definicija. Neka je f (x, y) realna funkcija dviju varijabli x A i y B. Točka (x 0, y 0) naziva se sjedištem za funkciju f (x, y) ako su zadovoljene sljedeće nejednakosti

f (x, y 0) f (x 0, y 0)f (x 0, y) (1.14)

za bilo koje x A i y B.

1.2 Optimalne mješovite strategije i njihova svojstva

Proučavanje matrične igre počinje pronalaženjem njezine sedlaste točke u čistim strategijama. Ako matrična igra ima sedlo u čistim strategijama, tada proučavanje igre završava pronalaskom te točke. Ako u matričnoj igri ne postoji sedla točka u čistim strategijama, tada se mogu pronaći donja i gornja neto cijena ove igre, koje pokazuju da se prvi igrač ne bi trebao nadati dobitku većem od gornje cijene igre, i može budite sigurni da ćete dobiti pobjedu po nižoj cijeni igre. Takve preporuke u vezi s ponašanjem igrača u matričnoj igri bez sedlaste točke u čistim strategijama ne mogu zadovoljiti istraživače i praktičare. Poboljšanje rješenja matričnih igara treba tražiti u korištenju tajnosti korištenja čistih strategija i mogućnosti višestrukog ponavljanja igara u obliku igara. Tako se, na primjer, igra niz partija šaha, dame i nogometa i svaki put igrači primjenjuju svoje strategije na način da protivnici nemaju pojma o njihovom sadržaju, a na taj način u prosjeku ostvariti određene dobitke igrajući cijeli niz igara. Ti su dobici u prosjeku veći od donje cijene igre i manji od gornje cijene igre. Što je ta prosječna vrijednost veća, to je bolja strategija koju igrač koristi. Stoga se javila ideja da se čiste strategije primjenjuju nasumično, s određenom vjerojatnošću. Time je u potpunosti osigurana tajnost njihove uporabe. Svaki igrač može promijeniti vjerojatnosti korištenja svojih čistih strategija na takav način da maksimizira svoju prosječnu isplatu i usput dobije optimalne strategije. Ova ideja dovela je do koncepta mješovite strategije.

Definicija. Igračeva mješovita strategija je pun skup vjerojatnosti korištenja njegovih čistih strategija.

Prema tome, ako prvi igrač ima m čistih strategija 1, 2, … i, … m, tada je njegova mješovita strategija x skup brojeva x = (x 1, x 2, ..., x i,…, x m ) koji zadovoljavaju odnosima

x i 0 (i = 1, 2, ... , t), = 1. (1.15)

Slično, za drugog igrača, koji ima n čistih strategija, mješovita strategija y je skup brojeva y = (y 1, ..., y j, ... y n) koji zadovoljavaju relacije

y j 0 (j = 1, 2, ... , n), = 1. (1.16)

Budući da svaki put kada igrač koristi jednu čistu strategiju isključuje korištenje druge, čiste strategije su nekompatibilni događaji. Štoviše, oni su jedini mogući događaji.

Očito je da je čista strategija poseban slučaj mješovite strategije. Doista, ako se u mješovitoj strategiji bilo koja i-ta čista strategija primijeni s vjerojatnošću jedan, tada se sve ostale čiste strategije ne primjenjuju. A ova i-ta čista strategija poseban je slučaj mješovite strategije. Kako bi održao tajnost, svaki igrač primjenjuje vlastite strategije bez obzira na izbore drugog igrača.

Definicija. Prosječna isplata prvog igrača u matričnoj igri s matricom A izražava se kao matematičko očekivanje njegovih isplata.

E (A, x, y) = (1,20)

Očito, prosječna isplata prvog igrača je funkcija dva skupa varijabli x i y. Prvi igrač ima za cilj, mijenjajući svoje mješovite strategije x, maksimizirati svoju prosječnu isplatu E (A, x, y), a drugi igrač, kroz svoje mješovite strategije, nastoji učiniti E (A, x, y) minimalnim, tj. Za rješavanje igre potrebno je pronaći takve x, y, pri kojima se postiže gornja cijena igre.

1.3 Igra reda 22

Matrična igra reda 22 dana je sljedećom matricom isplate za prvog igrača:

Rješenje ove igre trebalo bi započeti pronalaženjem sedišta u čistim strategijama. Da biste to učinili, pronađite minimalni element u prvom redu i provjerite je li maksimum u njegovom stupcu. Ako takav element nije pronađen, tada se drugi red provjerava na isti način. Ako se takav element nalazi u drugom redu, onda je to sedlo.

Pronalaženje elementa sedla, ako postoji, završava proces pronalaženja njegovog rješenja, jer je u ovom slučaju pronađena cijena igre - element sedla i točka sedla, tj. par čistih strategija za prvi i drugi igrač, čineći optimalne čiste strategije. Ako u čistim strategijama ne postoji sedlo, onda u mješovitim strategijama treba pronaći sedlo, koje prema glavnom teoremu matričnih igara nužno postoji.

Označimo s x = (x 1 , x 2), y = (y 1 , y 2) mješovite strategije prvog i drugog igrača. Podsjetimo se da x 1 znači vjerojatnost da će prvi igrač koristiti svoju prvu strategiju, a x 2 = 1 - x 1 je vjerojatnost da će on koristiti svoju drugu strategiju. Slično za drugog igrača: 1 je vjerojatnost da će koristiti prvu strategiju, 2 = 1 - 1 je vjerojatnost da će koristiti drugu strategiju.

Prema korolariji teorema, da bi mješovite strategije x i y bile optimalne, potrebno je i dovoljno da za nenegativne x 1, x 2, y 1, y 2 vrijede sljedeće relacije:

Pokažimo sada da ako matrična igra nema sedlu u čistim strategijama, onda se ove nejednakosti moraju pretvoriti u jednakosti:

Doista. Neka igra nema sedlo u čistim strategijama, tada optimalne vrijednosti mješovitih strategija zadovoljavaju nejednakosti

0<<1, 0<< 1,

0< <1, 01. (1.25)

Pretpostavimo da su obje nejednakosti iz (1.22) stroge

tada je prema teoremu y 1 = y 2 = 0, što je u suprotnosti s uvjetima (1.25).

Slično se dokazuje da obje nejednakosti iz (1.23) ne mogu biti stroge nejednakosti.

Pretpostavimo sada da jedna od nejednakosti (1.22) može biti stroga, na primjer prva

To znači da je prema teoremu y 1 = 0, y 2 = 1. Prema tome, iz (1.23) dobivamo

Ako su obje nejednakosti (1.24) stroge, tada je, prema teoremu, x 1 = x 2 = 0, što je u suprotnosti s (1.25). Ako je a 12 a 22, tada je jedna od nejednakosti (1.27) stroga, a druga je jednakost. Štoviše, jednakost će vrijediti za veći element od 12 i 22, tj. jedna nejednakost iz (1.27) mora biti stroga. Na primjer 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Dakle, pokazuje se da ako matrična igra nema sedlo u čistim strategijama, tada se za optimalne strategije prvog igrača nejednakosti (1.22) pretvaraju u jednakosti. Slično razmišljanje o nejednakostima (1.23) dovest će do činjenice da u ovom slučaju nejednakosti (1.23) moraju biti jednakosti.

Dakle, ako matrična igra reda 22 nema sedlu točku, tada se optimalne mješovite strategije igrača i cijena igre mogu odrediti rješavanjem sustava jednadžbi (1.24). Također je utvrđeno da ako u matričnoj igri reda 2x2 jedan od igrača ima optimalnu čistu strategiju, tada i drugi igrač ima optimalnu čistu strategiju.

Prema tome, ako matrična igra nema sjedište u čistim strategijama, onda mora imati rješenje u mješovitim strategijama, koje se određuju iz jednadžbi (1.24). Rješenje sustava (1.25)

1.4 Algebarska metoda

Dva su moguća slučaja rješavanja problema algebarskom metodom:

1. matrica ima sedlo;

2. matrica nema sedlu.

U prvom slučaju, rješenje je par strategija koje čine sedlo točke igre. Razmotrimo drugi slučaj. Rješenja ovdje treba tražiti u mješovitim strategijama:

Pronađimo strategije i... Kada prvi igrač koristi svoju optimalnu strategiju, drugi igrač može, na primjer, primijeniti dvije takve čiste strategije

Štoviše, zbog svojstva, ako jedan od igrača koristi optimalnu mješovitu strategiju, a drugi koristi bilo koju čistu strategiju uključenu u njegovu optimalnu mješovitu strategiju s vjerojatnošću koja nije jednaka nuli, tada matematičko očekivanje pobjede uvijek ostaje nepromijenjeno i jednako na cijenu igre, tj.

Dobici u svakom od ovih slučajeva moraju biti jednaki cijeni igre V. U ovom slučaju vrijede sljedeće relacije:

Sustav jednadžbi sličan (2.5), (2.6) može se konstruirati za optimalnu strategiju drugog igrača:

Uzimajući u obzir uvjet normalizacije:

Riješimo jednadžbu (1.37) - (1.41) zajedno s obzirom na nepoznanice, možete riješiti ne sve odjednom, već tri odjednom: odvojeno (1.36), (1.38), (1.40) i (1.37), ( 1.39), (1.41). Kao rezultat rješenja dobivamo:

1.5 Grafička metoda

Približno rješenje igre 22 može se vrlo jednostavno dobiti grafičkom metodom. Njegova suština je sljedeća:

Slika 1.1 - nalaženje odsječka jedinične duljine

Odaberite dio jedinične duljine na x-osi. Njegov lijevi kraj će prikazati prvu strategiju prvog igrača, a desni kraj će predstavljati drugu. Sve međutočke odgovaraju mješovitim strategijama prvog igrača, a duljina segmenta desno od točke jednaka je vjerojatnosti korištenja prve strategije, a duljina segmenta lijevo od je vjerojatnost korištenja drugu strategiju prvog igrača.

Nacrtane su dvije osi I-I i II-II. Dobitke ćemo staviti na I-I kada prvi igrač koristi prvu strategiju, na II-II kada koristi drugu strategiju. Neka, na primjer, drugi igrač primijeni svoju prvu strategiju, tada vrijednost treba iscrtati na osi I-I, a vrijednost treba iscrtati na osi II-II

Za bilo koju mješovitu strategiju prvog igrača, njegov dobitak će biti određen vrijednošću segmenta. Linija I-I odgovara primjeni prve strategije od strane drugog igrača; nazvat ćemo je prvom strategijom drugog igrača. Slično, možete konstruirati drugu strategiju drugog igrača. Tada će, općenito, grafički prikaz matrice igre imati sljedeći oblik:

Slika 1.2 - pronalaženje cijene igre

Međutim, treba napomenuti da je ova konstrukcija izvedena za prvog igrača. Ovdje je duljina segmenta jednaka cijeni igre V.

Linija 1N2 naziva se donja granica dobitka. Ovdje možete jasno vidjeti da točka N odgovara maksimalnom iznosu zajamčenog dobitka prvog igrača.

Općenito govoreći, strategija drugog igrača također se može odrediti iz ove brojke, na primjer na sljedeće načine. Na I-I osi:

odnosno na osi II-II

Međutim, strategija drugog igrača može se odrediti slično kao što se to radi za prvog igrača, tj. izgraditi takav grafikon.

Slika 1.3 - određivanje strategije drugog igrača

Ovdje je linija 1N2 gornja granica gubitka. Točka N odgovara minimalnom mogućem gubitku drugog igrača i određuje strategiju.

Ovisno o specifičnim vrijednostima koeficijenata matrice, grafikoni mogu imati drugačiji oblik, na primjer, ovo:

Slika 1.4 - određuje optimalnu strategiju prvog igrača

U takvoj situaciji optimalna strategija prvog igrača je čista:

1.6 Igre 2n ili m2

U igrama reda 2n prvi igrač ima 2 čiste strategije, a drugi igrač ima n čistih strategija, tj. Matrica isplate prvog igrača ima oblik:

Ako takva igra ima sedlo, onda ju je lako pronaći i dobiti rješenje.

Pretpostavimo da igra ima sedlaste točke. Tada je potrebno pronaći takve mješovite strategije i, sukladno tome, prvog i drugog igrača i cijenu igre v, koje zadovoljavaju relacije:

Budući da igra nema sedlu točku, nejednadžba (1.54) zamijenjena je nejednakostima

Za rješavanje sustava (1.56), (1.55), (1.53) preporučljivo je koristiti grafičku metodu. U tu svrhu uvodimo oznaku lijeve strane nejednakosti (1.53)

matrična igra matematički model

ili, stavljajući iz (1.55) i provodeći jednostavne transformacije, dobivamo

gdje je prosječna isplata prvog igrača, pod uvjetom da koristi svoju mješovitu strategiju, a drugog svoju j-tu čistu strategiju.

Prema izrazu, svaka vrijednost j=1, 2, …, n odgovara ravnoj liniji u pravokutnom koordinatnom sustavu.

Cilj drugog igrača je minimizirati dobitke prvog igrača odabirom njegovih strategija. Stoga računamo

gdje je donja granica skupa ograničenja. Na slici 1.6 debelom linijom prikazan je graf funkcije.

Objavljeno na http://www.allbest.ru/

Slika 1.6 - graf funkcije

Cilj prvog igrača je maksimizirati svoje dobitke putem izbora, tj. izračunati

Na slici 1.6 točka označava najveću vrijednost koja se dobiva na. Cijena igre je jer:

Na taj način se grafički određuje optimalna mješovita strategija prvog igrača i par čistih strategija drugog igrača, koje u sjecištu čine točku.Slika 1.6 prikazuje 2. i 3. strategiju drugog igrača. Za takve strategije nejednakosti (1.53) se pretvaraju u jednakosti. Na slici 1.6 to su strategije j=2, j=3.

Sada možemo riješiti sustav jednadžbi

te točno odrediti vrijednosti i (grafički se određuju približno). Zatim, stavljajući sve vrijednosti za one j za koje ne čine točku, rješavajući sustav jednadžbi (1.56) Za primjer prikazan na slici 1.6, ovo je sljedeći sustav:

a ostatak Ovaj sustav se može riješiti nagibom Ako za neki j=j 0 strategije drugog igrača tvore točku M 0 i tada je maksimalna vrijednost donje granice skupova ograničenja prikazana segmentom paralelnim s os U ovom slučaju, prvi igrač ima beskonačno mnogo optimalnih vrijednosti i cijenu igre Ovaj slučaj je prikazan na slici 1.7, gdje segment MN prikazuje gornje granice, optimalne vrijednosti su unutar granica Drugi igrač ima čistu optimalnu strategiju j=j 0 .

Matrične igre reda m2 mogu se rješavati i grafičkom metodom. Isplatna matrica prvog igrača u ovom slučaju ima oblik

Mješovite strategije prvog i drugog igrača definirane su slično kao u slučaju igara reda 2n. Neka je vrijednost od 0 do 1 iscrtana duž horizontalne osi, a vrijednost prosječnog dobitka) prvog igrača duž vertikalne osi, pod uvjetima da prvi igrač primjenjuje svoju čistu i-tu strategiju (i=1, 2, ..., m), drugi - njegova mješovita strategija (y 1, 1- y 1) =y. Na primjer, kada je m=4 grafički) može se prikazati kao što je prikazano na slici 1.7.

Slika 1.7 - grafikon funkcije)

Prvi igrač pokušava maksimizirati svoju prosječnu isplatu, pa nastoji pronaći

Funkcija je predstavljena debelom linijom i predstavlja gornju granicu skupa ograničenja. Drugi igrač pokušava minimizirati odabirom svoje strategije, tj. vrijednost odgovara

Na slici je vrijednost označena točkom. Drugim riječima, određuju se dvije strategije prvog igrača i vjerojatnost drugog igrača pri kojima se postiže jednakost

Iz slike vidimo da je cijena igre ordinata boda, vjerojatnost je apscisa boda. Za preostale čiste strategije prvog igrača u optimalnoj mješovitoj strategiji mora ().

Tako rješavanjem sustava (1.69) dobivamo optimalnu strategiju drugog igrača i cijenu igre. Pronalazimo optimalnu mješovitu strategiju za prvog igrača rješavanjem sljedećeg sustava jednadžbi:

1.7 Matrična metoda za rješavanje igara

Oznake:

Bilo koja kvadratna podmatrica matrice reda

Matrica(1);

Matrica transponirana u;

Matrica adjungirana na B;

- (1) matrica dobivena iz X brisanjem elemenata koji odgovaraju recima koji su obrisani nakon prijema;

- (1) matrica dobivena brisanjem elemenata koji odgovaraju recima koji su obrisani po primitku.

Algoritam:

1. Izaberite kvadratnu podmatricu matrice reda () i izračunajte

2. Ako ima ili, tada odbacite pronađenu matricu i pokušajte s drugom matricom.

3. Ako (), (), izračunavamo i konstruiramo X i iz i, dodajući nule na odgovarajuća mjesta.

Provjera jesu li nejednakosti zadovoljene

za sve (1,75)

i nejednakosti

za sve (1,76)

Ako jedan od odnosa nije zadovoljen, onda pokušavamo s drugim. Ako su sve relacije valjane, onda je X i tražena rješenja.

1.8 Metoda sukcesivne aproksimacije cijene igre

Pri proučavanju situacija u igri često se može dogoditi da nema potrebe za dobivanjem točnog rješenja igre ili je iz nekog razloga nemoguće ili vrlo teško pronaći točnu vrijednost cijene igre i optimalne mješovite strategije. Zatim možete koristiti približne metode za rješavanje matrične igre.

Opišimo jednu od tih metoda - metodu sukcesivne aproksimacije cijene igre. Broj izračunat korištenjem metode povećava se približno proporcionalno broju redaka i stupaca matrice isplate.

Suština metode je sljedeća: igra se mentalno igra više puta, tj. uzastopno, u svakoj igri igrač bira strategiju koja mu daje najveće ukupne (ukupne) dobitke.

Nakon takve provedbe nekih igara izračunava se prosječna vrijednost dobitaka prvog igrača i gubitaka drugog igrača, a njihov aritmetički prosjek uzima se kao približna vrijednost cijene igre. Metoda omogućuje pronalaženje približne vrijednosti optimalne mješovite strategije oba igrača: potrebno je izračunati učestalost primjene svake čiste strategije i uzeti je kao približnu vrijednost u optimalnoj mješovitoj strategiji odgovarajućeg igrača.

Može se dokazati da će se s neograničenim povećanjem broja programskih igara prosječni dobitak prvog igrača i prosječni gubitak drugog igrača neograničeno približavati cijeni igre, a približne vrijednosti mješovitih strategija u slučaj kada igra ima jedinstveno rješenje težit će optimalnim mješovitim strategijama svakog igrača. Općenito govoreći, tendencija približnih vrijednosti iznad ovih vrijednosti da se približe stvarnim vrijednostima je spora. Međutim, ovaj je proces lako mehanizirati i time pomoći u dobivanju rješenja igre sa potrebnim stupnjem točnosti čak i s matricama isplata relativno velikog reda.

2. Praktični dio

Par odlučuje gdje će otići u šetnju i provesti vrijeme korisno za oboje.

Djevojka odluči otići u šetnju parkom kako bi udahnula svjež zrak, a navečer pogledati film u najbližem kinu.

Tip predlaže odlazak u tehnološki park, a zatim gledanje utakmice lokalnih klupskih nogometaša na središnjem stadionu.

U skladu s tim, trebate pronaći koliko će vremena trebati da postigne cilj jednog od igrača. Pobjednička matrica će izgledati ovako:

Tablica 1. Isplatna matrica

Strategije

Od 1 2 , Očito, ova igra nema sedlo u čistim strategijama. Stoga koristimo sljedeće formule i dobivamo:

Objavljeno na http://www.allbest.ru/

2.2 Igra 2xn i mx2

Problem 1(2xn)

Uzgajaju se dvije žitarice za suhu i vlažnu klimu.

A prirodno stanje može se smatrati: suho, vlažno, umjereno.

Objavljeno na http://www.allbest.ru/

Najveća vrijednost M() postiže se u točki M, formiranoj sjecištem linija koje odgovaraju j=1, j"=2. Prema tome, pretpostavljamo:

Problem 2 (mx2)

Momak i djevojka razmatraju mogućnosti gdje otići za vikend.

Izbor mjesta za odmor može se zamisliti kao: park, kino, restoran.

Objavljeno na http://www.allbest.ru/

Najveća vrijednost M() postiže se u točki E, formiranoj sjecištem linija koje odgovaraju j=1, j"=2. Prema tome, pretpostavljamo:

Da bi se odredila vrijednost v, moraju se riješiti sljedeće jednadžbe:

2.5 Metoda matrice

Dva restorana (ugostiteljska objekta) koji se međusobno natječu pružaju sljedeće skupove usluga. Prvi restoran nalazi se u centru, a drugi na periferiji grada.

Centralni restoran uključuje sljedeće usluge:

1) skuplja i kvalitetnija usluga kupcima;

2) jela su usmjerena na francusku kuhinju;

Drugi restoran nudi:

1) jeftina i kvalitetna usluga;

2) jelovnik kombinira razne poznate kuhinje svijeta;

3) također stalne akcije i popusti;

4) dostavlja i prima narudžbe za dostavu na kućnu adresu.

U skladu sa zadatkom, dobit za jedan dan između dva restorana će se rasporediti na sljedeći način:

Tablica 2. Isplatna matrica

Strategije

Rješavanje igre oblika matričnom metodom:

Postoji šest podmatrica i:

Razmotrite matricu:

x 1 = ? 0, x 2 = ? 0

Budući da je x 2 =< 0, то мы отбрасываем.

Razmotrimo sada matricu:

x 1 = ? 0, x 2 = ? 0

Cijena igre.

Ovaj omjer je u suprotnosti sa zahtjevom i stoga nije prikladan.

Razmotrimo sada matricu:

x 1 = , x 2 = ? 0,

y 1 =< 0, y 2 = ? 0.

Kako je y 1 =< 0, то мы отбрасываем и.

Razmotrimo sada matricu:

x 1 = , x 2 = 0, budući da je x 2 = 0, tada odbacujemo i.

Razmotrimo sada matricu:

x 1 = , x 2 = ? 0. Kako je x 1 = 0, odbacujemo i.

Razmotrimo sada matricu:

x 1 = , x 2 =, y 1 = , y 2 =, pa nastavljamo dalje:

x 1 = , x 2 = , y 1 = , y 2 = ili

Cijena igre.

Sada se provjeravaju osnovni odnosi:

Objavljeno na http://www.allbest.ru/

Odgovor: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,.

Brown metoda

Na zahtjev radnika određenog poduzeća sindikat pregovara s upravom o organiziranju toplog ručka o trošku poduzeća. Sindikat radnika želi osigurati da ručak bude što kvalitetniji, a time i skuplji. Menadžment tvrtke ima suprotne interese. Na kraju su se strane složile oko sljedećeg. Sindikat (igrač 1) odabire jednu od tri tvrtke (A 1, A 2, A 3) koje isporučuju tople obroke, a uprava tvrtke (igrač 2) bira set posuđa od tri moguće opcije (B 1, B 2). , B 3) . Nakon potpisivanja ugovora, sindikat generira sljedeću matricu plaćanja čiji elementi predstavljaju cijenu seta posuđa:

Neka je igra definirana sljedećom matricom isplate:

Pretpostavimo da je drugi igrač izabrao svoju drugu strategiju, tada će prvi dobiti:

2, ako koristi svoju prvu strategiju,

3 ako koristi svoju 3. strategiju.

Dobivene vrijednosti su sažete u tablici 1.

Tablica 3. Strategija drugog igrača

Broj serije	Strategija igrača 2	Pobjeda 1. igrača

Iz tablice 3 može se vidjeti da će s 2. strategijom drugog igrača prvi dobiti najveću isplatu 3 koristeći svoju 2. ili 3. strategiju. Budući da prvi igrač želi ostvariti maksimalnu pobjedu, on na 2. strategiju drugog igrača odgovara svojom 2. strategijom. S drugom strategijom prvog igrača, drugi će izgubiti:

1 ako koristi svoju prvu strategiju,

3, ako koristi svoju drugu strategiju,

4 ako koristi svoju 3. strategiju.

Tablica 4. Strategija prvog igrača

Broj serije	Strategija prvog igrača	2. igrač gubi

Iz tablice 2 se vidi da će kod 2. strategije prvog igrača, drugi igrač imati najmanji gubitak od 1 ako primijeni svoju 1. strategiju. Budući da drugi igrač želi manje izgubiti, kao odgovor na 2. strategiju prvog igrača, on će koristiti svoju 1. strategiju. Dobiveni rezultati sažeti su u tablici 5.

Tablica 5. Strategije prvog, odnosno drugog igrača

Broj serije

Strategija igrača 2

Ukupni dobici 1. igrača

Strategija prvog igrača

U tablici 5 u stupcu strategije drugog igrača u drugom retku nalazi se broj 1, koji označava da je u drugoj igri korisno da drugi igrač koristi svoju 1. strategiju; u stupcu je najveći prosječni dobitak 3 prvog igrača, koji je dobio u prvoj igri; stupac w sadrži najmanji prosječni gubitak od 1 koji je primio drugi igrač u prvoj igri; stupac v sadrži aritmetičku sredinu v = (u + w) - tj. približnu vrijednost cijene igre dobivenu kao rezultat gubitka jedne partije u igri. Ako drugi igrač primijeni svoju 1. strategiju, tada će prvi dobiti 3, 1, 2, redom, sa svojom 1., 2., 3. strategijom, a ukupni dobici prvog igrača za obje igre bit će:

2 + 3=5 sa svojom prvom strategijom,

3 + 1=4 sa svojom drugom strategijom,

3 + 2=5 sa svojom trećom strategijom.

Ovi ukupni dobici bilježe se u drugom redu tablice. 3 i u stupcima koji odgovaraju strategijama prvog igrača: 1, 2, 3.

Od svih ukupnih dobitaka, najveći je 5. Dobiva se 1. i 3. strategijom prvog igrača, a zatim može izabrati bilo koju od njih; Recimo, u takvim slučajevima, kada postoje dva (ili više) identična ukupna dobitka, odaberite strategiju s najmanjim brojem (u našem slučaju, moramo uzeti 1. strategiju).

S 1. strategijom prvog igrača, drugi će izgubiti 3, 2, 3, redom, u odnosu na svoju 1., 2., 3. strategiju, a ukupni gubitak drugog igrača za obje igre bit će:

1 + 3=4 sa svojom prvom strategijom,

3 + 2=5 sa svojom drugom strategijom,

4 + 3=7 sa svojom trećom strategijom.

Ovi ukupni gubici bilježe se u drugom retku tablice. 5 i u stupcima koji odgovaraju 1., 2., 3. strategiji drugog igrača.

Od svih ukupnih gubitaka drugog igrača, najmanji je 4. Dobiva se njegovom 1. strategijom, dakle, u trećoj igri drugi igrač mora primijeniti svoju 1. strategiju. Najveći ukupni dobitak prvog igrača u dvije igre, podijeljen s brojem igara, stavlja se u stupac, tj.; Stupac w sadrži najmanji ukupni gubitak drugog igrača u dvije igre, podijeljen s brojem partija, tj.; u stupac v stavlja se aritmetička sredina ovih vrijednosti, tj. = Ovaj broj se uzima kao približna vrijednost cijene igre s dvije "odigrane" igre.

Tako se dobiva sljedeća tablica 4, za dvije utakmice.

Tablica 6. Ukupni dobici i gubici igrača nakon dvije odigrane utakmice

Strategija igrača 2

Ukupni dobici 1. igrača

Strategija prvog igrača

Potpuni gubitak 2. igrača

U trećem redu tablice 6 u stupcu strategija drugog igrača nalazi se broj 1, koji označava da u trećoj igri drugi igrač mora primijeniti svoju 1. strategiju. U ovom slučaju, prvi igrač osvaja 3, 1, 2, koristeći svoju 1., 2., 3. strategiju redom, a njegov ukupni dobitak u tri igre bit će:

3 + 5 = 8 sa svojom prvom strategijom,

1 +4 = 5 sa svojom drugom strategijom,

2 + 5 = 7 sa svojom trećom strategijom.

Ovi ukupni dobici prvog igrača bilježe se u trećem retku tablice 6 i stupcima koji odgovaraju njegovim strategijama 1, 2, 3. Budući da je najveći ukupni dobitak 8 prvog igrača postignut s 1. strategijom, odabire se 1. prema tome.

S 1. strategijom prvog igrača, drugi će izgubiti 3, 1, 2, redom, u odnosu na svoju 1., 2., 3. strategiju, a ukupni gubitak drugog igrača za obje igre bit će:

3 + 4=7 sa svojom prvom strategijom,

2 + 5=7 sa svojom drugom strategijom,

3 + 7 = 10 sa svojom trećom strategijom.

Ovi ukupni gubici bilježe se u trećem retku tablice. 6 i u stupcima koji odgovaraju 1., 2., 3. strategiji drugog igrača. Od svih njegovih ukupnih gubitaka, 7 je najmanji i dobiva se njegovom 1. i 2. strategijom, tada drugi igrač treba primijeniti svoju 1. strategiju.

U tablici 6 u trećem redu u stupcu i bilježi najveći ukupni dobitak prvog igrača u tri igre, podijeljen s brojem igre, tj.; u stupac w stavlja se najmanji ukupni gubitak drugog igrača u tri partije podijeljen s brojem partija, tj.; stupac v sadrži njihovu aritmetičku sredinu

Tako dobivamo tablicu. 7 za tri utakmice.

Tablica 7. Ukupni dobici i gubici igrača nakon tri odigrane utakmice

Broj serije

Strategija igrača 2

Ukupni dobici 1. igrača

Strategija prvog igrača

Potpuni gubitak 2. igrača

Tablica 8. Konačni stol nakon dvadeset odigranih partija

Broj serije

Strategija igrača 2

Ukupni dobici 1. igrača

Strategija prvog igrača

Potpuni gubitak 2. igrača

Sa stola Na slikama 7 i 8 može se vidjeti da se u 20 izgubljenih partija strategije 1, 2, 3 za prvog igrača pojavljuju 12, 3, 5 puta redom, dakle, njihove relativne učestalosti su redom jednake; strategije 1, 2, 3 za drugog igrača se pojavljuju 7, 11, 2 puta redom, stoga su njihove relativne učestalosti redom jednake; približna cijena igrice. Ova aproksimacija je prilično dobra.

Konačno, imajte na umu da ako igra ima više od jednog rješenja, tada će se aproksimacije cijene igre i dalje neograničeno približavati stvarnoj cijeni igre, a relativne učestalosti strategija igrača više se neće nužno približavati pravim optimalnim igračima mješovite strategije.

Analiza rezultata

U ovom kolegiju obrađeno je gradivo pronalaženja rješenja igara s nultim zbrojem grafičkom, matričnom metodom i metodom sukcesivne aproksimacije cijene igre. Pronađene su optimalne strategije prvog i drugog igrača, kao i cijena igranja u igrama 2x2, 2xn i mx2, kao iu igrama koje koriste matričnu metodu i Brownovu metodu.

Na primjeru para simulirana je igra 2x2 koja je rješavana algebarskom i grafičkom metodom. Rješavajući igru ​​algebarski, rješenje pokazuje da će korištenjem svojih optimalnih mješovitih strategija prvi i drugi igrač provesti 4,6 sati zajedno. Grafičko rješenje zadatka dobiveno je s malom greškom i iznosilo je 4,5 sata.

Također su simulirana dva problema 2xn i mx2. U problemu 2xn razmatrana je poljoprivredna kultura i strategija pokazuje da je bolje posaditi polje 50 prema 50, a cijena igre bila je 3,75 milijuna rubalja. A u problemu mx2 razmatran je par čija je strategija pokazala da je jeftinije ići u park i kino, a cijena bi bila 4,3 rublje.

Problem je modeliran za matričnu metodu, u kojoj su razmatrana dva restorana, rješenje problema pokazalo je da će pri korištenju njegove optimalne mješovite strategije dobit prvog restorana biti 15,6 milijuna rubalja, a pri korištenju njegove optimalne mješovite strategije prema drugi restoran, neće dopustiti da prvi zaradi više od 15,6 milijuna rubalja. Grafičko rješenje rezultiralo je greškom, a cijena igre bila je 14,9 milijuna rubalja.

Za Brownovu metodu sastavljen je zadatak u kojem se razmatraju sindikat i uprava poduzeća čija je zadaća osigurati hranu radnicima. Ako oba igrača koriste svoje optimalne strategije, hrana po osobi bit će 2,45 tisuća rubalja.

Popis korištenih izvora

1) Vilisov V.Ya. Bilješke s predavanja “Teorija igara i statističke odluke”, - Ogranak - “Voskhod” MAI. 1979. 146 str.

2) Kruševski A.V. Teorija igara, - Kijev: Vishcha School, 1977. - 216 str.

3) Churchmen U., Akof R., Arnof L., Uvod u operacijska istraživanja. - M.: Znanost. 1967. - 488 str.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Objavljeno na Allbest.ru

Slični dokumenti

Odlučivanje kao posebna vrsta ljudske djelatnosti. Racionalni prikaz matrice igre. Primjeri matričnih igara u čistim i mješovitim strategijama. Operacijska istraživanja: odnos problema linearnog programiranja s modelom teorije igara.

kolegij, dodan 05.05.2010


Igre koje se ponavljaju mnogo puta, njihova karakteristična svojstva i faze. Mješovite strategije, uvjeti i mogućnosti njihove primjene u praksi. Analitička metoda za rješavanje igre tipa 2 x 2. Osnovni teoremi za pravokutne igre. Algebarska rješenja.

prezentacija, dodano 23.10.2013


Osnovne definicije teorije bimatričnih igara. Primjer bimatrične igre "Učenik-učitelj". Mješovite strategije u bimatričnim igrama. Potražite "situaciju ravnoteže". 2x2 bimatrične igre i formule za slučaj kada svaki igrač ima dvije strategije.

sažetak, dodan 13.02.2011


Saznajte opće informacije o matričnim igrama i igrama s nultim zbrojem. Pojam pozicione igre, stablo, skup informacija. Razmatranje principa maksimina i principa ravnoteže. Pareto optimalnost. Pozicijska neantagonistička igra, njena svojstva.

kolegij, dodan 17.10.2014


Teorija igara je grana matematike čiji je predmet proučavanje matematičkih modela za donošenje optimalnih odluka u uvjetima sukoba. Iterativna Brown-Robinsonova metoda. Monotoni iterativni algoritam za rješavanje matričnih igara.

diplomski rad, dodan 08.08.2007


Izrada platne matrice, traženje donje i gornje neto cijene igre, maximin i minimax strategije igrača. Pojednostavljenje matrice plaćanja. Rješavanje matrične igre svođenjem na problem linearnog programiranja i dodatkom “Traži rješenje”.

test, dodan 10.11.2014


Teorija igara je matematička teorija konfliktnih situacija. Razvoj matematičkog modela igre s nultim zbrojem za dvije osobe, njegova implementacija u obliku programskih kodova. Metoda rješavanja problema. Ulazni i izlazni podaci. Program, uputstvo za upotrebu.

kolegij, dodan 17.08.2013


Osnove simpleks metode, ocjena njezine uloge i značenja u linearnom programiranju. Geometrijska interpretacija i algebarsko značenje. Određivanje maksimuma i minimuma linearne funkcije, posebni slučajevi. Rješavanje problema matrično simpleks metodom.

diplomski rad, dodan 01.06.2015


Tehnike konstruiranja matematičkih modela računalnih sustava koji odražavaju strukturu i procese njihova funkcioniranja. Broj pristupa datotekama u procesu rješavanja prosječnog problema. Utvrđivanje mogućnosti smještaja datoteka u vanjske memorijske pogone.

laboratorijski rad, dodano 21.06.2013


Dizajn matematičkog modela. Opis igre tic-tac-toe. Model logičke igre temeljen na Booleovoj algebri. Digitalni elektronički uređaji i razvoj njihovog matematičkog modela. Konzola za igru, kontroler za igru, linija polja za igru.