Principy řešení maticových antagonistických her. Maticové hry: příklady řešení problémů

Účel služby. Pomocí online služby můžete:

• určit cenu maticové hry (dolní a horní hranice), zkontrolovat přítomnost sedlového bodu, najít řešení smíšené strategie, najít minimax strategii hráčů;
• napsat matematický model dvojice úloh duálního lineárního programování, řešit maticovou hru metodami: minimax, simplexová metoda, grafická (geometrická) metoda, Brownova metoda.

Instrukce. Vyberte rozměr matice a klikněte na Další. V novém dialogovém okně vyberte způsob řešení maticové hry. Příklad plnění. Výsledky výpočtu jsou prezentovány ve zprávě ve formátu Word.

Hra je matematický model skutečné konfliktní situace. Konfliktní situace mezi dvěma hráči se nazývá hra ve čtyřhře. Je vhodné studovat párovou hru s nulovým součtem, pokud je popsána ve formě matice. Tato hra se jmenuje matice; matice složená z čísel a ij se nazývá platba. V tabulce jsou uvedeny možnosti řešení hry specifikované platební maticí A.

Popis algoritmu:

1. Na základě analýzy platební matice je nutné určit, zda v ní převládají strategie a eliminovat je.
2. Najděte horní a dolní cenu hry a určete, zda má tato hra sedlový bod (nižší cena hry se musí rovnat horní ceně hry).
3. Pokud sedlový bod existuje, pak optimální strategie hráčů, které jsou řešením hry, budou jejich čisté strategie odpovídající sedlovému bodu. Cena hry se rovná horní a dolní ceně hry, které se navzájem rovnají.
4. Pokud hra nemá sedlovou pointu, pak je třeba řešení hry hledat ve smíšených strategiích. K určení optimálních smíšených strategií v hrách m × n by se měla použít simplexová metoda, která nejprve přeformulovala problém hry na problém lineárního programování.

Pojďme si představit algoritmus pro grafické řešení maticové hry.

Obrázek - Schéma řešení maticové hry.

Metody řešení maticových her ve smíšených strategiích

Pokud tedy neexistuje žádný sedlový bod, hra se řeší pomocí smíšených strategií a řeší se pomocí následujících metod:

1. Řešení hry pomocí soustavy rovnic.
   Pokud je dána čtvercová matice nxn (n=m), pak lze vektor pravděpodobnosti nalézt řešením soustavy rovnic. Tato metoda se nepoužívá vždy a je použitelná pouze v určitých případech (pokud je matice 2x2, pak je řešení hry téměř vždy získáno). Pokud řešení dává záporné pravděpodobnosti, pak je tento systém řešen simplexovou metodou.
2. Grafické řešení hry.
   V případech, kdy n=2 nebo m=2, lze maticovou hru vyřešit graficky.
3. Řešení maticové hry simplexovou metodou.
   V tomto případě se maticová hra snižuje na

Přístup k řešení maticových her lze zobecnit na případ her s nulovým součtem, ve kterých je výplata hráčů specifikována jako spojitá funkce (nekonečná hra s nulovým součtem).

Tato hra je reprezentována jako hra pro dva hráče, ve které hráč 1 volí číslo X z mnoha X, hráč 2 si vybere číslo y ze sady 7 a poté hráči 1 a 2 obdrží výhru U(x, y) a -U(x, y). Volba určitého čísla hráčem znamená uplatnění jeho čisté strategie odpovídající tomuto číslu.

Analogicky s maticovými hrami lze nazvat čistou nižší cenu hry v ( = max min U(x, y), a čistou nejvyšší cenu hry -v 2 =

min max U(x, y). Pak analogicky můžeme předpokládat, že pokud pro některé

na *

nebo nekonečná antagonistická hra o velikosti PROTI A v 2 existují a jsou si navzájem rovny („i =v 2 =v), pak má taková hra řešení v čistých strategiích, tzn. Optimální strategií hráče 1 je vybrat číslo x° E X, a hráč 2 - čísla y 0 e 7, pro které ššč ( y 0) -proti.

V tomto případě proti se nazývá čistá cena hry a (x°, y 0) je sedlový bod nekonečné hry s nulovým součtem.

Pro maticové hry velikosti v x A v 2 vždy existují, ale v nekonečných antagonistických hrách nemusí existovat, tzn. nekonečná hra s nulovým součtem není vždy řešitelná.

Při formalizaci reálné situace v podobě nekonečné antagonistické hry se obvykle volí jeden strategický interval – jediný interval, ze kterého si hráči mohou vybrat (X -číslo (strategii) zvolené hráčem 1; -

číslo (strategii) zvolené hráčem 2). Technicky to řešení zjednodušuje, protože jednoduchou transformací lze libovolný interval převést na jednotkový interval a naopak. Tato hra se jmenuje antagonistická hra na jednotkovém čtverci.

Řekněme například, že hráč 1 zvolí číslo X z mnoha X=, hráč 2 vybere číslo y ze sady Y=. Poté hráč 2 zaplatí hráči 1 částku Shchh, y) -2x 2 -y 2. Protože se hráč 2 snaží minimalizovat platby hráče 1, určí min ( 2x 2 - y 2) = 2x 2- 1, tzn. v tomto případě = 1. Hráč 1 se snaží vytvořit mtag

Simulujte svou platbu, proto určuje maxi min ššč, y)1 =

xGX y např

- max (2x 2- 1) = 2- 1 = 1, čehož je dosaženo, když X = 1.

Tedy nižší čistá cena hry v x - 1. Horní čištění

cena hryv 2 =min - min (2 - y2) = 2 - 1 = 1, tzn. v tomhle

>napřheh u ey

hra v l = v 2 = l. Proto čistá cena hry proti= 1 a sedlový bod (x° = 1; y° = 1).

Předpokládejme to nyní Chi Y- otevřené intervaly, tzn. hráč 1 volí xeA"=(0; 1), hráč 2 volí ue 7= (0; 1). V tomto případě X, dostatečně blízko 1, hráč 1 si bude jistý, že obdrží odměnu ne menší než číslo blízké "=1; výběrem y blízké 1 hráč 2 nedovolí, aby výplata hráče 1 výrazně převýšila čisté náklady hry v= 1.

Stupeň blízkosti k ceně hry lze charakterizovat číslem?>0. Proto v popisované hře můžeme mluvit o optimálnosti čistých strategií x°= 1, 0 = 1 hráči 1 a 2 až do libovolného počtu?>0. Tečka (X", y E), kde x e e X, y (. eY, v nekonečné hře s nulovým součtem se nazývá z-rovnovážný bod (s.-sedlový bod), pokud pro nějaké strategie xTiger 1, ue Tiger 2 platí nerovnost ššč, u.) - ? Ш x r , у (.) U(x t., у) + ?. V tomto případě strategie x k. a vy jsou nazývány s,-optimálními strategiemi. Jsou tyto strategie optimální? v tom smyslu, že pokud odchylka od optimální strategie nemůže přinést hráči žádný prospěch, pak její odchylka od c-optimální strategie může zvýšit jeho výplatu maximálně o e.

Pokud hra nemá sedlový bod (c-seddle point), tzn. řešení v čistých strategiích, pak lze optimální strategie hledat mezi smíšenými strategiemi, které se používají jako funkce rozdělení pravděpodobnosti hráčů používajících čisté strategie.

Nechat F(x) je distribuční funkce pravděpodobnosti použití čistých strategií hráčem 1. Pokud je číslo E čistou strategií hráče 1, pak F(x) = P(q kde P(q -X)- pravděpodobnost, že náhodně zvolená čistá strategie E nepřekročí X. Podobným způsobem se uvažuje i funkce rozdělení pravděpodobnosti při použití čistých strategií r|. hráč 2: Q(y) = P(g .

Funkce F(x) A Q(y) jsou nazývány smíšené strategie respektive hráči 1 a 2. Pokud FX) A Q(y) jsou diferencovatelné, pak existují jejich deriváty, označované příslušně f(x) A q(y)(funkce hustoty distribuce).

Obecně diferenciál distribuční funkce dF(x) vyjadřuje pravděpodobnost, že strategie S, je mezi tím x E, Stejně tak pro hráče 2: dQ(y) znamená pravděpodobnost, že jeho strategie p je v intervalu y g| y+dy. Poté bude platba hráče 1 provedena Shx, y) dF(x), a platba hráče 2 je Shx, y) dQ(y).

Průměrná výplata hráče 1 vzhledem k tomu, že hráč 2 používá jeho čistou strategii y, lze získat integrací plateb přes všechny možné hodnoty X, těch. v jednotkovém intervalu:

Průměrná výplata hráče 1 za předpokladu, že oba hráči používají své smíšené strategie F(x) A Q(y), budou rovné

Analogicky s maticovými hrami se určují optimální smíšené strategie hráčů a cena hry: pokud dvojice smíšených strategií F*(x) A Q*(y) respektive pro hráče 1 a 2 jsou optimální, pak pro jakékoli smíšené strategie F(x) A Q(y) platí následující vztahy:

Pokud se hráč 1 odchýlí od své strategie F*(x), pak se jeho průměrná výplata nemůže zvýšit, ale může se snížit díky racionálnímu jednání hráče 2. Pokud hráč 2 ustoupí od své smíšené strategie Q*(y), pak se průměrná odměna hráče 1 může zvýšit, ale ne snížit, díky rozumnějším akcím hráče 1. Průměrná odměna E(F*, Q*), obdrží hráč 1, když hráči použijí optimální smíšené strategie, odpovídá ceně hry.

Potom lze spodní cenu nekonečné hry s nulovým součtem řešené ve smíšených strategiích definovat jako v x= kontrola

min E(FQ), a nejvyšší cena hry je jako v 2 = min max E(F, Q).

Q Q f

Pokud takové smíšené strategie existují F* (x) A Q*(y) respektive pro hráče 1 a 2, pro které se spodní a horní cena hry shoduje F*(x) A Q*(y) Optimální smíšené strategie odpovídajících hráčů je přirozené nazývat a v=v x = v 2- za cenu hry.

Na rozdíl od maticových her neexistuje řešení nekonečné hry s nulovým součtem pro každou funkci Psst, uh). Ale teorém byl dokázán, že každá nekonečná hra s nulovým součtem se spojitou výplatní funkcí Psst, uh) na jednotkovém čtverci má řešení (hráči mají optimální smíšené strategie), i když neexistují žádné obecné metody pro řešení nekonečných her s nulovým součtem, včetně kontinuálních her. Nicméně antagonistické nekonečné hry s konvexními a konkávními spojitými výplatními funkcemi (nazývají se resp konvexní A konkávní hry).

Uvažujme řešení her s konvexní výplatní funkcí. Řešení her s konkávní výplatní funkcí je symetrické.

Konvexní funkce/proměnná X na intervalu ( A; b) je funkce, pro kterou platí nerovnost

Kde Xx A x 2 - libovolné dva body z intervalu (a; b);

X.1, A.2 > 0 a +X.2= 1.

Pokud pro / h * 0 D 2 * 0 platí vždy přísná nerovnost

pak se zavolá funkce/ přísně konvexní na; b).

Geometricky konvexní funkce znázorňuje oblouk, jehož graf je umístěn pod tětivou, která jej přepíná. Analyticky konvexita dvakrát diferencovatelné funkce odpovídá nezápornosti (a v případě striktní konvexity pozitivitě) její druhé derivace.

Pro konkávní funkce jsou vlastnosti opačné, pro ně nerovnost /(/4X1 +A.2X2) > Kf(xi) +)-jestliže(x 2) (> s přísnou konkávností) a druhá derivace / "(x)

Je prokázáno, že spojitá a přísně konvexní funkce na uzavřeném intervalu nabývá minimální hodnoty pouze v jednom bodě intervalu. Li ššč, y) je spojitá funkce výher hráče 1 na jednotkovém poli a přísně konvexní podél na pro libovolné x pak existuje jedinečná optimální čistá strategie y=y° e pro hráče 2 je cena hry určena vzorcem

a význam y 0 je definována jako řešení následující rovnice:

Pokud je funkce ššč, y) není v y striktně konvexní, pak hráč 2 nebude mít jedinou optimální čistou strategii.

Symetrická vlastnost platí také pro přísně konkávní funkce. Pokud je funkce ššč, y) je spojitý v obou argumentech a přísně konkávní v x pro libovolné y, pak má hráč 1 jedinečnou optimální strategii.

Cena hry je určena vzorcem

a čistá optimální strategie x 0 hráče 1 je určena z rovnice

Na základě těchto vlastností nekonečných her s nulovým součtem s konvexními nebo konkávními výplatními funkcemi je zkonstruováno obecné schéma řešení takových her na jednotkovém čtverci (хе, уе). Toto schéma uvádíme pouze pro konvexní hry, protože pro konkávní hry je symetrické.

1. Zkontrolujte funkci ššč, y) pro konvexnost v y (druhá parciální derivace musí být větší nebo rovna 0).

2. Určete y 0 ze vztahu proti- min max Psst, uh) jako význam

y, při kterém je dosaženo minimax.

3. Najděte řešení rovnice v = U(x, y 0) a vytvořte dvojice jeho řešení X A x 2, pro který

4. Najděte parametr A z rov.

Parametr A určuje optimální strategii hráče 1 a má význam pravděpodobnosti jeho volby jeho čisté strategie x x. Hodnota 1 - a znamená pravděpodobnost, že hráč 1 zvolí svou čistou strategii x 2.

Ukažme si na příkladu použití tohoto schématu k řešení hry tohoto typu. Nechť je výplatní funkce v nekonečné hře s nulovým součtem dána na jednotkovém čtverci a rovná se Shchh, y) = =(x - y) 2 = x 2 - 2 xy ch-y 2.

1. Tato funkce je nepřetržitá X A y, a proto má tato hra řešení. Funkce Psst, uh) přísně konvexní podél y, protože

Hráč 2 má tedy jedinou čistě optimální strategii 0.

2. Máme proti= min max (x - y) 2. Chcete-li určit maximum (x 2 - 2xy Ch-y 2)

Najděte postupně první a druhou parciální derivaci platební funkce vzhledem k x:

Takže funkce U má minimum pro libovolné y v x=y. To znamená, že jak xy - roste, a jeho maxima by mělo být dosaženo v jednom z krajních bodů x = 0 nebo x = 1. Stanovme hodnoty funkce U v těchto bodech:

Poté zkontrolujte (x - y) 2 = max (y 2; 1 - 2y + y 2). Porovnání "vnitřního"

maxima ve složených závorkách, je to dobře vidět ve 2 > 1 - - 2y+y 2, Li y >*/ 2 a y 2 1 - 2 y+y 2, Li y "/ 2. Toto je názorněji znázorněno v grafu (obr. 2.5).

Rýže. 2.5. Vnitřní maxima platební funkce U(x, y) = (x- na) 2

Proto výraz (x - y) 2 dosáhne svého maxima při x=0, jestliže y > 7 2 a v x= 1 pokud v U 2:

Proto, v= min (min y2; min (1 - y) 2). Každý z

ranních minim je dosaženo v y=*/ 2 a nabývá hodnoty Y 4. Tedy cena hry r = Y 4 a optimální strategie hráče 2:

3. Určete optimální strategii hráče 1 z rovnice U(x, y 0)= proti, těch. pro tuto hru (x - Y 2) 2 = Y 4. Řešení této rovnice JSOU X| =0, x 2 = 1.

Jsou pro ně splněny podmínky

4. Stanovme parametr a, tzn. pravděpodobnost, že hráč 1 použije svou čistou strategii X] = 0. Vytvořme rovnici a-1 + (1 - a) (-1) = 0, z níž a = Y 2. Optimální strategií hráče 1 je tedy zvolit s pravděpodobností své čisté strategie 0 a 1 1 / 2 každý. Problém je vyřešen.

Nejjednodušším případem, podrobně rozvinutým v teorii her, je hra s konečným nulovým součtem párů (antagonická hra dvou osob nebo dvou koalic). Uvažujme hru G, které se účastní dva hráči A a B, kteří mají protichůdné zájmy: zisk jednoho se rovná ztrátě druhého. Jelikož se výplata hráče A rovná výplatě hráče B s opačným znaménkem, může nás zajímat pouze výplata hráče a. Přirozeně A chce maximalizovat a B chce minimalizovat a.

Pro zjednodušení se mentálně ztotožníme s jedním z hráčů (ať je to A) a nazveme ho „my“ a hráče B „soupeřem“ (samozřejmě z toho nevyplývají žádné skutečné výhody pro A). Mějme možné strategie a protivník - možné strategie (takové hře se říká hra). Označme naše výhry, pokud my používáme strategii a soupeř používá strategii

Tabulka 26.1

Předpokládejme, že pro každou dvojici strategií je nám známa výplata (nebo průměrná výplata) a. Pak je v zásadě možné sestavit obdélníkovou tabulku (matici), která uvádí strategie hráčů a odpovídající výplaty (viz tabulka 26.1).

Pokud je taková tabulka sestavena, pak říkají, že hra G byla zredukována na maticovou formu (dovést hru do takové podoby již samo o sobě může být obtížný úkol a někdy téměř nemožný, vzhledem k nesmírné rozmanitosti strategií ). Všimněte si, že pokud je hra zredukována na maticovou formu, pak se vícetahová hra ve skutečnosti zredukuje na hru s jedním tahem – hráč musí provést pouze jeden tah: zvolit strategii. Herní matici stručně označíme

Podívejme se na příklad hry G (4X5) v maticové podobě. Máme k dispozici čtyři strategie (na výběr), zatímco nepřítel má pět strategií. Matice hry je uvedena v tabulce 26.2

Zamysleme se nad tím, jakou strategii bychom měli (hráč A) použít? V Matrixu 26.2 je lákavá výplata "10"; jsme v pokušení zvolit strategii, ve které tuto „lahůdku“ získáme.

Ale počkejte: ani nepřítel není blázen! Zvolíme-li strategii, on, navzdory nám, zvolí strategii a my dostaneme nějakou žalostnou odměnu „1“. Ne, nemůžete zvolit strategii! Jak být? Je zřejmé, že na základě principu opatrnosti (a to je základní princip teorie her) musíme zvolit strategii, při které je náš minimální zisk maximální.

Tabulka 26.2

Toto je takzvaný „princip mini-max“: jednejte tak, abyste při nejhorším chování vašeho soupeře pro vás získali maximální výhru.

Přepišme tabulku 26.2 a do pravého doplňkového sloupce zapišme minimální výherní hodnotu v každém řádku (řádkové minimum); označme to pro řádek a (viz tabulka 26.3).

Tabulka 26.3

Ze všech hodnot (pravý sloupec) je zvýrazněna největší (3). Strategie tomu odpovídá. Volbou této strategie si můžeme být v každém případě jisti, že (za jakékoli chování nepřítele) nevyhrajeme méně než 3. Tato hodnota je naší zaručenou výhrou; Pokud se budeme chovat opatrně, nemůžeme dostat méně než toto, možná dostaneme více).

Tato výhra se nazývá nižší cena hry (neboli „maximin“ - maximum minimálních výher). Budeme jej označovat jako a. V našem případě

Nyní se podívejme na nepřítelův úhel pohledu a jeho důvod. Není to žádný pěšák, ale je také chytrý! Při volbě strategie by chtěl dát méně, ale musí počítat s naším pro něj nejhorším chováním. Pokud zvolí strategii, odpovíme mu a on dá 10; pokud si vybere, my mu odpovíme a on dá atd. Do tabulky 26.3 přidáme další spodní řádek a zapíšeme si do něj maxima sloupců Je zřejmé, že opatrný soupeř by měl zvolit strategii, ve které je tato hodnota minimální (odpovídající hodnota 5 je zvýrazněna v tabulce 26.3) . Tato hodnota P je hodnota zisku, nad kterou nám rozumný protivník jistě nedá. Říká se tomu horní cena hry (neboli „mi-nimax“ - minimum z maximálních výher). V našem příkladu a je dosaženo pomocí strategie nepřítele

Na základě principu opatrnosti (pravidlo zajištění „vždy počítejte s nejhorším!“) tedy musíme zvolit strategii A a nepřítele – strategii Takové strategie se nazývají „minimax“ (podle principu minimax). Dokud se obě strany v našem příkladu budou držet svých minimax strategií, bude to přínosné

Nyní si na chvíli představme, že jsme se dozvěděli, že nepřítel sleduje strategii. Pojď, potrestáme ho za to a zvolíme strategii, dostaneme 5, a to není tak špatné. Ale nepřítel také není selhání; dejte mu vědět, že naše strategie je , bude si také pospíšit s výběrem, sníží naši výhru na 2 atd. (partneři „spěchali se strategiemi“). Stručně řečeno, strategie minimaxu v našem příkladu jsou nestabilní s ohledem na informace o chování druhé strany; tyto strategie nemají vlastnost rovnováhy.

Je tomu tak vždy? Ne vždy. Zvažte příklad s maticí uvedenou v tabulce 26.4.

V tomto příkladu se nižší cena hry rovná horní ceně: . Co z toho vyplývá? Minimax strategie hráčů A a B budou stabilní. Dokud je oba hráči dodržují, je výplata 6. Podívejme se, co se stane, když (A) zjistíme, že soupeř (B) dodržuje strategii B?

Tabulka 26.4

Ale absolutně nic se nezmění, protože jakákoli odchylka od strategie může naši situaci jen zhoršit. Stejně tak informace, které obdrží protivník, ho nedonutí odchýlit se od své strategie Dvojice strategií má vlastnost rovnováhy (vyvážená dvojice strategií) a výplata (v našem případě 6) dosažená touto dvojicí strategií se nazývá „sedlový bod matrice“. Známkou přítomnosti sedlového bodu a vyvážené dvojice strategií je rovnost spodní a horní ceny hry; celková hodnota se nazývá cena hry. Označíme to

Strategie (v tomto případě), kterými je tohoto zisku dosaženo, se nazývají optimální čisté strategie a jejich souhrn se nazývá řešení hry. V tomto případě o hře samotné říkají, že je řešena v čistých strategiích. Oběma stranám A i B lze dát své optimální strategie, ve kterých je jejich pozice nejlepší možná. A pokud hráč A vyhraje 6 a hráč B prohraje, no, toto jsou podmínky hry: jsou výhodné pro A a nevýhodné pro B.

Čtenář může mít otázku: proč se optimální strategie nazývají „čisté“? Když se podíváme trochu dopředu, odpovíme na tuto otázku: existují „smíšené“ strategie, které spočívají v tom, že hráč nepoužívá pouze jednu strategii, ale několik, které je náhodně prolínají. Pokud tedy připustíme kromě čistých i smíšené strategie, každá konečná hra má řešení – rovnovážný bod. Ale o tom se ještě bude diskutovat.

Přítomnost sedlového bodu ve hře není zdaleka pravidlem, ale spíše výjimkou. Většina her nemá sedlový bod. Existuje však typ hry, která má vždy sedlovou pointu, a proto je řešena čistě strategiemi. Jedná se o takzvané „hry s úplnými informacemi“. Hra s kompletními informacemi je hra, ve které každý hráč s každým osobním tahem zná celé pozadí svého vývoje, tedy výsledky všech předchozích tahů, osobních i náhodných. Příklady her s úplnými informacemi zahrnují: dámu, šachy, piškvorky atd.

V teorii her je dokázáno, že každá hra s kompletní informací má sedlový bod, a proto je řešena čistě strategiemi. V každé hře s kompletními informacemi existuje dvojice optimálních strategií, které poskytují stabilní výplatu rovnající se ceně hry a. Pokud se taková hra skládá pouze z osobních tahů, pak když každý hráč použije svou optimální strategii, měla by skončit zcela jednoznačně – výhrou rovnající se ceně hry. To znamená, že pokud je známé řešení hry, hra samotná ztrácí smysl!

Vezměme si základní příklad hry s úplnými informacemi: dva hráči střídavě pokládají nikláky na kulatý stůl, náhodně volí polohu středu mince (vzájemné překrývání mincí není povoleno). Vyhrává ten, kdo vloží poslední nikl (když nezbyde místo pro ostatní). Je snadné vidět, že výsledek této hry je v podstatě předem daný. Existuje určitá strategie, která zajišťuje, že hráč, který umístí minci jako první, vyhraje.

Konkrétně musí nejprve umístit nikl do středu stolu a poté reagovat na každý soupeřův tah symetrickým pohybem. Je zřejmé, že bez ohledu na to, jak se nepřítel chová, nemůže se vyhnout prohře. Úplně stejná situace je u šachů a her obecně s úplnými informacemi: kterákoli z nich, napsaná v maticové formě, má sedlový bod, což znamená, že řešení je v čistých strategiích, a proto má smysl pouze do té doby, dokud toto řešení nenajde. Řekněme, že šachová partie buď vždy skončí výhrou bílého, nebo vždy výhrou černého, ​​nebo vždy remízou, ale zatím nevíme co přesně (naštěstí pro milovníky šachu). Ještě dodejme: v dohledné době se to pravděpodobně nedozvíme, protože počet strategií je tak obrovský, že je nesmírně obtížné (ne-li nemožné) dovést hru do matrixové podoby a najít v ní sedlový bod.

Nyní si položme otázku, co dělat, když hra nemá sedlovou pointu: No, pokud je každý hráč nucen zvolit jednu jedinou čistou strategii, pak není co dělat: musíme se řídit principem minimaxu. Jiná věc je, jestli můžete své strategie „míchat“, náhodně je střídat s určitou pravděpodobností. Použití smíšených strategií je myšleno tímto způsobem: hra se mnohokrát opakuje; před každou hrou hry, kdy je hráč na osobním tahu, „svěří“ svou volbu náhodě, „hodí losy“ a zvolí strategii, která přišla (jak uspořádat los již víme z předchozí kapitoly ).

Smíšené strategie v teorii her jsou modelem proměnlivé, flexibilní taktiky, kdy nikdo z hráčů neví, jak se v dané hře zachová soupeř. Tato taktika (ačkoli obvykle bez jakéhokoli matematického zdůvodnění) se často používá v karetních hrách. Zároveň podotýkáme, že nejlepší způsob, jak skrýt své chování před nepřítelem, je dát mu náhodný charakter, a tedy nevědět předem, co uděláte.

Pojďme se tedy bavit o smíšených strategiích. Budeme označovat smíšené strategie hráčů A a B, kde (tvoří celkem jednu) - pravděpodobnost, že hráč A použije strategie - pravděpodobnost, že hráč B použije strategie

Ve speciálním případě, kdy jsou všechny pravděpodobnosti kromě jedné rovny nule a tato je rovna jedné, se smíšená strategie změní na čistou.

Existuje základní teorém teorie her: každá konečná hra s nulovým součtem pro dvě osoby má alespoň jedno řešení – dvojici optimálních strategií, obecně smíšených, a odpovídající cenu.

Dvojice optimálních strategií, které tvoří řešení hry, má následující vlastnost: pokud jeden z hráčů dodržuje svou optimální strategii, nemůže být pro druhého výhodné odchýlit se od té jeho. Tato dvojice strategií tvoří určitou rovnovážnou pozici ve hře: jeden hráč chce proměnit zisk na maximum, druhý na minimum, každý táhne svým směrem a při rozumném chování obou rovnovážný a stabilní zisk v jsou založeny. Pokud je tedy hra pro nás prospěšná, pokud - pro nepřítele; když je hra „férová“, stejně výhodná pro oba účastníky.

Uvažujme příklad hry bez sedlového bodu a uveďme (bez důkazu) její řešení. Hra je následující: dva hráči A a B současně a beze slova ukážou jeden, dva nebo tři prsty. O výhrách rozhoduje celkový počet prstů: pokud je sudý, vyhrává A a dostává od B částku rovnající se tomuto číslu; pokud je lichá, pak naopak A zaplatí B částku rovnající se tomuto číslu. Co by měli hráči dělat?

Vytvořme herní matici. V jedné hře má každý hráč tři strategie: ukázat jeden, dva nebo tři prsty. Matice 3x3 je uvedena v tabulce 26.5; další pravý sloupec zobrazuje minima řádku a další spodní řádek zobrazuje maxima sloupců.

Nižší cena hry odpovídá strategii.To znamená, že při rozumném, opatrném chování garantujeme, že neprohrajeme více než 3. Malá útěcha, ale pořád lepší než řekněme výhra 5, nalezená v některých buňkách matice. Je to pro nás špatné, hráč L... Ale utěšme se: pozice nepřítele se zdá být ještě horší: nižší cena hry. rozumné chování nám dá alespoň 4.

Rozhodovací problém, posuzovaný v rámci systémového přístupu, obsahuje tři hlavní složky: rozlišuje systém, řídicí subsystém a prostředí. Nyní přejdeme ke studiu rozhodovacích problémů, ve kterých je systém ovlivňován ne jedním, ale několika řídicími subsystémy, z nichž každý má své vlastní cíle a možnosti působení. Tento přístup k rozhodování se nazývá herní teoretický a matematické modely odpovídajících interakcí se nazývají hry. Vzhledem k rozdílům v cílech řídicích subsystémů, jakož i určitým omezením možnosti výměny informací mezi nimi, jsou tyto interakce konfliktního charakteru. Proto je každá hra matematickým modelem konfliktu. Omezme se na případ, kdy existují dva řídicí subsystémy. Pokud jsou cíle systémů opačné, konflikt se nazývá antagonistický a matematický model takového konfliktu se nazývá antagonistická hra..

V herně teoretické terminologii se nazývá 1. řídicí subsystém hráč 1, 2. řídící subsystém - hráč 2, sady

jejich alternativní akce se nazývají sady strategií tito hráči. Nechat X- mnoho strategií pro hráče 1, Y- mnoho strategií

hráč 2. Stav systému je jednoznačně určen volbou kontrolních akcí subsystémy 1 a 2, tedy volbou strategií

X∈X A y∈Y. Nechat F(X,y) - posouzení užitečnosti pro hráče 1 tohoto státu

systém, do kterého jde, když si hráč zvolí 1 strategii X A

strategie hráče 2 na. Číslo F(X,y) je nazýván vyhrát hráč 1 v situaci ( X,y) a funkci F- výplatní funkce hráče 1. Výhry hráče

1 je současně ztráta hráče 2, tedy hodnota, kterou se první hráč snaží zvýšit, a druhý – snížit. Tak to je

projev antagonistického charakteru konfliktu: zájmy hráčů jsou zcela opačné (co jeden vyhraje, druhý prohraje).

Antagonistická hra je přirozeně definována systémem G=(X, Y, F).

Všimněte si, že formálně je hra s nulovým součtem nastavena prakticky stejným způsobem jako rozhodovací úloha za podmínek nejistoty – pokud

identifikovat řídicí subsystém 2 s prostředím. Podstatný rozdíl mezi řídicím subsystémem a prostředím je v tom

chování prvního je účelové. Máme-li při sestavování matematického modelu skutečného konfliktu důvod (či záměr) považovat prostředí za nepřítele, jehož cílem je přinášet

nám maximálně uškodí, pak může být taková situace prezentována formou antagonistické hry. Jinými slovy, hru s nulovým součtem lze interpretovat jako extrémní případ ZPR za podmínek nejistoty,

charakterizované tím, že zachází s životním prostředím jako s protivníkem s cílem. Zároveň musíme omezit typy hypotéz o chování okolí.

Nejopodstatněnější je zde hypotéza krajní opatrnosti, kdy při rozhodování počítáme s nejhorším možným postupem pro nás ze strany okolí.

Definice. Li X A Y jsou konečné, pak se antagonistická hra nazývá maticová hra. V maticové hře to můžeme předpokládat X={1,…,n},

Y={1,…,m) a dát aij=F(i,j). Maticová hra je tedy zcela určena matricí A=(aij), i=1,…,n, j=1,…,m.

Příklad 3.1. Hra dvěma prsty.

Dva lidé současně ukazují jeden nebo dva prsty a volají na číslo 1 nebo 2, což podle mluvčího znamená číslo

prsty ukázané ostatním. Po ukázání prstů a pojmenování čísel se výhry rozdělí podle následujících pravidel:

pokud oba uhodli nebo oba neuhodli, kolik prstů jejich soupeř ukázal, výhry všech jsou nulové; pokud uhodl pouze jeden, pak soupeř zaplatí tipujícímu částku peněz úměrnou celkovému zobrazenému počtu

Toto je maticová hra s nulovým součtem. Každý hráč má čtyři strategie: 1- ukaž 1 prst a zavolej 1, 2- ukaž 1 prst a zavolej 2, 3-

ukaž 2 prsty a zavolej 1, 4 - ukaž 2 prsty a zavolej 2. Poté výplatní matice A=(aij), i= 1,…, 4, j= 1,…, 4 je definován takto:

a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 v ostatních případech.

Příklad 3.2. Hra typu diskrétního souboje.

Problémy typu souboje popisují například boj dvou hráčů,

každý z nich chce provést nějakou jednorázovou akci (uvolnění šarže zboží na trh, podání žádosti o nákup v aukci) a zvolí si k tomu čas. Nechte hráče postupovat směrem k sobě n kroky. Po každém provedeném kroku si hráč může vybrat, zda bude na nepřítele střílet nebo ne. Každý může mít pouze jeden výstřel. Předpokládá se, že pravděpodobnost zasažení nepřítele, pokud postoupíte k n = 5 má tvar

Odeslat svou dobrou práci do znalostní báze je jednoduché. Použijte níže uvedený formulář

Studenti, postgraduální studenti, mladí vědci, kteří využívají znalostní základnu ve svém studiu a práci, vám budou velmi vděční.

Úvod

1. Teoretická část

1.3 Pořadí hry 2x2

1.4 Algebraická metoda

1.5 Grafická metoda

1.6 Hry 2xn nebo mx2

1.7 Řešení her maticovou metodou

2. Praktická část

2.2 Hry 2xn a mx2

2.3 Maticová metoda

2.4 Hnědá metoda

Analýza výsledků

Úvod

Hra s nulovým součtem je hra s nulovým součtem. Hra s nulovým součtem je nekooperativní hra zahrnující dva hráče, jejichž výplaty jsou opačné.

Formálně může být antagonistická hra reprezentována trojkou , kde X a Y jsou množiny strategií prvního a druhého hráče, F je výplatní funkce prvního hráče, přiřazující každé dvojici strategií (x,y), kde reálné číslo odpovídající užitku prvním hráčem při realizaci dané situace.

Protože zájmy hráčů jsou opačné, funkce F zároveň představuje ztrátu druhého hráče.

Historicky jsou hry s nulovým součtem první třídou modelů matematické teorie her, kterými byl hazard popsán. Předpokládá se, že tento předmět studia je místem, kde teorie her získala své jméno. V dnešní době jsou antagonistické hry považovány za součást širší třídy nekooperativních her.

1. Teoretická část

1.1 Základní definice a ustanovení hry

Hra se vyznačuje systémem pravidel, která určují počet účastníků hry, jejich možné akce a rozdělení výher v závislosti na jejich chování a výsledcích. Za hráče se považuje jeden účastník nebo skupina účastníků hry, kteří mají nějaké společné zájmy, které se neslučují se zájmy jiných skupin. Ne každý účastník je tedy považován za hráče.

Pravidla nebo podmínky hry určují možné chování, volby a pohyby hráčů v jakékoli fázi vývoje hry. Vybrat si pro hráče znamená vybrat si jednu z možností jeho chování. Tyto volby pak hráč provádí pomocí tahů. Udělat tah znamená v určité fázi hry provést celou volbu nebo její část najednou, v závislosti na možnostech poskytovaných pravidly hry. Každý hráč v určité fázi hry provede tah podle provedené volby. Druhý hráč, který ví nebo neví o volbě prvního hráče, také provede tah. Každý hráč se snaží zohlednit informace o minulém vývoji hry, pokud takovou možnost pravidla hry připouštějí.

Soubor pravidel, která hráči jasně naznačují, jakou volbu musí při každém tahu provést v závislosti na situaci, která v důsledku hry nastane, se nazývá strategie hráče. Strategie v teorii her znamená určitý ucelený akční plán pro hráče, ukazující, jak by měl jednat ve všech možných případech vývoje hry. Strategie znamená souhrn všech pokynů pro jakýkoli stav informací, které má hráč k dispozici v jakékoli fázi vývoje hry. Již z toho je jasné, že strategie mohou být dobré i špatné, úspěšné i neúspěšné atp.

Hra s nulovým součtem bude, když se součet výher všech hráčů v každé z jejích her rovná nule, tj. ve hře s nulovým součtem se celkový kapitál všech hráčů nemění, ale je přerozdělován mezi hráče. v závislosti na výsledných výsledcích. Na mnohé ekonomické a vojenské situace lze tedy pohlížet jako na hry s nulovým součtem.

Zejména hra s nulovým součtem mezi dvěma hráči se nazývá antagonistická, protože cíle hráčů v ní jsou přímo opačné: zisk jednoho hráče nastává pouze na úkor ztráty druhého.

1.1.1 Definice, příklady a řešení maticových her v čistých strategiích

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

První hráč má t strategií i =1, 2,…, t, druhý má n strategií j = 1, 2,…, p. Každá dvojice strategií (i, j) je spojena s číslem a ij , vyjadřujícím výhry prvního hráče připadající druhému hráči, pokud první hráč použije svou i-tou strategii, a druhý hráč použije svou j-tou strategii.

Každý hráč provede jeden tah: první hráč zvolí svou i-tou strategii (i = 1, 2,..., m), druhý zvolí svou j-tou strategii (j = 1, 2,..., n) , po kterém první hráč obdrží výhru a ij na úkor druhého hráče (pokud je ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Každá strategie hráče i = 1, 2,…, t; j = 1, 2,…, n se často nazývá čistá strategie.

Maticová hra pro dva hráče s nulovým součtem bude od nynějška jednoduše nazývána maticová hra. Je zřejmé, že matrixová hra patří k antagonistickým hrám. Z jeho definice vyplývá, že k definování maticové hry stačí zadat matici A = (a ij) v řádu výplat prvního hráče.

Pokud vezmeme v úvahu výplatní matici

poté je hraní každé hry maticové hry s maticí A omezeno na výběr prvního hráče i-té řady a druhého hráče j-tého sloupce a prvního hráče, který obdrží (na úkor druhého ) výhry umístěné v matici A na průsečíku i-tého řádku a j-tého sloupce.

Pro formalizaci skutečné konfliktní situace ve formě maticové hry je nutné identifikovat a přečíslovat čisté strategie každého hráče a vytvořit výplatní matici.

Další fází je stanovení optimálních strategií a výher hráčů.

Hlavní věcí při studiu her je koncept optimálních strategií hráčů. Tento koncept má intuitivně následující význam: strategie hráče je optimální, pokud mu použití této strategie poskytuje největší zaručenou výhru ze všech možných strategií druhého hráče. Na základě těchto pozic první hráč zkoumá matici A svých výplat pomocí vzorce (1.1) takto: pro každou hodnotu i (i = 1, 2,..., t) je určena minimální hodnota výplaty v závislosti na strategie používané druhým hráčem

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

tj. určí se minimální výplata pro prvního hráče za předpokladu, že uplatní svou i -tou čistou strategii, pak se z těchto minimálních výplat najde strategie i = i 0, pro kterou bude tato minimální výplata maximální, tzn.

Definice. Číslo b, určené vzorcem (1.3), se nazývá nižší čistá cena hry a ukazuje, jaké minimální výhry si první hráč může zaručit tím, že uplatní své čisté strategie pro všechny možné akce druhého hráče.

Druhý hráč by se svým optimálním chováním měl snažit pokud možno prostřednictvím svých strategií minimalizovat výhry prvního hráče. Proto pro druhého hráče najdeme

tj. je stanovena maximální výplata prvního hráče za předpokladu, že druhý hráč použije svou j-tou čistou strategii, pak druhý hráč najde svou strategii j = j 1, podle které první hráč obdrží minimální výplatu, tj.

Definice. Číslo b, určené vzorcem (1.5), se nazývá čistá horní cena hry a ukazuje, jaké maximální výhry si první hráč může svými strategiemi zaručit. Jinými slovy, použitím svých čistých strategií může první hráč zajistit výplatu ne menší než b, a druhý hráč použitím svých čistých strategií může zabránit tomu, aby první hráč vyhrál více než b.

Definice. Pokud se ve hře s maticí A spodní a horní čisté ceny hry shodují, tj. b = c, pak se říká, že tato hra má sedlový bod v čistých strategiích a čistou cenu hry:

n = b = v (1,6)

Sedlový bod je dvojice čistých strategií () prvního a druhého hráče, při kterých je dosaženo rovnosti

Pojem sedlového bodu má následující význam: pokud jeden z hráčů dodržuje strategii odpovídající sedlovému bodu, pak druhý hráč nemůže udělat lépe, než dodržovat strategii odpovídající sedlovému bodu. S ohledem na to, že nejlepší chování hráče by nemělo vést ke snížení jeho výher a nejhorší chování může vést ke snížení jeho výher, lze tyto podmínky zapsat matematicky ve formě následujících vztahů:

kde i, j jsou libovolné čisté strategie prvního a druhého hráče; (i 0 , j 0) jsou strategie, které tvoří sedlový bod. Níže si ukážeme, že definice sedlového bodu je ekvivalentní podmínkám (1.8).

Na základě (1.8) je tedy sedlový prvek minimální v i 0. řádku a maximální v j 0. sloupci matice A. Nalezení sedlového bodu matice A je snadné: v matici A se minimální prvek postupně nalézá v každý řádek a zkontrolujte, zda je tento prvek v jeho sloupci maximum. Je-li takový, pak se jedná o sedlový prvek a jemu odpovídající dvojice strategií tvoří sedlový bod. Dvojice čistých strategií (i 0 , j 0) prvního a druhého hráče, tvořící sedlový bod a sedlový prvek, se nazývá řešením hry.

Čisté strategie i 0 a j 0 tvořící sedlový bod se nazývají optimální čisté strategie prvního a druhého hráče.

Věta 1. Nechť f (x, y) je reálná funkce dvou proměnných x A a y B a existuje

pak b = c.

Důkaz. Z definice minima a maxima vyplývá, že

Protože na levé straně (1.11) je x libovolné, pak

Na pravé straně nerovnosti (1.12) je tedy y libovolné

Q.E.D.

Konkrétně matice () je speciální případ funkce f (x, y), tj. pokud položíme x = i, y = j, = f (x, y), pak z věty 1 dostaneme, že dolní síť cena nepřesahuje horní čistou cenu hry v maticové hře.

Definice. Nechť f (x, y) je reálná funkce dvou proměnných x A a y B. Bod (x 0, y 0) se nazývá sedlový bod pro funkci f (x, y), pokud jsou splněny následující nerovnosti

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

pro libovolné x A a y B.

1.2 Optimální smíšené strategie a jejich vlastnosti

Studium maticové hry začíná nalezením jejího sedla v čistých strategiích. Pokud má maticová hra sedlový bod v čistých strategiích, pak studium hry končí nalezením tohoto bodu. Pokud v maticové hře není žádný sedlový bod v čistých strategiích, pak lze najít spodní a horní čisté ceny této hry, které naznačují, že první hráč by neměl doufat, že vyhraje více, než je horní cena hry, a může buďte si jisti, že dostanete výhru, neméně nižší cenu hry. Taková doporučení týkající se chování hráčů v maticové hře bez sedlového bodu v čistých strategiích nemohou uspokojit výzkumníky a praktiky. Zlepšení řešení maticových her je třeba hledat ve využití utajení používání čistých strategií a možnosti mnohonásobného opakování her formou her. Hraje se tedy například série her šachy, dáma a fotbal a pokaždé hráči uplatňují své strategie tak, že o jejich obsahu nemají soupeři ani ponětí, a touto cestou v průměru dosáhnout určitých výher hraním celé série her. Tyto výhry jsou v průměru vyšší než nižší cena hry a nižší než horní cena hry. Čím vyšší je tato průměrná hodnota, tím lepší strategii hráč používá. Proto vznikl nápad aplikovat čisté strategie náhodně, s určitou pravděpodobností. Tím je zcela zajištěno utajení jejich použití. Každý hráč může změnit pravděpodobnost použití svých čistých strategií tak, aby maximalizoval svou průměrnou výplatu a získal optimální strategie. Tato myšlenka vedla ke konceptu smíšené strategie.

Definice. Hráčova smíšená strategie je úplný soubor pravděpodobností použití jeho čistých strategií.

Pokud má tedy první hráč m čistých strategií 1, 2, … i, … m, pak jeho smíšená strategie x je množina čísel x = (x 1, x 2, ..., x i,…, x m ) vyhovujících vztahy

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

Podobně pro druhého hráče, který má n čistých strategií, je smíšená strategie y množinou čísel y = (y 1, ..., y j, ... y n) splňujících vztahy

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

Protože pokaždé, když hráč použije jednu čistou strategii, vylučuje použití jiné, čisté strategie jsou neslučitelné události. Navíc jsou to jediné možné události.

Je zřejmé, že čistá strategie je zvláštním případem smíšené strategie. Pokud se totiž ve smíšené strategii použije jakákoli i-tá čistá strategie s pravděpodobností jedna, pak se všechny ostatní čisté strategie nepoužijí. A tato i-tá čistá strategie je zvláštním případem smíšené strategie. Pro zachování utajení uplatňuje každý hráč své vlastní strategie bez ohledu na volby druhého hráče.

Definice. Průměrná výplata prvního hráče v maticové hře s maticí A je vyjádřena jako matematické očekávání jeho výplat.

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

Je zřejmé, že průměrná výplata prvního hráče je funkcí dvou sad proměnných x a y. První hráč se snaží změnou svých smíšených strategií x maximalizovat svůj průměrný výnos E (A, x, y) a druhý hráč se prostřednictvím svých smíšených strategií snaží o to, aby E (A, x, y) byl minimální, tzn. Pro vyřešení hry je nutné najít takové x, y, při kterých je dosaženo horní ceny hry.

1.3 Hra o pořadí 22

Maticová hra pořadí 22 je dána následující výplatní maticí pro prvního hráče:

Řešení této hry by mělo začít nalezením sedlového bodu v čistých strategiích. Chcete-li to provést, najděte minimální prvek v prvním řádku a zkontrolujte, zda je v jeho sloupci maximum. Pokud takový prvek není nalezen, pak se stejným způsobem zkontroluje druhý řádek. Pokud je takový prvek nalezen ve druhém řádku, pak se jedná o sedlo.

Nalezení sedlového prvku, pokud existuje, ukončuje proces hledání jeho řešení, neboť v tomto případě byla nalezena cena hry — sedlový prvek a sedlový bod, tedy dvojice čistých strategií pro první a. druhého hráče, což představuje optimální čisté strategie. Pokud v čistých strategiích žádný sedlový bod neexistuje, pak musíme ve smíšených strategiích najít sedlový bod, který nutně existuje podle hlavní věty maticových her.

Označme x = (x 1 , x 2), y = (y 1 , y 2) smíšené strategie prvního a druhého hráče. Připomeňme, že x 1 znamená pravděpodobnost, že první hráč použije svou první strategii, a x 2 = 1 - x 1 je pravděpodobnost, že použije svou druhou strategii. Podobně pro druhého hráče: 1 je pravděpodobnost, že použije první strategii, 2 = 1 - 1 je pravděpodobnost, že použije druhou strategii.

Podle důsledků věty, aby smíšené strategie x a y byly optimální, je nutné a postačující, aby pro nezáporné x 1, x 2, y 1, y 2 platily následující vztahy:

Ukažme si nyní, že pokud maticová hra nemá sedlový bod v čistých strategiích, pak se tyto nerovnosti musí proměnit v rovnosti:

Vskutku. Ať hra nemá sedlový bod v čistých strategiích, pak optimální hodnoty smíšených strategií uspokojí nerovnosti

0<<1, 0<< 1,

0< <1, 01. (1.25)

Předpokládejme, že obě nerovnosti z (1.22) jsou striktní

pak podle věty y 1 = y 2 = 0, což odporuje podmínkám (1.25).

Podobně je dokázáno, že obě nerovnosti z (1,23) nemohou být striktními nerovnostmi.

Předpokládejme nyní, že jedna z nerovností (1.22) může být přísná, například první

To znamená, že podle věty y 1 = 0, y 2 = 1. Následně z (1.23) dostáváme

Jsou-li obě nerovnosti (1.24) striktní, pak podle věty x 1 = x 2 = 0, což je v rozporu s (1.25). Pokud je 12 a 22, pak jedna z nerovností (1,27) je přísná a druhá je rovnost. Kromě toho bude rovnost platit pro větší prvek 12 a 22, tj. jedna nerovnost z (1.27) musí být přísná. Například 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Ukazuje se tedy, že pokud maticová hra nemá sedlový bod v čistých strategiích, pak pro optimální strategie prvního hráče se nerovnosti (1,22) promění v rovnosti. Podobná úvaha ohledně nerovností (1.23) povede k tomu, že v tomto případě musí být nerovnostmi (1.23) rovnost.

Pokud tedy maticová hra řádu 22 nemá sedlový bod, lze optimální smíšené strategie hráčů a cenu hry určit řešením soustavy rovnic (1.24). Bylo také zjištěno, že pokud má v maticové hře pořadí 2x2 jeden z hráčů optimální čistou strategii, pak má i druhý hráč optimální čistou strategii.

Pokud tedy maticová hra nemá sedlový bod v čistých strategiích, musí mít řešení ve smíšených strategiích, které jsou určeny z rovnic (1.24). Řešení soustavy (1.25)

1.4 Algebraická metoda

Existují dva možné případy řešení problémů pomocí algebraické metody:

1. matrice má sedlový hrot;

2. matrice nemá sedlový hrot.

V prvním případě je řešením dvojice strategií, které tvoří sedlovou pointu hry. Podívejme se na druhý případ. Zde je třeba hledat řešení ve smíšených strategiích:

Pojďme najít strategie a... Když první hráč použije svou optimální strategii, může druhý hráč použít například dvě takové čisté strategie

Navíc díky této vlastnosti, pokud jeden z hráčů používá optimální smíšenou strategii a druhý používá jakoukoli čistou strategii zahrnutou v jeho optimální smíšené strategii s pravděpodobností ne rovnou nule, pak matematické očekávání výhry zůstává vždy nezměněné a stejné. k ceně hry, tzn.

Výhry se v každém z těchto případů musí rovnat ceně hry V. V tomto případě platí následující vztahy:

Pro optimální strategii druhého hráče lze sestavit systém rovnic podobných (2.5), (2.6):

S ohledem na normalizační podmínky:

Pojďme řešit rovnici (1,37) - (1,41) společně s ohledem na neznámé, můžete řešit ne všechny najednou, ale tři najednou: samostatně (1,36), (1,38), (1,40) a (1,37), ( 1,39), (1,41). V důsledku řešení dostaneme:

1.5 Grafická metoda

Přibližné řešení hry 22 lze získat zcela jednoduše pomocí grafické metody. Jeho podstata je následující:

Obrázek 1.1 - nalezení úseku jednotkové délky

Vyberte část jednotky délky na ose x. Levý konec bude zobrazovat první strategii prvního hráče a pravý konec bude představovat druhou. Všechny mezilehlé body odpovídají smíšeným strategiím prvního hráče a délka segmentu napravo od bodu se rovná pravděpodobnosti použití první strategie a délka segmentu nalevo je pravděpodobnost použití druhá strategie prvním hráčem.

Jsou nakresleny dvě osy I-I a II-II. Výhry vložíme na I-I, když první hráč použije první strategii, na II-II, když použije druhou strategii. Nechť například druhý hráč použije svou první strategii, pak by měla být hodnota vynesena na ose I-I a hodnota by měla být vynesena na ose II-II.

U jakékoli smíšené strategie prvního hráče bude jeho výplata určena hodnotou segmentu. Linie I-I odpovídá aplikaci první strategie druhým hráčem, budeme ji nazývat první strategií druhého hráče. Podobně můžete postavit druhou strategii druhého hráče. Potom bude mít grafické zobrazení herní matice obecně následující podobu:

Obrázek 1.2 - zjištění ceny hry

Nutno však podotknout, že tato konstrukce byla provedena pro prvního hráče. Zde se délka segmentu rovná ceně hry V.

Linie 1N2 se nazývá spodní výherní limit. Zde jasně vidíte, že bod N odpovídá maximální výši zaručené výhry prvního hráče.

Obecně lze říci, že z tohoto obrázku lze také určit strategii druhého hráče, například následujícími způsoby. Na ose I-I:

nebo na ose II-II

Strategie druhého hráče se však dá určit podobně, jako se to dělá u prvního hráče, tzn. vytvořit takový graf.

Obrázek 1.3 - určení strategie druhého hráče

Zde je čára 1N2 horní hranicí ztráty. Bod N odpovídá minimální možné ztrátě druhého hráče a určuje strategii.

V závislosti na konkrétních hodnotách maticových koeficientů mohou mít grafy různou formu, například:

Obrázek 1.4 - určuje optimální strategii prvního hráče

V takové situaci je optimální strategie prvního hráče čistá:

1.6 Hry 2n nebo m2

Ve hrách řádu 2n má první hráč 2 čisté strategie a druhý hráč má n čistých strategií, tzn. Výplatní matice prvního hráče má tvar:

Pokud má taková hra sedlový bod, je snadné jej najít a získat řešení.

Předpokládejme, že hra má sedlové body. Pak je třeba najít takové smíšené strategie a podle toho prvního a druhého hráče a cenu hry v, které splňují vztahy:

Protože hra nemá sedlový bod, nerovnost (1,54) je nahrazena nerovnostmi

Pro řešení soustav (1.56), (1.55), (1.53) je vhodné použít grafickou metodu. Za tímto účelem zavedeme zápis pro levou stranu nerovnosti (1.53)

matematický model maticové hry

nebo položením z (1.55) a provedením jednoduchých transformací dostaneme

kde je průměrná výplata prvního hráče za předpokladu, že používá svou smíšenou strategii, a druhého jeho j-té čisté strategie.

Podle výrazu každá hodnota j=1, 2, …, n odpovídá přímce v pravoúhlém souřadnicovém systému.

Cílem druhého hráče je minimalizovat výhru prvního hráče volbou jeho strategií. Proto počítáme

kde je spodní hranice množiny omezení. Na obrázku 1.6 je graf funkce znázorněn tlustou čarou.

Zveřejněno na http://www.allbest.ru/

Obrázek 1.6 - graf funkce

Cílem prvního hráče je maximalizovat svou výhru prostřednictvím výběru, tzn. vypočítat

Na obrázku 1.6 tečka znamená maximální hodnotu, která je získána při. Cena hry je proto, že:

Tímto způsobem se graficky určí optimální smíšená strategie prvního hráče a dvojice čistých strategií druhého hráče, které v průsečíku tvoří bod Obrázek 1.6 ukazuje 2. a 3. strategii druhého hráče. U takových strategií se nerovnosti (1,53) promění v rovnost. Na obrázku 1.6 jsou to strategie j=2, j=3.

Nyní můžeme vyřešit soustavu rovnic

a přesně určit hodnoty a (graficky jsou určeny přibližně). Poté zadáním všech hodnot pro ty j, pro které netvoří bod, vyřešíme soustavu rovnic (1.56) Pro příklad zobrazený na obrázku 1.6 se jedná o následující soustavu:

a zbytek Tento systém lze řešit šikmo Pokud pro nějaké j=j 0 strategie druhého hráče tvoří bod M 0 a pak maximální hodnota spodní hranice množin omezení je znázorněna úsečkou rovnoběžnou s osa V tomto případě má první hráč nekonečně mnoho optimálních hodnot a ceny hry Tento případ je znázorněn na obrázku 1.7, kde segment MN znázorňuje horní meze, optimální hodnoty jsou v mezích Druhý hráč má čistě optimální strategii j=j 0 .

Maticové hry řádu m2 lze řešit i grafickou metodou. Výplatní matice prvního hráče má v tomto případě tvar

Smíšené strategie prvního a druhého hráče jsou definovány podobně jako v případě her řádu 2n. Nechť je na vodorovné ose vynesena hodnota od 0 do 1 a na svislé ose hodnota průměrné výhry) prvního hráče za podmínky, že první hráč použije svou čistou i-tou strategii (i=1, 2, ..., m), druhý - jeho smíšená strategie (y 1, 1- y 1) =y. Například, když m=4 graficky) lze znázornit, jak je znázorněno na obrázku 1.7.

Obrázek 1.7 - funkční graf)

První hráč se snaží maximalizovat svou průměrnou výplatu, a tak se snaží najít

Funkce je znázorněna tlustou čarou a představuje horní hranici sady omezení. Druhý hráč se snaží minimalizovat volbou své strategie, tzn. hodnota odpovídá

Na obrázku je hodnota označena tečkou. Jinými slovy, dvě strategie prvního hráče a pravděpodobnost pro druhého hráče jsou určeny, při kterých je dosaženo rovnosti

Z obrázku vidíme, že cena hry je pořadnicí bodu, pravděpodobnost je úsečkou bodu. Pro zbývající čisté strategie prvního hráče v optimální smíšené strategii musí ().

Řešením (1.69) tak získáme optimální strategii druhého hráče a cenu hry. Optimální smíšenou strategii pro prvního hráče najdeme řešením následující soustavy rovnic:

1.7 Maticová metoda řešení her

Označení:

Libovolná čtvercová podmatice matice objednávky

Matice(1);

Matice transponovaná do;

Matice přiléhající k B;

- (1) matici získanou z X vymazáním prvků, které odpovídají řádkům vymazaným z po přijetí;

- (1) matici získanou vymazáním prvků, které odpovídají řádkům, které byly po obdržení odstraněny.

Algoritmus:

1. Vyberte čtvercovou podmatici matice řádu () a vypočítejte

2. Pokud nějaké nebo, pak nalezenou matici zahoďte a zkuste jinou matici.

3. Jestliže (), (), vypočítáme a sestrojíme X a z a, přičemž na příslušných místech přidáme nuly.

Kontrola, zda jsou nerovnosti splněny

pro všechny (1,75)

a nerovnosti

pro všechny (1,76)

Pokud jeden ze vztahů není spokojený, zkusíme další. Pokud jsou všechny vztahy platné, pak X a požadovaná řešení.

1.8 Metoda postupného přibližování ceny hry

Při studiu herních situací se často může stát, že není potřeba získat přesné řešení hry nebo je z nějakého důvodu nemožné či velmi obtížné zjistit přesnou hodnotu ceny hry a optimální smíšené strategie. Pak můžete použít přibližné metody pro řešení maticové hry.

Popišme si jednu z těchto metod - metodu postupného přibližování ceny hry. Počet vypočítaný při použití metody se zvyšuje přibližně úměrně počtu řádků a sloupců výplatní matice.

Podstata metody je následující: hra se hraje mentálně mnohokrát, tzn. postupně si hráč v každé hře vybere strategii, která mu dává největší celkové (celkové) výhry.

Po takové implementaci některých her se vypočítá průměrná hodnota výher prvního hráče a proher druhého hráče a jejich aritmetický průměr se vezme jako přibližná hodnota nákladů na hru. Metoda umožňuje najít přibližnou hodnotu optimálních smíšených strategií obou hráčů: je nutné vypočítat frekvenci aplikace každé čisté strategie a vzít ji jako přibližnou hodnotu v optimální smíšené strategii příslušného hráče.

Prokazatelně se při neomezeném nárůstu počtu programových her bude průměrný zisk prvního hráče a průměrná ztráta druhého hráče neomezeně blížit ceně hry a přibližné hodnoty smíšených strategií v případ, kdy má hra jedinečné řešení, bude inklinovat k optimální smíšené strategii každého hráče. Obecně řečeno, tendence přibližných hodnot nad těmito hodnotami přiblížit se skutečným hodnotám je pomalá. Tento proces je však snadno mechanizovatelný a pomáhá tak získat řešení hry s požadovaným stupněm přesnosti i s výplatními maticemi relativně velkého řádu.

2. Praktická část

Pár se rozhodne, kam se půjde projít a strávit čas užitečně pro oba.

Dívka se rozhodne jít na procházku do parku na čerstvý vzduch a večer se podívat na film v nejbližším kině.

Chlápek navrhuje jít do technologického parku a pak sledovat zápas místních klubových fotbalistů na centrálním stadionu.

V souladu s tím musíte zjistit, jak dlouho bude trvat dosažení cíle jednoho z hráčů. Vítězná matice bude vypadat takto:

Tabulka 1. Výplatní matice

Strategie

Od roku 1 2 Tato hra zjevně nemá sedlový bod v čistých strategiích. Proto použijeme následující vzorce a dostaneme:

Zveřejněno na http://www.allbest.ru/

2.2 Hra 2xn a mx2

Problém 1 (2xn)

Dvě obilniny se pěstují pro suché a vlhké podnebí.

A stav přírody lze považovat za: suchý, vlhký, mírný.

Zveřejněno na http://www.allbest.ru/

Maximální hodnoty M() je dosaženo v bodě M, který je tvořen průsečíkem přímek odpovídajících j=1, j"=2. Podle toho předpokládáme:

Problém 2 (mx2)

Chlap a dívka zvažují možnosti, kam vyrazit na víkend.

Výběr místa pro dovolenou si lze představit jako: park, kino, restaurace.

Zveřejněno na http://www.allbest.ru/

Maximální hodnoty M() je dosaženo v bodě E, který je tvořen průsečíkem přímek odpovídajících j=1, j"=2. Podle toho předpokládáme:

K určení hodnoty v je třeba vyřešit následující rovnice:

2.5 Maticová metoda

Dvě restaurace (stravovací zařízení), které si navzájem konkurují, poskytují následující soubory služeb. První restaurace se nachází v centru a druhá na okraji města.

Centrální restaurace zahrnuje tyto služby:

1) dražší a kvalitnější zákaznický servis;

2) jídla jsou zaměřena na francouzskou kuchyni;

Druhá restaurace nabízí:

1) levné a vysoce kvalitní služby;

2) menu kombinuje různé slavné kuchyně světa;

3) také neustálé akce a slevy;

4) doručuje a přijímá objednávky na doručení domů.

V souladu s úkolem bude zisk za jeden den rozdělen mezi dvě restaurace takto:

Tabulka 2. Výplatní matice

Strategie

Řešení hry s formulářem pomocí maticové metody:

Existuje šest podmatic a:

Zvažte matici:

x 1 = ? 0, x 2 = ? 0

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

Podívejme se nyní na matici:

x 1 = ? 0, x 2 = ? 0

Cena hry.

Tento poměr je v rozporu s požadavkem, a proto není vhodný.

Podívejme se nyní na matici:

x 1 =, x 2 =? 0,

y 1 =< 0, y 2 = ? 0.

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

Podívejme se nyní na matici:

x 1 =, x 2 = 0, protože x 2 = 0, pak vyřadíme a.

Podívejme se nyní na matici:

x 1 =, x 2 =? 0. Protože x 1 = 0, zahodíme a.

Podívejme se nyní na matici:

x 1 = , x 2 =, y 1 = , y 2 =, pak pokračujeme dále:

x 1 =, x 2 =, y 1 =, y 2 = nebo

Cena hry.

Nyní jsou zkontrolovány základní vztahy:

Zveřejněno na http://www.allbest.ru/

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

Hnědá metoda

Odborový svaz na žádost pracovníků určité firmy jedná s jejím vedením o pořádání teplých obědů na náklady firmy. Odborový svaz zastupující dělníky chce zajistit, aby obědy byly co nejkvalitnější, a tedy i dražší. Vedení společnosti má protichůdné zájmy. Nakonec se strany dohodly na následujícím. Odborová organizace (hráč 1) vybere jednu ze tří společností (A 1, A 2, A 3), které dodávají teplá jídla, a vedení společnosti (hráč 2) vybere sadu nádobí ze tří možných variant (B 1, B 2 , B3). Po podpisu smlouvy vygeneruje unie následující platební matici, jejíž prvky představují náklady na sadu nádobí:

Nechte hru definovat následující výplatní maticí:

Předpokládejme, že druhý hráč zvolil svou 2. strategii, pak první obdrží:

2, pokud použije svou 1. strategii,

3, pokud použije svou 3. strategii.

Získané hodnoty jsou shrnuty v tabulce 1.

Tabulka 3. Strategie druhého hráče

Číslo šarže	Strategie hráče 2	Vítězství 1. hráče

Z tabulky 3 je vidět, že s 2. strategií druhého hráče získá první největší výplatu 3 pomocí své 2. nebo 3. strategie. Protože první hráč chce získat maximální výhru, reaguje na 2. strategii druhého hráče svou 2. strategií. S 2. strategií prvního hráče prohraje druhý:

1, pokud použije svou 1. strategii,

3, pokud použije svou 2. strategii,

4, pokud použije svou 3. strategii.

Tabulka 4. Strategie prvního hráče

Číslo šarže	Strategie 1. hráče	2. hráč prohrává

Z tabulky 2 je vidět, že při 2. strategii prvního hráče bude mít druhý hráč nejmenší ztrátu 1, pokud použije svou 1. strategii. Protože druhý hráč chce prohrát méně, v reakci na 2. strategii prvního hráče použije svou 1. strategii. Získané výsledky jsou shrnuty v tabulce 5.

Tabulka 5. Strategie prvního a druhého hráče

Číslo šarže

Strategie hráče 2

Celkové výhry 1. hráče

Strategie 1. hráče

V tabulce 5 ve sloupci strategie druhého hráče ve druhém řádku je číslo 1, které označuje, že ve druhé hře je pro druhého hráče výhodné použít svou 1. strategii; ve sloupci je největší průměrná výhra 3 prvního hráče, kterou obdržel v první hře; sloupec w obsahuje nejmenší průměrnou ztrátu 1, kterou obdržel druhý hráč v první hře; sloupec v obsahuje aritmetický průměr v = (u + w) - tj. přibližnou hodnotu ceny hry získanou v důsledku prohry jedné hry ve hře. Pokud druhý hráč použije svou 1. strategii, pak první obdrží 3, 1, 2, v tomto pořadí, se svou 1., 2., 3. strategií a celkové výhry prvního hráče za obě hry budou:

2 + 3=5 s jeho 1. strategií,

3 + 1=4 s jeho 2. strategií,

3 + 2=5 s jeho 3. strategií.

Tyto celkové výhry se zapisují do druhého řádku tabulky. 3 a ve sloupcích odpovídajících strategiím prvního hráče: 1, 2, 3.

Ze všech celkových výher je největší 5. Získává se 1. a 3. strategií prvního hráče, poté si může vybrat kteroukoli z nich; Řekněme, že v takových případech, kdy jsou dvě (nebo více) shodné celkové výhry, zvolte strategii s nejnižším číslem (v našem případě musíme vzít 1. strategii).

S 1. strategií prvního hráče, druhý prohraje 3, 2, 3, v tomto pořadí, se svou 1., 2., 3. strategií a celková ztráta druhého hráče pro obě hry bude:

1 + 3=4 s jeho 1. strategií,

3 + 2=5 s jeho 2. strategií,

4 + 3=7 s jeho 3. strategií.

Tyto celkové ztráty jsou zaznamenány ve druhém řádku tabulky. 5 a ve sloupcích odpovídajících 1., 2., 3. strategii druhého hráče.

Ze všech celkových ztrát druhého hráče je nejmenší 4. Získává se jeho 1. strategií, proto musí ve třetí hře druhý hráč uplatnit svou 1. strategii. Největší celková výhra prvního hráče za dvě hry dělená počtem her se umístí do sloupce, tzn. Sloupec w obsahuje nejmenší celkovou ztrátu druhého hráče během dvou her, dělenou počtem her, tj. ; ve sloupci v je uveden aritmetický průměr těchto hodnot, tj. = Toto číslo je bráno jako přibližná hodnota ceny hry se dvěma „ohranými“ hrami.

Získáme tak následující tabulku 4 pro dvě hry.

Tabulka 6. Celkové výhry a prohry hráčů po dvou odehraných hrách

Strategie hráče 2

Celkové výhry 1. hráče

Strategie 1. hráče

Totální ztráta 2. hráče

Ve třetím řádku tabulky 6 ve sloupci strategie druhého hráče je číslo 1, které znamená, že ve třetí hře musí druhý hráč použít svou 1. strategii. V tomto případě první hráč vyhraje 3, 1, 2 pomocí své 1., 2., 3. strategie a jeho celkové výhry ve třech hrách budou:

3 + 5 = 8 s jeho 1. strategií,

1 +4 = 5 s jeho 2. strategií,

2 + 5 = 7 s jeho 3. strategií.

Tyto celkové výhry prvního hráče jsou zaznamenány ve třetím řádku tabulky 6 a ve sloupcích odpovídajících jeho strategiím 1, 2, 3. Vzhledem k tomu, že s 1. strategií se získá největší celková výhra 8 prvního hráče, vybere se 1. podle toho.

S 1. strategií prvního hráče, druhý prohraje 3, 1, 2, v tomto pořadí, se svou 1., 2., 3. strategií a celková ztráta druhého hráče pro obě hry bude:

3 + 4=7 s jeho 1. strategií,

2 + 5=7 s jeho 2. strategií,

3 + 7 = 10 s jeho 3. strategií.

Tyto celkové ztráty jsou zaznamenány ve třetím řádku tabulky. 6 a ve sloupcích odpovídajících 1., 2., 3. strategii druhého hráče. Ze všech jeho celkových ztrát je 7 nejmenších a získá se svou 1. a 2. strategií, poté musí druhý hráč použít svou 1. strategii.

V tabulce 6 ve třetím řádku ve sloupci a zaznamenává největší celkovou výhru prvního hráče za tři hry dělenou číslem hry, tzn. ve sloupci w je umístěna nejmenší celková prohra druhého hráče za tři hry dělená počtem her, tj.; sloupec v obsahuje jejich aritmetický průměr

Tak dostaneme tabulku. 7 na tři hry.

Tabulka 7. Celkové výhry a prohry hráčů po třech odehraných hrách

Číslo šarže

Strategie hráče 2

Celkové výhry 1. hráče

Strategie 1. hráče

Totální ztráta 2. hráče

Tabulka 8. Konečná tabulka po dvaceti odehraných zápasech

Číslo šarže

Strategie hráče 2

Celkové výhry 1. hráče

Strategie 1. hráče

Totální ztráta 2. hráče

Od stolu 7 a 8 je vidět, že ve 20 prohraných hrách se strategie 1, 2, 3 pro prvního hráče vyskytnou 12, 3, 5krát v tomto pořadí, proto jsou jejich relativní četnosti v tomto pořadí stejné; strategie 1, 2, 3 pro druhého hráče se vyskytují 7, 11, 2 krát, proto jsou jejich relativní četnosti příslušně stejné; přibližná cena hry. Tato aproximace je docela dobrá.

Nakonec si uvědomte, že pokud má hra více než jedno řešení, pak se aproximace ceny hry budou stále nekonečně blížit skutečným nákladům hry a relativní frekvence strategií hráčů se již nebudou nutně blížit skutečným optimálním hráčům. smíšené strategie.

Analýza výsledků

V této práci jsme studovali materiál pro hledání řešení her s nulovým součtem pomocí grafické, maticové metody a metody postupné aproximace ceny hry. Byly nalezeny optimální strategie prvního a druhého hráče a také náklady na hraní ve hrách 2x2, 2xn a mx2 a také ve hrách využívajících maticovou metodu a Brownovu metodu.

Na příkladu dvojice byla simulována hra 2x2, která byla řešena pomocí algebraických a grafických metod. Řešení hry algebraicky ukazuje, že při použití jejich optimálních smíšených strategií stráví první a druhý hráč spolu 4,6 hodiny. Grafické řešení problému bylo získáno s malou chybou a trvalo 4,5 hodiny.

A také byly simulovány dva problémy 2xn a mx2. V problému 2xn byla zvažována zemědělská plodina a strategie ukazuje, že je lepší zasadit pole 50 na 50 a cena hry byla 3,75 milionu rublů. A v problému mx2 byl zvažován pár, jehož strategie ukázala, že je levnější jít do parku a kina a cena by byla 4,3 rublů.

Pro maticovou metodu byl modelován problém, ve kterém byly uvažovány dvě restaurace, řešení problému ukázalo, že při použití její optimální smíšené strategie bude zisk první restaurace 15,6 milionů rublů a při použití její optimální smíšené strategie o druhá restaurace, nedovolí první vydělat více než 15,6 milionů rublů. Grafické řešení mělo za následek chybu a cena hry byla 14,9 milionů rublů.

Pro Brownovu metodu byl vypracován úkol, ve kterém je uvažován odborový svaz a vedení firmy, jejich úkolem je zajistit pracovníkům stravu. Pokud oba hráči použijí své optimální strategie, jídlo na osobu bude 2,45 tisíc rublů.

Seznam použitých zdrojů

1) Vilisov V.Ya. Poznámky k přednášce „Teorie her a statistická rozhodnutí“, - Obor - „Voskhod“ MAI. 1979. 146 s.

2) Krushevsky A.V. Teorie her, - Kyjev: Vishcha School, 1977. - 216 s.

3) Kostelníci U., Akof R., Arnof L., Úvod do operačního výzkumu. - M.: Věda. 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

Publikováno na Allbest.ru

Podobné dokumenty

Rozhodování jako zvláštní druh lidské činnosti. Racionální reprezentace herní matice. Příklady maticových her v čistých a smíšených strategiích. Operační výzkum: vztah problémů lineárního programování s herně-teoretickým modelem.

práce v kurzu, přidáno 05.05.2010


Mnohokrát opakované hry, jejich charakteristické vlastnosti a fáze. Smíšené strategie, podmínky a možnosti jejich využití v praxi. Analytická metoda pro řešení hry typu 2 x 2. Základní věty pro pravoúhlé hry. Algebraická řešení.

prezentace, přidáno 23.10.2013


Základní definice teorie bimaticových her. Příklad bimaticové hry "Student-Učitel". Smíšené strategie v bimaticových hrách. Hledejte „situaci rovnováhy“. 2x2 bimaticové hry a vzorce pro případ, kdy má každý hráč dvě strategie.

abstrakt, přidáno 13.02.2011


Získejte obecné informace o maticových hrách a hrách s nulovým součtem. Koncept poziční hry, strom, soubor informací. Úvaha o principu maximin a principu rovnováhy. Paretova optimalita. Poziční neantagonistická hra, její vlastnosti.

práce v kurzu, přidáno 17.10.2014


Teorie her je obor matematiky, jehož předmětem je studium matematických modelů pro přijímání optimálních rozhodnutí v podmínkách konfliktu. Iterativní Brown-Robinsonova metoda. Monotónní iterativní algoritmus pro řešení maticových her.

práce, přidáno 08.08.2007


Sestavení platební matice, hledání spodní a horní čisté ceny hry, strategie maximin a minimax hráčů. Zjednodušení platební matice. Řešení maticové hry pomocí redukce na úlohu lineárního programování a doplňku „Hledat řešení“.

test, přidáno 10.11.2014


Teorie her je matematická teorie konfliktních situací. Vývoj matematického modelu dvoučlenné hry s nulovým součtem, jeho implementace ve formě programových kódů. Metoda řešení problému. Vstupní a výstupní data. Program, uživatelská příručka.

práce v kurzu, přidáno 17.08.2013


Základní informace o simplexové metodě, posouzení její role a významu v lineárním programování. Geometrická interpretace a algebraický význam. Hledání maxima a minima lineární funkce, speciální případy. Řešení úlohy maticovou simplexovou metodou.

práce, přidáno 01.06.2015


Techniky pro konstrukci matematických modelů počítačových systémů, které odrážejí strukturu a procesy jejich fungování. Počet přístupů k souboru v procesu řešení průměrného problému. Určení možnosti umístění souborů na externí paměťové disky.

laboratorní práce, přidáno 21.06.2013


Návrh matematického modelu. Popis hry tic-tac-toe. Model logické hry založené na Booleově algebře. Digitální elektronická zařízení a vývoj jejich matematického modelu. Herní konzole, herní ovladač, herní pole.