Čista strategija- deterministički (isključujući slučajnost) plan djelovanja. U prethodnom poglavlju razmatrali smo samo čiste strategije. O mješovitim strategijama raspravljat ćemo u odjeljku 2.2, ali za sada, osim ako nije drugačije navedeno, pod strategijom uvijek mislimo na čistu strategiju.

Vrlo često ćemo u procesu izlaganja koncepte rješenja ilustrirati primjerima bimatričnih igara, pa ćemo dati odgovarajuće definicije.

Definicija 2.1. kraj igre je igra u kojoj skup igrača i skupovi strategija svakog igrača sadrže konačan broj elemenata. Konačna igra dviju osoba zove se bimatrična igra.

Prezime dolazi od prikladnog oblika bilježenja dobitaka u takvoj igri - pomoću dvostruke matrice.

Za daljnju analizu, zgodno je podijeliti strategije u proizvoljnom profilu strategije s na strategiju nekog /-tog igrača s i strategije svih ostalih igrača s_ (. Formalno, s = (.y, s,). Ovdje se ne podrazumijeva da mijenjamo koordinate strateškog profila, samo uvodimo drugi način da ga označimo.

Prvi koncept rješavanja igre koji ćemo razmotriti je ravnoteža u dominantnim strategijama.

Definicija 2.2. Strategija /-tog igrača strogo dominiraju njegova strategija s" ako Uj(s jt s ,) > h,(s", s ,) za bilo koji skup s strategija preostalih igrača. U ovom slučaju, strategija s" se zove strogo dominiraju.

U biti, to znači da za bilo koji fiksni u skupu strategija preostalih igrača, i-ti igrač odabirom strategije s dobiva striktno veća pobjeda nego pri izboru strategije s". Logično je pretpostaviti da racionalan igrač ne bi trebao birati striktno dominirane strategije. Takva pretpostavka u najjednostavnijim igrama može biti dovoljna da se pronađe rješenje igre.

Definicija 2.3. Profil strategija s* =(s*, s^,..., s*) se zove ravnoteža u (striktno) dominantne strategije, ako za bilo kojeg i-tog igrača strategija s" striktno dominira bilo kojom drugom njegovom strategijom.

Može se činiti da ovaj koncept rješenja može dovesti samo do trivijalnih zaključaka. Svaki igrač među svojim strategijama ima onu koja će mu donijeti više nego bilo kojoj drugoj, bez obzira na to kako se njegovi protivnici ponašaju. Tada će primijeniti upravo ovu strategiju u ravnoteži. Sve je prilično očito. No, upravo je ova situacija tipična za, možda, najpoznatiju i vrlo važnu za analizu niza praktičnih situacija igre “Zatvorenička dilema”.

Primjer 2.1 (zatvorenička dilema). Dvojica kriminalaca nalaze se u pritvoru u različitim ćelijama i ne mogu komunicirati. Istraga ima dovoljno dokaza da svakog od njih osudi za manje kazneno djelo na godinu dana. No, za veliki zločin, za koji kriminalcima prijeti deset godina zatvora, istraga nema dovoljno dokaza. Predstavnici istrage nude svakom od kriminalaca dogovor: kriminalac će dobiti kaznu

godinu manje ako svjedoči protiv partnera, što će biti dovoljno da ga optuži za teško kazneno djelo. Pretpostavimo da kriminalce zanima samo broj godina koje će provesti u zatvoru, svaka dodatna godina je minus jedna jedinica korisnosti. Tada se dobit kriminalaca može predstaviti sljedećom dvostrukom matricom:

U slučaju da sudionici igre nisu imenovani, pretpostavit ćemo da različite strategije prvog sudionika odgovaraju recima dvostruke matrice, a strategije drugog sudionika odgovaraju stupcima. Ako u našem primjeru prvi zatvorenik svjedoči, a drugi ne svjedoči, tada će prvi biti pušten, a drugi će dobiti deset godina zatvora.

Lako je vidjeti da je, bez obzira na to kako se drugi zatvorenik ponašao, dobitak veći (razdoblje zatvora je kraće) ako date dokaz (za prvog igrača, prve koordinate u prvom redu dvostruke matrice su striktno veće nego u drugom retku, za drugog igrača, druge koordinate u prvom stupcu dvostruke matrice su strogo veće nego u drugom stupcu). Tada će ravnoteža u dominantnim strategijama biti profil strategija (svjedočiti, svjedočiti).

zanimljivo u ovaj primjer da igrači, birajući ponašanje koje povećava njihov dobitak, završe u situaciji u kojoj su njihovi dobici niski u usporedbi s suprotnom situacijom - kada obojica odluče šutjeti. Objašnjenje leži u prisutnosti snažnog vanjskog učinka, tj. snažan utjecaj akcija jednog igrača na dobitke drugog igrača. Kao rezultat toga, pokazuje se da je profil ravnoteže strategija jedini Pareto neučinkovit u ovoj igri. Imajte na umu da Pareto učinkovitost, poželjna sa stajališta sudionika u igri, ne mora biti poželjna s društvenog stajališta, kao u ovom slučaju.

Situacije poput Zatvorenikove dileme često se pojavljuju u analizi ekonomskih situacija. Razmotrimo, na primjer, natjecanje između dviju trgovina koje prodaju sličan skup proizvoda. Radi jednostavnosti, pretpostavimo da trgovine mogu naplaćivati ​​samo dvije razine cijena - visoku ili nisku. Potrošači prirodno radije kupuju u trgovini s nižim cijenama. Tada isplate trgovina, karakterizirane njihovom dobiti, mogu izgledati, na primjer, kako slijedi:

Sa stajališta ravnoteže, ovdje je situacija analogna Zatvorenikovoj dilemi - ravnoteža u dominantnim strategijama (niske cijene, niske cijene) jedini je Pareto neučinkovit profil (i također poželjan s društvenog stajališta).

Već spomenuta velika popularnost Zatvorenikove dileme bila je razlog da se na njezinu primjeru eksperimentalno pokuša provjeriti točnost predviđanja teorije igara. Test je bio ta dva stranci predloženo je igrati igru ​​za novac s nagradama (na primjer, u dolarima) bliskim onima naznačenima za igru ​​dvije trgovine. Svaki od sudionika donosio je odluku zasebno (često anonimno) i nije znao odluke drugog igrača prije primanja dobitka. Ispostavilo se da pod takvim uvjetima, u mnogim igrama igre, igrači nisu došli do ravnotežnog ishoda, pod pretpostavkom da novčane nagrade ispravno procjenjuju njihov dobitak. Naravno, iz rezultata ovih eksperimenata ne proizlazi da su predviđanja teorije igara netočna, već samo da su igrači pri procjeni svog dobitka uzeli u obzir nemonetarne čimbenike - razmatranja altruizma, poštenja itd. Ako su isplate igrača ispravno procijenjene, tada bi igrači trebali preferirati dominantnu strategiju, te je stoga odabrati (u duhu otkrivenih preferencija u mikroekonomiji). Stoga vrijednost eksperimenata ove vrste nije u testiranju predviđanja teorije igara, već u procjeni uloge nematerijalne motivacije u postupcima pojedinaca.

Značajno manje od koncepta jake dominacije, teorija igara koristi koncept slabe dominacije.

Definicija 2.4. Strategija /-tog igrača s, slabo dominantan njegova strategija s" ako m, (s, s ,) > m ; (sJ, s ,) za bilo koji skup strategija drugih igrača s_j,štoviše, za barem jedan skup strategija drugih igrača, nejednakost je strogo zadovoljena. Tada se poziva strategija s". slabo dominira.

U slučaju nestriktnih nejednakosti više nije moguće ustvrditi da racionalan igrač neće izabrati slabo dominiranu strategiju, iako se takvo ponašanje čini sasvim logičnim. Postoji, iako se rijetko koristi, definicija ravnoteže u slabo dominantnim strategijama analogna slučaju jake dominacije.

Definicija 2.5. Poziva se profil strategije s* = (s*, Sj,..., s*). ravnoteža u slabo dominantnim strategijama, ako za bilo kojeg i-tog igrača strategija s" slabo dominira bilo kojom drugom njegovom strategijom.

Primjer 2.2 (zatvorena dražba druge cijene). Zatvorena dražba druge cijene održava se između dvije osobe. Dražba je organizirana na sljedeći način. Svaki od sudionika označava nenegativnu stopu, ne poznajući stope ostalih sudionika (u omotnici). Član koji je napravio najviša ponuda, plaća maksimalni iznos među ponudama ostalih sudionika (tj. iznos druge ali vrijednosti ponude) i prima neku stavku. Ako su npr. licitacije igrača bile 100 i 90, tada sudionik koji je licitirao 100 pobjeđuje na dražbi, on dobiva predmet za 90 - veličinu druge licitacije. Neka svaki sudionik ima procjenu predmeta, izraženu u novčanim jedinicama, v2> 0. Te su procjene poznate svim sudionicima. Neka, radi jednostavnosti opisa igre, ako oba sudionika navedu istu stopu, tada predmet ide prvom sudioniku.

U ovoj igri, strategija prvog igrača bit će veličina njegovog uloga. Budući da je stopa nenegativna, skup svih mogućih strategija

5, = 0 = u,(o, s 2) > w,(s, s 2) = u, - s 2 v x slabo dominira strategijom s,.

Pokazali smo da za prvog igrača strategija navođenja svog rezultata kao oklade slabo dominira bilo kojom drugom strategijom. Lako je provjeriti da slična tvrdnja vrijedi i za drugog igrača. Imajte na umu da u našem obrazloženju nikada nismo koristili činjenicu da igrač zna procjenu drugog igrača, što znači da u slučaju igre s nepotpunim informacijama u zatvorenoj dražbi druge cijene neće biti ništa manje isplativo navesti svoju procjenu nego dati bilo koju drugu ponudu.

Može se činiti da je prodavatelju neisplativo organizirati dražbu druge cijene, kada može organizirati dražbu prve cijene i primiti vrijednost ne druge, već prve ponude. Međutim, vrijednost stopa u slučaju aukcije prve cijene u ravnoteži bit će niža. O prinosima aukcija više ćemo govoriti u pogl. 5. U međuvremenu, napominjemo da je dražba druge cijene vrlo popularna i naširoko je koriste, primjerice, tvrtke Google i "Yandex" pri prodaji kontekstualnog oglašavanja na Internetu.

Ravnoteža u dominantnim strategijama postoji samo u maloj klasi igara. Tipično, igrači nemaju jednu strategiju koja dominira svim ostalima. Ali koncept dominacije omogućuje pronalaženje rješenja u široj klasi igara. Da biste to učinili, morate voditi dosljedno razmišljanje o postupcima igrača. Već smo primijetili da racionalan igrač neće izabrati striktno dominiranu strategiju. Ali to znači da drugi igrač može analizirati igru, zanemarujući mogućnost protivnikovog izbora takve strategije. Možda će neka analiza otkriti da drugi igrač ima dominantnu strategiju koja nije bila dominantna u izvornoj igri. I tako dalje. Dajmo formalnu definiciju.

Postupak sekvencijalno isključivanje snažno dominiranih strategija postavlja se na sljedeći način. Isključimo iz razmatranja sve striktno dominirane strategije igrača, tj. razmotrite novu igru ​​u kojoj su sve dominirajuće strategije isključene iz skupa mogućih strategija igrača. Zatim u ovom Nova igra eliminiramo sve striktno dominirane strategije, i tako dalje.

Moguće je da će takav proces završiti kada igračima preostane nekoliko strategija, ali je moguće da će svaki igrač imati samo jednu neisključenu strategiju, tada je logično razmatrati skup tih strategija kao rješenje igre. .

Definicija 2.6. Ako, kao rezultat uzastopne eliminacije snažno dominiranih strategija, svakom igraču ostane jedna strategija, tada se profil tih strategija naziva ravnoteža dominacije.

U primjeru 1.1 dobili smo upravo takvu ravnotežu. Razmotrimo još jedan primjer.

Profil strategije (N, P) jedina je Nashova ravnoteža u ovoj igri. No imajte na umu da, kako bi odabrao P, drugi igrač mora biti siguran da prvi igrač ne odabere B. Ali isplata prvog igrača je ista ako drugi igrač odabere II. Osim toga, odabirom B prvi igrač se možda neće bojati da će drugi izabrati L. Možda će racionalni drugi igrač razmisliti o odabiru strategije C.

Drugo pitanje, na koje još nije pronađen jednoznačan odgovor: kako igrači dolaze do Nashove ravnoteže?

Idealni teorijski scenarij je sljedeći. Igrači samostalno formiraju očekivanja o akcijama drugih igrača, a zatim biraju radnje koje maksimiziraju njihov dobitak s obzirom na zadana očekivanja. Ako, u ovom slučaju, očekivanja odgovaraju akcijama koje su igrači stvarno odabrali, tada dobivamo Nashovu ravnotežu. Ovo razmišljanje omogućuje nam da Nashovu ravnotežu nazovemo situacijom s samoispunjavajuća očekivanja. Ali odakle dolaze očekivanja? I koja će od Nashovih ravnoteža, ako ih ima više, biti odabrana kao rezultat opisanog procesa? U okviru razmatranog scenarija ova pitanja ostaju bez odgovora.

Drugi pristup uključuje prisutnost igrača na treningu. Igrači ili teoretski uče kako igrati igru ​​(mislite na studenta ekonomije) ili doživljavaju slične interakcije (npr. iskusni radnik dolazi novi tim), što im omogućuje pravilno oblikovanje očekivanja i odabir optimalnog ponašanja. Ovaj scenarij omogućuje objašnjenje formiranja očekivanja, ali, prvo, smanjuje opseg modela igre samo na standardne, proučavane i često susrećene situacije interakcije, i drugo, može dovesti do činjenice da situacije jednokratnih i ponovljenih situacija interakcije se ne razlikuju, a potonje se bitno razlikuju po strategijama i metodama rješavanja u okviru teorije igara, o čemu će biti više riječi u pogl. četiri.

Treći scenarij je da postoji prethodni dogovor između igrača, ili običaji, ili zakoni, ili upute trećih strana koje reguliraju interakciju između igrača. U tom slučaju dogovori ili upute možda nisu obvezujući, ali ako se preporučuje igrati Nashovu ravnotežu, tada nitko od igrača nema želju (sam) odstupiti od propisanog ponašanja. Jasno je da takav scenarij nije moguć u svakoj situaciji. Osim toga, sam proces sklapanja sporazuma ili uključivanje trećih strana može postati dio igre.

Konačno, treće prirodno pitanje koje se postavlja pri proučavanju koncepta Nashove ravnoteže je sljedeće: postoje li ikakvi empirijski dokazi da stvarni igrači obično biraju ravnotežne strategije? I ovdje je vrlo teško dati kratak i nedvosmislen odgovor. U isto vrijeme, priroda problema koji se javljaju više je u skladu s predmetom eksperimentalne ekonomije. Stoga se ograničavamo na preporuku da se obratimo stručnoj literaturi, na primjer, knjizi, gdje su pitanja eksperimentalne metodologije izvrsno analizirana i prikazani su brojni rezultati.

Postoje igre koje nemaju ravnotežu u čistim strategijama (vidi primjer 3.1), pa se postavlja pitanje koji su uvjeti dovoljni za postojanje takve ravnoteže? Formulirajmo i dokažimo tvrdnju o postojanju Nashove ravnoteže u čistim strategijama u igrama koje nisu konačne.

Izjava 2.3. Ako skupovi strategija za svakog od igrača S t su neprazni konveksni kompakti u euklidskom prostoru i funkcija isplate svakog igrača i- kontinuirano u s i kvazi-konkavna u 5, tada igra ima Nashovu ravnotežu u čistim strategijama.

Dokaz. Prisjetite se formulacije Kakutaijevi teoremi, koje ćemo koristiti u dokazu. Neka X- neprazan konveksan kompakt set in Rn, X* je skup svojih podskupova i/ je takvo gornje polukontinuirano preslikavanje iz x u x*, da za svaku točku x e x Mnogo f(x) neprazna, zatvorena i konveksna. Tada preslikavanje / ima fiksnu točku.

Ideja dokazivanja naše tvrdnje je konstruirati preslikavanje koje zadovoljava uvjete Kakutanijevog teorema. Da bismo to učinili, malo redefiniramo prikaz najboljeg odgovora. Čisto tehnički ćemo pretpostaviti da najbolji odgovor ne ovisi samo o strategijama drugih igrača, već io samim strategijama igrača. S promjenom igračeve vlastite strategije kada fiksne strategije ostatak igrača, najbolji odgovor, naravno, neće promijeniti. Sada uvedimo oznaku za prikaz najboljeg odgovora za sve igrače kao kartezijanski produkt s(s) = s,(s) x s 2 (s) x... x s n (s). Ovo mapiranje svakom profilu dodjeljuje skup profila u kojima svaki igrač najbolji način odgovara na strategije drugih igrača. Fiksna točka preslikavanja S, tj. profil s takav da s e s(s)> je po definiciji Nashova ravnoteža. Pokažimo da preslikavanje 5 zadovoljava uvjete Kakutanijevog teorema. Provjera svakog uvjeta predstavljat će zasebnu točku dokazivanja.

• 1. Pokažimo da skup S svi profili - konveksni kompakt. Budući da su, pod uvjetom utvrđivanja skupa strategija svakog od igrača S, neprazni konveksni kompaktni skupovi, tada je Kartezijev produkt S = S t x S2 X...x S n je konveksni kompakt.
• 2. Prikaz s ima neprazne slike. Prema Weierstrassovom teoremu, kontinuirana funkcija i- doseže na zatvorenom ograničenom skupu 5, svoju najveću vrijednost. Posljedično, s ima neprazne slike.
• 3. Prikaz slika s zatvorena i konveksna. Budući da je funkcija isplate svakog igrača u t kvazikonkavno u s ako tada je po svojstvu kvazikonkavne funkcije skup $. = (s. | u t (s i9 s .) > k) za fiksni s .i k zatvoreno u zatvoreno područje definicije i konveksan je ako nije prazan. Budući da ovo vrijedi za bilo koji k, tada je također točno da je skup 5. = (5/1 u t(s", 5 ,) > maks. (s., s .)}

konveksan. Ali tada je Kartezijev produkt 5(5) = s x (s) x s2(S) x... x s n CS) je zatvorena i konveksna.

4. Pokažimo da preslikavanje § polukontinuirano odozgo. Za funkciju koristimo uvjet kontinuiteta i, od s. Dokazat ćemo kontradikcijom. Pretpostavimo da zaslon § ns je gornji polukontinuiran. Zatim postoje nizovi strateških profila s m i s m, gdje t - broj elementa niza, takav da za bilo koji t s"" e S, s m e s(s""), lim s"" = s° e S, ali lim s"" = s° g lim s(s""). To znači da postoji

t~* oo t->/i -? oo

stijena za koju strategija s f° nije najbolji odgovor na s 0, tj. postoji strategija s" takav da i,(s), s 0 ,) > nas] s°;). Tada se može naći e > 0 tako da je m,(s/, s 0 ,) > m,(s ; °, s 0 ,) + Ze, odakle

Kako je po pretpostavci funkcija m neprekidna, lim s m = s°, lim s"” = s°,

m*oo m-*oo

s dovoljno velikim m pravo

Kombinirajući nejednadžbe (2.8)-(2.10) u jedan lanac, dobivamo

Iz relacija (2.11) slijedi u,(s", s"") > m,(s/", s"") + s, ali to je u suprotnosti s uvjetom s"" e s(s""), budući da s" daje striktno veću isplatu od s/", kao odgovor na s"". Došli su do kontradikcije. Stoga je naša izvorna pretpostavka da s nije gornje polukontinuirana bila pogrešna.

Pokazali smo da preslikavanje S zadovoljava sve uvjete Kakutanijevog teorema i stoga ima fiksnu točku. Ova fiksna točka je Nashova ravnoteža. Tvrdnja 2.3 je dokazana. ?

Konkretno, izjava 2.3 jamči postojanje Nashove ravnoteže u primjeru 2.7, ali ne iu primjeru 2.8, gdje su funkcije isplate igrača diskontinuirane.

„Primjer s posla.

5. TEORIJA IGARA I STATISTIČKA RJEŠENJA

5.1. Igra matrice s nultim zbrojem

Ekonomsko-matematičko modeliranje provodi se pod sljedećim uvjetima:

Sigurnost;

Neizvjesnosti.

Modeliranje pod uvjetima izvjesnosti pretpostavlja dostupnost svih početnih regulatornih podataka potrebnih za to (matrično modeliranje, mrežno planiranje i upravljanje).

Modeliranje u opasnosti provodi se pod stohastičkom nesigurnošću, kada su vrijednosti nekih početnih podataka slučajne i poznati su zakoni distribucije vjerojatnosti tih slučajnih varijabli (regresijska analiza, teorija čekanja).

Modeliranje u uvjetima neizvjesnosti odgovara potpunom nedostatku nekih za to potrebnih podataka (teorija igara).

U uvjetima neizvjesnosti grade se matematički modeli za donošenje optimalnih odluka u konfliktnim situacijama.

U teoriji igara koriste se sljedeći osnovni pojmovi:

Strategija;

funkcija pobjede.

potez nazvat ćemo izbor i provedbu od strane igrača jedne od radnji predviđenih pravilima igre.

Strategija - Ovo je tehnologija odabira pravca djelovanja za svaki potez, ovisno o situaciji.

funkcija pobjede služi za određivanje iznosa isplate poraženog igrača pobjedniku.

U matričnoj igri, funkcija dobitka je predstavljena kao platna matrica :

gdje je iznos isplate igraču I, koji je izabrao potez, od igrača II, koji je izabrao potez.

U takvoj igri parova, vrijednosti funkcija isplate oba igrača u svakoj situaciji jednake su veličine i suprotnog predznaka, tj. a ova igra se zove nulti zbroj .

Proces "igranja igre matrice" predstavljen je na sljedeći način:

Postavljena je matrica plaćanja;

Igrač I, bez obzira na igrača II, bira jedan od redaka ove matrice, na primjer, -ti;

Igrač II, bez obzira na igrača I, bira jedan od stupaca ove matrice, na primjer, - th;

Element matrice određuje koliko ću igrača I dobiti od igrača II. Naravno, ako , tada govorimo o stvarnom gubitku igrača I.

Antagonistička dvostruka igra sa platna matrica i zvat će se igra.

Primjer

Razmotrimo igru.

Data je matrica plaćanja:

.

Neka igrač I, bez obzira na igrača II, izabere 3. redak ove matrice, a igrač II, bez obzira na igrača I, izabere 2. stupac ove matrice:

Tada će igrač I dobiti 9 jedinica od igrača II.

5.2. Optimalna čista strategija u matrix igri

Optimalna strategija Strategija igrača I se naziva takva da on ne smanjuje svoj dobitak za bilo koji izbor strategije od strane igrača II, a takva strategija igrača II da on ne povećava svoj gubitak za bilo koji izbor strategije od strane igrača I.

Odabirom i-tog retka matrice isplate kao poteza, igrač I osigurava isplatu najmanje vrijednosti u najgorem slučaju, kada igrač II pokušava minimizirati tu vrijednost. Stoga će igrač I odabrati -ti red koji će mu osigurati maksimalan dobitak:

.

Igrač II tvrdi na sličan način i može si sigurno jamčiti minimalni gubitak:

.

Uvijek je istinita sljedeća nejednakost:

Vrijednost se zove niža cijena igre .

Vrijednost se zove najviša cijena igre .

Optimalne strategije su tzv čist , ako su za njih zadovoljene jednakosti:

,

.

Vrijednost se zove neto cijena igre , ako .

Optimalne čiste strategije i forma sedlasta točka platna matrica.

Za točku sedla zadovoljeni su sljedeći uvjeti:

tj. element je najmanji u redu, a najveći u stupcu.

Dakle, ako matrica isplate ima sedlasta točka , onda možete pronaći optimalne čiste strategije igrači.

Čista strategija igrača I može se prikazati uređenim skupom brojeva (vektorom) u kojem su svi brojevi jednaki nuli, osim broja na -tom mjestu, koji je jednak jedinici.

Čista strategija igrača II može se prikazati uređenim skupom brojeva (vektorom) u kojem su svi brojevi jednaki nuli, osim broja na -tom mjestu, koji je jednak jedinici.

Primjer

.

Odabirom nekog retka isplatne matrice kao poteza, igrač I osigurava isplatu u najgorem slučaju ne manju od vrijednosti u stupcu označenom s:

Stoga će igrač I izabrati 2. redak matrice isplate, koji mu daje najveći dobitak, bez obzira na potez igrača II, koji će pokušati minimizirati ovu vrijednost:

Igrač II raspravlja slično i odabire 1. stupac kao potez:

Dakle, postoji sjedište matrice isplate:

što odgovara optimalnoj čistoj strategiji za igrača I i za igrača II tako da igrač I ne smanjuje svoju isplatu za bilo koju promjenu strategije od strane igrača II i igrač II ne povećava svoj gubitak za bilo koju promjenu strategije od strane igrača I.

5.3. Optimalno mješovita strategija u matrix igri

Ako matrica isplate nema sedlu točku, tada nije racionalno za bilo kojeg igrača koristiti jednu čistu strategiju. Isplativije za korištenje "probabilističke mješavine" čiste strategije. Tada se već mješovite strategije definiraju kao optimalne.

Mješovita strategija igrača karakterizira distribucija vjerojatnosti slučajni događaj, koji se sastoji u izboru poteza ovog igrača.

Mješovita strategija igrača I takav je uređen skup brojeva (vektor) koji zadovoljava dva uvjeta:

1) za , tj. vjerojatnost odabira svakog retka matrice isplate je nenegativna;

2), tj. izbor svakog redaka matrice isplate u agregatu predstavlja puna grupa događanja.

Mješovita strategija igrača II je uređeni skup brojeva (vektor) koji zadovoljava uvjete:

Iznos uplate igraču I, koji odabere mješovitu strategiju

od igrača II, koji je izabrao mješovitu strategiju

,

je prosjek

.

Optimalno nazvane mješovite strategije

i ,

ako je za bilo koju proizvoljnu mješovitu strategiju i zadovoljen sljedeći uvjet:

tj. pod optimalnom mješovitom strategijom, dobitak igrača I je najveći, a gubitak igrača II je najmanji.

Ako u matrici isplate nema sedla, onda

,

tj. postoji pozitivna razlika ( zadržana razlika )

- ³ 0,

a igrači moraju tražiti dodatne prilike da s pouzdanjem dobiju veći udio ove razlike u svoju korist.

Primjer

Razmotrite igru ​​koju daje matrica isplate:

.

Odredite postoji li sedlasta točka:

, .

Ispada da u matrici isplate nema sedla i da je neraspodijeljena razlika:

.

5.4. Pronalaženje optimalnih mješovitih strategija

za igre 2×2

Određivanje optimalnih mješovitih strategija za matricu isplate s dimenzijama provodi se metodom pronalaženja točaka optimuma funkcije dviju varijabli.

Neka je vjerojatnost da igrač I odabere prvi redak matrice isplate

jednako je . Tada je vjerojatnost odabira drugog reda .

Neka je vjerojatnost da igrač II izabere prvi stupac jednaka . Tada je vjerojatnost odabira drugog stupca .

Iznos isplate igrača I od strane igrača II jednak je:

Ekstremna vrijednost dobitka igrača I i gubitka igrača II odgovara uvjetima:

;

.

Dakle, optimalne mješovite strategije igrača I i II su:

5.5. Geometrijsko rješenje 2× igaran

S povećanjem dimenzije matrice isplata s na više nije moguće reducirati definiciju optimalnih mješovitih strategija na pronalaženje optimuma funkcije dviju varijabli. Međutim, s obzirom da jedan od igrača ima samo dvije strategije, može se koristiti geometrijsko rješenje.

Glavne faze pronalaženja rješenja igre su sljedeće.

Uvodimo koordinatni sustav na ravnini. Stavimo isječak linije na os. S lijevog i desnog kraja ovog segmenta povlačimo okomice.

Lijevi i desni kraj jediničnog segmenta odgovaraju dvjema strategijama i , dostupnim igraču I. Na nacrtanim okomicama odgodit ćemo isplate ovog igrača. Na primjer, za matricu isplate

takve isplate igrača I pri odabiru strategije bit će i , a pri odabiru strategije bit će i .

Spojimo isplatne točke igrača I, koje odgovaraju strategijama igrača II, ravnim segmentima. Tada formirana isprekidana linija koja omeđuje grafikon odozdo određuje donju granicu isplate igrača I.

Pronalaženje optimalne mješovite strategije za igrača I

,

koja odgovara točki na donjoj granici isplate igrača I s maksimalnom ordinatom.

Obratimo pozornost na činjenicu da u primjeru koji razmatramo, koristeći samo dvije strategije i , koje odgovaraju ravnim linijama koje se sijeku u pronađenoj točki na donjoj granici isplate igrača I, igrač II može spriječiti igrača I da dobije veći isplatiti.

Time se igra svodi na igru ​​i optimalna mješovita strategija igrača II u razmatranom primjeru je

,

gdje je vjerojatnost ista kao u igrici:

5.6. Rješavanje igrem× n

Ako matrična igra nema rješenja u čistim strategijama (tj. nema sedlu točku) i, zbog velike dimenzije matrice isplate, ne može se riješiti grafički, tada za dobivanje rješenja upotrijebite metoda linearnog programiranja .

Neka je dana isplatna matrica dimenzije:

.

Moramo pronaći vjerojatnosti , s kojim igračem moram birati njegove poteze kako bi mu ova mješovita strategija jamčila isplatu od najmanje , bez obzira na izbor poteza igrača II.

Za svaki potez koji odabere igrač II, isplata igrača I određena je ovisnostima:

Dijelimo obje strane nejednakosti s i uvodimo nove oznake:

Jednakost

Imat će oblik:

Budući da igrač I želi maksimizirati isplatu, recipročna vrijednost mora biti minimizirana. Tada će problem linearnog programiranja za igrača I poprimiti oblik:

pod ograničenjima

Problem za igrača II je slično konstruiran kao dualni:

pod ograničenjima

Rješavanjem problema simpleks metodom dobivamo:

,

5.7. Značajke rješavanja matričnih igara

Prije rješavanja problema pronalaženja optimalnih strategija potrebno je provjeriti dva uvjeta:

Je li moguće pojednostaviti matricu plaćanja;

Ima li matrica isplate sedlu.

Razmotrite mogućnost pojednostavljenja matrice plaćanja:

Zbog činjenice da igrač kojeg želim dobiti najveća pobjeda, onda se -ta linija može izbrisati iz matrice isplate, budući da on nikada neće koristiti ovaj potez ako je sljedeća relacija zadovoljena s bilo kojom drugom -tom linijom:

Slično, težeći što manjem gubitku, igrač II nikada neće odabrati -ti stupac u matrici isplate kao potez, a ovaj stupac može biti precrtan ako vrijedi sljedeća relacija s bilo kojim drugim -tim stupcem:

Najviše jednostavno rješenje igra je prisutnost u pojednostavljenoj matrici isplate sedla koja ispunjava sljedeći uvjet (po definiciji):

Primjer

S obzirom na matricu isplate:

.

Pojednostavljenje matrice plaćanja:

Prisutnost sedlaste točke:

5.8. Igranje s prirodom

Za razliku od problematike teorije igara u teorija statističke odluke neizvjesna situacija nema antagonističku konfliktnu obojenost i ovisi o objektivnoj stvarnosti, koja se obično naziva "priroda" .

U matričnim igrama s prirodom igrač II je skup neizvjesnih faktora koji utječu na učinkovitost donesenih odluka.

Matrix igre s prirodom razlikuju se od običnih matrix igara samo po tome što kada igrač I odabere optimalnu strategiju, više se nije moguće pouzdati u to da će igrač II nastojati minimizirati svoj gubitak. Stoga, uz matricu isplate, uvodimo matrica rizika :

gdje je vrijednost rizika igrača I kada koristi potez pod uvjetima, jednaka razlici između isplate koju bih taj igrač dobio da je znao da će se uspostaviti uvjet, tj. , i isplatu , koju će dobiti, ne znajući pri odabiru poteza da će se uvjet uspostaviti.

Dakle, matrica isplate se jedinstveno transformira u matricu rizika, a obrnuta transformacija je dvosmislena.

Primjer

Matrica pobjede:

.

Matrica rizika:

moguće dvije izjave problema o izboru rješenja u matričnoj igri s prirodom :

Maksimizacija profita;

Minimizacija rizika.

Problem odlučivanja može se postaviti za jedan od dva uvjeta:

- u opasnosti kada je poznata funkcija distribucije vjerojatnosti strategija prirode, na primjer, slučajna varijabla pojave svake od predloženih specifičnih ekonomskih situacija;

- u uvjetima neizvjesnosti kada je takva funkcija distribucije vjerojatnosti nepoznata.

5.9. Rješavanje problema u teoriji statističkih rješenja

u opasnosti

Prilikom donošenja odluka pod rizikom, igrač I zna vjerojatnosti nastup prirodnih stanja.

Tada je svrhovito da igrač I izabere strategiju za koju prosječna vrijednost isplate, uzeta duž linije, je maksimalna :

.

Rješavanjem ovog problema matricom rizika dobivamo isto rješenje koje odgovara minimalni prosječni rizik :

.

5.10. Rješavanje problema u teoriji statističkih rješenja

u uvjetima neizvjesnosti

Kada donosite odluke u neizvjesnosti, možete koristiti sljedeće kriteriji :

Waldov maksiminski kriterij;

kriterij minimalan rizik Divljak;

Kriterij pesimizma – Hurwitzov optimizam;

Laplaceovo načelo nedovoljnog razloga.

Smatrati maximin Waldov kriterij .

Igra se s prirodom kao s razumno agresivnim protivnikom, odnosno provodi se pristup reosiguranja s pozicije krajnjeg pesimizma za isplatnu matricu:

.

Smatrati Savageov kriterij minimalnog rizika .

Slično prethodnom pristupu s pozicije ekstremnog pesimizma za matricu rizika:

.

Smatrati kriterij pesimizma – Hurwitzov optimizam .

Nudi priliku da se ne vodite ni ekstremnim pesimizmom ni ekstremnim optimizmom:

gdje je tu stupanj pesimizma ;

at - ekstremni optimizam,

at - ekstremni pesimizam.

Smatrati Laplaceovo načelo nedovoljnog razloga .

Pretpostavlja se da su sva stanja prirode jednako vjerojatna:

,

.

Zaključci o petom dijelu

U matričnoj igri sudjeluju dva igrača, a funkcija isplate, koja služi za određivanje iznosa isplate od igrača koji gubi prema pobjedniku, predstavljena je kao matrica isplate. Dogovoreno je da igrač I izabere jedan od redaka matrice isplate kao potez, a igrač II izabere jedan od njezinih stupaca. Tada je na sjecištu odabranog retka i stupca ove matrice numerička vrijednost isplate igraču I od igrača II (ako je ova vrijednost pozitivna, tada je igrač I stvarno pobijedio, a ako je negativna, tada je igrač II u biti pobijedio).

Ako postoji sedlo u matrici isplate, tada igrači imaju optimalne čiste strategije, tj. da bi pobijedili, svaki od njih mora ponoviti svoj jedan optimalni potez. Ako nema sedla, onda da bi pobijedio, svaki od njih mora koristiti optimalnu mješovitu strategiju, tj. koristiti mješavinu poteza, od kojih svaki mora biti izveden s optimalnom vjerojatnošću.

Pronalaženje optimalnih mješovitih strategija za igre 2×2 provodi se izračunavanjem optimalnih vjerojatnosti pomoću poznatih formula. Pomoću geometrijsko rješenje 2×n igre, definicija optimalnih mješovitih strategija u njima se svodi na pronalaženje optimalnih mješovitih strategija za 2×2 igre. Za rješavanje m×n igara koristi se metoda linearnog programiranja za pronalaženje optimalnih mješovitih strategija u njima.

Neke matrice isplate podložne su pojednostavljenju, uslijed čega se njihova dimenzija smanjuje brisanjem redaka i stupaca koji odgovaraju potezima koji ne obećavaju.

Ako je igrač II skup neizvjesnih čimbenika koji ovise o objektivnoj stvarnosti i nemaju antagonističku konfliktnu obojenost, tada se takva igra naziva igrom s prirodom, a za njeno rješavanje koriste se problemi teorije statističkih odluka. Tada se uz matricu isplate uvodi i matrica rizika te su moguće dvije formulacije problema izbora rješenja u matričnoj igri s prirodom: maksimiziranje dobitka i minimiziranje rizika.

Rješavanje problema teorije statističkih odluka u uvjetima rizika pokazuje da je svrhovito da igrač I odabere strategiju za koju je prosječna vrijednost (očekivanja) isplate, uzeta po liniji isplatne matrice, maksimalna, ili ( što je isto) prosječna vrijednost (očekivanja) rizika, uzeta linijom matrice rizika, je minimalna. Pri donošenju odluka u uvjetima neizvjesnosti koriste se sljedeći kriteriji: Waldov maksiminski kriterij, Savageov kriterij minimalnog rizika, Hurwitzov kriterij pesimizma-optimizma, Laplaceov princip nedovoljnog razloga.

Pitanja za samoispitivanje

Kako su definirani osnovni koncepti teorije igara: potez, strategija i funkcija isplate?

Kako je funkcija isplate predstavljena u matričnoj igri?

Zašto se igra matrice zove zero-sum?

Kakav je proces igranja igre matrica?

Koja se igra zove igra m×n?

Koja je optimalna strategija matrične igre?

Koja je optimalna strategija za matrix igru ​​koja se zove čista?

Što znači sjedište matrice isplate?

Koja je optimalna strategija za matričnu igru ​​koja se zove mješovita?

Koja je mješovita strategija igrača?

Koja je isplata igraču I od igrača II koji je odabrao mješovite strategije?

Koje se mješovite strategije nazivaju optimalnima?

Što znači neraspodijeljena razlika?

Koja se metoda koristi za pronalaženje optimalnih mješovitih strategija za igre 2×2?

Kako se pronalaze optimalne mješovite strategije za igre 2×n?

Koja se metoda koristi za pronalaženje optimalnih mješovitih strategija za m×n igara?

Koje su značajke rješavanja matričnih igara?

Što pojednostavljenje platne matrice znači i pod kojim uvjetima se može provesti?

Koju je matričnu igru ​​lakše riješiti kada matrica isplate ima ili nema sedlišnu točku?

Koji su problemi teorije igara povezani s problemima teorije statističkih odluka?

Kako se matrica isplate pretvara u matricu rizika?

Koje su dvije formulacije problema izbora rješenja moguće u matričnoj igri s prirodom?

Uz koja se dva uvjeta mogu postaviti problemi donošenja odluka u matričnoj igri s prirodom?

Koju je strategiju igrač I svrsishodno odabrati pri rješavanju problema teorije statističkih odluka pod rizikom?

Koji se kriteriji odlučivanja mogu koristiti pri rješavanju problema teorije statističkih odluka u uvjetima nesigurnosti?

Primjeri rješavanja problema

1. Platna matrica pokazuje iznos dobiti poduzeća kada prodaje različiti tipovi proizvoda (stupci) ovisno o utvrđenoj potražnji (redovi). Potrebno je odrediti optimalnu strategiju poduzeća za proizvodnju proizvoda različitih vrsta i odgovarajući maksimalni (u prosjeku) prihod od njihove prodaje.

Zadanu matricu označimo s i uvedemo varijable. Također ćemo koristiti matricu (vektor) . Tada i , tj .

Izračunava se inverzna matrica:

Vrijednosti se nalaze:

.

Vjerojatnosti se izračunavaju:

Prosječni prihod od prodaje određuje se:

.

2. Firma "Pharmatsevt" - proizvođač lijekova i biomedicinskih proizvoda u regiji. Poznato je da je potražnja za nekim lijekovima vrhunac ljetno razdoblje(lijekovi kardiovaskularne skupine, analgetici), za druge - za jesensko i proljetno razdoblje (antiinfektivno, antitusivno).

Troškovi po 1 konv. jedinice proizvodi za rujan-listopad bili su: za prvu skupinu (kardiovaskularni lijekovi i analgetici) - 20 rubalja; za drugu skupinu (antiinfektivni, antitusivni lijekovi) - 15 rubalja.

Prema promatranjima tijekom nekoliko zadnjih godina Marketinška služba tvrtke utvrdila je da može prodati 3050 konvencionalnih jedinica tijekom dva razmatrana mjeseca u toplim vremenskim uvjetima. jedinice proizvoda prve skupine i 1100 konv. jedinice proizvodi druge skupine; u hladnim vremenskim uvjetima - 1525 arb. jedinice proizvoda prve skupine i 3690 konv. jedinice druga skupina.

U vezi s mogućim vremenskim promjenama, zadatak je odrediti strategiju tvrtke u proizvodnji proizvoda koja osigurava maksimalan prihod od prodaje po prodajnoj cijeni od 40 rubalja. za 1 konv. jedinice proizvodi prve skupine i 30 str. - druga grupa.

RIJEŠENJE. Tvrtka ima dvije strategije:

Vrijeme će ove godine biti toplo;

Vrijeme će biti hladno.

Ako tvrtka usvoji strategiju i vrijeme je stvarno toplo (strategija prirode), tada će proizvedeni proizvodi (3050 konvencionalnih jedinica lijekova prve skupine i 1100 konvencionalnih jedinica druge skupine) biti u potpunosti ostvareni i prihod će biti

3050×(40-20)+1100×(30-15)=77500 r.

U uvjetima hladnog vremena (strategija prirode), lijekovi druge skupine prodat će se u cijelosti, a prva skupina samo u količini od 1525 konvencionalnih jedinica. jedinice a neki će lijekovi ostati neprodani. Prihod će biti

1525×(40-20)+1100×(30-15)-20×()=16500 r.

Slično tome, ako obrazac usvoji strategiju i vrijeme je zapravo hladno, tada će prihod biti

1525×(40-20)+3690×(30-15)=85850 r.

U toplom vremenu, prihod će biti

1525×(40-20)+1100×(30-15)-() ×15=8150 r.

Uzimajući u obzir tvrtku i vrijeme kao dva igrača, dobivamo matricu isplate

,

Cijena igre je u rangu

Iz matrice isplate može se vidjeti da će pod svim uvjetima prihod tvrtke biti najmanje 16 500 rubalja, ali ako vrijeme podudaraju s odabranom strategijom, tada prihod tvrtke može biti 77.500 rubalja.

Pronađimo rješenje igre.

Označimo vjerojatnost primjene strategije od strane poduzeća kao , strategija kroz , i . Rješavajući igru ​​grafički, dobivamo , dok je cijena igre r.

Optimalan plan za proizvodnju lijekova bit će

Stoga je svrsishodno da tvrtka tijekom rujna i listopada proizvede 2379 konvencionalnih jedinica. jedinice lijekovi prve skupine i 2239,6 konvencionalnih jedinica. jedinice lijekovi druge skupine, tada će u bilo kojem vremenu dobiti prihod od najmanje 46.986 rubalja.

U uvjetima neizvjesnosti, ako nije moguće da tvrtka koristi mješovitu strategiju (ugovori s drugim organizacijama), koristimo sljedeće kriterije za određivanje optimalne strategije tvrtke:

Waldeov kriterij:

Hurwitzov kriterij: za određenost prihvaćamo , zatim za strategiju poduzeća

za strategiju

preporučljivo je da tvrtka koristi strategiju .

Savageov kriterij. Maksimalni element u prvom stupcu je 77500, u drugom stupcu je 85850.

Elementi matrice rizika nalaze se iz izraza

,

gdje , ,

Matrica rizika ima oblik

,

preporučljivo je koristiti strategiju ili .

Stoga je preporučljivo poduzeću primijeniti strategiju ili .

Imajte na umu da se svaki od razmatranih kriterija ne može smatrati potpuno zadovoljavajućim za konačni izbor odluke, ali njihova zajednička analiza omogućuje jasnije prikazivanje posljedica donošenja pojedinih menadžerskih odluka.

Uz poznatu distribuciju vjerojatnosti različitih stanja prirode, kriterij odluke je maksimalno matematičko očekivanje isplate.

Ako je za razmatrani problem poznato da su vjerojatnosti toplog i hladnog vremena jednake i jednake 0,5, tada se optimalna strategija poduzeća određuje na sljedeći način:

Preporučljivo je da tvrtka koristi strategiju ili.

Zadaci za samostalan rad

1. Poduzeće može proizvoditi tri vrste proizvoda (A, B i C), a pritom ostvarivati ​​dobit koja ovisi o potražnji. Potražnja pak može imati jedno od četiri stanja (I, II, III i IV). U sljedećoj matrici elementi karakteriziraju dobit koju će poduzeće dobiti kada pusti u promet -ti proizvod i -to stanje potražnje:

Opis igre bimatrix. Sve igre koje su razmatrane pripadale su razredu igre s nultom sumom. Međutim, niz konfliktnih situacija koje se razvijaju tijekom radnji karakterizira činjenica da dobitak jedne strane nije baš jednak gubitku druge. Modeli teorije igara takve situacije su nekooperativne igre sa sumom različitom od nule. Takve igre se nazivaju bimatrične, jer se zadatak svake takve igre svodi na zadatak dvije matrice i istog oblika: .

Postupak bimatrična igra sastoji se u samostalnom izboru broja od strane igrača I i broja od strane igrača II, nakon čega igrač I dobiva isplatu, a igrač II dobiva isplatu.

Pozvat će se brojevi redaka matrica i igračeve čiste strategije I, a brojevi stupaca ovih matrica su igračeve čiste strategije II. Tada će parovi oblika biti situacije u čistim strategijama bimatrična igra, a brojevi i su dobitci igrača I i II u situaciji . Sukladno tome, distribucija vjerojatnosti primjene čistih strategija igrača I je i igrač II - nazvat ćemo mješovite strategije. Tada parovi oblika predstavljaju situacije bimatrična igra u mješovite strategije, i brojevi i očekivani su dobici igrača I i II.

Ravnotežna situacija bimatrične igre u mješovitim strategijama nazvat ćemo par tako da:

(8.2)

gdje je matematičko očekivanje isplate igrača I;

Matematičko očekivanje isplate igrača II;

Optimalno miješano strategija igrača ja;

Optimalno miješano strategija igrača II.

Zadatak

Konstrukcija i rješavanje bimatrične igre. Pretpostavimo da protupodmornička podmornica neke zemlje traži državnu raketnu podmornicu koja manevrira u strogo određenom dijelu područja borbene ophodnje. ASW podmornica djeluje u ostatku područja i traži ASW. Neka svaki protupodmornički čamac za otkrivanje neprijatelja može koristiti svoju hidroakustičku stanicu ili u aktivnom načinu rada, povremeno ga uključuje, ili samo u pasivnom načinu rada, obavljajući kontinuiranu potragu.

I protupodmornička podmornica i raketna podmornica s detekcijom sonarnih signala mogu izbjeći neprijatelja. No, učestalost uključivanja sonara čini detekciju mogućom, ali nepouzdanom.

U takvim konfliktna situacija jedan od igrača je protupodmornička podmornica, a drugi je protupodmornička podmornica. Očito, raketna podmornica ne može biti igrač, budući da ima samo jedan način djelovanja, a to je tajno manevriranje i izvođenje radnji izbjegavanja s otkrivanje sonarnih signala.

Ovdje je karakteristično da svaki od igrača teži različitim, ali ne suprotnim ciljevima. Doista, svrha ASW podmornice je locirati raketnu podmornicu, a svrha ASW podmornice je locirati ASW. Dakle, za procjenu ostvarenja cilja od strane svakog od igrača, ovisno o odabranim metodama djelovanja (strategiji), potrebno je imati dva kriterija učinkovitosti i, sukladno tome, dvije funkcije isplate. Tada će model takve konfliktne situacije biti konačna igra sa sumom različitom od nule, opisana s dvije matrice istog oblika i , koja se naziva bimatrica.

Uzmimo za kriterij učinkovitosti protupodmornička podmornica (igrač I) vjerojatnost otkrivanja raketne podmornice, a za kriterij učinkovitosti protupodmornička podmornica (igrač II) - vjerojatnost otkrivanja protupodmorničke podmornice . Tada će bimatrična igra biti dana matricom (slika 9.a) i matricom (slika 9.b).

Gdje - korištenje aktivnog načina rada;

Korištenje pasivnog načina rada.

Među konačnim igrama od praktične važnosti, igre sa sedlom su razmjerno rijetke; tipičniji je slučaj kada su donja i gornja cijena - igre različite. Analizirajući matrice takvih igara došli smo do zaključka da ako se svakom igraču da izbor

jedna - jedina strategija., onda, na temelju razumno djelujućeg protivnika, ovaj izbor treba odrediti minimaksnim načelom. Pridržavajući se naše maximin strategije, sigurno si jamčimo isplatu jednaku nižoj cijeni igre, a, za bilo kakvo ponašanje protivnika. Postavlja se prirodno pitanje: je li moguće zajamčiti sebi prosječnu isplatu veću od a ako ne primijenite samo jednu "čistu" strategiju, već nasumično izmjenjujete nekoliko strategija?

Takve kombinirane strategije, koje se sastoje od primjene nekoliko čistih strategija koje se izmjenjuju prema slučajnom zakonu s određenim omjerom frekvencija, nazivaju se u teoriji igara mješovitim strategijama.

Očito je da je svaka čista strategija poseban slučaj mješovite, u kojoj se sve strategije osim jedne primjenjuju s nula frekvencija, a ova - s frekvencijom 1.

Ispada da je primjenom ne samo čistih već i mješovitih strategija moguće dobiti rješenje za svaku konačnu igru, tj. par (općenito mješovitih) strategija tako da kada ih oba igrača koriste, isplata će biti jednaka cijenu igre, a pri bilo kakvom jednostranom odstupanju od optimalne strategije, dobitak se može promijeniti samo u smjeru nepovoljnom za devijanta.

Navedena tvrdnja sadržaj je tzv. glavnog teorema teorije igara. Ovaj teorem je prvi dokazao von Neumann 1928. Poznati dokazi teorema su relativno složeni; stoga donosimo samo njegovu formulaciju.

Svaka konačna igra ima barem jedno rješenje (možda u području mješovitih strategija).

Isplata koja proizlazi iz odluke naziva se cijena igre. Iz glavnog teorema slijedi da svaka konačna igra ima cijenu. Očito je da se cijena igre v uvijek nalazi između donje cijene igre a i gornje cijene igre:

Doista, postoji maksimalna zajamčena dobit koju možemo osigurati za sebe koristeći samo naše vlastite čiste strategije. Budući da mješovite strategije uključuju, kao poseban slučaj, sve čiste, dopuštajući, osim čistih, i mješovite

strategija, mi, u svakom slučaju, ne pogoršavamo svoje sposobnosti; Posljedično,

Isto tako, s obzirom na mogućnosti protivnika, to pokazujemo

odakle slijedi tražena nejednakost (3.1).

Uvedimo posebnu oznaku za mješovite strategije. Ako se, na primjer, naša mješovita strategija sastoji u primjeni AL strategija, s frekvencijama i ovu ćemo strategiju označiti

Slično tome, protivnikova mješovita strategija bit će označena sa:

gdje su frekvencije na kojima se strategije miješaju

Pretpostavimo da smo pronašli rješenje igre koje se sastoji od dvije optimalne mješovite strategije S, S. U općem slučaju, nisu sve čiste strategije dostupne danom igraču uključene u njegovu optimalnu mješovitu strategiju, već samo neke od njih. Strategije uključene u igračevu optimalnu mješovitu strategiju nazvat ćemo njegovim "korisnim" strategijama.

Ispada da rješenje igre ima još jedno izvanredno svojstvo: ako se jedan od igrača pridržava svoje optimalne mješovite strategije 5 (5). tada isplata ostaje nepromijenjena i jednaka cijeni igre v, bez obzira na to što drugi igrač čini, ako on. samo ne ide dalje od svojih "korisnih" strategija. On, na primjer, može upotrijebiti bilo koju svoju "korisnu" strategiju u čisti oblik, a može ih i miješati u bilo kojem omjeru.

Dokažimo ovu tvrdnju. Neka postoji rješenje za igru. Radi konkretnosti, pretpostavit ćemo da se optimalna mješovita strategija sastoji od mješavine triju strategija

"korisne" strategije sastoji se od mješavine triju "korisnih" strategija

i Tvrdi se da ako se držimo strategije S, tada protivnik može primijeniti strategije u bilo kojem omjeru, a dobitak će ostati nepromijenjen te će i dalje biti jednak cijeni igre

Općenito, V * ≠ V * - nema sedla. U čistim strategijama također nema optimalnog rješenja. Međutim, ako koncept čiste strategije proširimo uvođenjem koncepta mješovite strategije, tada možemo implementirati algoritam za pronalaženje optimalnog rješenja za ne sasvim definiran problem igre. U takvoj situaciji predlaže se korištenje statističkog (probabilističkog) pristupa pronalaženju optimalnog rješenja antagonističke igre. Za svakog igrača, uz zadani skup mogućih strategija za njega, uvodi se nepoznati vektor vjerojatnosti (relativnih frekvencija) s kojima treba primijeniti jednu ili drugu strategiju.

Označimo vektor vjerojatnosti (relativne frekvencije) izbora zadanih strategija igrača A na sljedeći način:
P = (p 1 , p 2 ,…, p m),
gdje je p i ≥ 0, p 1 + p 2 +…+ p m = 1. Vrijednost p i naziva se vjerojatnost (relativna frekvencija) primjene strategije A i .

Slično, za igrača B uvodi se nepoznati vektor vjerojatnosti (relativnih frekvencija) koji ima oblik:
Q = (q 1 , q 2 ,…, q n),
gdje je q j ≥ 0, q 1 + q 2 +…+ q n = 1. Veličina q j naziva se vjerojatnost (relativna učestalost) primjene strategije B j . Skup (kombinacija) čistih strategija A 1 , A 2 , …A m i B 1, B 2, …B n u kombinaciji s vektorima vjerojatnosti izbora svake od njih nazivaju se mješovite strategije.

Glavni teorem u teoriji konačnih antagonističkih igara je Von Neumannov teorem: svaka igra s konačnom matricom ima barem jedno optimalno rješenje, moguće među mješovitim strategijama.
Iz ovog teorema slijedi da igra koja nije dobro definirana ima barem jedno optimalno rješenje u mješovitim strategijama. U takvim igrama rješenje će biti par optimalnih mješovitih strategija P * i Q * , tako da ako se jedan od igrača pridržava svoje optimalne strategije, drugom igraču nije isplativo odstupiti od svoje optimalne strategije.
Prosječna isplata igrača A određena je matematičkim očekivanjem:

Ako je vjerojatnost (relativna učestalost) primjene strategije različita od nule, tada se takva strategija naziva aktivan.

Strategije P * , Q * nazivaju se optimalno mješoviti strategije ako je M A (P, Q *) ≤ M A (P *, Q *) ≤ M A (P *, Q) (1)
U ovom slučaju se poziva M A (P * , Q *). po cijeni igre i označava se sa V (V * ≤ V ≤ V *). Prva od nejednakosti (1) znači da odstupanje igrača A od njegove optimalne mješovite strategije pod uvjetom da se igrač B drži svoje optimalne mješovite strategije, dovodi do smanjenja prosječnog dobitka igrač A. Druga od nejednakosti znači da odstupanje igrača B od njegove optimalne mješovite strategije pod uvjetom da se igrač A drži svoje optimalne mješovite strategije, dovodi do povećanja prosječnog gubitka igrača B.

U općem slučaju, takve probleme ovaj kalkulator uspješno rješava.

Primjer.

1. Provjerite ima li matrica isplate sedlišnu točku. Ako da, onda ispisujemo rješenje igre u čistim strategijama.

Pretpostavljamo da igrač I bira svoju strategiju na takav način da maksimizira svoj dobitak, a igrač II bira svoju strategiju na takav način da minimizira dobitak igrača I.

Pronalazimo zajamčeni dobitak određen nižom cijenom igre a = max(a i) = 2, što označava maksimalnu čistu strategiju A 1 .
Gornja cijena igra b = min(b j) = 7. Ovo ukazuje na nepostojanje sedla, budući da je a ≠ b, tada je cijena igre unutar 2 ≤ y ≤ 7. Rješenje igre nalazimo u mješovitim strategijama. To se objašnjava činjenicom da igrači ne mogu objaviti svoje čiste strategije protivniku: trebali bi sakriti svoje akcije. Igra se može riješiti tako da igrači nasumično odaberu svoje strategije (pomiješajte čiste strategije).

2. Provjerite matricu isplata za dominantne retke i dominantne stupce.
U matrici isplate nema dominantnih redaka i dominantnih stupaca.

3. Pronalaženje rješenja igre u mješovitim strategijama.
Zapišimo sustav jednadžbi.
Za igrača I
4p1 +7p2 +2p3 = y
7p1 +3p2 +p3 = y
2p 1 +2p 2 +8p 3 = y
p1 +p2 +p3 = 1

Za igrača II
4q1 +7q2 +2q3 = y
7q1 +3q2 +2q3 = y
2q1 +q2 +8q3 = y
q 1 + q 2 + q 3 = 1

Rješavanjem ovih sustava Gaussovom metodom nalazimo:

y=4 1/34
p 1 = 29/68 (vjerojatnost primjene 1. strategije).
p 2 = 4/17 (vjerojatnost primjene 2. strategije).
p 3 = 23/68 (vjerojatnost primjene 3. strategije).

Optimalna mješovita strategija igrača I: P = (29 / 68 ; 4 / 17 ; 23 / 68)
q 1 = 6 / 17 (vjerojatnost primjene 1. strategije).
q 2 = 9/34 (vjerojatnost primjene 2. strategije).
q 3 = 13/34 (vjerojatnost primjene 3. strategije).

Optimalna mješovita strategija igrača II: Q = (6 / 17 ; 9 / 34 ; 13 / 34)
Cijena igre: y = 4 1 / 34