Čisté a zmiešané stratégie. Metóda výpočtu optimálnych stratégií

teória herná stratégia zmiešaná

Zmiešané stratégie

Ak maticová hra nemá sedlový bod v čistých stratégiách, potom sa zistí horná a dolná cena hry. Ukazujú, že hráč 1 nezíska výplatu vyššiu, ako je najvyššia cena hry, a že hráčovi 1 je zaručená výplata, ktorá nie je nižšia ako najnižšia cena hry.

Zmiešaná stratégia hráča je kompletný súbor jeho čistých stratégií, keď sa hra mnohokrát opakuje za rovnakých podmienok s danými pravdepodobnosťami. Zhrňme si, čo bolo povedané, a vymenujeme podmienky používania zmiešaných stratégií:

• * hra bez sedlového hrotu;
• * hráči používajú náhodnú zmes čistých stratégií s danými pravdepodobnosťami;
• * hra sa mnohokrát opakuje za podobných podmienok;
• * počas každého ťahu nie je žiaden hráč informovaný o voľbe stratégie druhým hráčom;
• * spriemerovanie výsledkov hry je povolené.

Pre zmiešané stratégie sa používajú nasledujúce označenia.

Pre hráča 1 zmiešaná stratégia spočíva v použití čistých stratégií A 1, A 2, ..., A t so zodpovedajúcimi pravdepodobnosťami p 1, p 2, ..., p t.

Pre hráča 2

qj je pravdepodobnosť použitia čistej stratégie Bj.

V prípade, že p i = 1, pre hráča 1 máme čistú stratégiu

Jediné možné nezlučiteľné udalosti sú hráčove čisté stratégie. V maticovej hre, keď poznáme maticu A (platí pre hráča 1 aj hráča 2), vieme určiť kedy dané vektory a priemerná odmena (matematické očakávanie účinku) hráča 1:

kde a sú vektory;

p i a q i sú zložky vektorov.

Použitím ich zmiešaných stratégií sa hráč 1 snaží maximalizovať svoj priemerný zisk a hráč 2 sa snaží tento efekt znížiť na minimálnu možnú hodnotu. Hráč 1 sa snaží dosiahnuť

Hráč 2 zabezpečuje splnenie podmienky

Označme aj vektory zodpovedajúce optimálnym zmiešaným stratégiám hráčov 1 a 2, t.j. také vektory a pre ktoré bude splnená rovnosť

Cena hry je priemerná odmena hráča 1, keď obaja hráči používajú zmiešané stratégie. Preto je riešením maticovej hry:

• - optimálna zmiešaná stratégia hráča 1;
• - optimálna zmiešaná stratégia pre hráča 2;

Cena hry.

Zmiešané stratégie budú optimálne (a), ak tvoria sedlový bod pre funkciu, t.j.

Existuje základná veta pre matematické hry.

Pre maticovú hru s akoukoľvek maticou A veľkosti

existujú a sú si navzájom rovné: = = .

Treba si uvedomiť, že pri výbere optimálne stratégie Hráč 1 bude mať vždy zaručenú priemernú výhru, ktorá nie je nižšia ako cena hry fixná stratégia hráč 2 (a naopak pre hráča 2). Aktívne stratégie hráčov 1 a 2 sú stratégie, ktoré sú súčasťou optimálnych zmiešaných stratégií zodpovedajúcich hráčov s pravdepodobnosťou inou ako nula. To znamená, že optimálne zmiešané stratégie hráčov nemusia zahŕňať všetky ich a priori dané stratégie.

Vyriešiť hru znamená nájsť cenu hry a optimálne stratégie. Začnime s úvahami o metódach na nájdenie optimálnych zmiešaných stratégií pre maticové hry najjednoduchšia hra, popísané maticou 22. Hry so sedlovou špičkou nebudú špecificky brané do úvahy. Ak sa dosiahne sedlový bod, znamená to, že existujú nerentabilné stratégie, ktoré by sa mali opustiť. Pri absencii sedlového bodu je možné získať dve optimálne zmiešané stratégie. Ako už bolo uvedené, tieto zmiešané stratégie sú napísané takto:

To znamená, že existuje platobná matica

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)

a11p1 + a21(1 - p1) = a12p1 + a22 (1 - p1); (1,19)

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

kde dostaneme optimálne hodnoty:

Poznáme a nájdeme:

Po výpočte zistíme:

a 11 q 1 + a 12 q 2 =; q1 + q2 = 1; (1,24)

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

o 11-12 hod. (1,26)

Problém je vyriešený, pretože vektory a cena hry boli nájdené. S platobnou maticou A môžete problém vyriešiť graficky. Pri tejto metóde je algoritmus riešenia veľmi jednoduchý (obr. 2.1).

• 1. Segment jednotkovej dĺžky je vynesený pozdĺž osi x.
• 2. Os y ukazuje výhru pre stratégiu A 1 .
• 3. Na priamke rovnobežnej s ordinátou v bode 1 sú vynesené výhry pre stratégiu a 2.
• 4. Konce segmentov sú označené pre a 11 -b 11, a 12 -b 21, a 22 -b 22, a 21 -b 12 a sú nakreslené dve priame čiary b 11 b 12 a b 21 b 22.
• 5. Súradnica priesečníka s je určená. Je rovnocenná. Os x bodu c sa rovná p 2 (p 1 = 1 - p 2).

Ryža. 1.1.

Táto metóda má pomerne širokú oblasť použitia. Toto je založené na všeobecný majetok games TP, ktorý spočíva v tom, že v každom hernom TP má každý hráč optimálnu zmiešanú stratégiu, v ktorej počet čistých stratégií nie je väčší ako min(m, n). Z tejto vlastnosti môžeme získať známy dôsledok: v každej hre 2n a m2 každá optimálna stratégia obsahuje najviac dve aktívne stratégie. To znamená, že ktorúkoľvek hru 2n a m2 je možné zredukovať na hru 22. Hry 2n a m2 je teda možné riešiť graficky. Ak má matica konečnej hry rozmer mn, kde m > 2 an > 2, potom sa na určenie optimálnych zmiešaných stratégií používa lineárne programovanie.

Vo všeobecnosti V * ≠ V * - neexistuje sedlový bod. V čistých stratégiách tiež neexistuje optimálne riešenie. Ak však rozšírime koncept čistej stratégie o koncept zmiešanej stratégie, potom je možné implementovať algoritmus na nájdenie optimálneho riešenia nie presne definovaného herného problému. V takejto situácii sa navrhuje použiť štatistický (pravdepodobnostný) prístup k nájdeniu optimálneho riešenia hry s nulovým súčtom. Pre každého hráča, spolu s daným súborom stratégií, ktoré sú pre neho možné, je zavedený neznámy vektor pravdepodobností (relatívne frekvencie), s ktorými by mala byť tá či oná stratégia použitá.

Označme vektor pravdepodobnosti (relatívnej frekvencie) výberu daných stratégií hráča A takto:
P = (p 1, p 2,…, p m),
kde p i ≥ 0, p 1 + p 2 +…+ p m = 1. Hodnota p i sa nazýva pravdepodobnosť (relatívna frekvencia) použitia stratégie A i.

Podobne pre hráča B je zavedený neznámy vektor pravdepodobností (relatívne frekvencie) a má tvar:
Q = (q 1, q 2,…, q n),
kde q j ≥ 0, q 1 + q 2 +…+ q n = 1. Hodnota q j sa nazýva pravdepodobnosť (relatívna frekvencia) použitia stratégie B j. Množina (kombinácia) čistých stratégií A 1, A 2, …A m a B 1, B 2, …B n v kombinácii s vektormi pravdepodobnosti výberu každej z nich sa nazýva zmiešané stratégie.

Hlavná veta v teórii hier s konečným nulovým súčtom je von Neumannova veta: každá hra s konečnou maticou má aspoň jedno optimálne riešenie, možno medzi zmiešanými stratégiami.
Z tejto vety vyplýva, že dobre nedefinovaná hra má aspoň jedno optimálne riešenie v zmiešaných stratégiách. V takýchto hrách bude riešením dvojica optimálnych zmiešaných stratégií P * a Q *, a to tak, že ak jeden z hráčov dodrží svoju optimálnu stratégiu, potom nie je výhodné, aby sa druhý hráč odchýlil od svojej optimálnej stratégie.
Priemerná odmena hráča A je určená matematickým očakávaním:

Ak je pravdepodobnosť (relatívna frekvencia) použitia stratégie iná ako nula, potom sa takáto stratégia nazýva aktívny.

Stratégie P*, Q* sa nazývajú optimálne zmiešané stratégie, ak MA (P, Q *) ≤ MA (P *, Q *) ≤ MA (P *, Q) (1)
V tomto prípade sa volá MA (P * , Q *). za cenu hry a označuje sa V (V * ≤ V ≤ V *). Prvá z nerovností (1) to znamená odchýlka hráča A od jeho optimálnej zmiešanej stratégie za predpokladu, že hráč B sa bude držať svojej optimálnej zmiešanej stratégie, vedie k zníženiu priemerných výhier hráč A. Druhá z nerovností znamená, že odchýlka hráča B od jeho optimálnej zmiešanej stratégie za predpokladu, že hráč A dodrží svoju optimálnu zmiešanú stratégiu, vedie k zvýšeniu priemernej straty hráča B.

Vo všeobecnosti možno takéto problémy úspešne vyriešiť pomocou tejto kalkulačky.

Príklad.

1. Skontrolujte, či má platobná matica sedlový bod. Ak áno, potom vypíšeme riešenie hry v čistých stratégiách.

Predpokladáme, že hráč I volí svoju stratégiu tak, aby maximalizoval svoju výplatu, a hráč II volí stratégiu tak, aby minimalizoval výplatu hráča I.

Nájdeme garantovaný výnos určený nižšou cenou hry a = max(a i) = 2, čo naznačuje maximálnu čistú stratégiu A 1 .
Horná cena hry je b = min(b j) = 7. Čo naznačuje absenciu sedlového bodu, keďže a ≠ b, potom je cena hry v rozmedzí 2 ≤ y ≤ 7. Nájdeme riešenie do hry v zmiešaných stratégiách. Vysvetľuje to skutočnosť, že hráči nemôžu oznámiť svoje čisté stratégie: Mali by skrývať svoje činy. Hru je možné vyriešiť tak, že hráčom umožníte vybrať si stratégie náhodne (zmiešaním čistých stratégií).

2. Skontrolujte, či v matici platieb nie sú dominantné riadky a dominantné stĺpce.
IN platobná matica neexistujú žiadne dominantné riadky a žiadne dominantné stĺpce.

3. Nájdite riešenie hry v zmiešaných stratégiách.
Napíšme si sústavu rovníc.
Pre hráča I
4p 1 +7p 2 +2p 3 = y
7p 1 +3p 2 +p 3 = y
2p 1 +2p 2 +8p 3 = y
p 1 + p 2 + p 3 = 1

Pre hráča II
4q 1 + 7 q 2 + 2 q 3 = y
7q 1 + 3 q 2 + 2 q 3 = y
2q 1 + q 2 + 8q 3 = y
q 1 + q 2 + q 3 = 1

Riešením týchto systémov pomocou Gaussovej metódy zistíme:

y = 4 1/34
p 1 = 29 / 68 (pravdepodobnosť použitia 1. stratégie).
p 2 = 4 / 17 (pravdepodobnosť použitia 2. stratégie).
p 3 = 23 / 68 (pravdepodobnosť použitia 3. stratégie).

Optimálna zmiešaná stratégia hráča I: P = (29 / 68; 4 / 17; 23 / 68)
q 1 = 6 / 17 (pravdepodobnosť použitia 1. stratégie).
q 2 = 9 / 34 (pravdepodobnosť použitia 2. stratégie).
q 3 = 13 / 34 (pravdepodobnosť použitia 3. stratégie).

Optimálna zmiešaná stratégia hráča II: Q = (6/17; 9/34; 13/34)
Cena hry: y = 4 1/34

Maticovú hru pre dvoch hráčov s nulovým súčtom si možno predstaviť ako nasledujúcu abstraktnú hru pre dvoch hráčov.

Prvý hráč má m stratégií i = 1,2,...,m, druhý má n stratégií j= 1,2,...,n. Každá dvojica stratégií ( i, j) zhodné číslo A ij , vyjadrenie zisku hráča 1 na úkor hráča 2, ak prvý hráč prijme jeho i- yu stratégiu a 2 – jeho vlastnú j stratégiu.

Každý hráč urobí jeden ťah: hráč 1 si vyberie ten svoj i stratégia ( i= ), 2 – váš j stratégia ( j=
), potom získa výhru hráč 1 A ij na úkor hráča 2 (ak A ij < 0, potom to znamená, že hráč 1 zaplatí druhú čiastku | A ij|). Tu sa hra končí.

Stratégia každého hráča i=
; j =
často nazývaná čistá stratégia.

Ak vezmeme do úvahy maticu

A=

potom vedenie každej hry maticovej hry s maticou A závisí od výberu hráča 1 i riadok a hráč 2 j stĺpec a hráč 1 (na úkor hráča 2) získa výhry a ij .

Hlavnou vecou pri štúdiu hier je koncept optimálnych stratégií hráčov. Tento koncept má intuitívne nasledujúci význam: stratégia hráča je optimálna, ak mu použitie tejto stratégie poskytuje najväčšiu zaručenú výhru pre všetky možné stratégie druhého hráča. Na základe týchto pozícií hráč 1 skúma výplatnú maticu A takto: pre každú hodnotu i (i =
) minimálna výherná hodnota je určená v závislosti od stratégií používaných hráčom 2

A ij (i=
)

tie. sú určené minimálne výhry pre hráča 1 za predpokladu, že prijme svoju ičistej stratégie, potom sa z týchto minimálnych výnosov takáto stratégia nájde i = i O, pri ktorej bude tento minimálny zisk maximálny, t.j. Nachádza

A ij =
=(1)

Definícia . číslo , definovaný vzorcom (1) sa nazýva nižšia čistá cena hry a ukazuje, aké minimálne výhry si môže hráč 1 zaručiť použitím svojich čistých stratégií na všetky možné akcie hráča 2.

Hráč 2 by sa mal svojím optimálnym správaním snažiť, pokiaľ je to možné, prostredníctvom svojich stratégií minimalizovať výplatu hráča 1. Preto pre hráča 2 nájdeme

A ij

tie. určí sa maximálna výhra hráča 1 za predpokladu, že hráč 2 použije svoje jčistá stratégia, potom hráč 2 hľadá svoju vlastnú j = j 1 stratégia, v ktorej hráč 1 získa min výhru, t.j. nájde

a ij =
=(2).

Definícia . číslo , určený vzorcom (2), sa nazýva čistá horná cena hry a ukazuje, aké maximálne výhry si hráč 1 môže zaručiť vďaka svojim stratégiám.

Inými slovami, pomocou svojich čistých stratégií môže hráč 1 zabezpečiť výhru nie menej ako a hráč 2 môže pomocou svojich čistých stratégií zabrániť hráčovi 1 vyhrať viac ako .

Definícia . Ak v hre s maticou A =potom hovoria, že táto hra má sedlo bod v čistých stratégiách a internetová cena hry

 = =.

Sedlový bod je dvojica čistých stratégií (i O , j O ) hráči 1 a 2, pri ktorých sa dosiahne rovnosť =. Tento pojem má nasledovný význam: ak jeden z hráčov dodržiava stratégiu zodpovedajúcu sedlovému bodu, potom druhý hráč nemôže urobiť lepšie, ako dodržiavať stratégiu zodpovedajúcu sedlovému bodu. Matematicky sa to dá napísať aj inak:

Kde i, j– akékoľvek čisté stratégie hráčov 1 a 2; (i O , j O ) – stratégie, ktoré tvoria sedlový bod.

Teda na základe (3) sedlového prvku
je minimálna v i o -tom riadku a maximum v j o -tom stĺpci matice A. Hľadanie sedlového bodu matice A prebieha nasledovne: v matici A postupne v každom riadok nájdite minimálny prvok a skontrolujte, či je tento prvok maximálny stĺpec. Ak áno, potom ide o sedlový prvok a jemu zodpovedajúca dvojica stratégií tvorí sedlový bod. Pár čistých stratégií (i O , j O ) hráčov 1 a 2, tvoriacich sedlový hrot a sedlový prvok
, volal riešenie hry . V čom i O A j O sa volajú optimálne čistenie stratégií hráči 1 a 2.

Príklad 1

Sedlový bod je pár ( i O = 3;j O= 1), pri ktorom = == 2.

Všimnite si, že hoci odmena v situácii (3;3) sa tiež rovná 2 = =, nejde o sedlový bod, pretože táto výhra nie je maximálna medzi výhrami v treťom stĺpci.

Príklad 2

Z analýzy výplatnej matice je zrejmé, že
, t.j. táto matrica nemá sedlový hrot. Ak si hráč 1 zvolí svoju stratégiu čistého maxima i = 2, potom hráč 2, ktorý si zvolí svoj minimax j= 2, prehrá len 20. V tomto prípade je pre hráča 1 výhodné zvoliť stratégiu i = 1, t.j. odchýliť sa od svojej čistej maximalinovej stratégie a vyhrať 30. Potom bude pre hráča 2 výhodné zvoliť stratégiu j = 1, t.j. odchýliť sa od svojej čistej minimax stratégie a stratiť 10. Na druhej strane si hráč 1 musí zvoliť svoju 2. stratégiu, aby vyhral 40, a hráč 2 zareaguje výberom 2. stratégie atď.

Pozrime sa na príklad. Nech je daná herná matica (4):

Musíme nájsť spodnú cenu hry α, hornú cenu hry β a stratégie minimax a skontrolovať, či sú stabilné. Riešenie. Z analýzy dodatočného stĺpca a riadku dostaneme: α = 5, β = 5. Maximin sa rovná minimaxu! Toto je špeciálny prípad. Čo z toho vyplýva? Zoberme si pár minimax stratégií: K 2 a C 3. Ak sa obaja budú držať týchto stratégií, potom bude odmena 5. Teraz povedzme, že sme sa dozvedeli o správaní nepriateľa. Čo urobíme? Nič! Naďalej sa budeme držať stratégie K2, pretože akékoľvek odklonenie od nej je pre nás nerentabilné. Či už vieme alebo nevieme o správaní nepriateľa, stále sa budeme držať stratégie K 2! To isté platí pre „modrých“ – nemá zmysel meniť svoju stratégiu C3. IN v tomto príklade dvojica stratégií K 2 a C 3 je stabilná, t. j. predstavuje rovnovážnu polohu a poskytuje riešenie hry. Prečo sa to stalo? Pretože v matici je špeciálny prvok 5; je minimálny vo svojom riadku a zároveň maximálny vo svojom stĺpci. Takýto prvok je tzv sedlový bod. Ak má matica sedlový bod (to znamená, že spodná cena hry sa rovná hornej), hra má riešenie v čistých stratégiách: ide o dvojicu stratégií, ktoré sa pretínajú v sedlovom bode. Samotný sedlový bod udáva cenu hry – v našom príklade sa rovná 5. Trieda hier, ktoré majú sedlový bod, má v teórii hier veľký význam. Predovšetkým je dokázané, že ak podľa pravidiel hry každý hráč pozná výsledok všetkých doterajších ťahov, svojich aj súperových (tzv. hra s kompletnými informáciami), potom hra má sedlovú pointu, a preto má riešenie v čistých stratégiách. Príklady hier s úplnými informáciami zahŕňajú: šach, dámu, piškvorky atď. Uveďme príklad hry s úplnými informáciami, ktorej riešenie sa dá ľahko nájsť. Dvaja hráči - K a C - striedavo kladú na okrúhly stôl rovnaké mince. Pozícia každej mince je zvolená ľubovoľne, pokiaľ sa neprekrýva s ostatnými. Hráč, ktorý umiestni mincu ako posledný, vyhráva (keď už nezostane miesto pre ostatných). Stojí za to sa trochu zamyslieť, aby ste sa uistili, že výsledok tejto hry je vždy vopred stanovený záver a že existuje dobre definovaná stratégia, ktorá zaručí výhru hráčovi, ktorý vhodí mincu ako prvý (nech je to K). Totiž, K musí umiestniť prvú mincu do stredu stola a potom na každý ťah C musí reagovať ťahom presne symetrickým vzhľadom na stred stola! Chudák S sa môže správať ako chce, no aj tak pre neho niet úniku... Evidentne má takáto hra zmysel len pre toho, kto nepozná riešenie. Je zvláštne, že situácia je úplne rovnaká ako u takýchto populárna hra ako šach! Táto hra má zmysel len dovtedy, kým sa nenájde riešenie. Teoreticky sa dokázalo, že riešenie existuje a výsledok šachovej partie je v podstate vopred daný: ak každá strana použije svoju optimálnu stratégiu, potom sa hra buď vždy skončí výhrou bieleho, alebo vždy výhrou čierneho, alebo vždy v remíze! Ale čo presne? To ešte nevieme, keďže počet možných stratégií je príliš veľký na to, aby sme dokázali zostrojiť maticu šachovej partie a nájsť v nej sedlový bod... Pravdepodobne šachových fanúšikov zaujíma, že šach hra sa tak skoro nevyrieši. Na záver si všimnime, že v matici môže byť nie jeden, ale niekoľko sedlových bodov; potom je toľko riešení hry v čistých stratégiách, koľko je sedlových bodov. Každý z nich dáva výhru rovnajúcu sa cene hry.

Medzi konečnými hrami praktického významu sú hry so sedlovým hrotom pomerne zriedkavé; Typickejší prípad je, keď je rozdielna spodná a horná cena hry. Pri analýze matíc takýchto hier sme dospeli k záveru, že ak má každý hráč na výber

one - only strategy., potom, počítajúc s racionálne konajúcim nepriateľom, by táto voľba mala byť určená princípom minimax. Dodržiavaním našej stratégie maximin, bez ohľadu na správanie nepriateľa, si samozrejme zaručujeme výhru rovnajúcu sa nižšej cene hry a. Vynára sa prirodzená otázka: je možné zaručiť vyšší priemerný výnos ako ak nepoužívate len jednu „čistú“ stratégiu, ale náhodne striedate niekoľko stratégií?

Takéto kombinované stratégie pozostávajúce z použitia niekoľkých čistých stratégií, ktoré sa striedajú podľa náhodného zákona s určitým pomerom frekvencií, sa v teórii hier nazývajú zmiešané stratégie.

Je zrejmé, že každá čistá stratégia je špeciálnym prípadom zmiešanej stratégie, v ktorej sú všetky stratégie okrem jednej aplikované s nulovými frekvenciami a táto s frekvenciou 1.

Ukazuje sa, že použitím nielen čistých, ale aj zmiešaných stratégií je možné pre každú konečnú hru získať riešenie, t. j. dvojicu takých (vo všeobecnosti zmiešaných) stratégií tak, že keď ich použijú obaja hráči, výplata sa bude rovnať cene hry, a keď Akákoľvek jednostranná odchýlka od optimálnej stratégie môže zmeniť výplatu iba v smere nepriaznivom pre devianta.

Uvedené tvrdenie tvorí obsah takzvanej základnej vety teórie hier. Túto vetu prvýkrát dokázal von Neumann v roku 1928. Známe dôkazy tejto vety sú pomerne zložité; Preto uvedieme len jeho formuláciu.

Každá konečná hra má aspoň jedno riešenie (možno v oblasti zmiešaných stratégií).

Výplata vyplývajúca z rozhodnutia sa nazýva cena hry. Z hlavnej vety vyplýva, že každá konečná hra má svoju cenu. Je zrejmé, že cena hry v leží vždy medzi nižšou cenou hry a a top cena hry:

V skutočnosti existuje maximálna zaručená výhra, ktorú si môžeme zabezpečiť použitím iba našich čistých stratégií. Keďže zmiešané stratégie zahŕňajú, ako špeciálny prípad, všetky čisté, potom umožňujúce okrem čistých aj zmiešané stratégie

stratégie, v žiadnom prípade nezhoršujeme naše schopnosti; teda,

Podobne to ukážeme vzhľadom na schopnosti nepriateľa

odkiaľ nasleduje požadovaná nerovnosť (3.1).

Uveďme špeciálny zápis pre zmiešané stratégie. Ak napríklad naša zmiešaná stratégia pozostáva z používania stratégií AL, s frekvenciami a túto stratégiu označíme

Podobne označíme zmiešanú stratégiu nepriateľa:

kde sú frekvencie, pri ktorých sa stratégie miešajú

Predpokladajme, že sme našli riešenie hry pozostávajúce z dvoch optimálnych zmiešaných stratégií S, S. Vo všeobecnosti nie sú v jeho optimálnej zmiešanej stratégii zahrnuté všetky čisté stratégie dostupné danému hráčovi, ale iba niektoré. Stratégie zahrnuté v optimálnej zmiešanej stratégii hráča budeme nazývať „užitočné“ stratégie.

Ukazuje sa, že riešenie hry má ešte jednu pozoruhodnú vlastnosť: ak jeden z hráčov dodržiava svoju optimálnu zmiešanú stratégiu 5 (5). potom výhra zostáva nezmenená a rovná sa cene hry v, bez ohľadu na to, čo urobí druhý hráč, ak on. jednoducho nepresahuje svoje „užitočné“ stratégie. Môže napríklad použiť ktorúkoľvek zo svojich „užitočných“ stratégií čistej forme, a tiež ich môžete zmiešať v ľubovoľnom pomere.

Dokážme toto tvrdenie. Nech existuje riešenie hry. Aby sme boli konkrétni, budeme predpokladať, že optimálna zmiešaná stratégia pozostáva zo zmesi troch

„užitočné“ stratégie teda pozostávajú zo zmesi troch „užitočných“ stratégií

Okrem toho sa uvádza, že ak sa budeme držať stratégie S, súper môže použiť stratégie v akomkoľvek pomere a výplata zostane nezmenená a bude sa stále rovnať nákladom na hru.

Ak v hre každý zo súperov používa rovnakú stratégiu, potom sa hovorí, že táto hra sa hrá v čistých stratégiách a stratégie hráčov A a B sa budú nazývať čisté stratégie.V hre s nulovým súčtom sa nazýva dvojica stratégií rovnováha(stabilná), ak je pre niektorého z hráčov nerentabilné ustúpiť od svojich stratégií. Má zmysel používať čisté stratégie, ak si hráči uvedomujú akcie súpera. Ak to tak nie je, potom je myšlienka rovnováhy narušená a hra sa môže hrať tak, ako to dopadne. Stratégie A1 B1 sú stabilné s ohľadom na informácie o správaní súpera. Znak stability dvojice stratégií je rovnosť hornej a dolnej ceny hry. A prípad A1 B1 bude

ν = α = β. ν > 0, potom hráč A vyhrá, ak ν< 0, то в выигрыше игрок В. Если ν = 0, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.

Veta: každá hra s kompletnými informáciami má sedlovú pointu a preto rieši v čistých stratégiách, t.j. existuje pár stabilných stratégií, ktoré poskytujú stabilnú výplatu rovnajúcu sa ν. Ak matica nemá sedlový bod, cena hry je α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии.Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.

Špecifikovať zmiešanú stratégiu znamená špecifikovať pravdepodobnosti, s ktorými sa čisté stratégie používajú.

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

Hru je možné niekoľkokrát opakovať, ale v každej hre sa hráč riadi zmiešanou stratégiou, kde čisté stratégie dodržiavajú pravdepodobnosti p i a q j .

Model zmiešanej stratégie sa líši od modelu čistej stratégie. V prípade zmiešaných stratégií bude taktika hráčov flexibilnejšia, pretože hráči vopred vedia, akú čistú stratégiu použijú.

Predpokladajme, že hráč A aj hráč B majú zmiešanú stratégiu. Je potrebné určiť A: ∑∑ a ij p i q j

Pre hráča B sa očakávaná prehra rovná očakávanému zisku hráča A. Výhry prvého hráča a priemerná prehra druhého hráča sa navzájom rovnajú.

18.Metódy riešenia konečnej dvojhry rádu m*n.

Predpokladajme, že všetky prvky platobnej matice sú 0≤aij. Potom α≤ν≤β. Podľa základnej vety maticových hier má každá maticová hra 2 optimálne zmiešané stratégie.

SA = (p 1 , p 2 , … , p n)

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

Hru riešime za hráča A, pričom predpokladáme, že hráč B používa iba čisté stratégie. Potom

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

X1 = P1/ν, X2 = P2/ν … Xm = Pm/ν

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

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

p1+p2 +...+pm=1

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

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

Definujme problém lineárneho programovania.

ν = 1/(X10 +X20 …Xm0) (5)

P1 = X 1 0 *ν opt

p2 = X 2 0 *ν opt (6)

min L(x) = ∑x i

∑a ij: 1≤x i (7) (priamy problém)

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 = q m /ν

q1 + q2 +...+q n = 1

y1 + y2 +...+y n = 1/ν

L(y)=∑y j -> max

∑a ij , y i ≤1 (i=1,2…) (9) (dvojitý problém)

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) a = 1, p = 3

2) Neexistujú žiadne zjednodušenia.

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

x 1 + 3 x 2 + x 3 >= 1

2x 1 +x 2 +x 3 >=1

3x 1 +x 2 +x 3 >=1

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

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

p1 = x 1 * v = 2/5

SA = (2/5, 2/5, 1/5)

duálny problém

L(y) = y1 +y2 +y3 => max

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

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

y1+3y2+y3<1y3=1/9

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

q1=y2*ν=(2/9)*(9/5)=2/5

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

q3 = (1/9)* (9/5) = 1/5

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

Problém mxn sa redukuje na problém lineárneho programovania.

Približná metóda na riešenie maticových hier mxn (Brown-Robinson).

Hráč A a hráč B sa striedajú pomocou čistých stratégií. Každý hráč sa snaží zvýšiť svoje výhry pomocou maximálneho alebo minimaxového prístupu. Nie je minimalizovaný (maximalizovaný) priemerný zisk, ale akumulovaný. Teória ukazuje, že takáto metóda nám nevyhnutne poskytne optimálne výhry a optimálne zmiešané stratégie.