Decision strategies/cs

From Simulace.info
Revision as of 17:33, 22 May 2021 by Satm03 (talk | contribs)
Jump to: navigation, search

Rozhodování je v teorii her proces, během kterého se hráči rozhodují, jakou svoji možnou strategii mají aplikovat. Při tomto procesu se samozřejmě hráči snaží, aby jimi zvolená strategie, byla co možná nejoptimálnější. Ovšem na míru optimality strategie je možné dívat se z vícero možných pohledů, přičemž není zaručeno, že nějaká strategie bude optimální ve všech možných ohlede. V první části této práce tedy bude seznámeno s definicemi nejznámějšími typů strategií, se kterými se můžeme v teorii her setkat. Následovat se bude popisem různých způsobů klasického rozhodování a také se způsoby rozhodování při nejistotě.

Typy strategií

V teorii her lze nalézt několik typů strategií. V této kapitole jsou popsány nejdůležitější z nich.

Optimální strategie

Optimální strategie jsou strategie, které jsou pro hráče z jeho pohledu na situaci nejvýhodnější.[1] Nejčastěji se termín optimální strategie objevuje s literatuře ve spojení Nashova ekvilibria (Nashovy rovnováhy). Optimální strategie v tomto kontextu popisována jakožto strategie, od níž žádný hráč nemá zájem upustit. Žádný z hráčů totiž nemůže jednostranným krokem zlepšit svoji situaci, jinak řečeno by mu jiné chování přineslo pouze snížení výplaty, nebo v nejlepším případě by teoreticky mohl skončit se stejným výsledkem v případě, že by nově nastalá kombinace strategií byla rovněž dalším Nashovým ekvilibriem.[2] Zajímavostí poté zůstává to, že ona nemožnost polepšení v jiném Nashovo ekvilibriu platí pouze pro hry s konstantním součtem. U her s nekonstantním součtem (bimaticových her) by v tomto případě bylo teoreticky možné dokonce zlepšení výplaty, jelikož Nashova ekvilibria mohou mít různou velikost výplaty.

Dominovaná a dominující strategie

V některých případech jsou některé strategie označeny za takzvaně dominované. K dominované strategii se pak váže i určitá dominující strategie. Pro slabě dominovanou strategii platí, že za jakýchkoliv okolností budou její výplaty vždy menší, nebo rovny výplatám strategie dominující. Výplaty silně dominovaných strategií pak již nemohou být ani rovny, ale jsou zpravidla vždy menší. Racionální hráči z tohoto důvodu nikdy nezvolí silně dominovanou strategii, díky čemuž můžeme tyto strategie ignorovat a brát v potaz pouze strategii dominující.[3]

Ryzí a smíšené strategie

Nejzákladnější poznatek teorie her hovoří o tom, že každá maticová, či dvoumaticová hra má řešení ve smíšených strategiích. Smíšené strategie lze také nalézt pod názvem pravděpodobnostní strategie. Pravděpodobnostní z toho důvodu, že řešení hry jsou dány vektory o délce počtu strategií hráčů. Vektory obsahují pravděpodobnosti se kterými by daný hráč měl volit svojí určitou strategii. Zvláštním případem smíšených strategií jsou pak ryzí strategie. U těchto strategií jsou určité strategie buď hrány se stoprocentní pravděpodobností, či nehrány vůbec. Lze říci, že vyhledávání Nashova ekvilibria je z tohoto důvodu jednoduší, nežli ve smíšených strategií a z toho důvodu se nejprve vyhledává řešení v ryzích strategií a teprve poté, co není nalezeno, se přejde k vyhledávání Nashova ekvilibria ve smíšených strategiích.[2]

Způsoby rozhodování

Při rozhodování hráčů mají vliv takzvané charakteristické funkce, což jsou funkce, díky nimž lze rozpoznat optimální strategii, popřípadě strategií v určitém úhlu pohledu. Funkcí se totiž dopočítává maximální možná konečná výplata, která bude danou strategií dosažena. Již jsem zmínil, že je důležitý úhel pohledu, s nímž hráč k dané situaci přistupuje. Různými přístupy se totiž lze dostat k odlišným výsledkům a to nejen z pohledu velikosti očekávaných výplat, ale i určení optimálních strategií, či rozhodnutí zda přistoupit na kooperaci, či nikoliv, pokud tedy možnost kooperace není z určitých důvodů znemožněna. Podle úhlu pohledu rozhodujícího se hráče můžeme rozlišovat několik druhů charakteristických funkcí, jež jsou popsány níže.

Kompetitivní charakteristická funkce

Kompetitivní charakteristická funkce je asi nejpoužívanější funkcí ze všech. Hráči se snaží o maximalizaci svých výplat. Sledují pouze tento vlastní cíl a nezabývají se výplatou protihráčů. Tato funkce je vlastně založena na vyhledávaní Nashových ekvilibriích v maticových hrách. Výplaty Nashova ekvilibria jsou při řešení v ryzích strategií určeny přímo z výplatní matice, či v případě, že Nashovo eklilibriu v ryzích strategiích neexistuje, jsou dopočítány na základě pravděpodobností užití strategií ve smíšených strategiích.[4]

Minimaxová charakteristická funkce

Při využití tohoto pohledu na situaci se předpokládá, že si hráči budou vzájemně co nejvíce poškozovat. Dopočítává se tedy jakási zaručená minimální výplata, kterou hráči při volbě strategií mohou získat. Jednodušeji řečeno se zjišťují nejhorší scénáře, kterou mohou nastat při zvolení každé strategie, lapidárně řečeno zjišťují se minimální výplaty všech možných strategií. Po zjištění minimálních výplat by hráč měl volit tu strategií, která mu přinese maximální minimální výplatu, tedy tu strategii, která má maximální minimum. Je dobré zmínit, že v tomto případě se očekává tato minimální hodnoty výplaty, takže je možné, že ve výsledku bude hodnota výplaty i vyšší.[2][4]

Funkce založená na očekávané hodnotě

Poslední funkce je využívána v případě, že protihráč chová jakožto náhodný mechanismus, tedy že nesleduje své cíle a své strategie volí nahodile. Při této funkci se tedy dopočítává střední hodnota výhry u každé strategie a za optimální strategii se považuje ta strategie, jenž má dopočítanou střední hodnotu nejvyšší. Střední hodnota určité strategie je dopočítána jakožto průměr všech možných výplat dané strategie.[4]

Příklad využití funkcí

Za účelem ukázky aplikace výše popsaných funkcí byla připravena hra dvou hráčů s nekonstantním součtem z nichž každý má právě 3 možné strategie. Řádkové strategie představují klasicky strategie hráče A a sloupcové strategie hráče B. Výplatní matice obou hráčů lze vidět níže. Pro účely určování optimálních strategií dle charakteristických funkcí byly rovnou připraveny minimální hodnoty a průměry jednotlivých strategií a nalezena jedna Nashova rovnováha v ryzích strategií. Nashova rovnováha byla nalezena tak, že byly vyhledávány maximální sloupcové hodnoty výplatní matice hráče a maximální hodnoty řádků výplatní matice hráče B. Po nalezení těchto maxim bylo patrné, že existuje právě jedno Nashovo ekvilibrium a to při kombinaci druhé strategie hráče A a první strategie hráče B.

Výplatní matice hráče A
Strategie hráče B
1 2 3 min průměr
Strategie
hráče A
1 20 35 20 20 25
2 27 30 42 27 33
3 26 40 36 26 34
Výplatní matice hráče B
Strategie hráče B
1 2 3
Strategie
hráče A
1 0 12 11
2 15 8 9
3 14 13 10
min 0 8 9
průměr 9,66 11 10

Vezmeme-li v úvahu charakteristiku charakteristicných funkcí, pak u kompetitivní charakteristické funkce budeme sledovat Nashovu rovnováhu, u minimaxového způsobu hodnoty sloupce a řádky min a nakonec u rozhodování dle funkce založené na očekávané hodnotě hodnoty ve sloupci a řádce průměr. Celkové výstupy z uvedeného příkladu pak lze naléze v tabulce níže.

Výstupy příkladu využití funkcí.
Zvolená strategie Očekávaný užitek
Hráč A Hráč B Hráč A Hráč B
Kompetitivní charakteristická funkce 2 1 27 15
Minimaxová charakteristická funkce 2 3 27 9
Funkce založená na očekávané hodnotě 3 2 34 11

Rozhodování za rizika a nejistoty

Rozlišujeme dva hlavní typy rozhodování ve hře proti hráči „Příroda“, jenž se chová jako náhodný mechanismus a nesleduje vlastní cíle. Dá se tedy říci, že jde o hru jednoho inteligentního hráče proti druhému neinteligentnímu hráči „Příroda“. Existence pouze jednoho inteligentního hráče může vést i k řešení těchto situací pomocí teorie pravděpodobnosti, či teorie rozhodování, jelikož jak jsme zmínili, neinteligentní hráč se chová nahodile.

Rozhodování při riziku

Rozhodování za rizika nastává v případech, kdy výsledky rozhodnutí nejsou dány s naprostou jistotou, nýbrž rozložením pravděpodobností.[2]Pro lepší představu si můžeme uvést nejjednodušší příklad jakési sázky, že při nadcházejícím hodu 6-ti hranou kostkou padne číslo 6. V této situaci sice nemůžeme s jistotou určit výsledek, avšak můžeme říci, že hráč úspěšně vyhraje s pravděpodobností 1/6 a s pravděpodobností 5/6 nevyhraje. Hráč „Příroda“ má v tomto případě 6 strategií, jenž spočívají v tom, že hodí určité číslo na kostce (od 1 do 6).

Za těchto okolností by se inteligentní hráč měl rozhodovat tak, že bude volit tu strategii, která má maximální střední hodnotu výplaty, jenž lze vypočítat pomocí známých výplat Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_{ij}} a jejich pravděpodobností.[2]

Obrázek představující obecnou výplatní matici Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m x n} , kde Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_1,... s_m} jsou strategie hráče 1 a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t_1,... t_n} strategie hráče 2. Hodnoty Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a_{11},... a_{ij}} představují výplaty hráče 1.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{j=1}^n p_ja_{ij}}

Vrátíme-li se například ke hrací kostce, můžeme si představit situaci, kdy se hráč rozhoduje, zda vsadit na to, že padne 6 s možnou výhrou 20, nebo zda padne 6, či 5 s možnou výhrou 11. Zajímavé na situaci je, že první varianta má sice menší pravděpodobnost, avšak slibuje vyšší zisk, přičemž druhá varianta je poněkud pravděpodobnější avšak méně finančně odměnitelná. Jak by se v tomto případě měl racionální hráč zachovat? Znázornění a řešení situace je znázorněno výplatní maticí níže. Řádky představují strategie hráče a sloupce čísla na kostce, přičemž je v závorkách uvedena pravděpodobnést jejich hození.

Sázka na hod kostkou
1 (p = 1/6) 2 (p = 1/6) 3 (p = 1/6) 4 (p = 1/6) 5 (p = 1/6) 6 (p = 1/6) střední hodnota
Strategie hráče Sázka na 6 0 0 0 0 0 20 3,33
Sázka na 5 a 6 0 0 0 0 0 20 3,66

Pro obě strategie hráče byla vypočítána střední hodnota výplat dle uvedeného vzorce. Jak můžeme vidět, pak druhá strategie má vyšší střední hodnotu (oranřově podbarveno), tudíž právě tuto strategii by měl inteligentní hráč zvolit.

Rozhodování při neurčitosti

Obdobně jako při rozhodování při riziku opět známe možné strategie hráč „Příroda“, avšak na rozdíl od něj neznáme rozložení pravděpodobností jeho strategií. Za těchto okolností není definován jednoznačný postup, avšak existuje několik známých rozhodovacích principů.[2] Na základě zvoleného principu lze určit rozdílné optimální strategie.

Laplaceův princip

V literatuře je též znám pod názvem princip nedostatečné evidence. Určování optimální strategie je voleno na podobném principu jakožto u rozhodování při riziku. Jádrem tohoto principu je to, že je počítáno s tím, že hráč „Příroda“ bude své strategie volit se stejnou pravděpodobností, což je bráno jako nejlepší způsob rozdělení známých pravděpodobností mezi jednotlivé „přírodní“ strategie. Jednoduše řešeno pak za optimální strategii inteligentního hráče zvolíme tu strategii (řádek), která bude mít největší průměr.[2]

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \max_i \frac{1}{n} \sum_{j=1}^n a_{ij}}

Waldův princip maximinu

Při zvolení tohoto principu je počítáno s tím, že hráč „Příroda“ bude chtít inteligentnímu hráči nejvíce uškodit. Z tohoto důvodu lze tento princip označit za silně pesimistický a přehnaně opatrný. Je doporučován v případech, kde je vyžadována krajní opatrnost. Optimální strategie je na základě Waldova principu ta, která převyšuje svoji minimální výplatou všechny ostatní strategie.[2]

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \max_i \min_j a_{ij}}

Savageův princip maximinu ztráty

Hráč se rozhoduje z pohledu „generála po bitvě“. Nejprve je vypracována matice ztrát z matice výplat inteligentního hráče. Matice ztrát je vytvořena ta, že od každé hodnoty sloupce výplatní matice odečteme maximální hodnotu tohoto sloupce.[2]

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b_{ij} = a_{ij} - \max_i a_{ij}}

Poté je na matici ztát použit klasický princip maximinu, čímž se určí optimální strategie.[2]

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \max_i \min_j b_{ij}}

Hurwiczův princip vyváženého optimismu a pesimismu

Výše zmíněný Waldův princip maximinu je jak již bylo zmíněno krajně pesimistický. Hráč se však nemusí vždy rozhodovat opatrně a může mít jistou míru optimismu. Právě s množstvím optimismu pak pracuje Hurwiczův princip, jenž počítá s tím, že se hráč nemusí rozhodovat úplně pesimisticky, či optimisticky, ale že si bude volit cestu mezi těmito extrémy. Za optimální řádkovou strategii bere tu, jenž má maximální hodnotu rovnice níže.[2]

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha \max_j a_{ij} + \left( 1-\alpha \right) \min_j a_{ij}}

V rovnici se vyskytuje parametr alfa, který znázorňuje míru optimismu. Obor hodnot parametru je od 0 do 1. Čím vyšší hodnota parametru je, tím je počítáno s vyšším optimismem inteligentního hráče. Při nulové hodnotě alfy by tedy byl výsledek stejný jakožto princip maximinu. V opačném případě, při hodnotě alfa jedna, by se pak jednalo o princip ještě nezmíněného maximaxu, krajního optimismu inteligentního hráče.

Princip maximaxu

Princip maximaxu počítá s tím, že hráči okolní svět vyjde vždy maximálně vstříc a z toho důvodu bude volit tu strategii, která je schopno přinést nejvyšší výplatu. Tento přístup je však v realitě velmi nepravděpodobný.[5]

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \max_i \max_j a_{ij}}

Princip totální ignorance

Teoretický neoficiální a nejspíše i nejjednodušší princip, jenž spočívá v tom, že za každých okolností se má volit první strategie.[2] Problém tohoto principu je, že nevyhovuje předpokladům dobrého rozhodování, jelikož zaměníme-li pořadí možných strategií může dojde k výběru odlišné strategie. Princip však přeci jenom má určitou racionalitu, myšlenku. Příkladem využití může být skupina lidí, který se ztratila v lese a přijdou na rozcestí. Velitel skupiny pak za využití tohoto principu rychle rozhodně, což pak má kladný psychologický efekt na zbytek skupiny.

Příklady aplikace principů

Představme si, že existuje firma, která se rozhoduje, jaké množství produktů má vyprodukovat. Během výroby je však možné, že některé neprojdou kontrolou kvality a budou vyřazeny jakožto vadné výrobky. Logicky pak platí, že čím větší produkce a méně vadných výrobků, tím více se prodá zboží a firma bude mít větší užitek. Ovšem může se stát, že při výrobě se vyskytne mnoho vadných výrobků, které nepůjdou prodat a náklady ve výrobě se firmě nevrátí. To přináší snížení zisků firmy. Níže je pro tento příklad vytvořena výplatní matice firmy. Strategie firmy jsou definovány jednoduše jako možné objemy produkce, kterou může firma produkovat. Sloupce matice pak představují strategie hráče „Příroda“, který určuje, procentuální množství vadných výrobků z výroby. V samotné tabulce pak lze vidět možné výplaty (zisky) firmy při kombinaci jednotlivých strategií. Níže je zobrazena výplatní matice firmy s již předem vypočtenými, či určenými pomocnými výpočty. V pomocných výpočtech lze nalézt sloupec max, jenž obsahuje maximum z řádku, sloupec min, jenž obsahuje minimální hodnotu z řádku, sloupec L, jenž představuje hodnoty dle rovnice Laplaceova principu (průměr) a nakonec sloupec H, jenž obsahuje hodnoty, jež nabývá daná firemní strategie dle výrazu Hurwiczova principu. U tohoto výpočtu pak je třeba dodat, že se počítalo s polovičním optimismem hráče, tedy s Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \alpha = 0,5} . Poslední řádek tabulky max představuje maximální hodnoty sloupce. Jelikož hledá zpravidla maximální hodnoty ve sloupcích pomocných výpočtů, tak jsou maximální hodnoty sloupce vždy vybarveny oranžově.

Produkce a vadné výrobky
Vadné výrobky Pomocné výpočty
<2% 2-3% >3% max min L H Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left( \alpha = 0,5 \right)}
Produkce 0 0 0 0 0 0 0 0
1000 25 0 -15 25 -15 3,33 5
2000 30 5 -20 30 -20 5 5
3000 45 10 -25 45 -25 10 10

Dle určených pomocných výpočtu lze již určit optimální strategie dle většiny principů. Z pohledu Laplaceova principu (sloupec L) lze označit za optimální strategii produkci 3000 výrobků. Dle Waldova principu maximinu (sloupec min) je optimální produkce 0, tedy vůbec daný výrobek nevyrábět. S poloviční mírou optimismu dle Hurwiczova principu (sloupec H) by mělo být produkováno 3000 výrobků. Stejná míra produkce by měla být volena taktéž za krajního optimismu, principu maximaxu (sloupec max). Dle teoretického principu totální ignorance by v tomto uspořádání strategií měla být volena strategie nulové produkce. Pro určení optimální strategie z hlediska Savageova principu maximinu ztráty je ještě nutné vytvořit nejprve matici ztrát a aplikovat na ní princip minimaxu.

Matice ztrát
<2% 2-3% >3% min
Produkce 0 -45 -10 0 -45
1000 -20 -10 -15 -20
2000 -15 -5 -20 -20
3000 0 0 -25 -25

Po vytvoření matice ztrát lze určit, že z pohledu minimaxu ztrát (sloupec min v matici ztrát) jsou dvě optimální strategie, produkce 1000, či 2000 výrobků.

Literatura

  1. Sawa, František. Teorie her [online]. Místo: VŠB–Technick ́a Univerzita Ostrava. 19.4.2021 [vid. 22.5.2021]. Dostupné z:https:http://www.cs.vsb.cz/sawa/teh/opora/TEH-opora.pdf
  2. 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 2.11 Dlouhý, Martin. Úvod do teorie her. 2., přepracované vydání Praha: Oeconomica, 2009, 119 s. ISBN 978-80-245-1609-7.
  3. Hruby, Martin. Doprovodné texty ke kurzu Teorie her [online]. Místo: Vysoké učení technické v Brně. listopad 2021 [vid. 22.5.2021]. Dostupné z:https:http:http://www.fit.vutbr.cz/~hrubym/THE/sk-2-nekoo.pdf
  4. 4.0 4.1 4.2 Rada, Miroslav. Bimaticovéhry [online]. In:4EK421 Teorie her a ekonomické rozhodování. Místo: Vysoká škola ekonomická v Praze. 8.3.2021 [vid. 22.5.2021]. Dostupné z:http://hry.polyedr.cz/static/cviceni/slidy-bimaticove-hry.pdf
  5. Doubravová, Hana. Vicekriteriální analýza variant a její aplikace v praxi [online]. Místo: Jihočeská univerzita v Českých Budějovicích. 17.4.2009 [vid. 22.5.2021]. Dostupné z:https://theses.cz/id/6citbe/downloadPraceContent_adipIdno_11361