Čiste i mješovite strategije. Metoda izračuna optimalnih strategija

teorija igra strategija mixed

Mješovite strategije

Ako nema sedla u čistim strategijama u matričnoj igri, tada se pronalaze gornja i donja cijena igre. Oni pokazuju da igrač 1 neće dobiti isplatu veću od gornje cijene igre i da je igraču 1 zajamčena isplata ne manja od niže cijene igre.

Igračeva mješovita strategija je kompletan skup njegovih čistih strategija kada se igra ponavlja mnogo puta u istim uvjetima sa zadanim vjerojatnostima. Rezimirajmo rečeno i nabrojimo uvjete za primjenu mješovitih strategija:

• * igra bez sedla;
• * igrači koriste slučajnu mješavinu čistih strategija sa zadanim vjerojatnostima;
• * igra se ponavlja mnogo puta u sličnim uvjetima;
• * pri svakom od poteza nijedan igrač nije obaviješten o izboru strategije od strane drugog igrača;
• * dopušteno je usrednjavanje rezultata igre.

Koristi se sljedeća oznaka za mješovite strategije.

Za igrača 1, mješovita strategija koja se sastoji u primjeni čistih strategija A 1 , A 2 , ..., A t s odgovarajućim vjerojatnostima p 1 , p 2, ..., p t.

Za igrača 2

q j je vjerojatnost primjene čiste strategije B j .

U slučaju kada je p i = 1, za igrača 1 imamo čistu strategiju

Igračeve čiste strategije jedini su mogući nekompatibilni događaji. U matričnoj igri, znajući matricu A (odnosi se i na igrača 1 i na igrača 2), možemo odrediti kada zadani vektori i prosječna isplata (matematičko očekivanje učinka) igrača 1:

gdje su i vektori;

p i i q i su komponente vektora.

Primjenom svojih mješovitih strategija, igrač 1 nastoji maksimizirati svoju prosječnu isplatu, a igrač 2 nastoji ovaj učinak svesti na najmanju moguću vrijednost. Igrač 1 ima za cilj doseći

Igrač 2 pokušava zadovoljiti uvjet

Označimo također vektore koji odgovaraju optimalnim mješovitim strategijama igrača 1 i 2, tj. takvi vektori i za koje jednakost

Trošak igre je prosječna isplata igrača 1 kada oba igrača koriste mješovite strategije. Stoga je rješenje igre matrice:

• - optimalna mješovita strategija igrača 1;
• - optimalna mješovita strategija igrača 2;

Cijena igre.

Mješovite strategije bit će optimalne (u) ako tvore sjedište za funkciju, tj.

Postoji osnovni teorem matematičkih igara.

Za matričnu igru ​​s bilo kojom matricom A, vrijednosti

postoje i međusobno su jednaki: = = .

Treba napomenuti da pri odabiru optimalne strategije igraču 1 uvijek će biti zajamčena prosječna isplata ne manja od cijene igre, za bilo koji fiksna strategija igrač 2 (i obrnuto za igrača 2). Aktivne strategije igrača 1 i 2 su strategije koje su dio optimalnih mješovitih strategija odgovarajućih igrača s vjerojatnostima različitima od nule. To znači da sastav optimalnih mješovitih strategija igrača ne mora uključivati ​​sve njihove apriori zadane strategije.

Riješiti igru ​​znači pronaći cijenu igre i optimalne strategije. Razmatrajući metode za pronalaženje optimalnih mješovitih strategija za matrične igre, počinjemo s najjednostavnija igrica, opisan matricom 22. Igre sa sedlom točkom nećemo posebno razmatrati. Ako se dobije sedlasta točka, to znači da postoje neprofitabilne strategije koje treba napustiti. U nedostatku sedlaste točke mogu se dobiti dvije optimalne mješovite strategije. Kao što je već navedeno, ove mješovite strategije su napisane na sljedeći način:

Dakle, postoji matrica isplate

a 11 p 1 + a 21 p 2 = ; (1.16)

a 12 p 1 + a 22 p 2 =; (1.17)

p 1 + p 2 = 1. (1.18)

a 11 p 1 + a 21 (1 - p 1) = a 12 p 1 + a 22 (1 - p 1); (1.19)

a 11 p 1 + a 21 - a 21 p 1 = a 12 p 1 + a 22 - a 22 p 1 , (1.20)

gdje dobivamo optimalne vrijednosti:

Znajući i nalazimo:

Računanjem nalazimo:

a 11 q 1 + a 12 q 2 = ; q 1 + q 2 \u003d 1; (1,24)

a 11 q 1 + a 12 (1 - q 1) = . (1,25)

za 11 do 12. (1,26)

Problem je riješen jer su pronađeni vektori i cijena igre. Imajući matricu plaćanja A, problem možemo riješiti grafički. Ovom metodom algoritam rješenja je vrlo jednostavan (slika 2.1).

• 1. Isječak jedinične duljine nacrtan je duž apscise.
• 2. Na y-osi dobici su ucrtani sa strategijom A 1 .
• 3. Na liniji paralelnoj s osi y, u točki 1, iscrtavaju se isplate za strategiju a 2 .
• 4. Krajevi segmenata označeni su za a 11 -b 11, a 12 -b 21, a 22 -b 22, a 21 -b 12 i nacrtane su dvije ravne crte b 11 b 12 i b 21 b 22.
• 5. Određuje se ordinata presječne točke s. Ona je ravnopravna. Apscisa točke c jednaka je p 2 (p 1 \u003d 1 - p 2).

Riža. 1.1.

Ova metoda ima prilično široko područje primjene. Ovo se temelji na zajedničko vlasništvo igre tn, koja se sastoji u tome da u bilo kojoj igri tn svaki igrač ima optimalnu mješovitu strategiju u kojoj je broj čistih strategija najviše min(m, n). Iz ovog svojstva može se dobiti dobro poznati korolar: u svakoj igri 2n i m2 svaka optimalna strategija u sadrži najviše dvije aktivne strategije. Stoga se svaka igra 2n i m2 može svesti na igru ​​22. Dakle, igre 2n i m2 mogu se riješiti grafički. Ako konačna matrica igre ima dimenziju mn, gdje je m > 2 i n > 2, tada se linearno programiranje koristi za određivanje optimalnih mješovitih strategija.

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 igre b = min(b j) = 7. Ovo ukazuje na odsutnost sedla, budući da je a ≠ b, tada je cijena igre unutar 2 ≤ y ≤ 7. Nalazimo rješenje igre u mješovitim strategijama. To se objašnjava činjenicom da igrači ne mogu proglasiti svoje protivnike čiste strategije: Trebali bi skrivati ​​svoje postupke. 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.
NA platna matrica 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

Matrična igra za dva igrača s nultim zbrojem može se promatrati kao sljedeća apstraktna igra za dva igrača.

Prvi igrač ima m strategije ja = 1,2,...,m, drugi ima n strategije j= 1,2,...,n. Svaki par strategija ( ja, j) dodijeljen je broj a i J , izražavajući isplatu igrača 1 na račun igrača 2 ako prvi igrač prihvati svoje ja- strategija, a 2 - vaša j-ta strategija.

Svaki igrač čini jedan potez: igrač 1 bira svoj ja-ta strategija ( ja= ), 2 – vlastiti j-ta strategija ( j=
), nakon čega igrač 1 pobjeđuje a i J na račun igrača 2 (ako a i J < 0, to znači da igrač 1 plaća drugom igraču | a i J|). Ovdje igra završava.

Strategija svakog igrača ja=
; j =
često nazivaju čistom strategijom.

Ako uzmemo u obzir matricu

I=

zatim izvođenje svake igre matrice igre s matricom I svodi se na izbor igrača 1 ja-ta linija, a igrač 2 j-ti stupac i igrač 1 (na račun igrača 2) dobiva isplatu a ij .

Glavna stvar u proučavanju igara je koncept optimalnih strategija za igrače. Ovaj koncept intuitivno ima sljedeće značenje: strategija igrača je optimalna ako mu primjena te strategije osigurava najveći zajamčeni dobitak za sve moguće strategije drugog igrača. Na temelju ovih pozicija, igrač 1 istražuje matricu isplate I kako slijedi: za svaku vrijednost ja (ja =
) minimalna vrijednost isplate određena je ovisno o primijenjenim strategijama igrača 2

a i J (ja=
)

oni. određena je minimalna isplata za igrača 1, pod uvjetom da on prihvati svoje ja-th čista strategija, onda se takva strategija nalazi iz ovih minimalnih dobitaka ja = ja oko, pri čemu će ova minimalna isplata biti maksimalna, tj. je

a i J =
=(1)

Definicija . Broj definiran formulom (1) naziva se niža neto cijena igre i pokazuje koju minimalnu isplatu igrač 1 može zajamčiti sebi primjenom svojih čistih strategija za sve moguće akcije igrača 2.

Igrač 2, svojim optimalnim ponašanjem, treba nastojati minimizirati isplatu igrača 1 što je više moguće nauštrb njegovih strategija. Stoga, za igrača 2,

a i J

oni. određuje se maksimalna isplata igrača 1, pod uvjetom da igrač 2 primijeni svoje j-th čista strategija, onda igrač 2 pronalazi takvu j = j 1 strategija u kojoj igrač 1 dobiva minimalnu isplatu, tj. nalazi

a i J =
=(2).

Definicija . Broj , određena formulom (2), naziva se neto gornja cijena igre i pokazuje koju maksimalnu isplatu igrač 1 može zajamčiti sebi zbog svojih strategija.

Drugim riječima, primjenom svojih čistih strategija, igrač 1 može osigurati isplatu ne manju od , a igrač 2, primjenom svojih čistih strategija, može spriječiti igrača 1 da osvoji više od .

Definicija . Ako je u igri s matricom A =, onda se kaže da ova igra ima sedlo točka u čistim strategijama i Internetska cijena igre

 = =.

sedlasta točka je par čistih strategija (ja oko , j oko ) igrači 1 i 2, redom, pod kojim je postignuta ravnopravnost =. Ovaj koncept ima sljedeće značenje: ako se jedan od igrača pridržava strategije koja odgovara sedloj točki, onda drugi igrač ne može učiniti bolje od toga da se pridržava strategije koja odgovara sedloj točki. Matematički, ovo se može napisati na drugi način:

gdje ja, j su sve čiste strategije igrača 1 i 2; (ja oko , j oko ) su strategije koje tvore sedlo.

Dakle, na temelju (3), element sedla
je minimum u i o -tom retku i maksimum u j o -tom stupcu u matrici A. Nalaženje sedlaste točke matrice A je kako slijedi: u matrici A, sukcesivno u svakoj crta pronađite minimalni element i provjerite je li taj element maksimalni u svom stupac. Ako da, onda je to sedlasti element, a par strategija koji mu odgovaraju čini sedlastu točku. Par čistih strategija (ja oko , j oko ) igrači 1 i 2, tvoreći sedlo i element sedla
, Zove se odluka igre . pri čemu ja oko i j oko nazvao optimalno čišćenje strategije igrači 1 i 2 redom.

Primjer 1

Sjedište je par ( ja oko = 3;j oko= 1), pri čemu je = == 2.

Imajte na umu da iako je isplata u situaciji (3;3) također jednaka 2 = =, nije sedlo, jer ova isplata nije najveća među isplatama trećeg stupca.

Primjer 2

Iz analize isplatne matrice vidljivo je da
, tj. ova matrica nema sedlu. Ako igrač 1 odabere svoju čistu maximin strategiju ja = 2, zatim igrač 2, nakon što je odabrao svoj minimaks j= 2, izgubit će samo 20. U ovom slučaju, igraču 1 je isplativo izabrati strategiju i = 1, tj. odstupiti od svoje čiste maximin strategije i osvojiti 30. Tada će igraču 2 biti isplativo odabrati strategiju j = 1, tj. odstupiti od svoje čiste minimax strategije i izgubiti 10. Zauzvrat, igrač 1 mora izabrati svoju 2. strategiju da bi osvojio 40, a igrač 2 odgovara odabirom svoje 2. strategije, i tako dalje.

Razmotrite primjer. Neka je dana matrica igre (4):

Potrebno je pronaći donju cijenu igre α, gornju cijenu igre β i minimax strategije te provjeriti jesu li stabilne. Odluka. Iz analize dodatnih stupaca i redaka dobivamo: α = 5, β = 5. Maksimin je jednak minimaksu! Slučaj je poseban. Što iz ovoga slijedi? Uzmimo nekoliko minimaks strategija: K 2 i C 3 . Ako se obojica drže ove strategije, dobit će biti 5. Sada, recimo da smo naučili o ponašanju protivnika. Što nam je činiti? I ništa! I dalje ćemo se držati strategije K 2 jer nam je svako odstupanje od nje neisplativo. Znali ili ne znali za ponašanje neprijatelja, i dalje ćemo se držati K 2 strategije! Isto vrijedi i za "modre" - nema smisla da mijenjaju strategiju C 3 . NA ovaj primjer par strategija K 2 i C 3 je stabilan, odnosno predstavlja ravnotežni položaj i daje rješenje igre. Zašto se to dogodilo? Budući da u matrici postoji poseban element 5; to je minimum u svom retku i istovremeno maksimum u svom stupcu. Takav se element naziva sedlasta točka. Ako matrica ima sedlo (tj. donja cijena igre jednaka je gornjoj), tada igra ima rješenje u čistim strategijama: to je par strategija koje se sijeku u sedlu. Sama sedlasta točka daje cijenu igre - u našem primjeru ona je jednaka 5. Klasa igara koje imaju sedlišnu točku je od velike važnosti u teoriji igara. Konkretno, dokazano je da ako, prema pravilima igre, svaki od igrača zna rezultat svih prethodnih poteza, i svojih i protivničkih (tzv. igra s potpunom informacijom), onda igra ima sedlo i stoga ima rješenje u čistim strategijama. Primjeri igara s potpunim informacijama su: šah, dama, "tic-tac-toe" itd. Navedimo primjer igre s potpunim informacijama, čije je rješenje lako pronaći. Dva igrača - K i C - naizmjenično stavljaju iste novčiće na okrugli stol. Položaj svakog novčića odabire se proizvoljno, sve dok se ne preklapa s ostalima. Pobjednik je igrač koji zadnji stavi novčić (kada nema mjesta za ostale). Potrebno je malo razmisliti kako bi se osiguralo da je ishod ove igre uvijek predodređen i da postoji dobro definirana strategija koja jamči pobjedu igraču koji prvi stavi novčić (neka bude K). Naime, K mora staviti prvi novčić u središte stola, a zatim na svaki potez C mora odgovoriti potezom točno simetričnim u odnosu na središte stola! Jadni C se može ponašati kako hoće, ipak mu nema spasa... Očito, takva igra ima smisla samo za one koji ne znaju rješenje. Zanimljivo je da je upravo isti slučaj i s takvima popularna igra kao šah! Ova igra ima smisla samo dok se ne pronađe rješenje. Teoretski je dokazano da rješenje postoji i da je ishod šahovske partije u biti unaprijed gotov zaključak: ako svaka strana koristi vlastitu optimalnu strategiju, tada će partija ili uvijek završiti pobjedom bijelog, ili uvijek pobjedom bijelog Crno, ili uvijek neriješeno! Ali što točno? To još ne znamo, jer je broj mogućih strategija prevelik da bi se konstruirala matrica šahovske partije i u njoj pronašla sedlasta točka... Vjerojatno ljubitelje šaha zanima činjenica da šahovska partija neće biti uskoro riješeno. Zaključno, napominjemo da u matrici ne može postojati jedna, već nekoliko točaka sedla; onda postoji onoliko rješenja igre u čistim strategijama koliko ima sedlišnih točaka. Svaki od njih daje isplatu jednaku cijeni igre.

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 niže cijene igre a i vrhunska cijena 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

Ako u igri svaki od protivnika koristi istu strategiju, tada se za ovu igru ​​kaže da se odvija u čistim strategijama, a strategije igrača A i B će se zvati čiste strategije.U antagonističkoj igri par strategija se zove ravnoteža(održivo) ako je nekom od igrača neisplativo odustati od svojih strategija.Ima smisla koristiti čiste strategije ako su igrači svjesni akcija protivnika. Ako to nije slučaj, tada je ideja ravnoteže narušena i igra se može igrati kako hoće. Strategije A1 B1 su stabilne u odnosu na informacije o ponašanju protivnika. Znak stabilnosti para strategija je jednakost gornje i donje cijene igre. I slučaj A1 B1 će biti

ν = α = β. ν > 0, tada će igrač A pobijediti ako je ν< 0, то в выигрыше игрок В. Если ν = 0, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.

Teorem: svaka igra sa savršenim informacijama ima sjedište i stoga rješava u čistim strategijama, tj. postoji par stabilnih strategija koje daju stabilnu isplatu jednaku ν. Ako matrica nema sjedište, tada je cijena igre α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии.Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.

Određivanje mješovite strategije znači određivanje vjerojatnosti s kojima se koriste čiste strategije.

S A = || p 1 , p 2 .... popodne || ,S B = || q1, q2 …. q m || , A: ∑pi = 1, B: ∑qi = 1

Igra se može ponoviti nekoliko puta, ali u svakoj igri igrač slijedi mješovitu strategiju, gdje čiste strategije slijede vjerojatnosti p i i q j .

Model mješovite strategije razlikuje se od modela čiste strategije. U slučaju mješovitih strategija, taktika ponašanja igrača bit će fleksibilnija, jer igrači unaprijed znaju koju će čistu strategiju koristiti.

Pretpostavimo da i igrač A i igrač B slijede mješovitu strategiju. Potrebno je odrediti A: ∑∑ a ij p i q j

Za igrača B, očekivani gubitak jednak je očekivanom dobitku igrača A. Dobitak prvog igrača i prosječni gubitak drugog igrača međusobno su jednaki.

18. Metode rješavanja konačne igre za dvije osobe reda m * n.

Pretpostavimo da su svi elementi matrice isplate 0≤aij. Tada je α≤ν≤β. Prema temeljnom teoremu matričnih igara, svaka matrična igra ima 2 optimalne mješovite strategije.

S A \u003d (p 1, p 2, ..., p n)

S B = (p 1 , p 2 , … , p n)

Rješavamo igru ​​za igrača A, uz pretpostavku da igrač B koristi samo čiste strategije. Zatim

a 11 p 1 + a 21 p 2 + … + a m1 p m ≥ ν: B 1

a 12 p 1 + a 22 p 2 + … + a m2 p m ≥ ν: B 2 (1)

a 1n p 1 + a 2n p 2 + … + a mn p m ≥ ν: B n

X 1 \u003d P 1 / ν, X 2 = P 2 / ν ... X m \u003d P m / ν

a 11 X 1 … + a m1 p m ≥ 1

a 1n X 1 … + a m1 p m ≥ 1 (2)

p 1 +p 2 +…+p m =1

X 1 +X 2 +…+X m = 1/ν (3)

L(x) = X 1 +X 2 +…+X m -> min (4)

Definirajmo problem linearnog programiranja.

ν = 1/(X 1 0 +X 2 0 …X m 0) (5)

P1 = X 1 0 *ν opt

p2 = X 2 0 *ν opt (6)

minL(x) = ∑x i

∑a ij: 1≤x i (7) (izravni zadatak)

0≤x i (i=1,2..)

a 11 q 1 + a 21 q 2 + … + a m1 q m< ν: A 1

a 21 q 1 + a 22 q 2 + … + a m2 q m< ν: A 2 (8)

a m1 q 1 + a m2 q 2 + … + a mn q m< ν: A m

Y 1 \u003d q 1 / ν, Y 2 \u003d q 2 / ν ... Y m \u003d q m / ν

q 1 + q 2 +… + q n =1

y 1 +y 2 +…+y n =1/ν

L(y)=∑yj -> maks

∑a ij , y i ≤1 (i=1,2…) (9) (dvostruki problem)

y 1 0 +y 2 0 …y m 0 = 1/ν opt

ν opt = 1/∑y m 0

Q1 = y 1 0 *ν opt

q2 = y 2 0 *ν opt

ν=1/∑x i = 1/∑y i = 1/min L(x) = 1/ max L(y) (11)

1) α = 1, β = 3

2) Nema pojednostavljenja.

L(x)=x 1 +x 2 +x 3 => min

x1 +3x2 +x3 >= 1

2x1 +x2 +x3 >=1

3x1 +x2 +x3 >=1

x 1 \u003d 2/9, x 2 = 2/9, x 3 \u003d 1/9

v=1/(2/9+2/9+1/9)=9/5

p 1 \u003d x 1 * ν \u003d 2/5

S A =(2/5, 2/5, 1/5)

dvostruki zadatak

L(y) = y 1 + y 2 + y 3 => maks

y 1 +2y 2 +3y 3 ≤ 1 y 1 =2/9

3y 1 +y 2 +y 3 ≤1 => y 2 =2/9 max L(y) = 5/9

y 1 +3y 2 +y 3 ≤1 y 3 =1/9

v=1/(2/9+2/9+1/9)=9/5

q 1 \u003d y 2 *ν \u003d (2/9) * (9/5) \u003d 2/5

q 2 \u003d (2/9) * (9/5) \u003d 2/5

q 3 \u003d (1/9) * (9/5) \u003d 1/5

S B =(2/5, 2/5, 1/5)

Problem mxn svodi se na problem linearnog programiranja.

Približna metoda za rješavanje mxn matričnih igara (Brown-Robinson).

Igrač A i igrač B naizmjence primjenjuju čiste strategije. Svaki igrač pokušava povećati svoj dobitak korištenjem maximin ili minimax pristupa. Ne minimizira se (maksimizira) prosječni dobitak, nego akumulirani. U teoriji je pokazano da će nam takva metoda neizbježno dati optimalnu isplatu i optimalne mješovite strategije.