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

teorija igre strategija mješovita

Mješovite strategije

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

Mešovita strategija igrača je kompletan skup njegovih čistih strategija kada se igra ponavlja mnogo puta u istim uslovima sa datim verovatnoćama. Hajde da sumiramo ono što je rečeno i navedemo uslove za primenu mešovitih strategija:

• * igra bez sedla;
• * igrači koriste nasumičnu mješavinu čistih strategija sa datim vjerovatnoćama;
• * igra se ponavlja više puta u sličnim uslovima;
• * pri svakom potezu nijedan igrač nije obaviješten o izboru strategije od strane drugog igrača;
• * Usrednjavanje rezultata igre je dozvoljeno.

Za mješovite strategije koristi se sljedeća notacija.

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

Za igrača 2

q j je vjerovatnoća primjene čiste strategije B j .

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

Čiste strategije igrača su jedini 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 dati vektori i prosječna isplata (matematičko očekivanje efekta) igrača 1:

gdje i su vektori;

p i i q i su vektorske komponente.

Primjenom svojih mješovitih strategija, igrač 1 nastoji maksimizirati svoju prosječnu isplatu, a igrač 2 nastoji dovesti ovaj efekat do minimalne moguće vrijednosti. Igrač 1 ima za cilj da dosegne

Igrač 2 pokušava da zadovolji uslov

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

Cijena igre je prosječna isplata igrača 1 kada oba igrača koriste mješovite strategije. Dakle, rješenje matrične igre je:

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

Cijena igre.

Mješovite strategije će biti optimalne (u) ako formiraju sedlo za funkciju, tj.

Postoji osnovna teorema matematičkih igara.

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

postoje i jednaki su jedno drugom: = = .

Treba napomenuti da prilikom odabira optimalne strategije igraču 1 će uvijek biti zagarantovana 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 sa vjerovatnoćama različitim od nule. To znači da sastav optimalnih mješovitih strategija igrača možda ne uključuje sve njihove a priori 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 od najjednostavnija igrica, opisan matricom 22. Igre sa sedlom neće se posebno razmatrati. Ako se dobije sedlo, onda to znači da postoje neisplative strategije koje treba napustiti. U nedostatku sedla mogu se dobiti dvije optimalne mješovite strategije. Kao što je već napomenuto, 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)

gde dobijamo optimalne vrednosti:

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 a 12 . (1.26)

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

• 1. Segment jedinične dužine iscrtan je duž apscise.
• 2. Na y-osi, dobici su iscrtani sa strategijom A 1 .
• 3. Na liniji paralelnoj sa y-osom, u tački 1, isplate su iscrtane za strategiju a 2 .
• 4. Krajevi segmenata su označeni za a 11 -b 11, a 12 -b 21, a 22 -b 22, a 21 -b 12 i nacrtane su dvije prave linije b 11 b 12 i b 21 b 22.
• 5. Određuje se ordinata tačke preseka sa. Ona je jednaka. Apscisa tačke c jednaka je p 2 (p 1 \u003d 1 - p 2).

Rice. 1.1.

Ova metoda ima prilično široko područje primjene. Ovo se zasniva na zajedničko vlasništvo igre tn, koji se sastoji u činjenici 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 ove osobine može se dobiti dobro poznati zaključak: u bilo kojoj igri 2n i m2 svaka optimalna strategija u sadrži najviše dvije aktivne strategije. Dakle, bilo koja igra 2n i m2 može se svesti na igru ​​22. Dakle, igre 2n i m2 mogu se riješiti grafički. Ako matrica konačne 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. Također ne postoji optimalno rješenje u čistim strategijama. Međutim, ako proširimo koncept čiste strategije 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 (vjerovatnog) pristupa za pronalaženje optimalnog rješenja za antagonističku igru. Za svakog igrača, zajedno sa zadatim skupom mogućih strategija za njega, uvodi se nepoznati vektor vjerovatnoća (relativnih frekvencija) s kojim treba primijeniti jednu ili drugu strategiju.

Označimo vektor vjerovatnoća (relativnih frekvencija) izbora datih 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 vjerovatnoća (relativna frekvencija) primjene strategije A i .

Slično, za igrača B uvodi se nepoznati vektor vjerovatnoća (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 vjerovatnoća (relativna frekvencija) primjene strategije B j . Skup (kombinacija) čistih strategija A 1 , A 2 , …A m i B 1, B 2, …B n u kombinaciji sa vektorima vjerovatnoće izbora svake od njih naziva se mješovite strategije.

Glavna teorema u teoriji konačnih antagonističkih igara je Von Neumannova teorema: svaka igra konačne matrice ima barem jedno optimalno rješenje, moguće među mješovitim strategijama.
Iz ove teoreme slijedi da nedovoljno definirana igra 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, onda drugom igraču nije isplativo da odstupi od svoje optimalne strategije.
Prosječna isplata igrača A određena je matematičkim očekivanjem:

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

Strategije P*, Q* se nazivaju optimalno mešano 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) to znači odstupanje igrača A od njegove optimalne mješovite strategije pod uslovom da se igrač B drži svoje optimalne mješovite strategije, dovodi do smanjenja prosječnog dobitka igrač A. Druga od nejednakosti to znači odstupanje igrača B od njegove optimalne mješovite strategije pod uslovom da se igrač A drži svoje optimalne mješovite strategije, dovodi do povećanja prosječnog gubitka igrača B.

U opštem slučaju, ovakve probleme ovaj kalkulator uspešno rešava.

Primjer.

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

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

Pronalazimo zagarantovanu isplatu određen nižom cijenom igre a = max(a i) = 2, što ukazuje na maksimalnu čistu strategiju A 1 .
Gornja cijena igre b = min(b j) = 7. Ovo ukazuje na nepostojanje sedla, pošto je a ≠ b, onda je cijena igre unutar 2 ≤ y ≤ 7. Nalazimo rješenje igre u mešovitim strategijama. Ovo se objašnjava činjenicom da igrači ne mogu da se izjasne o svojim protivnicima čiste strategije: Trebali bi sakriti svoje postupke. Igra se može riješiti tako da se igračima pusti da nasumično biraju svoje strategije (miješaju čiste strategije).

2. Provjerite matricu isplate za dominantne redove i dominantne stupce.
AT matrica plaćanja nema dominantnih redova i dominantnih kolona.

3. Pronalaženje rješenja za igru ​​u mješovitim strategijama.
Zapišimo sistem jednačina.
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šavajući ove sisteme Gaussovom metodom, nalazimo:

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

Optimalna mješovita strategija igrača I: P = (29 / 68 ; 4 / 17 ; 23 / 68)
q 1 = 6 / 17 (vjerovatnoća primjene 1. strategije).
q 2 = 9/34 (vjerovatnoća primjene 2. strategije).
q 3 = 13/34 (vjerovatnoća 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 sa nultom sumom može se posmatrati kao sljedeća apstraktna igra za dva igrača.

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

Svaki igrač čini jedan potez: igrač 1 bira svoj i-ta strategija ( i= ), 2 – vl j-ta strategija ( j=
), nakon čega igrač 1 pobjeđuje a ij o trošku igrača 2 (ako a ij < 0, to znači da igrač 1 plaća drugom igraču | a ij|). Ovdje se igra završava.

Strategija svakog igrača i=
; j =
često se naziva čistom strategijom.

Ako uzmemo u obzir matricu

ALI=

zatim izvođenje svake igre matrične igre sa matricom ALI svodi se na izbor igrača 1 i-ta linija i igrač 2 j-th kolona i igrač 1 (na trošak igrača 2) prima isplatu a ij .

Glavna stvar u proučavanju igara je koncept optimalnih strategija za igrače. Ovaj koncept intuitivno ima sledeće značenje: igračeva strategija je optimalna ako mu primena ove strategije obezbeđuje najveću zagarantovanu isplatu za sve moguće strategije drugog igrača. Na osnovu ovih pozicija, igrač 1 istražuje matricu isplate ALI kako slijedi: za svaku vrijednost i (i =
) minimalna isplatna vrijednost se određuje u zavisnosti od primijenjenih strategija igrača 2

a ij (i=
)

one. određuje se minimalna isplata za igrača 1, pod uslovom da on prihvati svoju i-ta čista strategija, onda se takva strategija nalazi iz ovih minimalnih isplata i = i o, pri čemu će ova minimalna isplata biti maksimalna, tj. nalazi

a ij =
=(1)

Definicija . Broj definisan formulom (1) se zove niža neto cijena igrice i pokazuje koju minimalnu isplatu igrač 1 može sebi garantirati primjenom svojih čistih strategija za sve moguće akcije igrača 2.

Igrač 2 svojim optimalnim ponašanjem treba da nastoji da što više minimizira isplatu igrača 1 nauštrb njegovih strategija. Dakle, za igrača 2,

a ij

one. određuje se maksimalna isplata igrača 1, pod uslovom da igrač 2 primeni svoje j-ta čista strategija, onda igrač 2 pronađe takvu j = j 1 strategija u kojoj igrač 1 dobija minimalnu isplatu, tj. nalazi

a ij =
=(2).

Definicija . Broj , određeno formulom (2), se zove neto najviša cijena igrice i pokazuje koju maksimalnu isplatu igrač 1 može sebi garantirati zahvaljujući svojim strategijama.

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

Definicija . Ako u igri sa matricom A =, onda se za ovu igru ​​kaže da ima sedlo tačka u čistim strategijama i neto cijena igrice

 = =.

sedlo je par čistih strategija (i o , j o ) igrači 1 i 2, pod kojima se postiže jednakost =. Ovaj koncept ima sljedeće značenje: ako se jedan od igrača pridržava strategije koja odgovara tački sedla, onda drugi igrač ne može učiniti bolje nego da se pridržava strategije koja odgovara tački sedla. Matematički, ovo se može napisati na drugi način:

gdje i, j su bilo koje čiste strategije igrača 1 i 2, respektivno; (i o , j o ) su strategije koje formiraju sedlo.

Dakle, na osnovu (3), element sedla
je minimum u io -tom redu i maksimum u j o -tom stupcu u matrici A. Pronalaženje sedla matrice A je kako slijedi: u matrici A, sukcesivno u svakoj linija pronađite minimalni element i provjerite da li je ovaj element maksimalni u svom kolona. Ako je odgovor da, onda je to element sedla, a par strategija koje mu odgovaraju formiraju sedlo. Par čistih strategija (i o , j o ) igrači 1 i 2, formirajući sedlo i element sedla
, zove se odluka u igri . Gde i o i j o pozvao optimalno čišćenje strategije igrači 1 i 2.

Primjer 1

Tačka sedla je par ( i o = 3;j o= 1), pri čemu je = == 2.

Imajte na umu da iako je isplata u situaciji (3;3) takođe jednaka 2 = =, nije sedlo, jer ova isplata nije maksimalna među isplatama treće kolone.

Primjer 2

Iz analize matrice isplate može se vidjeti da
, tj. ova matrica nema tačku sedla. Ako igrač 1 odabere svoju čistu maksiminsku strategiju i = 2, zatim igrač 2, koji je izabrao svoj minimax j= 2, izgubiće samo 20. U ovom slučaju je isplativo da igrač 1 izabere strategiju i = 1, tj. odstupiti od svoje čiste maksiminske strategije i osvojiti 30. Tada će igraču 2 biti isplativo da odabere strategiju j = 1, tj. odstupiti od svoje čiste minimaks strategije i izgubiti 10. Zauzvrat, igrač 1 mora izabrati svoju 2. strategiju da bi dobio 40, a igrač 2 odgovara odabirom svoje 2. strategije, i tako dalje.

Razmotrimo primjer. Neka je data matrica igre (4):

Potrebno je pronaći donju cijenu igre α, gornju cijenu igre β i minimaks strategije i provjeriti jesu li stabilne. Rješenje. Analizom dodatnih kolona i redova dobijamo: α = 5, β = 5. Maksimum je jednak minimumu! Slučaj je poseban. Šta iz ovoga slijedi? Uzmimo nekoliko minimaks strategija: K 2 i C 3 . Ako se oboje drže ove strategije, onda će isplata biti 5. Sada, recimo da smo naučili o ponašanju protivnika. Šta da radimo? I ništa! I dalje ćemo se držati strategije K 2, jer svako odstupanje od nje je za nas neisplativo. Bilo da znamo ili ne znamo za ponašanje neprijatelja, ipak ćemo se držati K 2 strategije! Isto važi i za "plave" - ​​nema smisla da menjaju strategiju C 3 . AT ovaj primjer par strategija K 2 i C 3 je stabilan, odnosno predstavlja ravnotežni položaj i daje rješenje igri. Zašto se to dogodilo? Zato što postoji poseban element 5 u matrici; to je minimum u svom redu i istovremeno maksimum u njegovoj koloni. Takav element se zove sedlo. Ako matrica ima sedlo (tj. donja cijena igre je jednaka gornjoj), onda igra ima rješenje u čistim strategijama: to je par strategija koje se sijeku u sedlu. Sama tačka sedla daje cenu igre - u našem primeru je jednaka 5. Klasa igara koje imaju sedlo je od velikog značaja u teoriji igara. Konkretno, dokazano je da ako, prema pravilima igre, svaki od igrača zna rezultat svih prethodnih poteza, kako vlastitih tako i protivničkih (tzv. igra s potpunim informacijama), tada igra ima sedlo i stoga ima rješenje u čistim strategijama. Primjeri igara sa potpunim informacijama su: šah, dame, "tik-tak-toe" itd. Navedimo primjer igre sa potpunim informacijama, čije rješenje je lako pronaći. Dva igrača - K i C - naizmjenično stavljaju iste novčiće na okrugli sto. Položaj svakog novčića bira se proizvoljno, sve dok se ne preklapa s ostalima. Pobjednik je igrač koji zadnji stavi novčić (kada nema mjesta za druge). Potrebno je malo razmisliti kako bi se osiguralo da je ishod ove igre uvijek unaprijed zaključen i da postoji dobro definirana strategija koja garantuje pobjedu igraču koji prvi stavi novčić (neka bude K). Naime, K mora staviti prvi novčić u centar stola, a zatim na svaki potez C mora odgovoriti potezom tačno simetričnim u odnosu na centar stola! Jadni C može da se ponaša kako hoće, i dalje mu nema spasa... Očigledno, takva igra ima smisla samo za one koji ne znaju rešenje. Zanimljivo je da je potpuno isti slučaj i sa takvima popularna igra kao šah! Ova igra ima smisla samo dok se ne pronađe rješenje. Teorijski je dokazano da rješenje postoji i da je ishod šahovske partije u suštini unaprijed određen zaključak: ako svaka strana koristi svoju vlastitu optimalnu strategiju, onda će partija ili uvijek završiti pobjedom bijelih, ili uvijek pobjedom za bijele. Crni, ili uvijek neriješeni! Ali šta tačno? To još ne znamo, jer je broj mogućih strategija prevelik da bi se konstruisala matrica šahovske partije i u njoj pronašla sedla... Vjerovatno ljubitelje šaha zanima činjenica da šahovska partija neće biti uskoro riješeno. U zaključku, napominjemo da ne može postojati jedna, već nekoliko sedla u matrici; onda postoji onoliko rješenja za igru ​​u čistim strategijama koliko ima sedla. Svaki od njih daje isplatu jednaku cijeni igre.

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

jedna - jedina strategija., onda, na osnovu razumno djelujućih protivnika, ovaj izbor treba odrediti po principu minimaksa. Pridržavajući se naše maksiminske strategije, svakako garantujemo sebi isplatu jednaku nižoj cijeni igre, a, za svako ponašanje protivnika. Postavlja se prirodno pitanje: da li je moguće da sebi garantujete prosečnu isplatu veću od a ako primenite ne samo jednu „čistu“ strategiju, već nasumično menjate nekoliko strategija?

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

Očigledno, svaka čista strategija je poseban slučaj mješovite, u kojoj se sve strategije osim jedne primjenjuju sa nultom frekvencijom, a ova sa frekvencijom od 1.

Ispada da je primjenom ne samo čistih već i mješovitih strategija moguće dobiti rješenje za svaku konačnu igru, odnosno par (generalno mješovitih) strategija tako da kada ih oba igrača koriste, isplata će biti jednaka cijena igre, a kod bilo kakvog jednostranog odstupanja od optimalne strategije, isplata se može promijeniti samo u smjeru nepovoljnom za devijanta.

Navedena tvrdnja je sadržaj takozvane glavne teoreme teorije igara. Ovu teoremu je prvi dokazao von Neumann 1928. Poznati dokazi teoreme su relativno složeni; stoga predstavljamo 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 glavne teoreme slijedi da svaka konačna igra ima cijenu. Očigledno, cijena igre v uvijek leži između niže cijene igre a i top cijena igre:

Zaista, postoji maksimalna zagarantovana isplata koju možemo sebi osigurati koristeći samo naše vlastite čiste strategije. Budući da mješovite strategije uključuju, kao poseban slučaj, sve čiste, onda, dopuštajući, pored čistih, i mješovite

strategije, mi, u svakom slučaju, ne pogoršavamo svoje mogućnosti; shodno tome,

Slično, s obzirom na mogućnosti protivnika, to pokazujemo

odakle slijedi tražena nejednakost (3.1).

Uvedemo posebnu notaciju za mješovite strategije. Ako se, na primjer, naša mješovita strategija sastoji od primjene AL strategija, sa frekvencijama i mi ćemo ovu strategiju označiti

Slično, mješovita strategija protivnika će biti označena sa:

gdje su frekvencije na kojima se strategije miješaju

Pretpostavimo da smo pronašli rješenje za igru ​​koja se sastoji od dvije optimalne mješovite strategije S, S. U opštem slučaju, nisu sve čiste strategije dostupne datom 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.

Ispostavilo se 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 je cijeni igre v, bez obzira na to što drugi igrač radi, ako on. samo ne ide dalje od svojih "korisnih" strategija. On, na primjer, može koristiti bilo koju od svojih "korisnih" strategija u čista forma, a također ih možete miješati u bilo kojoj proporciji.

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

"korisne" strategije se sastoje od mješavine tri "korisne" strategije

i Navodi se da ako se držimo strategije S, onda protivnik može primijeniti strategije u bilo kojem omjeru, a isplata će ostati nepromijenjena i i dalje će biti jednaka cijeni igre

Ako u igri svaki od protivnika koristi istu strategiju, tada se kaže da se ova igra odvija u čistim strategijama, a strategije igrača A i B će se zvati čiste strategije.U antagonističkoj igri naziva se par strategija ravnoteža(održivo) ako je za bilo koga od igrača neisplativo da se povuče od svojih strategija Ima smisla koristiti čiste strategije ako su igrači svjesni akcija protivnika. Ako to nije slučaj onda 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, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.

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

Specificiranje mješovite strategije znači specificiranje vjerovatnoća s kojima se čiste strategije koriste.

S A = || p 1 , p 2 .... pm || ,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 prate vjerovatnoće 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 će biti 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 je jednak očekivanoj isplati igrača A. Isplata prvog igrača i prosječan gubitak drugog igrača jednaki su jedno drugom.

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

Pretpostavimo da su svi elementi matrice isplate 0≤aij. Tada je α≤ν≤β. Prema osnovnoj teoremi 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)

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

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 \u003d P 2 / ν ... X m = 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)

Hajde da definišemo 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) (direktan problem)

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 = q 1 / ν, Y 2 = q 2 / ν ... Y m \u003d q m / ν

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

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

L(y)=∑yj -> max

∑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 = 2/9, x 2 = 2/9, x 3 = 1/9

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

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

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

dvostruki zadatak

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

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 = y 2 *ν = (2/9) * (9/5) \u003d 2/5

q 2 = (2/9) * (9/5) = 2/5

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

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

Problem mxn se svodi na problem linearnog programiranja.

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

Igrač A i igrač B naizmjenično primjenjuju čiste strategije. Svaki igrač pokušava povećati svoju isplatu koristeći maksimin ili minimax pristup. Nije prosječan dobitak taj koji se minimizira (maksimizira), već akumulirani. U teoriji se pokazuje da će nam takva metoda neizbježno dati optimalnu isplatu i optimalne mješovite strategije.