Antagonistické hry s kontinuálnymi stratégiami. Riešenie maticových antagonistických hier Riešenie antagonistických hier online

Nazýva sa hra s nulovým súčtom pre dve osoby, v ktorej má každý z nich obmedzený súbor stratégií. Pravidlá maticovej hry určuje matica výplat, ktorej prvkami sú výplaty prvého hráča, ktoré sú zároveň prehrami druhého hráča.

Maticová hra je antagonistická hra. Prvý hráč dostane maximálnu garantovanú (nezávislú od správania druhého hráča) výplatu rovnajúcu sa cene hry, podobne aj druhý hráč dosiahne minimálnu garantovanú stratu.

Pod stratégie sa chápe ako súbor pravidiel (princípov), ktoré určujú výber variantu akcií pre každý osobný ťah hráča v závislosti od aktuálnej situácie.

Teraz o všetkom v poriadku a podrobne.

Výplatná matica, čisté stratégie, cena hry

AT maticová hra sú určené jeho pravidlá výplatná matica .

Predstavte si hru, v ktorej sú dvaja účastníci: prvý hráč a druhý hráč. Nech má prvý hráč mčisté stratégie, ktoré má k dispozícii druhý hráč - nčisté stratégie. Keďže sa uvažuje o hre, je prirodzené, že v tejto hre sú výhry a prehry.

AT platobná matica prvky sú čísla vyjadrujúce zisky a straty hráčov. Výhry a prehry môžu byť vyjadrené v bodoch, peniazoch alebo iných jednotkách.

Vytvorme výplatnú maticu:

Ak sa prvý hráč rozhodne i-tá čistá stratégia a druhý hráč j- čistá stratégia, potom je odmena prvého hráča aij jednotiek a strata druhého hráča je tiež aij Jednotky.

Pretože aij + (- a ij) = 0, potom je opísaná hra maticová hra s nulovým súčtom.

Najjednoduchším príkladom maticovej hry je hádzanie mincou. Pravidlá hry sú nasledovné. Prvý a druhý hráč si hodí mincou a výsledkom sú hlavy alebo chvosty. Ak sú súčasne hodené hlavy a hlavy alebo chvosty alebo chvosty, potom prvý hráč vyhrá jednu jednotku av ostatných prípadoch stratí jednu jednotku (druhý hráč vyhrá jednu jednotku). Druhý hráč má k dispozícii dve rovnaké stratégie. Zodpovedajúca výplatná matica by bola:

Úlohou teórie hier je určiť voľbu stratégie prvého hráča, ktorá by mu zaručila maximálny priemerný zisk, ako aj voľbu stratégie druhého hráča, ktorá by mu zaručila maximálnu priemernú stratu.

Ako sa vyberá stratégia v maticovej hre?

Pozrime sa ešte raz na výplatnú maticu:

Najprv určíme výplatu prvého hráča, ak použije ičistá stratégia. Ak prvý hráč použije i-tú čistú stratégiu, potom je logické predpokladať, že druhý hráč použije takú čistú stratégiu, vďaka ktorej by bola výplata prvého hráča minimálna. Prvý hráč zase použije takú čistú stratégiu, ktorá by mu zabezpečila maximálnu výplatu. Na základe týchto podmienok výplata prvého hráča, ktorú označujeme ako v1 , volal maximalne vyhra alebo nižšia cena hry .

O pre tieto hodnoty by mal prvý hráč postupovať nasledovne. Z každého riadku vypíšte hodnotu minimálneho prvku a vyberte z neho maximum. Výplata prvého hráča bude teda maximum z minima. Odtiaľ pochádza názov - maximin win. Číslo riadku tohto prvku bude číslom čistej stratégie zvolenej prvým hráčom.

Teraz určme stratu druhého hráča, ak použije j-tá stratégia. V tomto prípade prvý hráč používa vlastnú čistú stratégiu, pri ktorej by strata druhého hráča bola maximálna. Druhý hráč musí zvoliť takú čistú stratégiu, pri ktorej by bola jeho strata minimálna. Strata druhého hráča, ktorú označujeme ako v2 , volal minimax strata alebo najvyššia cena hry .

O riešenie problémov o cene hry a určenie stratégie na určenie týchto hodnôt pre druhého hráča postupujte nasledovne. Z každého stĺpca vypíšte hodnotu maximálneho prvku a vyberte z neho minimum. Strata druhého hráča bude teda minimom z maxima. Odtiaľ pochádza názov – minimax gain. Číslo stĺpca tohto prvku bude číslom čistej stratégie zvolenej druhým hráčom. Ak druhý hráč použije „minimax“, tak bez ohľadu na voľbu stratégie prvým hráčom najviac prehrá v2 Jednotky.

Príklad 1

.

Najväčší z najmenších prvkov radov je 2, to je nižšia cena hry, tomu zodpovedá prvý riadok, preto je stratégia maximin prvého hráča prvá. Najmenší z najväčších prvkov stĺpcov je 5, to je horná cena hry, tomu zodpovedá druhý stĺpec, preto je minimaxová stratégia druhého hráča druhá.

Teraz, keď sme sa naučili, ako nájsť dolnú a hornú cenu hry, stratégie maximin a minimax, je čas naučiť sa tieto pojmy formálne označovať.

Takže zaručená výplata prvého hráča je:

Prvý hráč si musí zvoliť čistú stratégiu, ktorá by mu zabezpečila maximum z minimálnych výplat. Tento zisk (maximum) je označený takto:

.

Prvý hráč používa svoju čistú stratégiu tak, aby strata druhého hráča bola maximálna. Táto strata je definovaná takto:

Druhý hráč musí zvoliť svoju čistú stratégiu tak, aby jeho strata bola minimálna. Táto strata (minimax) sa označuje takto:

.

Ďalší príklad z rovnakej série.

Príklad 2 Daná maticová hra s výplatnou maticou

.

Určite stratégiu maxima prvého hráča, stratégiu minimaxu druhého hráča, dolnú a hornú cenu hry.

Riešenie. Napravo od výplatnej matice zapíšeme najmenšie prvky do jej riadkov a označíme ich maximum a zospodu matice - najväčšie prvky v stĺpcoch a vyberieme minimum z nich:

Najväčší z najmenších prvkov radov je 3, to je nižšia cena hry, tomu zodpovedá druhý riadok, preto je maximálna stratégia prvého hráča druhá. Najmenší z najväčších prvkov stĺpcov je 5, to je horná cena hry, tomu zodpovedá prvý stĺpec, preto je minimax stratégia druhého hráča prvá.

Sedlový bod v maticových hrách

Ak je horná a dolná cena hry rovnaká, potom sa maticová hra považuje za hru so sedlom. Platí to aj naopak: ak má maticová hra sedlový bod, horná a dolná cena maticovej hry sú rovnaké. Príslušný prvok je najmenší v riadku a najväčší v stĺpci a rovná sa cene hry.

Ak teda , potom je optimálna čistá stratégia prvého hráča a optimálna čistá stratégia druhého hráča. To znamená, že rovnaké nižšie a vyššie ceny hry sa dosahujú na rovnakom páre stratégií.

V tomto prípade maticová hra má riešenie v čistých stratégiách .

Príklad 3 Daná maticová hra s výplatnou maticou

.

Riešenie. Napravo od výplatnej matice zapíšeme najmenšie prvky do jej riadkov a označíme ich maximum a zospodu matice - najväčšie prvky v stĺpcoch a vyberieme minimum z nich:

Nižšia cena hry je rovnaká ako horná cena hry. Cena hry je teda 5. To znamená . Hodnota hry sa rovná hodnote sedlového bodu. Maximinová stratégia prvého hráča je druhá čistá stratégia a minimax stratégia druhého hráča je treťou čistou stratégiou. Táto maticová hra má riešenie v čistých stratégiách.

Vyriešte problém maticovej hry sami a potom uvidíte riešenie

Príklad 4 Daná maticová hra s výplatnou maticou

.

Nájdite spodnú a hornú cenu hry. Má táto maticová hra sedlovú pointu?

Matrixové hry s optimálnou zmiešanou stratégiou

Vo väčšine prípadov maticová hra nemá sedlový bod, takže zodpovedajúca maticová hra nemá žiadne čisté strategické riešenia.

Ale má riešenie v optimálnych zmiešaných stratégiách. Na ich nájdenie treba predpokladať, že sa hra opakuje toľkokrát, aby sa na základe skúseností dalo odhadnúť, ktorá stratégia je vhodnejšia. Preto je rozhodnutie spojené s pojmom pravdepodobnosť a priemer (očakávania). V konečnom riešení je tak analóg sedlového bodu (teda rovnosť spodnej a hornej ceny hry), ako aj analóg im zodpovedajúcich stratégií.

Takže, aby prvý hráč získal maximálny priemerný zisk a druhý hráč mal minimálnu priemernú stratu, mali by sa s určitou pravdepodobnosťou používať čisté stratégie.

Ak prvý hráč používa čisté stratégie s pravdepodobnosťou , potom vektor sa nazýva zmiešaná stratégia prvého hráča. Inými slovami, je to „zmes“ čistých stratégií. Súčet týchto pravdepodobností sa rovná jednej:

.

Ak druhý hráč používa čisté stratégie s pravdepodobnosťou , potom vektor sa nazýva zmiešaná stratégia druhého hráča. Súčet týchto pravdepodobností sa rovná jednej:

.

Ak prvý hráč používa zmiešanú stratégiu p, a druhý hráč - zmiešaná stratégia q, potom to dáva zmysel očakávaná hodnota prvý hráč vyhráva (druhý hráč prehráva). Aby ste to našli, musíte vynásobiť vektor zmiešanej stratégie prvého hráča (čo bude jednoriadková matica), maticu výplaty a vektor zmiešanej stratégie druhého hráča (čo bude matica s jedným stĺpcom):

.

Príklad 5 Daná maticová hra s výplatnou maticou

.

Určte matematické očakávanie zisku prvého hráča (prehry druhého hráča), ak zmiešaná stratégia prvého hráča je , a zmiešaná stratégia druhého hráča je .

Riešenie. Podľa vzorca matematického očakávania zisku prvého hráča (straty druhého hráča) sa rovná súčinu vektora zmiešanej stratégie prvého hráča, výplatnej matice a vektora zmiešanej stratégie druhého hráča:

Prvý hráč sa nazýva taká zmiešaná stratégia, ktorá by mu pri dostatočnom počte opakovaní zabezpečila maximálnu priemernú výplatu.

Optimálna zmiešaná stratégia Druhý hráč sa nazýva taká zmiešaná stratégia, ktorá by mu pri dostatočnom počte opakovaní zabezpečila minimálnu priemernú stratu.

Analogicky so zápisom maximínu a minimaxu v prípade čistých stratégií sa optimálne zmiešané stratégie označujú nasledovne (a sú spojené s matematickým očakávaním, teda priemerom zisku prvého hráča a straty druhého hráča):

,

.

V tomto prípade pre funkciu E je tam sedlový bod , čo znamená rovnosť.

Aby sa našli optimálne zmiešané stratégie a sedlový bod, t.j. riešiť maticovú hru v zmiešaných stratégiách , musíte zredukovať maticovú hru na problém lineárneho programovania, teda na problém optimalizácie, a vyriešiť zodpovedajúci problém lineárneho programovania.

Redukcia maticovej hry na problém lineárneho programovania

Ak chcete vyriešiť maticovú hru v zmiešaných stratégiách, musíte zostaviť priamku problém lineárneho programovania a svoju dvojitú úlohu. V duálnom probléme sa transponuje rozšírená matica, ktorá ukladá koeficienty premenných v systéme obmedzení, konštantné členy a koeficienty premenných v cieľovej funkcii. V tomto prípade je minimum cieľovej funkcie pôvodného problému spojené s maximom v duálnom probléme.

Cieľová funkcia v úlohe priameho lineárneho programovania:

.

Systém obmedzení v priamom probléme lineárneho programovania:

Cieľová funkcia v duálnom probléme:

.

Systém obmedzení v duálnom probléme:

Označte optimálny plán úlohy priameho lineárneho programovania

,

a optimálny plán duálneho problému je označený

Lineárne formy pre zodpovedajúce optimálne návrhy budú označené a,

a musíte ich nájsť ako súčet zodpovedajúcich súradníc optimálnych plánov.

V súlade s definíciami v predchádzajúcej časti a súradnicami optimálnych plánov platia nasledujúce zmiešané stratégie prvého a druhého hráča:

.

Matematici to dokázali cena hry je vyjadrená v lineárnych formách optimálnych plánov takto:

,

to znamená, že ide o prevrátenú hodnotu súčtu súradníc optimálnych plánov.

My, praktizujúci, môžeme použiť tento vzorec iba na riešenie maticových hier v zmiešaných stratégiách. Páči sa mi to vzorce na hľadanie optimálnych zmiešaných stratégií prvý a druhý hráč:

v ktorých sú druhými faktormi vektory. Optimálne zmiešané stratégie sú tiež vektory, ako sme už definovali v predchádzajúcom odseku. Preto vynásobením čísla (ceny hry) vektorom (so súradnicami optimálnych plánov) dostaneme aj vektor.

Príklad 6 Daná maticová hra s výplatnou maticou

.

Nájdite cenu hry V a optimálne zmiešané stratégie a .

Riešenie. Zostavíme problém lineárneho programovania zodpovedajúci tejto maticovej hre:

Dostaneme riešenie priameho problému:

.

Lineárny tvar optimálnych plánov nájdeme ako súčet nájdených súradníc.

Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár

Študenti, postgraduálni študenti, mladí vedci, ktorí pri štúdiu a práci využívajú vedomostnú základňu, vám budú veľmi vďační.

Úvod

1. Teoretická časť

1.3 Poradie hry 2v2

1.4 Algebraická metóda

1.5 Grafická metóda

1.6 Hry 2xn alebo mx2

1.7 Riešenie hier maticovou metódou

2. Praktická časť

2.2 2xn a mx2 hry

2.3 Maticová metóda

2.4 Hnedá metóda

Analýza výsledkov

Úvod

Antagonistická hra je hra s nulovým súčtom. Antagonistická hra je nekooperatívna hra, v ktorej sa zúčastňujú dvaja hráči, ktorých výnosy sú opačné.

Formálne môže byť antagonistická hra reprezentovaná trojkou , kde X a Y sú množiny stratégií prvého a druhého hráča, F je výplatná funkcia prvého hráča, ktorá spája každú dvojicu stratégií (x, y), kde je reálne číslo zodpovedajúce užitočnosti prvého hráča, ktorý si túto situáciu uvedomil.

Keďže záujmy hráčov sú opačné, funkcia F zároveň predstavuje stratu druhého hráča.

Historicky sú antagonistické hry prvou triedou matematických modelov teórie hier, ktoré boli použité na opis hazardných hier. Predpokladá sa, že vďaka tomuto predmetu výskumu dostala teória hier svoje meno. V súčasnosti sa antagonistické hry považujú za súčasť širšej triedy nekooperatívnych hier.

1. Teoretická časť

1.1 Základné definície a ustanovenia hry

Hra sa vyznačuje systémom pravidiel, ktoré určujú počet účastníkov hry, ich možné akcie a rozdelenie výhier v závislosti od ich správania a výsledkov. Za hráča sa považuje jeden účastník alebo skupina účastníkov hry, ktorí majú pre nich nejaké spoločné záujmy, ktoré sa nezhodujú so záujmami iných skupín. Preto nie každý účastník je považovaný za hráča.

Pravidlá alebo podmienky hry určujú možné správanie, voľby a pohyby hráčov v ktorejkoľvek fáze vývoja hry. Vybrať si pre hráča znamená zastaviť sa pri jednej z jeho možností správania. Hráč potom urobí túto voľbu pomocou ťahov. Urobiť ťah znamená v určitej fáze hry urobiť celý výber alebo jeho časť naraz, v závislosti od možností, ktoré poskytujú pravidlá hry. Každý hráč v určitej fáze hry vykoná ťah podľa vykonanej voľby. Druhý hráč, ktorý vie alebo nevie o voľbe prvého hráča, tiež urobí ťah. Každý z hráčov sa snaží brať do úvahy informácie o minulom vývoji hry, ak takúto možnosť pravidlá hry pripúšťajú.

Súbor pravidiel, ktoré hráčovi jednoznačne hovoria, akú voľbu by mal urobiť pri každom ťahu v závislosti od situácie, ktorá sa vyvinula v dôsledku hry, sa nazýva stratégia hráča. Stratégia v teórii hier znamená určitý ucelený plán činnosti hráča, ktorý ukazuje, ako by mal konať vo všetkých možných prípadoch vývoja hry. Stratégia znamená súhrn všetkých indikácií pre akýkoľvek stav informácií dostupných hráčovi v ktorejkoľvek fáze vývoja hry. Už z toho je jasné, že stratégie môžu byť dobré aj zlé, úspešné aj neúspešné atď.

Hra s nulovým súčtom bude, keď súčet výplat všetkých hráčov v každej z jej hier je nulový, t. j. v hre s nulovým súčtom sa celkový kapitál všetkých hráčov nemení, ale je prerozdelený medzi hráčov v závislosti od na výsledných výsledkoch. Mnohé ekonomické a vojenské situácie možno teda považovať za hry s nulovým súčtom.

Najmä hra dvoch hráčov s nulovým súčtom sa nazýva antagonistická, pretože ciele hráčov v nej sú priamo opačné: zisk jedného hráča nastáva iba na úkor straty druhého.

1.1.1 Definícia, príklady a riešenia maticových hier v čistých stratégiách

Maticovú hru pre dvoch hráčov s nulovým súčtom možno považovať za nasledujúcu abstraktnú hru pre dvoch hráčov.

Prvý hráč má m stratégií i =1, 2,…, m, druhý hráč má n stratégií j = 1, 2,…, n. Každej dvojici stratégií (i, j) je priradené číslo a ij , ktoré vyjadruje výplata prvého hráča v prospech druhého hráča, ak prvý hráč použije svoju i-ta stratégia, a druhá - jej j-tá stratégia.

Každý z hráčov urobí jeden ťah: prvý si zvolí svoju i-tu stratégiu (i = 1, 2, ..., m), druhý --váš j-tý stratégia (j = 1, 2,…, n), po ktorej prvý hráč dostane odmenu a ij na úkor druhého hráča (ak a ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Každá stratégia hráča i = 1, 2,…, t; j = 1, 2,…, n sa často nazýva čistá stratégia.

Maticová hra s nulovým súčtom dvoch hráčov sa bude označovať jednoducho ako maticová hra. Je zrejmé, že matrixová hra patrí k antagonistickým hrám. Z jej definície vyplýva, že na definovanie maticovej hry stačí špecifikovať maticu A = (a ij) rádovo m výplat prvého hráča.

Vzhľadom na výplatnú maticu

potom sa vykonávanie každej hry maticovej hry s maticou A zredukuje na výber prvého hráča i-tý riadok, a tým, že druhý hráč v j-tom stĺpci a prvý hráč (na úkor druhého) dostane výplatu nachádzajúcu sa v matici A na priesečníku i-tého riadku a j-tého stĺpca.

Na formalizáciu skutočnej konfliktnej situácie vo forme maticovej hry je potrebné identifikovať a prečíslovať čisté stratégie každého hráča a zostaviť výplatnú maticu.

Ďalším krokom je určenie optimálnych stratégií a výplat hráčov.

Hlavnou vecou pri štúdiu hier je koncept optimálnych stratégií pre hráčov. Tento koncept má intuitívne nasledujúci význam: stratégia hráča je optimálna, ak mu aplikácia tejto stratégie poskytuje najväčšiu garantovanú odmenu pre všetky možné stratégie druhého hráča. Na základe týchto pozícií prvý hráč skúma maticu A svojich výplat podľa vzorca (1.1) takto: pre každú hodnotu i (i = 1, 2, ..., m) sa určí minimálna hodnota výplaty v závislosti na stratégiách používaných druhým hráčom

(i = 1, 2,..., m) (1,2)

t.j. určí sa minimálna odmena pre prvého hráča za predpokladu, že uplatní svoju i -tu čistú stratégiu, potom sa z týchto minimálnych odmien nájde taká stratégia i=i 0, pre ktorú bude táto minimálna odmena maximálna, t.j.

Definícia. Číslo 6 určené vzorcom (1.3) sa nazýva nižšie čisté náklady na hru a ukazuje, akú minimálnu výhru si môže prvý hráč zaručiť použitím svojich čistých stratégií na všetky možné akcie druhého hráča.

Druhý hráč by sa svojím optimálnym správaním mal snažiť, pokiaľ je to možné, minimalizovať výplatu prvého hráča na úkor jeho stratégií. Preto pre druhého hráča nájdeme

t.j. je určená maximálna výhra prvého hráča za predpokladu, že druhý hráč uplatní svoju j-tý čistý stratégiu, potom druhý hráč nájde svoju vlastnú j = j 1 stratégiu, za ktorú prvý hráč dostane minimálnu odmenu, t.j.

Definícia. Číslo β určené vzorcom (1.5) sa nazýva čistá horná cena hry a ukazuje, aký maximálny zisk si môže prvý hráč zaručiť vďaka svojim stratégiám. Inými slovami, použitím svojich čistých stratégií si prvý hráč môže zabezpečiť výplatu aspoň b a druhý hráč môže použitím svojich čistých stratégií zabrániť prvému hráčovi vyhrať viac ako c.

Definícia. Ak sa v hre s maticou A spodná a horná čistá cena hry zhoduje, t. j. b = c, potom sa hovorí, že táto hra má sedlový bod v čistých stratégiách a čistú cenu hry:

n = b = c (1,6)

Sedlový bod je dvojica čistých stratégií () prvého a druhého hráča, podľa ktorých sa dosiahne rovnosť

Pojem sedlového bodu má nasledujúci význam: ak jeden z hráčov dodrží stratégiu zodpovedajúcu sedlovému bodu, potom druhý hráč nemôže urobiť lepšie, ako dodržať stratégiu zodpovedajúcu sedlovému bodu. Majúc na pamäti, že najlepšie správanie hráča by nemalo viesť k zníženiu jeho výplaty a najhoršie správanie môže viesť k zníženiu jeho výplaty, tieto podmienky možno zapísať matematicky vo forme nasledujúcich vzťahov:

kde i, j sú ľubovoľné čisté stratégie prvého a druhého hráča; (i 0 , j 0) -- stratégie tvoriace sedlový bod. Nižšie ukážeme, že definícia sedlového bodu je ekvivalentná podmienkam (1.8).

Sedlový prvok je teda na základe (1.8) minimom v i 0 -tom riadku a maximom v j 0 -tom stĺpci matice A. Nájdenie sedlového bodu matice A je jednoduché: v matici A postupne v každom riadku nájdite minimálny prvok a skontrolujte, či je tento prvok maximálny v jeho stĺpci. Ak je taký, potom ide o sedlový prvok a jemu zodpovedajúca dvojica stratégií tvorí sedlový bod. Dvojica čistých stratégií (i 0 , j 0) prvého a druhého hráča, tvoriacich sedlový bod a sedlový prvok, sa nazýva riešenie hry.

Čisté stratégie i 0 a j 0 tvoriace sedlový bod sa nazývajú optimálne čisté stratégie prvého a druhého hráča.

Veta 1. Nech f (x, y) je reálna funkcia dvoch premenných x A a y B a existuje

potom b = c.

Dôkaz. Z definície minima a maxima vyplýva, že

Pretože x je ľubovoľné na ľavej strane (1.11), potom

Na pravej strane nerovnosti (1.12) je y ľubovoľné, tzn

Q.E.D.

Najmä matica () je špeciálny prípad funkcie f (x, y), t. j. ak dáme x = i, y = j, = f (x, y), potom z vety 1 dostaneme, že nižšia čistá cena nepresiahne hornú čistú hodnotu hry v maticovej hre.

Definícia. Nech f (x, y) je reálna funkcia dvoch premenných x A a y B. Bod (x 0, y 0) sa nazýva sedlový bod pre funkciu f (x, y), ak platia nasledujúce nerovnosti:

f (x, y 0) f (x 0, y 0) f (x 0, y) (1,14)

pre ľubovoľné x A a y B.

1.2 Optimálne zmiešané stratégie a ich vlastnosti

Štúdium maticovej hry začína nájdením jej sedla v čistých stratégiách. Ak má maticová hra sedlový bod v čistých stratégiách, nájdenie tohto bodu ukončí štúdium hry. Ak v maticovej hre nie je sedlový bod v čistých stratégiách, potom je možné nájsť dolnú a hornú čistú cenu tejto hry, čo naznačuje, že prvý hráč by nemal dúfať vo vyššiu odmenu, ako je horná cena hry, a si môžete byť istí, že dostanete odmenu nie nižšiu, ako je nižšia cena hry. Takéto odporúčania týkajúce sa správania hráčov v maticovej hre bez sedlového bodu v čistých stratégiách nemôžu uspokojiť výskumníkov a odborníkov z praxe. Zlepšenie riešenia maticových hier treba hľadať vo využívaní utajenia aplikácie čistých stratégií a možnosti opakovaného opakovania hier formou večierkov. Takže sa hrá napríklad séria hier šach, dáma, futbal a zakaždým, keď hráči aplikujú svoje stratégie tak, že ich súperi si neuvedomujú ich obsah, a pritom dosahujú určité odmeny v priemere o hranie celej série hier. Tieto výnosy sú v priemere vyššie ako nižšia cena hry a nižšie ako horná cena hry. Čím väčšia je táto priemerná hodnota, tým lepšia stratégia aplikovaný prehrávačom. Preto vznikla myšlienka aplikovať čisté stratégie náhodne, s určitou pravdepodobnosťou. To plne zabezpečuje utajenie ich použitia. Každý hráč môže zmeniť pravdepodobnosti použitia svojich čistých stratégií tak, aby maximalizoval svoj priemerný zisk a zároveň získal optimálne stratégie. Táto myšlienka viedla ku konceptu zmiešanej stratégie.

Definícia. Zmiešaná stratégia hráča je kompletný súbor pravdepodobností použitia jeho čistých stratégií.

Ak má teda prvý hráč m čistých stratégií 1, 2, … i, … m, potom jeho zmiešaná stratégia x je množina čísel x = (x 1 , x 2 , ..., x i ,…, x t ), ktoré spĺňajú vzťahy

x i 0 (i = 1, 2, ... , m), = 1. (1,15)

Podobne pre druhého hráča, ktorý má n čistých stratégií, je zmiešaná stratégia y množinou čísel y = (y 1 ,…, y j, … y n) spĺňajúcich vzťahy

y j 0 (j = 1, 2, ... , n), = 1. (1,16)

Keďže zakaždým, keď hráč použije jednu čistú stratégiu, zabráni použitiu inej, čisté stratégie sú nezlučiteľné udalosti. Navyše sú to jediné možné udalosti.

Je zrejmé, že čistá stratégia je špeciálnym prípadom zmiešanej stratégie. Vskutku, ak v zmiešanej stratégii nejakú i-tá sieť stratégia sa použije s pravdepodobnosťou jedna, potom sa všetky ostatné čisté stratégie neaplikujú. A táto i-tá čistá stratégia je špeciálnym prípadom zmiešanej stratégie. Aby sa zachovalo tajomstvo, každý hráč uplatňuje svoje vlastné stratégie bez ohľadu na výber druhého hráča.

Definícia. Priemerná výplata prvého hráča v maticovej hre s maticou A je vyjadrená ako matematické očakávanie jeho výplat

E (A, x, y) = (1,20)

Je zrejmé, že priemerný zisk prvého hráča je funkciou dvoch súborov premenných x a y. Prvý hráč sa snaží maximalizovať svoj priemerný výnos E (A, x, y) zmenou svojich zmiešaných stratégií x a druhý hráč sa prostredníctvom svojich zmiešaných stratégií snaží dosiahnuť, aby E (A, x, y) bolo minimálne, t.j. na vyriešenie hry je potrebné nájsť také x, y, pri ktorých sa dosiahne horná cena hry.

1.3 Hra Objednávka 22

Maticová hra poradia 22 je daná nasledujúcou výplatnou maticou pre prvého hráča:

Riešenie tejto hry by malo začať hľadaním sedla v čistých stratégiách. Na tento účel nájdite minimálny prvok v prvom riadku a skontrolujte, či je v jeho stĺpci maximálny. Ak sa takýto prvok nenájde, druhý riadok sa skontroluje rovnakým spôsobom. Ak sa takýto prvok nachádza v druhom riadku, potom ide o sedlový prvok.

Nájdením sedlového prvku, ak existuje, sa proces hľadania jeho riešenia končí, keďže v tomto prípade sa zisťuje cena hry - sedlový prvok a sedlový bod, teda dvojica čistých stratégií pre prvý resp. druhých hráčov, čo predstavuje optimálne čisté stratégie. Ak v čistých stratégiách neexistuje sedlový bod, potom je potrebné nájsť sedlový bod v zmiešaných stratégiách, ktorý nevyhnutne existuje podľa hlavnej vety maticových hier.

Označme x=(x 1 ,x 2), y=(y 1 ,y 2) zmiešané stratégie prvého a druhého hráča. Pripomeňme, že x 1 znamená pravdepodobnosť, že prvý hráč použije svoju prvú stratégiu, a x 2 \u003d 1 - x 1 je pravdepodobnosť použitia druhej stratégie. Podobne pre druhého hráča: 1 - pravdepodobnosť použitia prvej stratégie, y 2 = 1 - 1 - pravdepodobnosť použitia druhej stratégie.

Podľa následku vety pre optimálnosť zmiešaných stratégií x a y je potrebné a postačujúce, aby pre nezáporné x 1 , x 2 , y 1 , y 2 platili nasledujúce vzťahy:

Teraz ukážeme, že ak maticová hra nemá sedlový bod v čistých stratégiách, potom sa tieto nerovnosti musia zmeniť na rovnosti:

Naozaj. Nech hra nemá sedlový bod v čistých stratégiách, potom optimálne hodnoty zmiešaných stratégií uspokoja nerovnosti

0<<1, 0<< 1,

0< <1, 01. (1.25)

Predpokladajme, že obe nerovnosti z (1,22) sú prísne

potom podľa vety y 1 = y 2 = 0, čo je v rozpore s podmienkami (1.25).

Podobne je dokázané, že obe nerovnosti v (1.23) nemôžu byť striktnými nerovnosťami.

Predpokladajme teraz, že jedna z nerovností (1,22) môže byť striktná, napr.

To znamená, že podľa vety y 1 = 0, y 2 =1. Preto z (1.23) získame

Ak sú obe nerovnosti (1.24) prísne, potom podľa vety x1 = x2 = 0, čo je v rozpore (1.25). Ale ak je 12 a 22 , potom jedna z nerovností (1,27) je prísna a druhá je rovnosť. Navyše, rovnosť bude platiť pre väčší prvok z 12 a 22, t.j. jedna nerovnosť z (1.27) musí byť prísna. Napríklad 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Ukazuje sa teda, že ak maticová hra nemá sedlový bod v čistých stratégiách, potom sa nerovnosti (1.22) zmenia na rovnosti pre optimálne stratégie prvého hráča. Podobné argumenty o nerovnostiach (1.23) povedú k tomu, že v tomto prípade musia byť nerovnosti (1.23) rovnosťami.

Ak teda maticová hra poradia 22 nemá sedlový bod, optimálne zmiešané stratégie hráčov a cenu hry možno určiť riešením sústavy rovníc (1.24). Tiež sa zistilo, že ak v maticovej hre 2x2 má jeden z hráčov optimálnu čistú stratégiu, potom má aj druhý hráč optimálnu čistú stratégiu.

Ak teda maticová hra nemá sedlový bod v čistých stratégiách, potom musí mať riešenie v zmiešaných stratégiách, ktoré sú určené z rovníc (1.24). Systémové riešenie (1.25)

1.4 Algebraická metóda

Existujú dva prípady riešenia problémov algebraickou metódou:

1. matrica má sedlový hrot;

2. matrica nemá sedlový hrot.

V prvom prípade je riešením dvojica stratégií, ktoré tvoria sedlovú pointu hry. Zoberme si druhý prípad. Riešenia tu treba hľadať v zmiešaných stratégiách:

Nájdite stratégie a Keď prvý hráč použije svoju optimálnu stratégiu, druhý hráč môže použiť napríklad dve takéto čisté stratégie

Navyše, na základe vlastnosti, ak jeden z hráčov používa optimálnu zmiešanú stratégiu a druhý - akúkoľvek čistú, zahrnutú v jeho optimálnej zmiešanej stratégii s nenulovou pravdepodobnosťou, potom matematické očakávania výplaty vždy zostávajú nezmenené a rovná cene hry, t.j.

Výplata sa musí v každom z týchto prípadov rovnať hodnote hry V. V tomto prípade platia nasledujúce vzťahy:

Pre optimálnu stratégiu druhého hráča možno zostaviť aj systém rovníc podobný (2.5), (2.6):

Berúc do úvahy podmienky normalizácie:

Riešime rovnicu (1,37) - (1,41) spolu vzhľadom na neznáme a nie všetky naraz, ale tri naraz: samostatne (1,36), (1,38), (1,40) a (1,37), (1,39) (1,41). Výsledkom riešenia je:

1.5 Grafická metóda

Približné riešenie hry 22 sa dá celkom jednoducho získať pomocou grafickej metódy. Jeho podstata je nasledovná:

Obrázok 1.1 - nájdenie úseku jednotkovej dĺžky

Vyberte časť jednotky dĺžky na osi x. Ľavý koniec bude zobrazovať prvú stratégiu prvého hráča a pravý koniec druhého. Všetky medziľahlé body zodpovedajú zmiešaným stratégiám prvého hráča a dĺžka segmentu napravo od bodu sa rovná pravdepodobnosti použitia prvej stratégie a dĺžka segmentu naľavo je pravdepodobnosť použitia druhú stratégiu prvým hráčom.

Vykonávajú sa dve osi I-I a II-II. Na I-I odložíme výplatu, keď prvý hráč použije prvú stratégiu, na II-II, keď použije druhú stratégiu. Nech napríklad druhý hráč použije svoju prvú stratégiu, potom by sa hodnota mala vyniesť na os I-I a hodnota na os II-II

Pre akúkoľvek zmiešanú stratégiu prvého hráča bude jeho výplata určená veľkosťou segmentu. Línia I-I zodpovedá aplikácii prvej stratégie druhým hráčom, nazvime ju prvá stratégia druhého hráča. Druhá stratégia druhého hráča môže byť skonštruovaná podobne. Potom bude mať grafické zobrazenie hernej matice vo všeobecnosti nasledujúcu formu:

Obrázok 1.2 - zistenie ceny hry

Treba však poznamenať, že táto konštrukcia bola vykonaná pre prvého hráča. Tu sa dĺžka segmentu rovná hodnote hry V.

Línia 1N2 sa nazýva dolná výplatná línia. Tu je jasne vidieť, že bod N zodpovedá maximálnej hodnote garantovanej výplaty prvého hráča.

Vo všeobecnosti možno z tohto čísla určiť aj stratégiu druhého hráča, napríklad takýmito spôsobmi. Na osi I-I:

alebo na osi II-II

Stratégia druhého hráča však môže byť definovaná rovnako ako pre prvého hráča, t.j. vytvoriť takýto graf.

Obrázok 1.3 - definícia stratégie druhého hráča

Tu je čiara 1N2 hornou hranicou straty. Bod N zodpovedá minimálnej možnej strate druhého hráča a určuje stratégiu.

V závislosti od konkrétnych hodnôt koeficientov môžu mať matice grafu aj inú formu, napríklad takto:

Obrázok 1.4 - určuje optimálnu stratégiu prvého hráča

V takejto situácii je optimálna stratégia prvého hráča čistá:

1.6 Hry 2n alebo m2

V hrách poradia 2n má prvý hráč 2 čisté stratégie a druhý hráč má n čistých stratégií, t.j. Výplatná matica pre prvého hráča je:

Ak má takáto hra sedlový bod, potom je ľahké ho nájsť a získať riešenie.

Predpokladajme, že hra má sedlové body. Potom je potrebné nájsť také zmiešané stratégie, respektíve prvého a druhého hráča a cenu hry v, ktoré spĺňajú vzťahy:

Keďže hra nemá sedlový bod, nerovnosť (1,54) je nahradená nerovnosťami

Na riešenie sústav (1.56), (1.55), (1.53) je účelné použiť grafickú metódu. Pre tento účel zavedieme označenie pre ľavú stranu nerovnosti (1,53)

maticový matematický model hry

alebo nastavením z (1.55) a vykonaním jednoduchých transformácií dostaneme

kde je priemerná výplata prvého hráča za predpokladu, že používa svoju zmiešanú stratégiu, a druhá - jeho j-tá čistá stratégia.

Podľa výrazu každá hodnota j=1, 2, …, n zodpovedá priamke v pravouhlom súradnicovom systéme.

Cieľom druhého hráča je minimalizovať výplatu prvého hráča výberom jeho stratégií. Preto počítame

kde je spodná hranica množiny obmedzení. Na obrázku 1.6 je graf funkcie znázornený hrubou čiarou.

Hostené na http://www.allbest.ru/

Obrázok 1.6 - graf funkcie

Cieľom prvého hráča je maximalizovať svoju výplatu prostredníctvom výberu, t.j. vypočítať

Na obrázku 1.6 bodka znamená maximálnu hodnotu, ktorá sa získa pri. Cena hry, pretože:

Takto sa graficky určí optimálna zmiešaná stratégia prvého hráča a dvojica čistých stratégií druhého hráča, ktoré tvoria bod na priesečníku Obrázok 1.6 znázorňuje 2. a 3. stratégiu druhého hráča. Pre takéto stratégie sa nerovnosti (1,53) zmenia na rovnosť. Na obrázku 1.6 sú to stratégie j=2, j=3.

Teraz môžeme vyriešiť systém rovníc

a presne určiť hodnoty a (graficky sú určené približne). Potom umiestnite všetky hodnoty na tie j, pre ktoré netvoria bod, čím sa vyrieši systém rovníc (1.56) Pre príklad zobrazený na obrázku 1.6 je to nasledujúci systém:

a zvyšok Tento systém možno vyriešiť šikmým Ak pre nejaké j=j 0 stratégie druhého hráča tvoria bod M 0 a potom maximálna hodnota dolnej hranice množín obmedzení je reprezentovaná segmentom rovnobežným s os V tomto prípade má prvý hráč nekonečne veľa optimálnych hodnôt a ceny hry Tento prípad je znázornený na obrázku 1.7, kde a segment MN predstavuje hornú hranicu, optimálne hodnoty sú v rámci druhého hráča má čistú optimálnu stratégiu j=j 0 .

Grafickou metódou sú riešené aj maticové hry rádu m2. Výplatná matica prvého hráča má v tomto prípade tvar

Zmiešané stratégie prvého a druhého hráča sú definované rovnakým spôsobom ako v prípade hier poradia 2n. Na vodorovnej osi nech je vynesená hodnota od 0 do 1, hodnota priemernej výhry) prvého hráča na zvislej osi za podmienky, že prvý hráč použije svoju čistú i-tú stratégiu (i=1, 2, ..., m), druhá - jeho zmiešaná stratégia (y 1 , 1- y 1) =y. Napríklad, keď m=4 graficky) možno znázorniť, ako je znázornené na obrázku 1.7.

Obrázok 1.7 - funkčný graf)

Prvý hráč sa snaží maximalizovať svoju priemernú výplatu, a tak sa snaží nájsť

Funkcia je znázornená hrubou čiarou a predstavuje hornú hranicu množiny obmedzení. Druhý hráč sa snaží minimalizovať výberom svojej stratégie, t.j. hodnota zodpovedá

Na obrázku je hodnota označená bodkou. Inými slovami, sú definované také dve stratégie prvého hráča a pravdepodobnosť pre druhého hráča, pre ktorú sa dosiahne rovnosť

Z obrázku vidíme, že cena hry je ordináta bodu, pravdepodobnosť je úsečka bodu. Pre zostávajúce čisté stratégie prvého hráča v optimálnej zmiešanej stratégii musí ().

Riešením systému (1.69) teda získame optimálnu stratégiu druhého hráča a hodnotu hry. Optimálnu zmiešanú stratégiu pre prvého hráča nájdeme riešením nasledujúceho systému rovníc:

1.7 Maticová metóda na riešenie hier

Označenia:

Ľubovoľná štvorcová podmatica matice objednávky

Matica (1);

Matica transponovaná do;

Matica pripojená k B;

- (1) maticu získanú z X vymazaním prvkov, ktoré zodpovedajú riadkom vymazaným z po prijatí;

- (1) matica získaná vymazaním prvkov, ktoré zodpovedajú riadkom vymazaným, keď boli prijaté.

Algoritmus:

1. Vyberte štvorcovú podmaticu matice objednávky () a vypočítajte

2. Ak nejaké alebo, tak nájdenú maticu zahoďte a skúste inú maticu.

3. Ak (), (), vypočítame a zostavíme X a od a, pričom na príslušné miesta pridáme nuly.

Kontrola, či sú nerovnosti splnené

za každú (1,75)

a nerovnosti

za každú (1,76)

Ak jeden z pomerov nie je splnený, skúsime iný. Ak sú všetky vzťahy platné, potom X a požadované riešenia.

1.8 Spôsob postupného približovania sa k cene hry

Pri vyšetrovaní herných situácií sa často môže stať, že nie je potrebné získať presné riešenie hry alebo je z nejakého dôvodu nemožné alebo veľmi ťažké zistiť presnú hodnotu ceny hry a optimálne zmiešané stratégie. Potom môžete použiť približné metódy riešenia maticovej hry.

Opíšme si jednu z týchto metód - metódu postupného približovania sa ceny hry. Počet výplat vypočítaných pomocou metódy sa zvyšuje približne úmerne počtu riadkov a stĺpcov matice výplat.

Podstata metódy je nasledovná: mentálne sa hra hrá veľakrát, t.j. postupne si hráč v každej hre vyberá stratégiu, ktorá mu dáva najväčšiu celkovú (celkovú) výplatu.

Po takejto implementácii niektorých hier vypočíta priemernú hodnotu zisku prvého hráča a straty druhého hráča a ich aritmetický priemer berie ako približnú hodnotu ceny hry. Metóda umožňuje nájsť približnú hodnotu optimálnych zmiešaných stratégií oboch hráčov: je potrebné vypočítať frekvenciu aplikácie každej čistej stratégie a brať ju ako približnú hodnotu v optimálnej zmiešanej stratégii príslušného hráča.

Dá sa dokázať, že pri neobmedzenom zvyšovaní počtu programových hier sa priemerný zisk prvého hráča a priemerná strata druhého hráča budú neobmedzene blížiť k cene hry a približné hodnoty zmiešaných stratégií v r. prípad, keď je riešenie hry jedinečné, bude smerovať k optimálnym zmiešaným stratégiám každého hráča. Všeobecne povedané, aproximácia hodnôt nad špecifikovanými hodnotami skutočným hodnotám je pomalá. Tento proces je však možné ľahko mechanizovať a pomôcť tak získať riešenie hry s požadovaným stupňom presnosti aj s výplatnými maticami pomerne veľkého rádu.

2. Praktická časť

Pár sa rozhodne, kam sa pôjde prejsť a stráviť čas v prospech dvoch.

Dievča sa rozhodne ísť na prechádzku do parku, aby sa nadýchalo čerstvého vzduchu, a večer si pôjde pozrieť film do najbližšieho kina.

Chlapík sa po zhliadnutí zápasu futbalistov miestneho klubu na centrálnom štadióne ponúkne, že pôjde do technoparku.

V súlade s tým musíte zistiť, ako dlho bude cieľ jedného z hráčov dosiahnutý. Výplatná matica bude vyzerať takto:

Tabuľka 1. Výplatná matica

Od 1 2 v tejto hre evidentne nie je sedlo v čistých stratégiách. Preto používame nasledujúce vzorce a dostaneme:

Hostené na http://www.allbest.ru/

2.2 Prehrávanie 2xn a mx2

Problém 1 (2xn)

Pre suché a vlhké podnebie sa pestujú dve plodiny.

A stav prírody možno považovať za: suchý, vlhký, mierny.

Hostené na http://www.allbest.ru/

Maximálnu hodnotu M() dosiahneme v bode M tvorenom priesečníkom priamok zodpovedajúcich j=1, j"=2. Preto predpokladáme: ,

Úloha 2 (mx2)

Chlapec a dievča zvažujú možnosti, kam ísť cez víkend.

Výber miesta odpočinku môže byť reprezentovaný ako: park, kino, reštaurácia.

Hostené na http://www.allbest.ru/

Maximálnu hodnotu M() dosiahneme v bode E tvorenom priesečníkom priamok zodpovedajúcich j=1, j"=2. Preto predpokladáme: ,

Ak chcete určiť hodnotu v, musíte vyriešiť nasledujúce rovnice:

2.5 Maticová metóda

Dve konkurenčné reštaurácie (stravovacie zariadenia) poskytujú nasledovné súbory služieb. Prvá reštaurácia sa nachádza v centre a druhá na okraji mesta.

Centrálna reštaurácia zahŕňa tieto služby:

1) drahšie a lepšie služby zákazníkom;

2) jedlá sú zamerané na francúzsku kuchyňu;

Druhá reštaurácia ponúka:

1) nie drahé a vysokokvalitné služby;

2) menu kombinuje rôzne slávne kuchyne sveta;

3) aj pravidelné akcie a zľavy;

4) vykonáva doručenie a prijíma objednávky na doručenie domov.

V súlade s úlohou sa zisk za jeden deň rozdelí medzi dve reštaurácie takto:

Tabuľka 2. Výplatná matica

Riešenie hry s formulárom maticovým spôsobom:

Existuje šesť podmatíc a:

Zvážte maticu:

x 1 =? 0,x2=? 0

Pretože x 2 =< 0, то мы отбрасываем.

Zvážte teraz maticu:

x 1 =? 0,x2=? 0

Cena hry.

Tento pomer je v rozpore s požiadavkou, preto nie je vhodný.

Zvážte teraz maticu:

x 1 =, x 2 =? 0,

y1 =< 0, y 2 = ? 0.

Keďže y 1 =< 0, то мы отбрасываем и.

Zvážte teraz maticu:

x 1 \u003d, x 2 \u003d 0, pretože x 2 \u003d 0, potom vyhodíme a.

Zvážte teraz maticu:

x 1 =, x 2 =? 0. Keďže x 1 \u003d 0, potom vyradíme a.

Zvážte teraz maticu:

x 1 = , x 2 =, y 1 = , y 2 =, potom pokračujeme ďalej:

x 1 =, x 2 =, y1 =, y2 = alebo

Cena hry.

Teraz sú skontrolované hlavné vzťahy:

Hostené na http://www.allbest.ru/

Odpoveď: x 1 =, x 2 =, y 1 =, y 2 =, y 3 = 0, y 4 = 0,.

Hnedá metóda

Odborová organizácia na žiadosť pracovníkov určitého podniku rokuje s jeho vedením o organizácii teplých jedál na náklady podniku. Odborová organizácia zastupujúca záujmy pracovníkov zabezpečuje, že jedlo je najvyššej možnej kvality, a teda aj drahšie. Vedenie spoločnosti má protichodné záujmy. Nakoniec sa strany dohodli na nasledujúcom. Odborová organizácia (hráč 1) vyberie jednu z troch firiem (A 1, A 2, A 3) dodávajúcich teplé jedlá a vedenie spoločnosti (hráč 2) vyberie sadu jedál z troch možností (B 1, B 2, B 3). Po podpísaní zmluvy odborová organizácia vytvorí nasledujúcu platobnú maticu, ktorej prvky predstavujú náklady na sadu riadu:

Nech je hra daná nasledujúcou výplatnou maticou:

Predpokladajme, že druhý hráč si vybral svoju 2. stratégiu, potom prvý získa:

2, ak použije svoju 1. stratégiu,

3, ak použije svoju 3. stratégiu.

Získané hodnoty sú zhrnuté v tabuľke 1.

Tabuľka 3. Stratégia druhého hráča

Tabuľka 3 ukazuje, že pri 2. stratégii druhého hráča získa prvý hráč najväčšiu výplatu 3 pomocou svojej 2. alebo 3. stratégie. Keďže prvý hráč chce získať maximálnu výplatu, reaguje na 2. stratégiu druhého hráča svojou 2. stratégiou. Pri 2. stratégii prvého hráča prehrá druhý:

1, ak použije svoju 1. stratégiu,

3, ak použije svoju druhú stratégiu,

4, ak použije svoju 3. stratégiu.

Tabuľka 4. Stratégia prvého hráča

Tabuľka 2 ukazuje, že pri 2. stratégii prvého hráča bude mať druhý hráč najmenšiu stratu 1, ak použije svoju 1. stratégiu. Keďže druhý hráč chce stratiť menej, potom ako odpoveď na 2. stratégiu prvého hráča použije svoju 1. stratégiu. Získané výsledky sú zhrnuté v tabuľke 5.

Tabuľka 5. Stratégie prvého a druhého hráča

V tabuľke. 5 v stĺpci stratégie druhého hráča v druhom riadku je číslo 1, ktoré naznačuje, že v druhej hre je výhodné, aby druhý hráč použil svoju 1. stratégiu; v stĺpci a je najväčšia priemerná výplata 3 prvého hráča, ktorú získal v prvej hre; stĺpec w obsahuje najmenšiu priemernú stratu 1, ktorú získal druhý hráč v prvej hre; stĺpec v obsahuje aritmetický priemer v = (u + w) -- teda približnú hodnotu ceny hry, získanú ako výsledok odohrania jednej hry danej hry. Ak druhý hráč použije svoju 1. stratégiu, potom prvý hráč dostane 3, 1, 2, v uvedenom poradí, so svojou 1., 2., 3. stratégiou a celková odmena prvého hráča za obe hry bude:

2 + 3 = 5 s jeho 1. stratégiou,

3 + 1=4 s jeho 2. stratégiou,

3 + 2=5 s jeho 3. stratégiou.

Tieto celkové výhry sú zaznamenané v druhom riadku tabuľky. 3 a v stĺpcoch zodpovedajúcich stratégiám prvého hráča: 1, 2, 3.

Zo všetkých celkových výhier je najväčšia 5. Získava sa 1. a 3. stratégiou prvého hráča, potom si môže vybrať ktorúkoľvek z nich; povedzme, v takých prípadoch, keď sú dva (alebo viaceré) rovnaké celkové výnosy, vyberie sa stratégia s najmenším číslom (v našom prípade musíme použiť 1. stratégiu).

Pri 1. stratégii prvého hráča prehrá druhý hráč 3, 2, 3 v tomto poradí so svojou 1., 2., 3. stratégiou a celková strata druhého hráča v oboch hrách bude:

1 + 3 = 4 s jeho 1. stratégiou,

3 + 2 = 5 s jeho druhou stratégiou,

4 + 3=7 s jeho 3. stratégiou.

Tieto celkové straty sú zaznamenané v druhom riadku tabuľky. 5 a v stĺpcoch zodpovedajúcich 1., 2., 3. stratégii druhého hráča.

Zo všetkých celkových prehier druhého hráča je najmenšia 4. Získava ju svojou 1. stratégiou, preto v tretej hre musí druhý hráč uplatniť svoju 1. stratégiu. Do stĺpca vložte najväčšiu celkovú výplatu prvého hráča v dvoch hrách vydelenú počtom hier, t.j.; stĺpec w obsahuje najmenšiu celkovú prehru druhého hráča v dvoch hrách vydelenú počtom hier, t.j. aritmetický priemer týchto hodnôt je uvedený v stĺpci v, t.j. = Toto číslo je brané ako približná hodnota ceny hry s dvoma „ohranými“ hrami.

Takto sa získa nasledujúca tabuľka 4 pre dve sady hry.

Tabuľka 6. Celkové zisky a straty hráčov v dvoch odohraných zápasoch

V treťom riadku tabuľky 6 je v stĺpci stratégie druhého hráča číslo 1, ktoré znamená, že v tretej hre musí druhý hráč uplatniť svoju 1. stratégiu. V tomto prípade prvý hráč vyhrá 3, 1, 2 pomocou svojej 1., 2., 3. stratégie a jeho celková odmena za tri hry bude:

3 + 5 = 8 pri jeho prvej stratégii,

1 + 4 = 5 s jeho druhou stratégiou,

2 + 5 = 7 pre jeho 3. stratégiu.

Tieto celkové odmeny prvého hráča sú zaznamenané v treťom riadku tabuľky 6 a stĺpcoch zodpovedajúcich jeho stratégiám 1, 2, 3. Keďže najväčší celkový zisk 8 prvého hráča získa pri 1. stratégii, vyberie si 1. podľa toho.

Pri 1. stratégii prvého hráča prehrá druhý hráč 3, 1, 2 v tomto poradí so svojou 1., 2., 3. stratégiou a celková strata druhého hráča v oboch hrách bude:

3 + 4=7 s jeho 1. stratégiou,

2 + 5 = 7 s jeho 2. stratégiou,

3 + 7=10 s jeho 3. stratégiou.

Tieto celkové straty sú zaznamenané v treťom riadku tabuľky. 6 a v stĺpcoch zodpovedajúcich 1., 2., 3. stratégii druhého hráča. Zo všetkých jeho celkových strát je 7 najmenšia a získa sa svojou 1. a 2. stratégiou, potom musí druhý hráč uplatniť svoju 1. stratégiu.

V tabuľke. 6 v treťom riadku v stĺpci a najväčšia celková výhra prvého hráča za tri hry vydelená číslom hry, t.j. stĺpec w obsahuje najmenšiu celkovú stratu druhého hráča v troch hrách vydelenú počtom hier, t.j. do stĺpca v uveďte ich aritmetický priemer

Tak dostaneme tabuľku. 7 pre tri strany.

Tabuľka 7. Celkové zisky a straty hráčov v troch odohraných zápasoch

Tabuľka 8. Finálový stôl s dvadsiatimi odohratými hrami

Z tabuľky. 7 a 8 je možné vidieť, že v 20 prehratých hrách sa stratégie 1, 2, 3 pre prvého hráča vyskytnú 12, 3, 5 krát, preto sú ich relatívne frekvencie v tomto poradí rovnaké; stratégie 1, 2, 3 pre druhého hráča sa vyskytujú v tomto poradí 7, 11,2 krát, teda ich relatívne frekvencie sú v tomto poradí rovnaké; približná hodnota ceny hry. Táto aproximácia je dostatočne dobrá.

Na záver poznamenávame, že ak má hra viac ako jedno riešenie, potom sa približné hodnoty nákladov na hru budú stále približovať skutočným nákladom na hru a relatívna frekvencia výskytu stratégií hry. hráči už nebudú nevyhnutne pristupovať k skutočným optimálnym zmiešaným stratégiám hráčov.

Analýza výsledkov

V tejto kurzovej práci sa študuje materiál na hľadanie riešenia antagonistických hier grafickou, maticovou metódou, metódou postupnej aproximácie ceny hry. Zisťujú sa optimálne stratégie prvého a druhého hráča, ako aj cena hry v hrách 2x2, 2xn a mx2, ako aj v hrách s použitím maticovej metódy a Brownovej metódy.

Na príklade dvojice bola vymodelovaná hra 2x2, ktorá bola riešená algebraickou a grafickou metódou. Pri riešení hry algebraickou metódou riešenie ukazuje, že pri použití svojich optimálnych zmiešaných stratégií strávi prvý a druhý hráč spolu 4,6 hodiny. Grafické riešenie problému dopadlo s malou chybou a trvalo 4,5 hodiny.

A tiež boli modelované dve úlohy 2xn a mx2. V probléme 2xn sa uvažovalo o poľnohospodárskej kultúre a stratégia ukazuje, že je lepšie zasadiť pole 50 na 50 a cena hry bola 3,75 milióna rubľov. A v probléme mx2 sa uvažovalo o dvojici, ktorej stratégia ukázala, že je lacnejšie ísť do parku a kina a cena a náklady budú 4,3 rubľov.

Pre maticovú metódu bol modelovaný problém, v ktorom boli uvažované dve reštaurácie, riešenie problému ukázalo, že pri aplikácii jej optimálnej zmiešanej stratégie bude zisk prvej reštaurácie 15,6 milióna rubľov a pri použití jej optimálnej zmiešanej stratégie o druhá reštaurácia, nedovolí prvej zarobiť viac ako 15,6 milióna rubľov. Riešenie grafickou metódou poskytlo chybu a cena hry bola 14,9 milióna rubľov.

Pre Brownovu metódu bola vypracovaná úloha, v ktorej sa uvažuje o odborovom a podnikovom manažmente, ktorých úlohou je zabezpečiť pracovníkom stravu. Keď obaja hráči použijú svoje optimálne stratégie, jedlo na osobu bude 2,45 tisíc rubľov.

Zoznam použitých zdrojov

1) Vilisov V.Ya. Poznámky k prednáške "Teória hier a štatistické riešenia", - odbor - "Voskhod" MAI. 1979. 146 s.

2) Krushevsky A.V. Teória hier, - Kyjev: Vishcha school, 1977. - 216 s.

3) Cherchmen U., Akof R., Arnof L., Úvod do operačného výskumu. - M.: Veda. 1967. - 488 s.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Hostené na Allbest.ru

Podobné dokumenty

Rozhodovanie ako osobitný druh ľudskej činnosti. Racionálne znázornenie hernej matice. Príklady maticových hier v čistých a zmiešaných stratégiách. Operačný výskum: vzťah problémov lineárneho programovania s herno-teoretickým modelom.

semestrálna práca, pridaná 05.05.2010


Mnohokrát opakované hry, ich charakteristické vlastnosti a fázy. Zmiešané stratégie, podmienky a možnosti ich využitia v praxi. Analytická metóda na riešenie hry 2 x 2. Základné vety pre pravouhlé hry. Algebraické riešenia.

prezentácia, pridané 23.10.2013


Základné definície teórie bimaticových hier. Príklad bimatrixovej hry „Študent-Učiteľ“. Zmiešané stratégie v bimaticových hrách. Hľadajte „rovnovážnu situáciu“. 2x2 bimaticové hry a vzorce pre prípad, keď má každý hráč dve stratégie.

abstrakt, pridaný 13.02.2011


Štúdium všeobecných informácií o matrixových a antagonistických hrách. Koncept pozičnej hry, strom, informačná množina. Zohľadnenie princípu maxima a princípu rovnováhy. Paretova optimálnosť. Pozičná neantagonistická hra, jej vlastnosti.

ročníková práca, pridaná 17.10.2014


Teória hier je odvetvie matematiky, ktorej predmetom je štúdium matematických modelov na prijímanie optimálnych rozhodnutí v konflikte. Iteratívna Brown-Robinsonova metóda. Monotónny iteračný algoritmus na riešenie maticových hier.

diplomová práca, doplnené 08.08.2007


Zostavenie výplatnej matice, hľadanie spodnej a hornej čistej ceny hry, stratégie maximin a minimax hráčov. Zjednodušenie platobnej matice. Riešenie maticovej hry pomocou redukcie na úlohu lineárneho programovania a doplnku „Hľadaj riešenie“.

test, pridaný 10.11.2014


Teória hier je matematická teória konfliktných situácií. Vývoj matematického modelu hry s nulovým súčtom pre dve osoby, jeho implementácia vo forme programových kódov. Metóda riešenia problémov. Vstupné a výstupné dáta. Program, návod na použitie.

semestrálna práca, pridaná 17.08.2013


Základné informácie o simplexovej metóde, zhodnotenie jej úlohy a významu v lineárnom programovaní. Geometrická interpretácia a algebraický význam. Hľadanie maxima a minima lineárnej funkcie, špeciálne prípady. Riešenie úlohy maticovou simplexovou metódou.

práca, pridané 01.06.2015


Techniky konštrukcie matematických modelov výpočtových systémov, ktoré odrážajú štruktúru a procesy ich fungovania. Počet prístupov k súboru počas priemernej úlohy. Určenie možnosti umiestnenia súborov na externé pamäťové jednotky.

laboratórne práce, doplnené 21.06.2013


Navrhovanie matematického modelu. Popis hry tic-tac-toe. Logický herný model založený na Booleovej algebre. Digitálne elektronické zariadenia a vývoj ich matematického modelu. Herná konzola, herný ovládač, výplet hernej dosky.

Teória hier je teória matematických modelov rozhodovania v podmienkach konfliktu alebo neistoty. Predpokladá sa, že akcie strán v hre sa vyznačujú určitými stratégiami – súbormi akčných pravidiel. Ak zisk jednej strany nevyhnutne vedie k strate druhej strany, potom sa hovorí o antagonistických hrách. Ak je množina stratégií obmedzená, potom sa hra nazýva matrix a riešenie sa dá získať veľmi jednoducho. Riešenia získané pomocou teórie hier sú užitočné pri zostavovaní plánov v prípade možného odporu konkurentov alebo neistoty vo vonkajšom prostredí.

Ak je bimatická hra antagonistická, potom je výplatná matica hráča 2 úplne určená výplatnou maticou hráča 1 (zodpovedajúce prvky týchto dvoch matíc sa líšia iba znamienkami). Preto je bimaticová antagonistická hra úplne opísaná jedinou maticou (matica výplaty hráča 1) a podľa toho sa nazýva maticová hra.

Táto hra je antagonistická. V ňom j \u003d x2 - O, P a R (O, O] \u003d H (P, P) \u003d -I a R (O, P) \u003d R (P, O) \u003d 1, alebo v matričnej podobe o p

Nech je niektorá trieda hier Г "zrkadlovo uzavretá", t.j. spolu s každou svojou hrou obsahuje zrkadlovo izomorfnú hru (keďže všetky hry, ktoré sú zrkadlovo izomorfné k danej, sú navzájom izomorfné, môžeme v súlade s práve povedané hovoriť o jednej zrkadlovo izomorfnej hre). Takouto triedou je napríklad trieda všetkých antagonistických hier alebo trieda všetkých maticových hier.

Keď si pripomenieme definíciu prijateľných situácií v antagonistickej hre, zistíme, že situácia (X, Y) v zmiešanom rozšírení maticovej hry je prijateľná pre hráča 1 vtedy a len vtedy, ak pre ľubovoľné x G x nerovnosť

Proces premeny hier na symetrické sa nazýva symetrizácia. Opíšeme tu jednu metódu symetrizácie. Iná, zásadne odlišná verzia symetrizácie bude uvedená v časti 26.7. Oba tieto varianty symetrizácie sú v skutočnosti použiteľné pre ľubovoľné antagonistické hry, ale budú formulované a preukázané len pre maticové hry.

Počiatočné termíny a označenia teórie všeobecných antagonistických hier sa teda zhodujú so zodpovedajúcimi termínmi a označeniami teórie maticových hier.

Pre konečné antagonistické (maticové) hry sme existenciu týchto extrémov dokázali v kapitole 10. 1, a hlavným cieľom bolo nastoliť ich rovnosť, alebo aspoň nájsť spôsoby, ako ich nerovnosť prekonať.

Aj úvaha o maticových hrách ukazuje, že v pôvodne daných stratégiách hráčov existujú antagonistické hry bez rovnovážnych situácií (a dokonca aj bez e-rovnovážnych situácií pre dostatočne malé e > 0).

Ale každá konečná (maticová) hra môže byť rozšírená na nekonečnú hru, napríklad tým, že každému hráčovi poskytneme ľubovoľný počet dominantných stratégií (pozri 22 kap. 1). Je zrejmé, že takéto rozšírenie hráčovej množiny stratégií v skutočnosti nebude znamenať rozšírenie jeho možností a jeho skutočné správanie v rozšírenej hre by sa nemalo líšiť od správania v pôvodnej hre. Okamžite sme tak získali dostatočné množstvo príkladov nekonečných antagonistických hier, ktoré nemajú sedlové body. Existujú aj príklady tohto druhu.

Na implementáciu princípu maximínu v nekonečnej antagonistickej hre je teda potrebné, podobne ako v prípade konečnej (maticovej) hry, určité rozšírenie strategických možností hráčov. Za 96

Podobne ako v prípade maticových hier (pozri kap. 17, 17) aj pri všeobecných antagonistických hrách zohráva dôležitú úlohu koncept zmiešaného strategického spektra, ktorý však treba definovať všeobecnejšie.

Nakoniec si všimnite, že množina všetkých zmiešaných stratégií hráča 1 v ľubovoľnej antagonistickej hre je ako v matici

Dokonca aj úvaha o antagonistických hrách ukazuje, že veľké množstvo takýchto hier, vrátane konečných, maticových hier má rovnovážne situácie nie v pôvodných, čistých stratégiách, ale len v zovšeobecnených, zmiešaných stratégiách. Preto je pre všeobecné, neantagonistické, nekooperatívne hry prirodzené hľadať rovnovážne situácie práve v zmiešaných stratégiách.

Takže napríklad (pozri obr. 3.1) sme si už všimli, že „zhotoviteľ“ takmer nikdy nemusí riešiť neistotu správania. Ale ak si vezmeme koncepčnú úroveň typu „Správca“, tak je všetko presne naopak. Hlavným typom neistoty, ktorej musí takýto „náš rozhodovateľ“ čeliť, je spravidla „konflikt“. Teraz môžeme objasniť, že zvyčajne ide o neprísnu rivalitu. O niečo menej často sa „Správca“ rozhoduje v podmienkach „prirodzenej neistoty“ a ešte zriedkavejšie sa stretáva s prísnym, antagonistickým konfliktom. Navyše k stretu záujmov pri rozhodovaní zo strany „Správcu“ dochádza takpovediac „raz“, teda v našej klasifikácii často hrá len jednu (niekedy veľmi malý počet) partií hry. Stupnice na hodnotenie dôsledkov sú častejšie kvalitatívne ako kvantitatívne. Strategická nezávislosť „správcu“ je dosť obmedzená. Berúc do úvahy vyššie uvedené, možno tvrdiť, že problémové situácie tohto rozsahu sa najčastejšie musia analyzovať pomocou nekooperatívnych neantagonistických bimaticových hier, navyše v čistých stratégiách.

Princípy riešenia maticových antagonistických hier

Z toho vyplýva, že je rozumné očakávať, že vo vyššie opísanej hre budú súperi dodržiavať zvolené stratégie. Maticová antagonistická hra, pre ktorú max min fiv = min max Aiy>

Nie všetky maticové antagonistické hry sú však celkom jednoznačné a vo všeobecnosti

Vo všeobecnom prípade je teda na vyriešenie maticovej antagonistickej hry o dimenzii /uxl potrebné vyriešiť dvojicu problémov s duálnym lineárnym programovaním , ktorých výsledkom je súbor optimálnych stratégií , / a cena hry v.

Ako je definovaná matrixová antagonistická hra dvoch osôb?

Aké sú metódy na zjednodušenie a riešenie maticových antagonistických hier

V prípade hry dvoch osôb je prirodzené považovať ich záujmy za priamo opačné – hra je antagonistická. Výplata jedného hráča sa teda rovná strate druhého (súčet výhier oboch hráčov je nula, odtiaľ názov, hra s nulovým súčtom). Budeme uvažovať o hrách, v ktorých má každý hráč konečný počet alternatív. Výplatná funkcia pre takúto hru pre dvoch hráčov s nulovým súčtom môže byť uvedená v maticovej forme (vo forme matice výhry).

Ako už bolo uvedené, posledná antagonistická hra sa nazýva matrix.

MATRIX GAMES - trieda antagonistických hier, v ktorých sa zúčastňujú dvaja hráči a každý hráč má obmedzený počet stratégií. Ak jeden hráč má m stratégií a druhý hráč má n stratégií, potom môžeme zostaviť hernú maticu s dimenziou txn. M.i. môže alebo nemusí mať sedlový hrot. V druhom prípade

Predstavte si hru s konečným nulovým súčtom. Označiť podľa a odmena hráča A a cez b- výhra hráča B. Pretože a = –b, potom pri analýze takejto hry nie je potrebné brať do úvahy obe tieto čísla - stačí zvážiť výplatu jedného z hráčov. Nech je napr. A. V nasledujúcom texte, pre pohodlie prezentácie, strana A podmienečne pomenujeme" my"a stranu B – "nepriateľa".

Nechaj nás mať m možné stratégie A 1 , A 2 , …, A m a nepriateľa n možné stratégie B 1 , B 2 , …, B n(takejto hre sa hovorí hra m×n). Predpokladajme, že každá strana si zvolila určitú stratégiu: my sme si vybrali A i, protivník B j. Ak sa hra skladá len z osobných ťahov, potom výber stratégií A i a B j jednoznačne určuje výsledok hry – našu výplatu (pozitívnu alebo negatívnu). Označme tento zisk ako aij(výhra, keď zvolíme stratégiu A i, a nepriateľ - stratégie B j).

Ak hra obsahuje okrem osobných náhodných ťahov aj výplatu za dvojicu stratégií A i, B j je náhodná hodnota, ktorá závisí od výsledkov všetkých náhodných ťahov. V tomto prípade je prirodzený odhad očakávanej výplaty matematické očakávanie náhodnej výhry. Pre pohodlie budeme označovať podľa aij ako samotná výplata (v hre bez náhodných ťahov), tak aj jej matematické očakávanie (v hre s náhodnými ťahmi).

Predpokladajme, že poznáme hodnoty aij pre každú dvojicu stratégií. Tieto hodnoty možno zapísať ako maticu, ktorej riadky zodpovedajú našim stratégiám ( A i) a stĺpce zobrazujú súperove stratégie ( B j):

Takáto matica je tzv výplatná matica hry alebo jednoducho herná matica.

Všimnite si, že konštrukcia výplatnej matice pre hry s veľkým počtom stratégií môže byť náročná úloha. Napríklad pri šachovej hre je počet možných stratégií taký veľký, že zostavenie výplatnej matice je prakticky nemožné. V princípe však môže byť každá konečná hra zredukovaná na maticovú formu.

Zvážte príklad 1 Antagonistická hra 4×5. My máme k dispozícii štyri stratégie, nepriateľ má päť stratégií. Matrica hry je nasledovná:

Akú stratégiu by sme mali (t.j. hráč A) použit? Bez ohľadu na to, akú stratégiu zvolíme, rozumný protivník na ňu zareaguje takou stratégiou, pre ktorú bude naša odmena minimálna. Napríklad, ak zvolíme stratégiu A 3 (pokúšaný výhrou 10), súper si ako odpoveď zvolí stratégiu B 1 a naša odmena bude len 1. Je zrejmé, že na základe princípu opatrnosti (a to je hlavným princípom teórie hier) musíme zvoliť stratégiu, v ktorej náš minimálny zisk je maximálny.

Označiť podľa a i minimálna hodnota výnosu pre stratégiu A i:

a pridajte stĺpec obsahujúci tieto hodnoty do matice hry:

Pri výbere stratégie musíme zvoliť tú, pre ktorú je hodnota a i maximálne. Označme túto maximálnu hodnotu pomocou α :

Hodnota α volal nižšia cena hry alebo maximin(maximálna minimálna výhra). Stratégia hráča A zodpovedajúce maximínu α , volal stratégia maximin.

V tomto príklade je maximín α sa rovná 3 (zodpovedajúca bunka v tabuľke je zvýraznená sivou farbou) a stratégia maximin je Aštyri . Pri zvolení tejto stratégie si môžeme byť istí, že pri akomkoľvek správaní nepriateľa vyhráme nie menej ako 3 (a možno aj viac pri „nerozumnom“ správaní nepriateľa) Táto hodnota je naším garantovaným minimom, ktoré vieme zabezpečiť pre nás samých, pričom sa budeme držať najopatrnejšej („zaisťovacej“) stratégie.

Teraz vykonáme podobné uvažovanie pre nepriateľa B B A B 2 - odpovieme mu A .

Označiť podľa β j A B) pre stratégiu A i:

β j β :

7. ČO JE HRA HORNÁ HODNOTA Teraz vykonáme podobné uvažovanie pre súpera B. Má záujem minimalizovať náš zisk, teda dať nám menej, no musí počítať s naším správaním, ktoré je pre neho najhoršie. Napríklad, ak zvolí stratégiu B 1 , potom mu odpovieme stratégiou A 3 , a dá nám 10. Ak sa rozhodne B 2 - odpovieme mu A 2 a dá 8 atď. Je zrejmé, že opatrný súper musí zvoliť stratégiu, v ktorej náš maximálny zisk bude minimálny.

Označiť podľa β j maximálne hodnoty v stĺpcoch výplatnej matice (maximálna výplata hráča A, alebo, čo je to isté, maximálna strata hráča B) pre stratégiu A i:

a pridajte riadok obsahujúci tieto hodnoty do matice hry:

Pri výbere stratégie bude nepriateľ preferovať tú, pre ktorú je hodnota β j minimálne. Označme to podľa β :

Hodnota β volal najvyššia cena hry alebo minimax(minimálna maximálna výhra). Stratégia súpera (hráča) zodpovedajúca minimaxu B), sa nazýva minimax stratégiu.

Minimax je hodnota zisku, viac ako nám rozumný súper určite nedá (inými slovami, rozumný súper stratí maximálne β ). V tomto príklade minimax β sa rovná 5 (príslušná bunka v tabuľke je zvýraznená sivou farbou) a dosiahne sa súperovou stratégiou B 3 .

Takže na základe zásady opatrnosti („vždy očakávaj to najhoršie!“) musíme zvoliť stratégiu A 4 a nepriateľ - stratégia B 3. Princíp opatrnosti je základom teórie hier a je tzv princíp minimax.

Zvážte príklad 2. Nechajte hráčov A a AT jedno z troch čísel sa píše súčasne a nezávisle od seba: buď „1“, alebo „2“ alebo „3“. Ak je súčet zapísaných čísel párny, tak hráč B platí hráč A túto sumu. Ak je suma nepárna, hráč túto sumu zaplatí A hráč AT.

Zapíšme si výplatnú maticu hry a nájdime spodnú a hornú cenu hry (číslo stratégie zodpovedá zapísanému číslu):

Hráč A musí dodržiavať stratégiu maximin A 1 vyhrať aspoň -3 (to znamená prehrať maximálne 3). Stratégia Minimax Player B niektorú zo stratégií B 1 a B 2 , čo zaručuje, že nedá viac ako 4.

Rovnaký výsledok dostaneme, ak výplatnú maticu napíšeme z pohľadu hráča AT. V skutočnosti sa táto matica získa transpozíciou matice skonštruovanej z pohľadu hráča A a zmena znamienka prvkov na opak (od výplaty hráča A je strata hráča AT):

Na základe tejto matice vyplýva, že hráč B musí dodržiavať niektorú zo stratégií B 1 a B 2 (a potom nestratí viac ako 4) a hráč A– stratégie A 1 (a potom nestratí viac ako 3). Ako vidíte, výsledok je úplne rovnaký ako ten, ktorý sme získali vyššie, takže na analýze nezáleží z hľadiska toho, ktorý hráč ju vedie.

8 ČO JE HODNOTNÁ HRA.

9. Z ČOHO SA SKLADÁ PRINCÍP MINIMAX. 2. Dolná a horná cena hry. Princíp Minimax

Zvážte maticovú hru typu s výplatnou maticou

Ak hráč ALE zvolí stratégiu A i, potom všetky jeho možné prínosy budú prvky i-tý riadok matice OD. Najhoršie pre hráča ALE prípad, keď hráč AT uplatňuje vhodnú stratégiu minimálne prvok tejto línie, odmena hráča ALE sa bude rovnať číslu.

Preto, aby hráč získal maximálnu odmenu ALE musíte si vybrať jednu zo stratégií, pre ktoré je číslo maximálne.

Najjednoduchším prípadom, podrobne rozpracovaným v teórii hier, je hra konečných párov s nulovým súčtom (antagonická hra dvoch osôb alebo dvoch koalícií). Uvažujme hru G, v ktorej sa zúčastňujú dvaja hráči A a B, ktorí majú opačné záujmy: zisk jedného sa rovná strate druhého. Keďže výplata hráča A sa rovná výplate hráča B s opačným znamienkom, môže nás zaujímať iba výplata hráča a. Prirodzene, A chce maximalizovať a B chce minimalizovať a.

Pre jednoduchosť sa mentálne stotožnme s jedným z hráčov (nech je to A) a nazvime ho „my“ a hráčom B – „súperom“ (samozrejme z toho nevyplývajú žiadne skutočné výhody pre A). Majme možné stratégie a protivník - možné stratégie (takejto hre sa hovorí hra). Označme našu výplatu, ak my používame stratégiu a súper používa stratégiu

Tabuľka 26.1

Predpokladajme, že pre každý pár stratégií je nám známy výnos (alebo priemerný výnos) a. Potom je v princípe možné zostaviť obdĺžnikovú tabuľku (maticu), v ktorej sú uvedené stratégie hráčov a zodpovedajúce výplaty (pozri tabuľku 26.1).

Ak sa takáto tabuľka zostaví, potom sa hovorí, že hra G sa zredukuje na maticovú formu (samotné doviesť hru do takejto formy už môže byť náročná úloha a niekedy prakticky nemožná, vzhľadom na obrovské množstvo stratégií ). Všimnite si, že ak je hra zredukovaná na maticovú formu, potom sa hra s viacerými ťahmi v skutočnosti zredukuje na hru s jedným ťahom – hráč musí urobiť iba jeden ťah: zvoliť si stratégiu. Hernú maticu stručne označíme

Zoberme si príklad hry G (4X5) v maticovej forme. Máme k dispozícii (na výber) štyri stratégie, nepriateľ má päť stratégií. Matica hry je uvedená v tabuľke 26.2

Zamyslime sa nad tým, akú stratégiu (hráč A) používame? Matrix 26.2 má lákavú odmenu "10"; ťahá nás to k tomu, aby sme si zvolili stratégiu, v ktorej túto „lahôdku“ získame.

Ale počkajte, ani nepriateľ nie je hlúpy! Ak si zvolíme stratégiu, on napriek nám zvolí stratégiu a my dostaneme mizernú odmenu „1“. Nie, nemôžete si zvoliť stratégiu! Ako byť? Samozrejme, vychádzajúc z princípu opatrnosti (a to je hlavný princíp teórie hier), musíme zvoliť stratégiu, pre ktorú je náš minimálny zisk maximálny.

Tabuľka 26.2

Toto je takzvaný „princíp mini-maxu“: konajte tak, aby ste pri najhoršom správaní svojho súpera získali maximálny zisk.

Prepíšeme tabuľku 26.2 a do pravého doplnkového stĺpca zapíšeme minimálnu hodnotu zosilnenia v každom riadku (minimum riadku); označme ho pre riadok a (pozri tabuľku 26.3).

Tabuľka 26.3

Zo všetkých hodnôt (pravý stĺpec) je vybratá najväčšia (3). Zodpovedá stratégii. Po zvolení tejto stratégie si v každom prípade môžeme byť istí, že (za akékoľvek správanie nepriateľa) vyhráme nie menej ako 3. Táto hodnota je naším garantovaným ziskom; ak sa budeme správať opatrne, nemôžeme získať menej ako toto, môžeme získať viac).

Táto odmena sa nazýva nižšia cena hry (alebo „maximin“ – maximum z minimálnych odmien). Budeme ho označovať ako a. V našom prípade

Teraz zoberme uhol pohľadu nepriateľa a argumentujme za neho. Nie je to nejaký pešiak, ale tiež rozumný! Pri výbere stratégie by chcel dať menej, ale musí počítať s naším správaním, ktoré je pre neho najhoršie. Ak zvolí stratégiu, odpovieme mu a dá 10; ak si vyberie, odpovieme mu a on to vráti, atď. Do tabuľky 26.3 pridáme ďalší spodný riadok a zapíšeme doň maximá stĺpcov. Je zrejmé, že opatrný protivník musí zvoliť stratégiu, pre ktorú je táto hodnota minimálna (zodpovedajúca hodnota 5 je zvýraznená v tabuľke 26.3) . Táto hodnota P je hodnota zisku, viac ako nám rozumný súper určite nedá. Nazýva sa horná cena hry (alebo „mi-nimax“ – minimum maximálnej výhry). V našom príklade a je dosiahnuté pomocou súperovej stratégie

Na základe princípu opatrnosti (pravidlo zaistenia „vždy rátajte s najhorším!“) si teda musíme zvoliť stratégiu A a nepriateľa – stratégiu.Takéto stratégie sa nazývajú „minimax“ (podľa princípu minimax). Pokiaľ sa obe strany v našom príklade budú držať svojich minimax stratégií, vyplatí sa

Teraz si na chvíľu predstavte, že sme sa dozvedeli, že nepriateľ nasleduje stratégiu. No tak, potrestáme ho za to a zvolíme stratégiu, dostaneme 5, a to nie je také zlé. Ale napokon, nepriateľ tiež nie je slečna; dajte mu vedieť, že naša stratégia je , bude sa tiež ponáhľať s výberom , zníži našu výplatu na 2 atď. (partneri sa „rozbehli okolo stratégií“). Stručne povedané, stratégie minimaxu v našom príklade sú nestabilné vzhľadom na informácie o správaní druhej strany; tieto stratégie nemajú rovnovážnu vlastnosť.

Je to vždy takto? Nie vždy. Zvážte príklad s maticou uvedenou v tabuľke 26.4.

V tomto príklade sa spodná cena hry rovná hornej: . Čo z toho vyplýva? Stratégie minimaxu hráčov A a B budú stabilné. Pokiaľ sa ich budú držať obaja hráči, odmena je 6. Pozrime sa, čo sa stane, ak (A) zistíme, že súper (B) sa drží stratégie B?

Tabuľka 26.4

A presne nič sa nezmení, pretože akákoľvek odchýlka od stratégie môže našu situáciu len zhoršiť. Rovnako informácie prijaté protivníkom ho nedonútia ustúpiť od svojej stratégie Dvojica stratégií má rovnovážnu vlastnosť (vyvážená dvojica stratégií) a odmena (v našom prípade 6) dosiahnutá touto dvojicou stratégií je nazývaný „sedlový bod matice“. Znakom prítomnosti sedlového bodu a vyváženej dvojice stratégií je rovnosť spodnej a hornej ceny hry; celková hodnota sa nazýva cena hry. Označíme ho

Stratégie (v tomto prípade ), pri ktorých sa tento zisk dosahuje, sa nazývajú optimálne čisté stratégie a ich kombinácia je riešením hry. Samotná hra sa v tomto prípade vraj rieši v čistých stratégiách. Obe strany A aj B môžu dostať svoje optimálne stratégie, v ktorých je ich pozícia najlepšia. A že hráč A vyhrá 6 a hráč B prehrá, no, toto sú podmienky hry: sú výhodné pre A a nevýhodné pre B.

Čitateľ môže mať otázku: prečo sa optimálne stratégie nazývajú „čisté“? Keď sa pozrieme trochu dopredu, odpovedzme si na túto otázku: existujú „zmiešané“ stratégie, ktoré spočívajú v tom, že hráč nepoužíva jednu stratégiu, ale niekoľko, pričom ich náhodne strieda. Ak teda pripustíme okrem čistých aj zmiešané stratégie, každá konečná hra má riešenie – rovnovážny bod. Viac o tom však ešte len príde.

Prítomnosť sedlového bodu v hre nie je ani zďaleka pravidlom, ale skôr výnimkou. Väčšina hier nemá sedlový hrot. Existuje však množstvo hier, ktoré majú vždy sedlovú pointu, a preto sú riešené čistými stratégiami. Ide o takzvané „hry s úplnými informáciami“. Hra s úplnými informáciami je hra, v ktorej každý hráč pozná celú prehistóriu svojho vývoja pri každom osobnom ťahu, t. j. výsledky všetkých predchádzajúcich ťahov, osobných aj náhodných. Príkladmi hier s úplnými informáciami sú dáma, šach, piškvorky atď.

V teórii hier je dokázané, že každá hra s úplnými informáciami má sedlový bod, a preto sa dá riešiť čistými stratégiami. V každej hre s dokonalými informáciami existuje pár optimálnych stratégií, ktoré poskytujú stabilnú výplatu rovnajúcu sa cene hry a. Ak takáto hra pozostáva len z osobných ťahov, potom keď každý hráč použije svoju optimálnu stratégiu, musí to skončiť celkom definitívnym spôsobom – s výplatou rovnajúcou sa cene hry. Ak je teda známe riešenie hry, samotná hra stráca zmysel!

Uveďme si základný príklad hry s úplnými informáciami: dvaja hráči striedavo umiestňujú nikláky na okrúhly stôl, pričom si ľubovoľne vyberajú polohu stredu mince (vzájomné prekrývanie mincí nie je povolené). Vyhráva ten, kto vloží posledný cent (keď už nie je miesto pre ostatných). Je ľahké vidieť, že výsledok tejto hry je v podstate vopred rozhodnutý. Existuje určitá stratégia, ktorá zabezpečuje, že hráč, ktorý vloží mincu ako prvý, vyhrá.

Totiž, musí prvýkrát položiť nikel do stredu stola a potom reagovať na každý ťah súpera symetrickým ťahom. Je zrejmé, že nech sa súper správa akokoľvek, prehre sa nevyhne. Situácia je úplne rovnaká so šachom a hrami s úplnými informáciami vo všeobecnosti: ktorákoľvek z nich, napísaná v maticovej forme, má sedlový bod, a preto je riešenie v čistých stratégiách, a preto má zmysel len dovtedy, kým má toto riešenie nenašiel sa. Povedzme šachová hra buď to vždy skončí výhrou bieleho, alebo to vždy skončí výhrou čierneho, alebo to vždy skončí remízou, ale čo presne - to zatiaľ nevieme (našťastie pre milovníkov šachu). Dodajme ešte jednu vec: v dohľadnej dobe sa to len ťažko dozvieme, pretože počet stratégií je taký obrovský, že zredukovať hru do matricovej podoby a nájsť v nej sedlový bod je mimoriadne náročné (ak nie nemožné).

A teraz si položme otázku, čo robiť, ak hra nemá sedlovú pointu: Nuž, ak je každý hráč nútený zvoliť si jedinú čistú stratégiu, potom sa nedá nič robiť: musíme sa riadiť princípom minimaxu. Iná vec je, ak dokážete „miešať“ svoje stratégie, náhodne ich striedať s určitými pravdepodobnosťami. Použitie zmiešaných stratégií je koncipované takto: hra sa mnohokrát opakuje; pred každou partiou hry, keď hráč dostane osobný ťah, „zverí“ svoj výber náhode, „hádže žreby“ a zvolí stratégiu, ktorá vypadla (už vieme, ako organizovať žreb z predchádzajúcej kapitoly ).

Zmiešané stratégie v teórii hier sú modelom premenlivej, flexibilnej taktiky, kedy nikto z hráčov nevie, ako sa v danej hre zachová súper. Táto taktika (aj keď zvyčajne bez akéhokoľvek matematického zdôvodnenia) sa často používa v kartové hry. Zároveň podotýkame, že najlepší spôsob, ako skryť svoje správanie pred nepriateľom, je dať mu náhodný charakter a teda vopred nevedieť, čo urobíte.

Poďme sa teda baviť o zmiešaných stratégiách. Budeme označovať zmiešané stratégie hráčov A a B, resp

V konkrétnom prípade, keď sa všetky pravdepodobnosti okrem jednej rovnajú nule a táto sa rovná jednej, zmiešaná stratégia sa zmení na čistú.

Existuje základná veta teórie hier: každá hra s konečným nulovým súčtom pre dvoch hráčov má aspoň jedno riešenie - pár optimálnych stratégií, zvyčajne zmiešaných, a zodpovedajúcu cenu.

Dvojica optimálnych stratégií, ktoré tvoria riešenie hry, má nasledujúcu vlastnosť: ak jeden z hráčov dodrží svoju optimálnu stratégiu, potom nemôže byť pre druhého výhodné odchýliť sa od tej svojej. Táto dvojica stratégií tvorí akúsi rovnováhu v hre: jeden hráč chce otočiť výplatu na maximum, druhý na minimum, každý ťahá vlastným smerom a pri rozumnom správaní oboch rovnováha a stabilná výplata v. Ak je potom hra prospešná pre nás, ak - pre nepriateľa; keď je hra „férová“, rovnako výhodná pre oboch účastníkov.

Zvážte príklad hry bez sedlového bodu a uveďte (bez dôkazu) jej riešenie. Hra je nasledovná: dvaja hráči A a B súčasne a bez slova ukážu jeden, dva alebo tri prsty. O výhre rozhoduje celkový počet prstov: ak je párny, A vyhrá a dostane od B čiastku rovnajúcu sa tomuto počtu; ak je nepárny, potom, naopak, A zaplatí B sumu rovnajúcu sa tomuto číslu. Čo by mali hráči robiť?

Vytvorme hernú maticu. V jednej hre má každý hráč tri stratégie: ukázať jeden, dva alebo tri prsty. Matica 3x3 je uvedená v tabuľke 26.5; extra pravý stĺpec zobrazuje minimá riadkov a ďalší spodný riadok zobrazuje maximá stĺpcov.

Nižšia cena hry je v súlade so stratégiou. To znamená, že pri rozumnom, opatrnom správaní garantujeme, že neprehráme viac ako 3. Malá útecha, ale stále lepšia ako povedzme výhra - 5, nájdené v niektorých bunkách matice. Je to pre nás zlé, hráč L... Ale potešme sa: pozícia súpera sa zdá byť ešte horšia: nižšia cena hry pri. rozumné správanie, dá nám minimálne 4.