Čisté a smíšené strategie. Metoda výpočtu optimálních strategií

teorie herní strategie smíšená

Smíšené strategie

Pokud v maticové hře není žádný sedlový bod v čistých strategiích, pak se zjistí horní a dolní cena hry. Ukazují, že hráč 1 nezíská výplatu vyšší, než je horní cena hry, a že hráči 1 je zaručena výplata ne menší než nižší cena hry.

Hráčova smíšená strategie je kompletní sadou jeho čistých strategií, kdy se hra mnohokrát opakuje za stejných podmínek s danou pravděpodobností. Shrňme, co bylo řečeno, a uveďme podmínky pro aplikaci smíšených strategií:

• * hra bez sedlového hrotu;
• * hráči používají náhodnou směs čistých strategií s danými pravděpodobnostmi;
• * hra se mnohokrát opakuje v podobných podmínkách;
• * při každém z tahů není žádný hráč informován o volbě strategie druhým hráčem;
• * je povoleno průměrování výsledků hry.

Pro smíšené strategie se používá následující označení.

Pro hráče 1 smíšená strategie, která spočívá v aplikaci čistých strategií A 1 , A 2 , ..., A t s odpovídajícími pravděpodobnostmi p 1 , p 2, ..., p t.

Pro hráče 2

qj je pravděpodobnost použití čisté strategie Bj.

V případě, že p i = 1, pro hráče 1 máme čistou strategii

Jediné možné neslučitelné události jsou hráčovy čisté strategie. V maticové hře, když známe matici A (platí pro hráče 1 i hráče 2), můžeme určit kdy dané vektory a průměrná výplata (matematické očekávání efektu) hráče 1:

kde a jsou vektory;

p i a q i jsou vektorové složky.

Použitím svých smíšených strategií se hráč 1 snaží maximalizovat svůj průměrný zisk a hráč 2 se snaží tento efekt přivést na minimální možnou hodnotu. Hráč 1 se snaží dosáhnout

Hráč 2 se pokusí splnit podmínku

Označme také vektory odpovídající optimálním smíšeným strategiím hráčů 1 a 2, tj. takové vektory a pro které je rovnost

Cena hry je průměrná výplata hráče 1, když oba hráči používají smíšené strategie. Proto řešení maticové hry je:

• - optimální smíšená strategie hráče 1;
• - optimální smíšená strategie hráče 2;

Cena hry.

Smíšené strategie budou optimální (u), pokud tvoří sedlový bod pro funkci tzn.

Existuje základní teorém matematických her.

U maticové hry s libovolnou maticí A hodnoty

existují a jsou si navzájem rovny: = = .

Nutno podotknout, že při výběru optimální strategie hráč 1 bude mít vždy zaručenou průměrnou výplatu, která nebude nižší než cena hry, pro kteroukoli pevná strategie hráč 2 (a naopak pro hráče 2). Aktivní strategie hráčů 1 a 2 jsou strategie, které jsou součástí optimálních smíšených strategií odpovídajících hráčů s jinou než nulovou pravděpodobností. To znamená, že složení optimálních smíšených strategií hráčů nemusí zahrnovat všechny jejich a priori dané strategie.

Vyřešit hru znamená najít cenu hry a optimální strategie. Začneme tím, že zvážíme metody pro nalezení optimálních smíšených strategií pro maticové hry nejjednodušší hra, popsané maticí 22. Hry se sedlovou špičkou nebudou speciálně brány v úvahu. Pokud se získá sedlový bod, znamená to, že existují nerentabilní strategie, které by měly být opuštěny. Při absenci sedlového bodu lze získat dvě optimální smíšené strategie. Jak již bylo uvedeno, tyto smíšené strategie jsou napsány následovně:

Existuje tedy výplatní matice

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)

kde získáme optimální hodnoty:

Víme a zjistíme:

Při výpočtech zjistíme:

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)

Problém je vyřešen, protože jsou nalezeny vektory a cena hry. Máme-li platební matici A, můžeme problém vyřešit graficky. U této metody je algoritmus řešení velmi jednoduchý (obr. 2.1).

• 1. Segment jednotky délky je vynesen na úsečce.
• 2. Na ose y jsou vyneseny zisky se strategií A 1 .
• 3. Na přímce rovnoběžné s osou y jsou v bodě 1 vyneseny výplaty pro strategii a 2 .
• 4. Konce segmentů jsou označeny pro a 11 -b 11, a 12 -b 21, a 22 -b 22, a 21 -b 12 a jsou nakresleny dvě přímé čáry b 11 b 12 a b 21 b 22.
• 5. Je určena souřadnice průsečíku s. Je rovnocenná. Abscisa bodu c se rovná p 2 (p 1 \u003d 1 - p 2).

Rýže. 1.1.

Tato metoda má poměrně širokou oblast použití. Toto je založeno na společný majetek games tn, který spočívá v tom, že v jakékoli hře tn má každý hráč optimální smíšenou strategii, ve které je počet čistých strategií maximálně min(m, n). Z této vlastnosti lze získat známý důsledek: v každé hře 2n a m2 každá optimální strategie u obsahuje nejvýše dvě aktivní strategie. Proto lze libovolnou hru 2n a m2 redukovat na hru 22. Proto lze hry 2n a m2 řešit graficky. Pokud má matice konečné hry dimenzi mn, kde m > 2 an > 2, pak se k určení optimální smíšené strategie použije lineární programování.

Obecně platí, že V * ≠ V * - neexistuje žádný sedlový bod. V čistých strategiích také neexistuje optimální řešení. Pokud však koncept čisté strategie rozšíříme o koncept smíšené strategie, můžeme implementovat algoritmus pro nalezení optimálního řešení ne zcela definovaného herního problému. V takové situaci se navrhuje použít statistický (pravděpodobnostní) přístup k nalezení optimálního řešení antagonistické hry. Pro každého hráče je spolu s danou sadou pro něj možných strategií zaveden neznámý vektor pravděpodobností (relativní frekvence), se kterými by měla být ta či ona strategie aplikována.

Označme vektor pravděpodobností (relativních četností) výběru daných strategií hráče A takto:
P = (p 1 , p 2 ,…, p m),
kde p i ≥ 0, p 1 + p 2 +…+ p m = 1. Hodnota p i se nazývá pravděpodobnost (relativní frekvence) aplikace strategie A i .

Podobně pro hráče B je zaveden neznámý vektor pravděpodobností (relativní frekvence), který má tvar:
Q = (q 1, q 2,…, q n),
kde q j ≥ 0, q 1 + q 2 +…+ q n = 1. Veličina q j se nazývá pravděpodobnost (relativní frekvence) aplikace strategie B j . Množina (kombinace) čistých strategií A 1 , A 2 , …A m a B 1, B 2, …B n v kombinaci s pravděpodobnostními vektory výběru každé z nich se nazývá smíšené strategie.

Hlavní věta v teorii konečných antagonistických her je Von Neumannova věta: každá hra s konečnou maticí má alespoň jedno optimální řešení, případně mezi smíšenými strategiemi.
Z této věty vyplývá, že ne přesně definovaná hra má ve smíšených strategiích alespoň jedno optimální řešení. V takových hrách bude řešením dvojice optimálních smíšených strategií P * a Q * , a to tak, že pokud jeden z hráčů dodržuje svou optimální strategii, pak se pro druhého hráče nevyplácí odchýlit se od své optimální strategie.
Průměrná výplata hráče A je určena matematickým očekáváním:

Pokud je pravděpodobnost (relativní četnost) aplikace strategie jiná než nula, pak se taková strategie nazývá aktivní.

Nazývají se strategie P * , Q * optimálně smíšené strategie, pokud M A (P, Q *) ≤ M A (P * , Q *) ≤ M A (P * , Q) (1)
V tomto případě se volá MA (P * , Q *). za cenu hry a značí se V (V * ≤ V ≤ V *). První z nerovností (1) to znamená odchylka hráče A od jeho optimální smíšené strategie za předpokladu, že hráč B se bude držet své optimální smíšené strategie, vede ke snížení průměrného zisku hráč A. Druhá z nerovností znamená, že odchylka hráče B od jeho optimální smíšené strategie za předpokladu, že hráč A dodrží svou optimální smíšenou strategii, vede ke zvýšení průměrné ztráty hráče B.

V obecném případě jsou takové problémy úspěšně vyřešeny touto kalkulačkou.

Příklad.

1. Zkontrolujte, zda má výplatní matice sedlový bod. Pokud ano, vypíšeme řešení hry v čistých strategiích.

Předpokládáme, že hráč I volí svou strategii tak, aby maximalizoval svou výplatu, a hráč II volí strategii tak, aby minimalizoval výplatu hráče I.

Garantovanou výplatu najdeme určenou nižší cenou hry a = max(a i) = 2, což udává maximální čistou strategii A 1 .
Horní cena hry b = min(b j) = 7. To ukazuje na absenci sedlového bodu, protože a ≠ b, pak je cena hry v rozmezí 2 ≤ y ≤ 7. Najdeme řešení hry ve smíšených strategiích. To se vysvětluje tím, že hráči nemohou deklarovat své soupeře čisté strategie: Měli by skrývat své činy. Hru lze vyřešit tak, že necháte hráče volit své strategie náhodně (mix čisté strategie).

2. Zkontrolujte výplatní matici pro dominantní řádky a dominantní sloupce.
V platební matice neexistují žádné dominantní řady a žádné dominantní sloupce.

3. Hledání řešení hry ve smíšených strategiích.
Zapišme si soustavu rovnic.
Pro hráče I
4p1 +7p2 +2p3 = y
7p1 +3p2 +p3 = y
2p 1 +2p 2 +8p 3 = y
p1 + p2 + p3 = 1

Pro hráče II
4q1 + 7q2 + 2q3 = y
7q1 + 3q2 + 2q3 = y
2q1 + q2 + 8q3 = y
q 1 + q 2 + q 3 = 1

Řešením těchto systémů Gaussovou metodou zjistíme:

y=4 1/34
p 1 = 29/68 (pravděpodobnost uplatnění 1. strategie).
p 2 = 4/17 (pravděpodobnost uplatnění 2. strategie).
p 3 = 23/68 (pravděpodobnost uplatnění 3. strategie).

Optimální smíšená strategie hráče I: P = (29/68; 4/17; 23/68)
q 1 = 6 / 17 (pravděpodobnost uplatnění 1. strategie).
q 2 = 9/34 (pravděpodobnost uplatnění 2. strategie).
q 3 = 13/34 (pravděpodobnost uplatnění 3. strategie).

Optimální smíšená strategie hráče II: Q = (6/17; 9/34; 13/34)
Cena hry: y = 4 1 / 34

Maticovou hru pro dva hráče s nulovým součtem lze považovat za následující abstraktní hru pro dva hráče.

První hráč má m strategie i = 1,2,...,m, druhý má n strategie j= 1,2,...,n. Každá dvojice strategií ( i, j) je přiřazeno číslo A ij , vyjadřující výplatu hráče 1 na úkor hráče 2, pokud první hráč přijme jeho i- strategie a 2 - vaše j-tá strategie.

Každý hráč provede jeden tah: hráč 1 si vybere svůj i- strategie ( i= ), 2 – vlastní j- strategie ( j=
), po kterém vyhrává hráč 1 A ij na úkor hráče 2 (pokud A ij < 0, to znamená, že hráč 1 platí druhému hráči | A ij|). Tady hra končí.

Strategie každého hráče i=
; j =
často nazývána čistou strategií.

Pokud vezmeme v úvahu matici

ALE=

pak provedení každé hry maticové hry s maticí ALE záleží na volbě hráče 1 i-tý řádek a hráč 2 j-tý sloupec a hráč 1 (na úkor hráče 2) obdrží výplatu a ij .

Hlavní věcí při studiu her je koncept optimálních strategií pro hráče. Tento koncept má intuitivně následující význam: strategie hráče je optimální, pokud mu aplikace této strategie poskytuje největší zaručený výnos ze všech možných strategií druhého hráče. Na základě těchto pozic hráč 1 prozkoumá výplatní matici ALE takto: pro každou hodnotu i (i =
) minimální hodnota výhry je určena v závislosti na použitých strategiích hráče 2

A ij (i=
)

těch. minimální výhra pro hráče 1 je určena za předpokladu, že přijme svou i-th čisté strategie, pak taková strategie je nalezena z těchto minimálních výnosů i = i o, při které bude tato minimální výplata maximální, tzn. nachází se

A ij =
=(1)

Definice . Číslo definovaný vzorcem (1) se nazývá nižší čistá cena hry a ukazuje, jakou minimální výplatu si může hráč 1 zaručit tím, že použije své čisté strategie pro všechny možné akce hráče 2.

Hráč 2 by se svým optimálním chováním měl snažit co nejvíce minimalizovat výplatu hráče 1 na úkor jeho strategií. Proto pro hráče 2

A ij

těch. maximální výhra hráče 1 je určena za předpokladu, že hráč 2 uplatní svou j-th čistá strategie, pak hráč 2 najde takový j = j 1 strategie, ve které hráč 1 dostane min výplatu, tzn. najde

A ij =
=(2).

Definice . Číslo , určený vzorcem (2), se nazývá čistá nejvyšší cena hry a ukazuje, jakou maximální výplatu si hráč 1 může zaručit díky svým strategiím.

Jinými slovy, použitím svých čistých strategií si hráč 1 může zajistit výplatu ne menší než a hráč 2 může použitím svých čistých strategií zabránit hráči 1 ve výhře více než .

Definice . Pokud ve hře s maticí A =, pak tato hra prý má sedlo směřovat v čistých strategiích a čistá cena hry

 = =.

sedlový bod je dvojice čistých strategií (i o , j o ) hráči 1 a 2, pod kterými je dosaženo rovnosti =. Tento koncept má následující význam: pokud jeden z hráčů dodržuje strategii odpovídající sedlovému bodu, pak druhý hráč nemůže udělat lépe, než dodržovat strategii odpovídající sedlovému bodu. Matematicky to lze napsat i jinak:

kde i, j jsou jakékoli čisté strategie hráčů 1 a 2; (i o , j o ) jsou strategie, které tvoří sedlový bod.

Tedy na základě (3) sedlového prvku
je minimum v i o -tém řádku a maximum v j o -tém sloupci matice A. Nalezení sedlového bodu matice A je následující: v matici A postupně v každé čára najděte minimální prvek a zkontrolujte, zda je tento prvek ve svém maximu sloupec. Pokud ano, pak se jedná o sedlový prvek a dvojice strategií, které mu odpovídají, tvoří sedlový bod. Pár čistých strategií (i o , j o ) hráči 1 a 2, tvořící sedlový hrot a sedlový prvek
, je nazýván herní rozhodnutí . V čem i o a j o volala optimální čištění strategie hráči 1 a 2.

Příklad 1

Sedlový bod je pár ( i o = 3;j o= 1), při kterém = == 2.

Všimněte si, že i když je výplata v situaci (3;3) také rovna 2 = =, to není sedlový bod, protože tato výplata není maximální mezi výplatami třetího sloupce.

Příklad 2

Z analýzy výplatní matice je to vidět
, tj. tato matrice nemá sedlový bod. Pokud hráč 1 zvolí svou strategii čistého maxima i = 2, poté hráč 2, který si zvolil svůj minimax j= 2, prohraje pouze 20. V tomto případě je pro hráče 1 výhodné zvolit strategii i = 1, tj. odchýlit se od své čisté strategie maximin a vyhrát 30. Pak bude pro hráče 2 výhodné zvolit strategii j = 1, tzn. odchýlit se od své čisté minimax strategie a ztratit 10. Hráč 1 si zase musí vybrat svou 2. strategii, aby vyhrál 40, a hráč 2 odpoví výběrem své 2. strategie a tak dále.

Zvažte příklad. Nechť je dána herní matice (4):

Je nutné najít spodní cenu hry α, horní cenu hry β a strategie minimax a zkontrolovat, zda jsou stabilní. Řešení. Z analýzy dalších sloupců a řádků dostaneme: α = 5, β = 5. Maximin je roven minimax! Případ je zvláštní. Co z toho vyplývá? Vezměme si pár minimax strategií: K 2 a C 3 . Pokud se oba budou držet těchto strategií, pak bude výplata 5. Nyní řekněme, že jsme se dozvěděli o chování soupeře. Co děláme? A nic! Nadále se budeme držet strategie K 2, protože jakákoliv odchylka od ní je pro nás nerentabilní. Ať už o chování nepřítele víme nebo nevíme, stále se budeme držet strategie K 2! Totéž platí pro „modré“ – pro ně nemá smysl měnit strategii C 3 . V tento příklad dvojice strategií K 2 a C 3 je stabilní, to znamená, že představuje rovnovážnou polohu a dává řešení hry. Proč se to stalo? Protože v matici je speciální prvek 5; je to minimum v jeho řádku a zároveň maximum v jeho sloupci. Takový prvek se nazývá sedlový bod. Pokud má matice sedlový bod (tedy nižší cena hry je rovna horní), pak má hra řešení v čistých strategiích: je to dvojice strategií, které se v sedlovém bodě protínají. Samotný sedlový bod udává cenu hry – v našem příkladu se rovná 5. Třída her, které mají sedlový bod, má v teorii her velký význam. Zejména bylo prokázáno, že pokud podle pravidel hry zná každý z hráčů výsledek všech dosavadních tahů, jak svých, tak i soupeřových (tzv. hra s kompletní informací), pak hra má sedlovou pointu, a proto má řešení v čistých strategiích. Příklady her s úplnými informacemi jsou: šachy, dáma, piškvorky atd. Uveďme příklad hry s úplnými informacemi, jejíž řešení lze snadno najít. Dva hráči - K a C - střídavě dávají stejné mince na kulatý stůl. Pozice každé mince je zvolena libovolně, pokud se nepřekrývá s ostatními. Vyhrává hráč, který vloží minci jako poslední (když už není místo pro ostatní). Chce to trochu přemýšlet, abyste se ujistili, že výsledek této hry je vždy předem daný závěr a že existuje dobře definovaná strategie, která zaručí výhru hráči, který vloží minci jako první (ať je to K). Totiž K musí položit první minci do středu stolu a potom na každý tah C musí reagovat tahem přesně symetrickým vzhledem ke středu stolu! Chudák C se může chovat jak chce, stejně nemá spásu... Evidentně má taková hra smysl jen pro toho, kdo nezná řešení. Je zvláštní, že přesně totéž platí i pro takové populární hra jako šachy! Tato hra má smysl pouze do té doby, než se najde řešení. Bylo teoreticky dokázáno, že řešení existuje a výsledek šachové partie je v podstatě předem daný: pokud každá strana použije svou vlastní optimální strategii, pak hra buď vždy skončí výhrou pro bílého, nebo vždy výhrou pro Černá, nebo vždy remíza! Ale co přesně? To ještě nevíme, protože počet možných strategií je příliš velký na to, aby sestrojil matici šachové partie a našel v ní sedlový bod... Pravděpodobně milovníky šachů zajímá, že šachová partie nebude vyřešeno brzy. Na závěr poznamenáváme, že v matici může být ne jeden, ale několik sedlových bodů; pak je v čistých strategiích tolik řešení hry, kolik je sedlových bodů. Každý z nich dává výplatu rovnající se ceně hry.

Mezi konečnými hrami praktického významu jsou hry se sedlovým hrotem poměrně vzácné; typičtější je případ, kdy se spodní a horní cena - hry liší. Analýzou matic takových her jsme došli k závěru, že pokud má každý hráč na výběr

jedna - jediná strategie., pak na základě rozumně jednajícího protivníka by tato volba měla být určena zásadou minimax. Při dodržení naší strategie maximin si jistě garantujeme výplatu rovnající se nižší ceně hry, a, za jakékoli chování soupeře. Vyvstává přirozená otázka: je možné si zaručit průměrnou výplatu větší, než když použijete nejen jednu „čistou“ strategii, ale náhodně střídáte několik strategií?

Takové kombinované strategie, spočívající v aplikaci několika čistých strategií střídajících se podle náhodného zákona s určitým poměrem frekvencí, se v teorii her nazývají smíšené strategie.

Je zřejmé, že každá čistá strategie je zvláštním případem smíšené strategie, ve které jsou všechny strategie kromě jedné aplikovány s nulovými frekvencemi a tato s frekvencí 1.

Ukazuje se, že aplikací nejen čistých, ale i smíšených strategií je možné získat řešení pro každou konečnou hru, tedy dvojici (obecně smíšených) strategií tak, že když je použijí oba hráči, bude výplata rovna cena hry a při jakékoli jednostranné odchylce od optimální strategie se výplata může změnit pouze směrem nepříznivým pro devianta.

Uvedené tvrzení je obsahem tzv. hlavní věty teorie her. Tato věta byla poprvé prokázána von Neumannem v roce 1928. Známé důkazy věty jsou poměrně složité; proto uvádíme pouze jeho formulaci.

Každá konečná hra má alespoň jedno řešení (možná v oblasti smíšených strategií).

Výplata vyplývající z rozhodnutí se nazývá cena hry. Z hlavní věty vyplývá, že každá konečná hra má svou cenu. Je zřejmé, že cena hry v leží vždy mezi nižší cenou hry a a nejvyšší cena hry:

Ve skutečnosti existuje maximální zaručený výnos, který si můžeme zajistit pouze pomocí vlastních čistých strategií. Vzhledem k tomu, že smíšené strategie zahrnují jako zvláštní případ všechny čisté, pak umožňují kromě čistých také smíšené

strategie, v žádném případě nezhoršujeme své schopnosti; Tudíž,

Podobně to ukazujeme s ohledem na schopnosti soupeře

odkud následuje požadovaná nerovnost (3.1).

Uveďme speciální označení pro smíšené strategie. Pokud například naše smíšená strategie spočívá v aplikaci strategií AL, s frekvencemi a tuto strategii označíme

Podobně smíšená strategie protivníka bude označena:

kde jsou frekvence, při kterých se strategie mísí

Předpokládejme, že jsme našli řešení hry sestávající ze dvou optimálních smíšených strategií S, S. V obecném případě nejsou v jeho optimální smíšené strategii zahrnuty všechny čisté strategie dostupné danému hráči, ale pouze některé z nich. Strategie obsažené v optimální smíšené strategii hráče budeme nazývat jeho „užitečné“ strategie.

Ukazuje se, že řešení hry má ještě jednu pozoruhodnou vlastnost: pokud jeden z hráčů dodržuje svou optimální smíšenou strategii 5 (5). pak výplata zůstane nezměněna a rovná se ceně hry v, bez ohledu na to, co udělá druhý hráč, pokud ano. pouze nepřekračuje své „užitečné“ strategie. Může například použít jakoukoli ze svých „užitečných“ strategií čistá forma a může je také míchat v libovolných poměrech.

Pojďme toto tvrzení dokázat. Ať existuje řešení hry. Pro konkrétnost budeme předpokládat, že optimální smíšená strategie se skládá ze směsi tří

„užitečné“ strategie sestávají ze směsi tří „užitečných“ strategií

a Uvádí se, že pokud se budeme držet strategie S, tak soupeř může aplikovat strategie v libovolném poměru a výplata zůstane nezměněna a bude se stále rovnat ceně hry.

Pokud ve hře každý ze soupeřů používá stejnou strategii, pak se říká, že tato hra probíhá v čistých strategiích a strategie hráčů A a B se budou nazývat čisté strategie.V antagonistické hře se nazývá dvojice strategií rovnováha(udržitelné), pokud je pro některého z hráčů nerentabilní ustoupit od svých strategií. Má smysl používat čisté strategie, pokud si hráči uvědomují akce soupeře. Pokud tomu tak není, pak je myšlenka rovnováhy narušena a hru lze hrát, jak bude. Strategie A1 B1 jsou stabilní s ohledem na informace o chování soupeře. Známka stability páru strategií je rovnost horní a dolní ceny hry. A případ A1 B1 bude

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

Věta: každá hra s perfektními informacemi má sedlovou pointu a proto řeší v čistých strategiích, tzn. existuje dvojice stabilních strategií, které poskytují stabilní výplatu rovnou ν. Pokud matice nemá sedlový bod, pak cena hry leží α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии.Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.

Specifikovat smíšenou strategii znamená specifikovat pravděpodobnosti, se kterými se čisté strategie používají.

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

Hru lze několikrát opakovat, ale v každé hře se hráč řídí smíšenou strategií, kde čisté strategie sledují pravděpodobnosti p i a q j .

Model smíšené strategie se liší od modelu čisté strategie. V případě smíšených strategií bude taktika chování hráčů flexibilnější, protože hráči předem vědí, jakou čistou strategii použijí.

Předpokládejme, že hráč A i hráč B postupují podle smíšené strategie. Je třeba určit А: ∑∑ a ij p i q j

U hráče B se očekávaná ztráta rovná očekávané výplatě hráče A. Výplata prvního hráče a průměrná prohra druhého hráče se navzájem rovnají.

18. Metody řešení konečné dvouhry řádu m * n.

Předpokládejme, že všechny prvky výplatní matice jsou 0≤aij. Potom α≤ν≤β. Podle základní věty maticových her má každá maticová hra 2 optimální smíšené strategie.

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

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

Hru řešíme za hráče A, přičemž předpokládáme, že hráč B používá pouze čisté strategie. Pak

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 \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)

Definujme problém lineárního programování.

ν = 1/(X 10 +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) (přímý 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 \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 -> max

∑a ij , y i ≤1 (i=1,2…) (9) (duální 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) α = 1, β = 3

2) Neexistují žádná zjednodušení.

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 \u003d 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

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

dvojí úkol

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

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

3y 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

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)

Problém mxn je redukován na problém lineárního programování.

Přibližná metoda pro řešení maticových her mxn (Brown-Robinson).

Hráč A a hráč B střídavě uplatňují čisté strategie. Každý hráč se snaží zvýšit svou výplatu pomocí maximinových nebo minimaxových přístupů. Není minimalizován (maximalizován) průměrný zisk, ale akumulovaný. Teoreticky se ukazuje, že taková metoda nám nevyhnutelně poskytne optimální výnos a optimální smíšené strategie.