Čistá stratégia- deterministický (okrem náhodnosti) plán činnosti. V predchádzajúcej kapitole sme uvažovali iba o čistých stratégiách. O zmiešaných stratégiách sa bude diskutovať v časti 2.2, ale zatiaľ, ak nie je uvedené inak, pod pojmom stratégia máme vždy na mysli čistú stratégiu.

Veľmi často v procese prezentácie budeme ilustrovať koncepty riešenia s príkladmi bimaticových hier, takže uvedieme príslušné definície.

Definícia 2.1. koniec hry je hra, v ktorej množina hráčov a množina stratégií každého hráča obsahuje konečný počet prvkov. Konečná hra dvoch osôb sa nazýva bimatická hra.

Priezvisko pochádza z pohodlnej formy zaznamenávania výhier v takejto hre – pomocou dvojitej matice.

Pre ďalšiu analýzu je vhodné rozdeliť stratégie v ľubovoľnom strategickom profile s na stratégiu niektorých /-tých hráčov s a stratégie všetkých ostatných hráčov s_ (. Formálne s = (.y, s,). Neznamená to, že vymeníme súradnice strategického profilu, iba zavedieme iný spôsob jeho označenia.

Prvým konceptom riešenia hry, ktorý budeme uvažovať, je rovnováha v dominantných stratégiách.

Definícia 2.2. Stratégia /-tého hráča prísne dominoval jeho stratégia s“ ak Uj(s jt s ,) > h,(s", s ,) pre ľubovoľnú množinu s , stratégií zostávajúcich hráčov. V tomto prípade sa stratégia s" nazýva prísne dominoval.

V podstate to znamená, že pre každého pevné v množine stratégií zostávajúcich hráčov i-tý hráč, ktorý si zvolí stratégiu s, získa striktne väčšia výhra než pri voľbe stratégie s". Je logické predpokladať, že racionálny hráč by si nemal vyberať striktne dominované stratégie. Takýto predpoklad v najjednoduchších hrách môže stačiť na nájdenie riešenia hry.

Definícia 2.3. Profil stratégií s* =(s*, s^,..., s*) sa nazýva rovnováhu v (prísne) dominantné stratégie, ak u ktoréhokoľvek i-tého hráča stratégia s“ striktne dominuje nad ktoroukoľvek inou jeho stratégiou.

Môže sa zdať, že tento koncept riešenia môže viesť len k triviálnym záverom. Každý hráč má vo svojich stratégiách jednu, ktorá mu prinesie odmenu viac ako ktorákoľvek iná, bez ohľadu na to, ako sa jeho súperi správajú. Potom použije presne túto stratégiu v rovnováhe. Všetko je celkom zrejmé. Ale je to práve táto situácia, ktorá je typická pre azda najznámejšiu a pre analýzu množstva praktických situácií z hry „väzňova dilema“ veľmi dôležitá.

Príklad 2.1 (dilema väzňov). Dvaja zločinci sú vo väzbe v rôznych celách a nemôžu spolu komunikovať. Vyšetrovanie má dostatok dôkazov na to, aby každého z nich odsúdili za menší trestný čin na jeden rok. No na veľký zločin, za ktorý zločincom hrozí desať rokov väzenia, vyšetrovanie nemá dostatok dôkazov. Zástupcovia vyšetrovania ponúkajú každému zo zločincov dohodu: zločinec dostane termín

o rok menej, ak predloží dôkazy proti svojmu partnerovi, čo bude stačiť na jeho obvinenie zo závažného zločinu. Predpokladajme, že zločinci sa zaoberajú len počtom rokov, ktoré strávia vo väzení, každý ďalší rok je mínus jedna jednotka užitočnosti. Potom môžu byť výnosy zločincov reprezentované nasledujúcou dvojitou maticou:

V prípade, že účastníci hry nie sú uvedení, budeme predpokladať, že rôzne stratégie prvého účastníka zodpovedajú riadkom dvojitej matice a stratégie druhého účastníka zodpovedajú stĺpcom. Ak v našom príklade prvý väzeň vypovedá a druhý nevypovedá, tak prvý bude prepustený a druhý dostane desať rokov väzenia.

Je ľahké vidieť, že bez ohľadu na to, ako sa druhý väzeň správa akokoľvek, zisk je väčší (doba odňatia slobody je kratšia), ak poskytnete dôkaz (pre prvého hráča sú prvé súradnice v prvom riadku dvojitej matice prísne väčšie ako v druhom riadku, pre druhého hráča sú druhé súradnice v dvojitej matici prvého stĺpca striktne väčšie ako v druhom stĺpci). Potom bude rovnováha v dominantných stratégiách profilom stratégií (svedčiť, svedčiť).

zaujímavé v tento príkladže hráči, ktorí si zvolia správanie, ktoré zvyšuje ich výplatu, skončia v situácii, keď sú ich výplaty nízke v porovnaní s opačnou situáciou – keď sa obaja rozhodnú mlčať. Vysvetlenie spočíva v prítomnosti silného vonkajšieho účinku, t.j. silný vplyv akcií jedného hráča na výplaty iného hráča. Výsledkom je, že rovnovážny profil stratégií sa ukazuje ako jediný paretovský neefektívny v tejto hre. Upozorňujeme, že Paretova efektivita, žiaduca z pohľadu účastníkov hry, nemusí byť žiaduca zo sociálneho hľadiska, ako v tomto prípade.

Pri analýze ekonomických situácií sa často vyskytujú situácie ako väzňova dilema. Uvažujme napríklad o konkurencii dvoch obchodov predávajúcich podobný súbor produktov. Pre zjednodušenie predpokladajme, že obchody môžu účtovať len dve cenové úrovne – vysokú alebo nízku. Spotrebitelia prirodzene uprednostňujú nákup v obchode s nižšími cenami. Potom môžu výnosy obchodov, charakterizované ich ziskami, vyzerať napríklad takto:

Z hľadiska rovnováhy je tu situácia analogická s väzňovou dilemou - rovnováha v dominantných stratégiách (nízke ceny, nízke ceny) je jediným paretovským neefektívnym profilom (a tiež žiaducim zo sociálneho hľadiska).

Už spomínaná široká obľuba Väzňova dilema bola dôvodom, prečo sa na jej príklade pokúsili experimentálne otestovať správnosť predpovedí teórie hier. Test bol, že dva cudzinci bolo navrhnuté hrať hru o peniaze s cenami (napríklad v dolároch) blízkymi tým, ktoré sú uvedené pre hru dvoch obchodov. Každý z účastníkov sa rozhodoval samostatne (často anonymne) a pred prevzatím výhry nepoznal rozhodnutia druhého hráča. Ukázalo sa, že za takýchto podmienok v mnohých hrách nedospeli hráči k rovnovážnemu výsledku za predpokladu, že peňažné výhry správne odhadnú svoje výhry. Z výsledkov týchto experimentov samozrejme nevyplýva, že predpovede teórie hier sú nesprávne, ale len to, že hráči pri hodnotení svojej výplaty brali do úvahy aj nepeňažné faktory – úvahy o altruizme, férovosti atď. Ak sú výnosy hráčov správne odhadnuté, mali by hráči preferovať dominantnú stratégiu, a teda ju zvoliť (v duchu odhalených preferencií v mikroekonómii). Preto hodnota experimentov tohto druhu nespočíva v testovaní herných teoretických predpovedí, ale v hodnotení úlohy nemateriálnej motivácie v konaní jednotlivcov.

Teória hier výrazne menej ako pojem silnej dominancie využíva pojem slabej dominancie.

Definícia 2.4. Stratégia /-tého hráča, slabo dominantný jeho stratégia s“ ak m,(s, s ,) > m; (sJ, s ,) pre ľubovoľný súbor stratégií iných hráčov s_j, navyše pre aspoň jeden súbor stratégií iných hráčov je nerovnosť striktne splnená. Potom sa nazýva stratégia s slabo dominoval.

V prípade nestriktných nerovností už nie je možné tvrdiť, že racionálny hráč nezvolí slabo dominovanú stratégiu, hoci takéto správanie vyzerá celkom logicky. Existuje, aj keď sa zriedka používa, definícia rovnováhy v slabo dominantných stratégiách analogická k prípadu silnej dominancie.

Definícia 2.5. Volá sa strategický profil s* = (s*, Sj,..., s*). rovnováha v slabo dominantných stratégiách, ak u ktoréhokoľvek i-tého hráča stratégia s“ slabo dominuje nad ktoroukoľvek inou z jeho stratégií.

Príklad 2.2 (uzavretá aukcia druhej ceny). Uzavretá aukcia druhej ceny sa koná medzi dvoma osobami. Aukcia je usporiadaná nasledovne. Každý z účastníkov uvádza nezápornú mieru, pričom nepozná miery ostatných účastníkov (v obálke). Člen, ktorý urobil najvyššia ponuka, zaplatí maximálnu sumu spomedzi ponúk ostatných účastníkov (t. j. sumu druhej, ale hodnotu ponuky) a dostane nejakú položku. Ak boli ponuky hráčov napríklad 100 a 90, tak účastník, ktorý dal ponuku 100, vyhráva aukciu, získava predmet za 90 – veľkosť druhej ponuky. Nechajte každého účastníka posúdiť predmet vyjadrený v peňažných jednotkách, v2> 0. Tieto odhady sú známe všetkým účastníkom. Pre zjednodušenie popisu hry, ak obaja účastníci uvádzajú rovnakú mieru, potom predmet pripadne prvému účastníkovi.

V tejto hre bude stratégia prvého hráča s veľkosťou jeho stávky. Keďže miera je nezáporná, množina všetkých možných stratégií

5, = 0 = u,(o, s 2) > w,(s, s 2) = u, - s 2 v x slabo dominuje stratégii s,.

Ukázali sme, že pre prvého hráča stratégia pomenovať svoje skóre ako stávku slabo dominuje akejkoľvek inej stratégii. Je ľahké si overiť, že podobné tvrdenie platí aj pre druhého hráča. Všimnite si, že v našej úvahe sme nikdy nepoužili fakt, že hráč pozná odhad iného hráča, čo znamená, že v prípade hry s neúplnými informáciami v uzavretej aukcii druhej ceny bude nemenej výhodné menovať váš odhad než urobiť akúkoľvek inú ponuku.

Môže sa zdať, že pre predávajúceho je nerentabilné dohodnúť aukciu druhej ceny, keď môže vydražiť prvú cenu a získať hodnotu nie druhej, ale prvej ponuky. Hodnota sadzieb v prípade aukcie prvej ceny v rovnováhe však bude nižšia. Viac o výnose aukcií si povieme v kap. 5. Medzitým podotýkame, že druhá cenová aukcia je veľmi populárna a je hojne využívaná napr. Google a "Yandex" pri predaji kontextovej reklamy na internete.

Rovnováha v dominantných stratégiách existuje len v malej triede hier. Hráči zvyčajne nemajú jedinú stratégiu, ktorá by dominovala všetkým ostatným. Koncept dominancie však umožňuje nájsť riešenia v širšej triede hier. Aby ste to dosiahli, musíte dôsledne uvažovať o činnostiach hráčov. Už sme poznamenali, že racionálny hráč nezvolí striktne dominovanú stratégiu. To však znamená, že druhý hráč môže hru analyzovať, pričom ignoruje možnosť voľby takejto stratégie súpera. Možno nejaká analýza odhalí, že iný hráč má dominantnú stratégiu, ktorá nebola dominantná v pôvodnej hre. A tak ďalej. Uveďme formálnu definíciu.

Proces postupné vylúčenie silne dominovaných stratégií je nastavený nasledovne. Vylúčme z úvahy všetky striktne dominované stratégie hráčov, t.j. zvážiť novú hru, v ktorej sú všetky dominantné stratégie vylúčené zo súboru možných stratégií hráčov. Potom v tomto Nová hra eliminujeme všetky prísne dominované stratégie atď.

Je možné, že takýto proces skončí, keď hráčom zostane niekoľko stratégií, ale je možné, že každý hráč bude mať len jednu nevylúčenú stratégiu, potom je logické považovať súbor týchto stratégií za riešenie hry. .

Definícia 2.6. Ak v dôsledku postupnej eliminácie silne dominovaných stratégií zostane každému hráčovi jediná stratégia, potom sa profil týchto stratégií nazýva tzv. rovnováha dominancie.

V príklade 1.1 sme získali práve takúto rovnováhu. Uvažujme ešte o jednom príklade.

Strategický profil (N, P) je jedinou Nashovou rovnováhou v tejto hre. Ale všimnite si, že aby si druhý hráč mohol vybrať P, musí si byť istý, že prvý hráč nezvolí B. Ale výplata prvého hráča je rovnaká, ak si druhý hráč vyberie II. Navyše výberom B sa prvý hráč nemusí báť, že druhý hráč si vyberie L. Možno sa racionálny druhý hráč zamyslí nad voľbou stratégie C.

Druhá otázka, na ktorú sa zatiaľ nenašla jednoznačná odpoveď: ako sa hráči dostanú do Nashovej rovnováhy?

Ideálny teoretický scenár je nasledovný. Hráči nezávisle vytvárajú očakávania o činnostiach iných hráčov a potom si vyberajú činnosti, ktoré maximalizujú ich zisk vzhľadom na dané očakávania. Ak v tomto prípade očakávania zodpovedajú akciám, ktoré si hráči skutočne vybrali, získame Nashovu rovnováhu. Tento spôsob uvažovania nám umožňuje nazvať Nashovu rovnováhu situáciou s sebanaplňujúce očakávania. Ale odkiaľ pochádzajú očakávania? A ktorá z Nashových rovnováh, ak ich je niekoľko, sa vyberie ako výsledok opísaného procesu? V rámci uvažovaného scenára zostávajú tieto otázky nezodpovedané.

Ďalší prístup zahŕňa prítomnosť tréningu hráčov. Hráči sa buď teoreticky naučia hru hrať (spomeňme si na študenta ekonómie), alebo zažívajú podobné interakcie (napr. skúsený pracovník príde na nový tím), čo im umožňuje správne formovať očakávania a zvoliť si optimálne správanie. Tento scenár umožňuje vysvetliť formovanie očakávaní, ale po prvé redukuje rozsah herných modelov iba na štandardné, študované a často sa vyskytujúce situácie interakcie a po druhé môže viesť k tomu, že situácie jednotlivých a opakovaných interakcie sa nerozlišujú a tie sa výrazne líšia v stratégiách a metódach riešenia v rámci teórie hier, ktorým sa budeme podrobnejšie venovať v kap. štyri.

Tretím scenárom je, že medzi hráčmi existuje predchádzajúca dohoda alebo zvyky, zákony alebo pokyny tretích strán, ktoré riadia interakciu hráčov. V tomto prípade dohody alebo pokyny nemusia byť záväzné, ale ak sa odporúča hrať Nashovu rovnováhu, potom žiadny z hráčov nemá túžbu (sám) odchýliť sa od predpísaného správania. Je jasné, že takýto scenár nie je možný v každej situácii. Okrem toho sa súčasťou hry môže stať aj samotný proces vytvárania dohody alebo zapojenia tretích strán.

Napokon, tretia prirodzená otázka, ktorá vyvstáva pri štúdiu konceptu Nashovej rovnováhy, je nasledujúca: existuje nejaký empirický dôkaz, že skutoční hráči si zvyčajne vyberajú rovnovážne stratégie? Aj tu je mimoriadne ťažké dať stručnú a jednoznačnú odpoveď. Povaha problémov, ktoré vznikajú, je zároveň v súlade s predmetom experimentálnej ekonómie. Preto sa obmedzujeme na odporúčanie obrátiť sa na odbornú literatúru, napríklad knihu, kde sú výborne rozobraté otázky experimentálnej metodológie a prezentovaných množstvo výsledkov.

Sú hry, ktoré v čistých stratégiách nemajú rovnováhu (pozri príklad 3.1), preto vzniká otázka: aké podmienky sú dostatočné na existenciu takejto rovnováhy? Sformulujme a dokážme tvrdenie o existencii Nashovej rovnováhy v čistých stratégiách v hrách, ktoré nie sú konečné.

Vyhlásenie 2.3. Ak sú sady stratégií pre každého z hráčov S t sú neprázdne konvexné kompakty v euklidovskom priestore a výplatná funkcia každého hráča a- nepretržitý v s a kvázi konkávne v 5, potom má hra Nashovu rovnováhu v čistých stratégiách.

Dôkaz. Pripomeňte si formuláciu Kakutaiove vety, ktorý použijeme pri dôkaze. Nechaj X- neprázdny konvexný kompaktný zasadený v Rn, X* je množina jeho podmnožín a/ je také horné polospojité zobrazenie z X v X*,že za každý bod x e x veľa f(x) neprázdne, uzavreté a konvexné. Potom má mapovanie / pevný bod.

Myšlienkou dokázať naše tvrdenie je vytvoriť mapovanie, ktoré spĺňa podmienky Kakutaniho vety. Aby sme to dosiahli, mierne predefinujeme zobrazenie najlepšej odpovede. Čisto technicky budeme predpokladať, že najlepšia odpoveď závisí nielen od stratégií ostatných hráčov, ale aj od hráčovej vlastnej stratégie s y (s). So zmenou vlastnej stratégie hráča kedy fixné stratégie zvyšok hráčov, najlepšia odpoveď sa samozrejme nezmení. Teraz si predstavme notáciu na zobrazenie najlepšej odpovede pre všetkých hráčov ako karteziánsky súčin s(s) = s,(s) x s 2 (s) x... x s n (s). Toto mapovanie ku každému profilu priraďuje množinu profilov, v ktorých má každý hráč najlepšia cesta reaguje na stratégie ostatných hráčov. Pevný bod mapovania S, t.j. profilu s také že s e s(s)> je podľa definície Nashova rovnováha. Ukážme, že zobrazenie 5 spĺňa podmienky Kakutaniho vety. Overenie každej podmienky bude predstavovať samostatný dôkaz.

• 1. Ukážme, že množina S všetky profily - konvexný kompakt. Keďže pod podmienkou presadzovania množiny stratégií každého z hráčov S sú neprázdne konvexné kompaktné množiny, potom karteziánsky súčin S = S t X S2 X...x S n je konvexný kompakt.
• 2. Displej s má neprázdne obrázky. Podľa Weierstrassovej vety spojitá funkcia a- dosiahne na uzavretej ohraničenej množine 5 svoju maximálnu hodnotu. v dôsledku toho s má neprázdne obrázky.
• 3. Zobrazte obrázky s uzavreté a konvexné. Od výplatnej funkcie každého hráča u t kvázi konkávne v s ak potom vlastnosťou kvázikonkávnej funkcie množina $. = (s. | u t (s i9 s .) > k) za pevné s .a k zatvorené o uzavretá oblasť definície a je konvexný, ak nie je prázdny. Keďže to platí pre každého k, potom tiež platí, že množina 5. = (5/1 u t(s", 5 ,) > max. hm. (s., s .)}

konvexné. Ale potom karteziánsky súčin 5(5) = s x (s) X s2(S) x... x s n CS) je uzavretý a konvexný.

4. Ukážme, že mapovanie § polosúvislý zhora. Pre funkciu používame podmienku spojitosti a od s. Dokážeme protirečením. Predpokladajme, že displej § ns je horný semikontinuálny. Potom sú tu sekvencie strategických profilov s m a s m , kde t -číslo sekvenčného prvku, také, že pre ľubovoľné t s"" e S, s m e s(s""), lim s"" = s° e S, ale lim s"" = s° g lim s(s""). To znamená, že existuje a

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

skala, pre ktorú stratégia s f ° nie je najlepšou odozvou na s 0, t.j. existuje stratégia s" také že a,(s", s 0,) > u,(y] s° ;). Potom môžeme nájsť e > 0 také, že m,(s/, s 0 ,) > m, (s ; °, s 0 ,) + Ze, odkiaľ

Keďže podľa predpokladu je funkcia m spojitá, lim s m = s°, lim s"" = s°,

m*oo m-*oo

s dostatočne veľkým m správny

Zlúčením nerovností (2.8)-(2.10) do jedného reťazca dostaneme

Zo vzťahov (2.11) vyplýva, že u,(s", s"") > m,(s/", s"") + s, ale to je v rozpore s podmienkou s"" e s(s""), pretože s" poskytuje striktne väčšiu odmenu ako s/", ako odpoveď na s"". Došli k rozporu. Preto bol náš pôvodný predpoklad, že s nie je horná polospojitá, nesprávny.

Ukázali sme, že mapovanie S spĺňa všetky podmienky Kakutaniho vety, a preto má pevný bod. Tento pevný bod je Nashova rovnováha. Tvrdenie 2.3 je dokázané. ?

Najmä vyhlásenie 2.3 zaručuje existenciu Nashovej rovnováhy v príklade 2.7, ale nie v príklade 2.8, kde sú výplatné funkcie hráčov nespojité.

„Príklad z práce.

5. TEÓRIA HER A ŠTATISTICKÉ RIEŠENIA

5.1. Maticová hra s nulovým súčtom

Ekonomické a matematické modelovanie sa vykonáva za nasledujúcich podmienok:

Istota;

Neistoty.

Modelovanie za podmienok istoty predpokladá dostupnosť všetkých počiatočných regulačných údajov potrebných na to (maticové modelovanie, plánovanie siete a manažment).

Modelovanie v ohrození sa vykonáva za stochastickej neistoty, keď sú hodnoty niektorých počiatočných údajov náhodné a sú známe zákony rozdelenia pravdepodobnosti týchto náhodných premenných (regresná analýza, teória radenia).

Modelovanie v podmienkach neistoty zodpovedá úplnej absencii niektorých údajov na to potrebných (teória hier).

Matematické modely na prijímanie optimálnych rozhodnutí v konfliktných situáciách sa budujú v podmienkach neistoty.

V teórii hier sa používajú tieto základné pojmy:

stratégia;

win funkcia.

pohybovať sa budeme nazývať výber a implementáciu jednej z akcií stanovených v pravidlách hry hráčom.

Stratégia - Ide o technológiu na výber postupu pre každý pohyb v závislosti od situácie.

win funkcia slúži na určenie výšky platby porazeného hráča víťazovi.

V maticovej hre je výplatná funkcia reprezentovaná ako platobná matica :

kde je výška platby hráčovi I, ktorý si vybral ťah , od hráča II, ktorý si ťah vybral .

V takejto párovej hre sú hodnoty výplatných funkcií oboch hráčov v každej situácii rovnaké vo veľkosti a opačné v znamienku, t.j. a táto hra sa volá nulová suma .

Proces „hrania maticovej hry“ je znázornený takto:

Platobná matica je nastavená;

Hráč I, bez ohľadu na hráča II, si vyberie jeden z riadkov tejto matice, napríklad -th;

Hráč II, bez ohľadu na hráča I, si vyberie jeden zo stĺpcov tejto matice, napríklad - th;

Prvok matice určuje, koľko hráča dostanem od hráča II. Samozrejme, ak , potom hovoríme o skutočnej strate hráča I.

Antagonistická dvojitá hra s platobná matica a bude sa nazývať hrou.

Príklad

Uvažujme o hre.

Platobná matica je daná:

.

Nech si hráč I, bez ohľadu na hráča II, vyberie 3. riadok tejto matice a hráč II, bez ohľadu na hráča I, vyberie 2. stĺpec tejto matice:

Potom hráč I dostane 9 jednotiek od hráča II.

5.2. Optimálna čistá stratégia v maticovej hre

Optimálna stratégia Stratégia hráča I sa nazýva taká, že hráč II nezníži svoju výplatu za akúkoľvek voľbu stratégie, a taká stratégia hráča II, že nezvýši svoju stratu pri akejkoľvek voľbe stratégie hráča I.

Zvolením i-tého riadku výplatnej matice ako ťahu si hráč I zabezpečí výplatu aspoň v hodnote v najhoršom prípade, keď sa hráč II snaží túto hodnotu minimalizovať. Preto si hráč vyberie -tý riadok, ktorý mu poskytne maximálna výhra:

.

Hráč II argumentuje podobným spôsobom a môže si zaručiť minimálnu stratu:

.

Nasledujúca nerovnosť platí vždy:

Hodnota sa volá nižšia cena hry .

Hodnota sa volá najvyššia cena hry .

Optimálne stratégie sú tzv čisté , ak sú pre nich splnené rovnosti:

,

.

Hodnota sa volá čistá cena hry , ak .

Optimálne čisté stratégie a forma sedlový bod platobná matica.

Pre sedlový bod sú splnené tieto podmienky:

t.j. prvok je najmenší v rade a najväčší v stĺpci.

Ak teda výplatná matica má sedlový bod , potom môžete nájsť optimálne čisté stratégie hráčov.

Čistá stratégia hráča I môže byť reprezentovaná usporiadanou množinou čísel (vektorom), v ktorej sú všetky čísla rovné nule, okrem čísla na -tom mieste, ktoré sa rovná jednej.

Čistá stratégia hráča II môže byť reprezentovaná usporiadanou množinou čísel (vektorom), v ktorej sa všetky čísla rovnajú nule, okrem čísla na -tom, ktoré sa rovná jednej.

Príklad

.

Zvolením niektorého riadku výplatnej matice ako ťahu si hráč I zabezpečí výplatu v najhoršom prípade nie menšiu ako je hodnota v stĺpci označenom:

Preto si hráč I vyberie 2. riadok výplatnej matice, ktorý mu poskytuje maximálnu výplatu bez ohľadu na ťah hráča II, ktorý sa bude snažiť túto hodnotu minimalizovať:

Hráč II argumentuje podobne a ako ťah zvolí 1. stĺpec:

Existuje teda sedlový bod matice výplaty:

čo zodpovedá optimálnej čistej stratégii pre hráča I a pre hráča II tak, že hráč I nezníži svoju výplatu za akúkoľvek zmenu stratégie hráča II a hráč II nezvýši svoju stratu za akúkoľvek zmenu stratégie hráča I.

5.3. Optimálne zmiešaná stratégia v maticovej hre

Ak výplatná matica nemá sedlový bod, potom nie je pre žiadneho hráča racionálne používať jednu čistú stratégiu. Ziskovejšie použitie "pravdepodobnostné zmesi" čisté stratégie. Potom sú už zmiešané stratégie definované ako optimálne.

Zmiešaná stratégia hráč sa vyznačuje rozdelením pravdepodobnosti náhodná udalosť, spočívajúci vo výbere ťahu týmto hráčom.

Zmiešaná stratégia hráča I je taká usporiadaná množina čísel (vektor), ktorý spĺňa dve podmienky:

1) pre, t.j. pravdepodobnosť výberu každého riadku výplatnej matice nie je záporná;

2), t.j. výber každého z riadkov výplatnej matice v súhrne predstavuje celá skupina diania.

Zmiešaná stratégia hráča II je usporiadaná množina čísel (vektor) spĺňajúci podmienky:

Čiastka na úhradu hráčovi I, ktorý zvolí zmiešanú stratégiu

od hráča II, ktorý zvolil zmiešanú stratégiu

,

je priemer

.

Optimálne nazývané zmiešané stratégie

a ,

ak je pre ľubovoľné zmiešané stratégie splnená nasledujúca podmienka:

t.j. pri optimálnej zmiešanej stratégii je výplata hráča I najväčšia a strata hráča II najmenšia.

Ak v matici výplaty nie je sedlový bod, potom

,

t.j. existuje kladný rozdiel ( zachovaný rozdiel )

- ³ 0,

a hráči musia hľadať ďalšie príležitosti, aby s istotou získali väčší podiel z tohto rozdielu vo svoj prospech.

Príklad

Zvážte hru danú výplatnou maticou:

.

Zistite, či existuje sedlový bod:

, .

Ukazuje sa, že v matici výplaty nie je sedlový bod a nerozdelený rozdiel je:

.

5.4. Hľadanie optimálnych zmiešaných stratégií

na 2×2 hry

Určenie optimálnych zmiešaných stratégií pre výplatnú maticu s rozmermi sa vykonáva metódou hľadania optimálnych bodov funkcie dvoch premenných.

Nech je pravdepodobnosť, že hráč I vyberie prvý riadok výplatnej matice

rovná sa . Potom je pravdepodobnosť výberu druhého radu .

Nech sa pravdepodobnosť, že hráč II vyberie prvý stĺpec, rovná . Potom je pravdepodobnosť výberu druhého stĺpca .

Výška platby hráčovi I hráčom II sa rovná:

Extrémna hodnota zisku hráča I a straty hráča II zodpovedá podmienkam:

;

.

Optimálne zmiešané stratégie hráčov I a II sú teda:

5.5. Geometrické riešenie 2× hiern

S nárastom dimenzie výplatnej matice od do už nie je možné zredukovať definíciu optimálnych zmiešaných stratégií na hľadanie optima funkcie dvoch premenných. Avšak vzhľadom na to, že jeden z hráčov má len dve stratégie, možno použiť geometrické riešenie.

Hlavné fázy hľadania riešenia hry sú nasledovné.

V rovine zavedieme súradnicový systém. Položme na os úsečku. Z ľavého a pravého konca tohto segmentu nakreslíme kolmice.

Ľavý a pravý koniec segmentu jednotiek zodpovedá dvom stratégiám a , dostupným pre hráča I. Na nakreslených kolmiciach odložíme výplaty tohto hráča. Napríklad pre výplatnú maticu

také výplaty hráča I pri výbere stratégie budú a , a pri výbere stratégie budú a .

Spojme výplatné body hráča I, zodpovedajúce stratégiám hráča II, priamymi úsečkami. Potom vytvorená prerušovaná čiara, ktorá ohraničuje graf zdola, určuje spodnú hranicu výplaty hráča I.

Nájdenie optimálnej zmiešanej stratégie pre hráča I

,

čo zodpovedá bodu na spodnej hranici výplaty hráča I s maximálnou súradnicou.

Venujme pozornosť skutočnosti, že v uvažovanom príklade s použitím iba dvoch stratégií a , zodpovedajúcich rovným čiaram pretínajúcim sa v nájdenom bode na spodnej hranici výplaty hráča I, môže hráč II zabrániť hráčovi I získať väčšiu vyplatiť.

Hra je teda zredukovaná na hru a optimálna zmiešaná stratégia hráča II v uvažovanom príklade je

,

kde je pravdepodobnosť rovnaká ako v hre:

5.6. Riešenie hrym× n

Ak maticová hra nemá riešenie v čistých stratégiách (t. j. neexistuje sedlový bod) a vzhľadom na veľký rozmer matice výplaty ju nemožno vyriešiť graficky, potom na získanie riešenia použite metóda lineárneho programovania .

Nech je daná výplatná matica dimenzie:

.

Musíme nájsť pravdepodobnosti , s ktorým hráčom musím voliť jeho ťahy, aby mu táto zmiešaná stratégia zaručila výplatu minimálne , bez ohľadu na výber ťahov hráčom II.

Pre každý ťah vybraný hráčom II je výplata hráča I určená závislosťami:

Vydelíme obe strany nerovností a zavedieme nový zápis:

Rovnosť

Bude mať formu:

Keďže hráč chcem maximalizovať zisk, recipročné musí byť minimalizované. Potom bude mať úloha lineárneho programovania pre hráča I podobu:

pod obmedzeniami

Problém pre hráča II je podobne konštruovaný ako duálny:

pod obmedzeniami

Riešením úloh simplexovou metódou dostaneme:

,

5.7. Vlastnosti riešenia maticových hier

Pred riešením problému hľadania optimálnych stratégií by sa mali skontrolovať dve podmienky:

Je možné zjednodušiť platobnú maticu?

Má výplatná matica sedlový bod?

Zvážte možnosť zjednodušenia platobnej matice:

Vzhľadom k tomu, že hráč sa snažím získať najväčšia výhra, potom môže byť -tý riadok vymazaný z výplatnej matice, pretože tento ťah nikdy nepoužije, ak je nasledujúci vzťah spokojný s iným -tým riadkom:

Podobne, v snahe o čo najmenšiu stratu, hráč II nikdy nezvolí -tý stĺpec v matici výplat ako ťah a tento stĺpec môže byť prečiarknutý, ak platí nasledujúci vzťah s ktorýmkoľvek iným -tým stĺpcom:

Väčšina jednoduché riešenie hra je prítomnosť sedlového bodu v zjednodušenej výplatnej matici, ktorý spĺňa nasledujúcu podmienku (podľa definície):

Príklad

Vzhľadom na výplatnú maticu:

.

Zjednodušenie platobnej matice:

Prítomnosť sedlového bodu:

5.8. Hra s prírodou

Na rozdiel od problémov teórie hier v teória štatistické rozhodnutia neistá situácia nemá antagonistické konfliktné zafarbenie a závisí od objektívnej reality, ktorá sa bežne nazýva "príroda" .

V maticových hrách s prírodou je hráč II súborom neistých faktorov, ktoré ovplyvňujú efektivitu prijímaných rozhodnutí.

Matrixové hry s prírodou sa od bežných maticových hier líšia len tým, že keď hráč I zvolí optimálnu stratégiu, už sa nedá spoliehať na to, že hráč II sa bude snažiť minimalizovať svoju stratu. Preto spolu s výplatnou maticou uvádzame riziková matica :

kde je hodnota rizika hráča I pri použití ťahu za podmienok, rovná rozdielu medzi výplatou ten hráč by som dostal, keby vedel, že podmienka bude stanovená, t.j. , a výplatu , ktorú dostane, pričom pri výbere ťahu nevie, že podmienka bude splnená.

Výplatná matica je teda jedinečne transformovaná na rizikovú maticu a spätná transformácia je nejednoznačná.

Príklad

Win Matrix:

.

Matica rizika:

možné dve problémové vyhlásenia o výbere riešenia v matrixovej hre s prírodou :

maximalizácia zisku;

Minimalizácia rizika.

Problém rozhodovania možno nastaviť pre jednu z dvoch podmienok:

- v ohrození keď je známa funkcia rozdelenia pravdepodobnosti stratégií prírody, napríklad náhodná premenná výskytu každej z navrhovaných špecifických ekonomických situácií;

- v podmienkach neistoty keď takáto funkcia rozdelenia pravdepodobnosti nie je známa.

5.9. Riešenie úloh v teórii štatistických riešení

v ohrození

Pri rozhodovaní pod rizikom hráč I pozná pravdepodobnosti nástup stavov prírody.

Potom je účelné, aby hráč I zvolil stratégiu, pre ktorú priemerná hodnota výnosu, meraná pozdĺž línie, je maximálna :

.

Pri riešení tohto problému pomocou matice rizika získame rovnaké riešenie zodpovedajúce minimálne priemerné riziko :

.

5.10. Riešenie úloh v teórii štatistických riešení

v podmienkach neistoty

Pri rozhodovaní v neistote môžete použiť nasledujúce kritériá :

Waldovo kritérium maxima;

kritérium minimálne riziko Savage;

Kritérium pesimizmu - Hurwitzov optimizmus;

Laplaceov princíp nedostatočného rozumu.

Zvážte maximálne Waldovo kritérium .

Hra s prírodou sa hrá ako s rozumným agresívnym súperom, t. j. prístup zaistenia je realizovaný z pozície extrémneho pesimizmu pre výplatnú maticu:

.

Zvážte Savage kritérium minimálneho rizika .

Podobne ako predchádzajúci prístup z pozície extrémneho pesimizmu pre maticu rizika:

.

Zvážte kritérium pesimizmu - Hurwitzov optimizmus .

Ponúka možnosť nenechať sa viesť extrémnym pesimizmom ani extrémnym optimizmom:

kde je miera pesimizmu;

pri extrémnom optimizme,

at - extrémny pesimizmus.

Zvážte Laplaceov princíp nedostatočného rozumu .

Predpokladá sa, že všetky prírodné stavy sú rovnako pravdepodobné:

,

.

Závery k piatej časti

Maticovej hry sa zúčastňujú dvaja hráči a výplatná funkcia, ktorá slúži na určenie výšky platby od porazeného hráča k víťazovi, je reprezentovaná ako výplatná matica. Bolo dohodnuté, že hráč I si vyberie jeden z riadkov výplatnej matice ako ťah a hráč II si vyberie jeden z jeho stĺpcov. Potom na priesečníku vybraného riadka a stĺpca tejto matice je číselná hodnota platby hráčovi I od hráča II (ak je táto hodnota kladná, potom hráč, ktorý som skutočne vyhral, ​​a ak je záporná, potom hráč II. v podstate vyhral).

Ak je vo výplatnej matici sedlový bod, hráči majú optimálne čisté stratégie, t.j. aby vyhrali, každý z nich musí zopakovať svoj jeden optimálny ťah. Ak nie je bod sedla, potom na víťazstvo musí každý z nich použiť optimálnu zmiešanú stratégiu, t. j. použiť zmes ťahov, z ktorých každý musí byť vykonaný s optimálnou pravdepodobnosťou.

Nájdenie optimálnych zmiešaných stratégií pre hry 2×2 sa vykonáva výpočtom optimálnych pravdepodobností pomocou známych vzorcov. Používaním geometrické riešenie 2×n hry, definícia optimálnych zmiešaných stratégií v nich sa redukuje na hľadanie optimálnych zmiešaných stratégií pre hry 2×2. Na riešenie m×n hier sa používa metóda lineárneho programovania, aby sa v nich našli optimálne zmiešané stratégie.

Niektoré výplatné matice sa hodia na zjednodušenie, v dôsledku čoho sa ich rozmer zmenšuje vymazaním riadkov a stĺpcov zodpovedajúcich nesľubným ťahom.

Ak je hráč II súborom neistých faktorov, ktoré závisia od objektívnej reality a nemajú antagonistické zafarbenie konfliktov, potom sa takáto hra nazýva hra s prírodou a na jej riešenie sa používajú problémy teórie štatistických rozhodnutí. Potom sa spolu s výplatnou maticou zavedie matica rizika a sú možné dve formulácie problému výberu riešenia v maticovej hre s prírodou: maximalizácia zisku a minimalizácia rizika.

Riešenie problémov teórie štatistického rozhodovania za rizikových podmienok ukazuje, že pre hráča I je účelné zvoliť stratégiu, pre ktorú je priemerná hodnota (očakávania) výplaty, braná podľa matice výplaty maximálna, resp. ktorá je rovnaká) priemerná hodnota (očakávania) rizika, brané čiarou matice rizika, je minimálna. Pri rozhodovaní v neistote sa používajú tieto kritériá: Waldovo kritérium maxima, Savageovo kritérium minimálneho rizika, Hurwitzovo pesimisticko-optimistické kritérium, Laplaceov princíp nedostatočného rozumu.

Otázky na samovyšetrenie

Ako sú definované základné pojmy teórie hier: pohyb, stratégia a výplatná funkcia?

Ako je výplatná funkcia zastúpená v maticovej hre?

Prečo sa maticová hra nazýva nulový súčet?

Aký je proces hrania maticovej hry?

Aká hra sa nazýva hra m×n?

Aká je optimálna stratégia maticovej hry?

Aká je optimálna stratégia pre maticovú hru s názvom pure?

Čo znamená sedlový bod matice výplaty?

Aká je optimálna stratégia pre maticovú hru s názvom zmiešaná?

Aká je zmiešaná stratégia hráča?

Aký je prínos pre hráča I od hráča II, ktorý si zvolil zmiešané stratégie?

Aké zmiešané stratégie sa nazývajú optimálne?

Čo znamená nerozdelený rozdiel?

Aká metóda sa používa na nájdenie optimálnych zmiešaných stratégií pre hry 2×2?

Ako sa nájdu optimálne zmiešané stratégie pre hry 2×n?

Aká metóda sa používa na nájdenie optimálnych zmiešaných stratégií pre hry m×n?

Aké sú vlastnosti riešenia maticových hier?

Čo znamená zjednodušenie platobnej matice a za akých podmienok ju možno zaviesť?

Ktorá maticová hra sa ľahšie rieši, keď matica výplaty má alebo nemá sedlový bod?

Aké problémy teórie hier súvisia s problémami teórie štatistických rozhodnutí?

Ako sa matica výplaty transformuje na maticu rizika?

Aké dve formulácie problému výberu riešení sú možné v maticovej hre s prírodou?

Za aké dve podmienky možno nastaviť problémy rozhodovania v matrixovej hre s prírodou?

Akú stratégiu je vhodné pre hráča zvoliť pri riešení problému teórie štatistických rozhodnutí pod rizikom?

Aké rozhodovacie kritériá možno použiť pri riešení problémov teórie štatistického rozhodovania v neistote?

Príklady riešenia problémov

1. Platobná matica udáva výšku zisku podniku pri predaji odlišné typy produktov (stĺpcov) v závislosti od stanoveného dopytu (riadkov). Je potrebné určiť optimálnu stratégiu podniku na výrobu produktov rôznych typov a zodpovedajúci maximálny (priemerný) príjem z ich predaja.

Označte danú maticu a uveďte premenné . Použijeme aj maticu (vektor) . Potom a t.j.

Inverzná matica sa vypočíta:

Hodnoty sa nachádzajú:

.

Vypočítavajú sa tieto pravdepodobnosti:

Priemerný príjem z predaja sa určuje:

.

2. Firma "Pharmatsevt" - výrobca liekov a biomedicínskych produktov v regióne. Je známe, že dopyt po niektorých liekoch vrcholí letné obdobie(lieky kardiovaskulárnej skupiny, analgetiká), pre ostatných - na jesenné a jarné obdobie (antiinfekčné, antitusické).

Náklady na 1 konv. Jednotky produkty na september až október boli: pre prvú skupinu (kardiovaskulárne lieky a analgetiká) - 20 rubľov; pre druhú skupinu (antiinfekčné, antitusické lieky) - 15 rubľov.

Podľa pozorovaní nad viacerými v posledných rokoch Marketingová služba spoločnosti zistila, že môže predať 3050 konvenčných jednotiek počas dvoch uvažovaných mesiacov v teplom počasí. Jednotky produktov prvej skupiny a 1100 konv. Jednotky výrobky druhej skupiny; v chladnom počasí - 1525 arb. Jednotky produktov prvej skupiny a 3690 konv. Jednotky druhá skupina.

V súvislosti s možnými zmenami počasia je úlohou určiť stratégiu spoločnosti pri výrobe produktov, ktorá poskytuje maximálny príjem z predaja pri predajnej cene 40 rubľov. za 1 konv. Jednotky výrobky prvej skupiny a 30 p. - druhá skupina.

RIEŠENIE. Firma má dve stratégie:

Počasie bude tento rok teplé;

Počasie bude chladné.

Ak spoločnosť prijme stratégiu a počasie je skutočne teplé (stratégia prírody), tak vyrobené produkty (3050 konvenčných jednotiek liekov prvej skupiny a 1100 konvenčných jednotiek druhej skupiny) sa plne zrealizujú a príjmy sa byť

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

V podmienkach chladného počasia (prírodná stratégia) sa lieky druhej skupiny budú predávať v plnom rozsahu a prvá skupina sa bude predávať iba v množstve 1525 konvenčných jednotiek. Jednotky a niektoré lieky zostanú nepredané. Príjem bude

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

Podobne, ak formulár prijme stratégiu a počasie je skutočne chladné, výnosy budú

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

V teplom počasí bude príjem

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

Ak vezmeme do úvahy firmu a počasie ako dvoch hráčov, dostaneme výplatnú maticu

,

Cena hry sa pohybuje v rozmedzí

Z výplatnej matice je možné vidieť, že za všetkých podmienok bude príjem firmy najmenej 16 500 rubľov, ale ak počasie sa zhodujú so zvolenou stratégiou, potom môže byť príjem spoločnosti 77 500 rubľov.

Poďme nájsť riešenie hry.

Pravdepodobnosť uplatnenia stratégie firmou označme ako , cez stratégiu a . Po grafickom vyriešení hry dostaneme , pričom cena hry r.

Optimálny plán na výrobu liekov bude

Preto je vhodné, aby firma v priebehu septembra a októbra vyrobila 2379 konvenčných jednotiek. Jednotky liekov prvej skupiny a 2239,6 konvenčných jednotiek. Jednotky lieky druhej skupiny, potom za každého počasia dostane príjem najmenej 46 986 rubľov.

V podmienkach neistoty, ak nie je možné pre spoločnosť použiť zmiešanú stratégiu (zmluvy s inými organizáciami), používame na určenie optimálnej stratégie spoločnosti nasledujúce kritériá:

Waldeho kritérium:

Hurwitzovo kritérium: pre jednoznačnosť akceptujeme, potom pre stratégiu spoločnosti

pre stratégiu

pre firmu je vhodné použiť stratégiu.

Savageovo kritérium. Maximálny prvok v prvom stĺpci je 77500, v druhom stĺpci je to 85850.

Prvky matice rizika sa nachádzajú z výrazu

,

kde , ,

Matica rizika má tvar

,

je vhodné použiť stratégiu alebo .

Preto je vhodné, aby firma uplatňovala stratégiu resp.

Upozorňujeme, že každé z posudzovaných kritérií nemožno považovať za úplne vyhovujúce konečná voľba rozhodnutia, ale ich spoločná analýza umožňuje jasnejšie prezentovať dôsledky prijímania určitých manažérskych rozhodnutí.

Pri známom rozdelení pravdepodobnosti rôznych stavov prírody je rozhodovacím kritériom maximálne matematické očakávanie výnosu.

Nech je pre uvažovaný problém známe, že pravdepodobnosti teplého a studeného počasia sú rovné a rovné 0,5, potom sa optimálna stratégia firmy určí takto:

Pre firmu je vhodné použiť stratégiu resp.

Úlohy na samostatnú prácu

1. Podnik môže vyrábať tri druhy produktov (A, B a C), pričom získava zisk, ktorý závisí od dopytu. Dopyt zase môže mať jeden zo štyroch stavov (I, II, III a IV). V nasledujúcej matici prvky charakterizujú zisk, ktorý podnik získa pri uvoľnení --tého produktu a --tý stav dopytu:

Popis bimatrixovej hry. Všetky hry, ktoré boli posudzované, patrili do triedy hry s nulovým súčtom. Množstvo konfliktných situácií, ktoré sa v priebehu konania vyvíjajú, sa však vyznačuje tým, že zisk jednej strany sa presne nerovná strate druhej. Herno-teoretické modely takéto situácie sú nekooperatívne hry s nenulovým súčtom. Takéto hry sa nazývajú bimatice, pretože úloha každej takejto hry je redukovaná na úlohu dvoch matíc a rovnakého tvaru: .

Proces bimatická hra spočíva v samostatnom výbere čísla hráčom I a čísla hráčom II, po ktorom hráč I dostane výplatu a hráč II dostane výplatu.

Vyvolajú sa čísla riadkov matíc a čisté stratégie hráča I a čísla stĺpcov týchto matíc sú čisté stratégie hráča II. Potom páry formy budú situácie v čistých stratégiách bimatická hra, a čísla a sú výplaty hráčov I a II v danej situácii . Podľa toho je rozdelenie pravdepodobnosti pri použití čistých stratégií hráča I a hráč II - zavoláme zmiešané stratégie. Potom dvojice formulárov predstavujú situácie bimatická hra v zmiešané stratégie a čísla a sú očakávané výplaty hráčov I. a II.

Rovnovážna situácia bimatrixovej hry v zmiešaných stratégiách zavoláme pár tak, že:

(8.2)

kde je matematické očakávanie výplaty hráča I;

Matematické očakávanie odmeny hráča II;

Optimálne zmiešané hráčska stratégia I;

Optimálne zmiešané hráčska stratégia II.

Úloha

Konštrukcia a riešenie bimaticovej hry. Predpokladajme, že protiponorková ponorka krajiny hľadá raketovú ponorku štátu, ktorá manévruje v presne vymedzenej časti bojovej hliadkovej oblasti. Ponorka ASW operuje vo zvyšku oblasti a hľadá ASW. Nechajte každý protiponorkový čln na detekciu nepriateľa použiť svoju hydroakustickú stanicu buď v aktívnom režime, ktorý sa pravidelne zapína, alebo iba v pasívnom režime, pričom vykonáva nepretržité vyhľadávanie.

Ako protiponorková ponorka, tak aj raketová ponorka s detekciou sonarových signálov sa môžu nepriateľovi vyhnúť. Frekvencia zapínania sonaru však umožňuje detekciu, no nespoľahlivú.

V takej konfliktná situácia jeden z hráčov je protiponorková ponorka a druhý je protiponorková ponorka. Je zrejmé, že raketová ponorka nemôže byť hráčom, pretože má iba jeden spôsob činnosti, ktorým je skryté manévrovanie a vyhýbanie sa detekcia sonarových signálov.

Príznačné tu je, že každý z hráčov sleduje iné, nie však opačné ciele. Účelom ponorky ASW je nájsť raketovú ponorku a účelom ponorky ASW je lokalizovať ASW. Preto na posúdenie dosiahnutia cieľa každým z hráčov, v závislosti od zvolených metód konania (stratégie), je potrebné mať dve kritériá efektívnosti, a teda dve výplatné funkcie. Potom bude modelom takejto konfliktnej situácie konečná hra s nenulovým súčtom, popísaná dvoma maticami rovnakého tvaru a , nazývaný bimatrix.

Vezmime si za kritérium účinnosti protiponorková ponorka (hráč I) pravdepodobnosť odhalenia raketovej ponorky a za kritérium účinnosti protiponorková ponorka (hráč II) - pravdepodobnosť odhalenia protiponorkovej ponorky . Potom bude dvojmaticová hra daná maticou (obrázok 9.a) a maticou (obrázok 9.b).

Kde - použitie aktívneho režimu;

Použitie pasívneho režimu.

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

jedna - jediná stratégia., potom na základe rozumne konajúceho protivníka by táto voľba mala byť určená princípom minimax. Pri dodržaní našej stratégie maximin si určite garantujeme odmenu rovnajúcu sa nižšej cene hry, a, za akékoľvek správanie súpera. Vynára sa prirodzená otázka: je možné zaručiť si priemernú návratnosť vyššiu ako v prípade, ak nepoužívate iba jednu „čistú“ stratégiu, ale náhodne striedate niekoľko stratégií?

Takéto kombinované stratégie, spočívajúce v aplikácii niekoľkých čistých stratégií striedajúcich sa 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 aplikovaním nielen čistých, ale aj zmiešaných stratégií je možné získať riešenie pre každú konečnú hru, t. j. pár (všeobecne zmiešaných) stratégií tak, že keď ich použijú obaja hráči, výplata sa bude rovnať cena hry a pri akomkoľvek jednostrannom odklone od optimálnej stratégie sa výplata môže zmeniť len smerom nevýhodným pre devianta.

Uvedené tvrdenie je obsahom takzvanej hlavnej vety teórie hier. Túto vetu prvýkrát dokázal von Neumann v roku 1928. Známe dôkazy vety sú pomerne zložité; preto uvádzame 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 hornou cenou hry:

V skutočnosti existuje maximálna zaručená odmena, ktorú si môžeme zabezpečiť iba pomocou vlastných č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, v žiadnom prípade nezhoršujeme naše schopnosti; v dôsledku toho

Podobne to ukazujeme aj vzhľadom na schopnosti súpera

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 spočíva v aplikácii stratégií AL, s frekvenciami a túto stratégiu označíme

Podobne bude zmiešaná stratégia protivníka označená:

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é z nich. Stratégie zahrnuté v optimálnej zmiešanej stratégii hráča budeme nazývať jeho „užitočné“ stratégie.

Ukazuje sa, že riešenie hry má ešte jednu pozoruhodnú vlastnosť: ak jeden z hráčov dodrží 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. len neprekračuje 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. Pre konkrétnosť budeme predpokladať, že optimálna zmiešaná stratégia pozostáva zo zmesi troch

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

a Uvádza sa, že ak sa budeme držať stratégie S, tak súper môže aplikovať stratégie v akomkoľvek pomere a výplata zostane nezmenená a bude sa stále rovnať cene hry.

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, môžeme implementovať algoritmus na nájdenie optimálneho riešenia nie celkom 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 antagonistickej hry. Pre každého hráča, spolu s daným súborom pre neho možných stratégií, 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 pravdepodobností (relatívnych frekvencií) výberu daných stratégií hráča A takto:
P = (p 1 , p 2 ,..., p m),
kde pi ≥ 0, p 1 + p 2 +…+ p m = 1. Hodnota p i sa nazýva pravdepodobnosť (relatívna frekvencia) uplatnenia stratégie A i.

Podobne pre hráča B sa zavedie neznámy vektor pravdepodobností (relatívne frekvencie), ktorý má tvar:
Q = (q 1 , q 2 ,..., q n),
kde q j ≥ 0, q 1 + q 2 +…+ q n = 1. Veličina q j sa nazýva pravdepodobnosť (relatívna frekvencia) uplatnenia 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 konečných antagonistických hier 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 nie dobre definovaná 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) uplatnenia 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) znamená, že 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ého zisku 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šeobecnom prípade takéto problémy úspešne rieši táto kalkulačka.

Príklad.

1. Skontrolujte, či má výplatná 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 zvolil 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 hra b = min(b j) = 7. To naznačuje absenciu sedlového bodu, keďže a ≠ b, potom je cena hry v rozmedzí 2 ≤ y ≤ 7. Riešenie hry nájdeme v zmiešaných stratégiách. Vysvetľuje to skutočnosť, že hráči nemôžu súperovi oznámiť svoje čisté stratégie: mali by svoje činy skryť. Hru je možné vyriešiť tak, že necháte hráčov, aby si svoje stratégie vybrali náhodne (zmiešali čisté stratégie).

2. Skontrolujte maticu výplat pre dominantné riadky a dominantné stĺpce.
V matici výplat nie sú žiadne dominantné riadky a dominantné stĺpce.

3. Hľadanie riešenia hry v zmiešaných stratégiách.
Zapíšme si sústavu rovníc.
Pre hráča I
4p1 +7p2 +2p3 = y
7p1 +3p2 +p3 = y
2p 1 +2p 2 +8p 3 = y
p1 + p2 + p3 = 1

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

Riešením týchto systémov Gaussovou metódou zistíme:

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

Optimálna zmiešaná stratégia hráča I: P = (29/68; 4/17; 23/68)
q 1 = 6 / 17 (pravdepodobnosť uplatnenia 1. stratégie).
q 2 = 9/34 (pravdepodobnosť uplatnenia 2. stratégie).
q 3 = 13/34 (pravdepodobnosť uplatnenia 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