Decision strategies/cs

From Simulace.info
Revision as of 20: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é se dívat z vícero možných pohledů, přičemž není zaručeno, že nějaká strategie bude nejoptimálnější ve všech možných ohledech. Pod termínem rozhodovací strategie si můžeme představit jednak druhy strategiích jako takových, ale také právě strategie výběru nejoptimálnějších strategií. V první části této práce tedy bude seznámeno s definicemi nejznámějších typů strategií, se kterými je možné se v teorii her setkat. Následovat bude popis různých způsobů klasického rozhodování a v poslední řadě budou rozebrány i způsoby rozhodování při riziku a 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 v literatuře ve spojení s Nashovým ekvilibriem (Nashovy rovnováhy). Optimální strategie je 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, jelikož by mu jiné chování přineslo pouze snížení výplaty, nebo v nejlepším případě by teoreticky mohl skončit pouze se stejnou výplatou 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ž v těchto hrách mohou mít Nashova ekvilibria různou velikost výplaty. I to je však velmi nepravděpodobné, jelikož hráči při znalosti všech existujících Nashových ekvilibrií budou nejspíše již odpočátku volit to, které jim přinese nejvyšší užitek.

Dominovaná a dominující strategie

V některých případech jsou 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] Příklad silně dominované strategie můžeme vidět v příkladu níže, kdy máme definovanou výplatní matici hráče A. Z matice lze vyčíst, že jsou známy dvě strategie hráče A, přičemž výplaty první strategie ve všech případěch převyšují výplaty druhé strategie. První strategii lze tedy označit za dominující a druhou za silně dominovanou a lze prohlásit, že hráč A bude vždy hrát strategii 1.

Výplatní matice hráče A
Strategie hráče B
1 2 3
Strategie
hráče A
1 2 2 2
2 1 1 1

Ryzí a smíšené strategie

Nejzákladnější poznatek teorie her hovoří o tom, že každá maticová, či bimaticová hra má alespoň jedno ř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 pravděpodobnostními vektory o délce počtu strategií hráčů. Vektory obsahují pravděpodobnosti, se kterými by daný hráč měl volit své strategie. 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. Je dobré poznamenat, že vyhledávání Nashova ekvilibria v ryzích strategiích je jednoduší než-li ve smíšených strategií a z tohoto důvodu se nejprve vyhledává řešení v ryzích strategií a teprve poté, není-li 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ě optimální strategie, v určitém úhlu pohledu. Charakteristickou funkcí se totiž dopočítává maximální možná konečná výplata, která bude danou strategií dosažena. Jak již bylo zmíněno, důležitý je ú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ůže být rozlišováno 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í z Nashova ekvilibria nalezeném 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 škodit. 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, které 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í hodnota 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 se 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 jediná existující 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 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 popis charakteristicných funkcí z minulých kapitol, 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 lze nalézt 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

Tento typ rozhodování se využívá v případech, kdy se jeden inteligentní hráč rozhoduje proti obecné štěstěně, jež v teorii her bývá označována jakožto hráč "Příroda". Uměle vytvořený hráč "Příroda" se chová jako náhodný mechanismus a nesleduje vlastní cíle. Dá se tedy říci, že se vždy jedná 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 bylo zmíněno, 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, jež lze dopočí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? Definování a řešení situace je znázorněno v tabulce níže. Řádky představují strategie sázejícího se hráče a sloupce čísla na kostce, coby strategie protihráče "Příroda", 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 v posledním sloupci tabulky 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, 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. Za optimální strategii inteligentního hráče tedy zvolíme strategii, 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 tak, že se od každé hodnoty sloupce výplatní matice odečte maximální hodnota 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 u principu 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 schopna přinést nejvyšší možnou 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 dojít 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 která přijde na rozcestí. Velitel skupiny za využití tohoto principu rychle rozhodne kudy dál, což 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 možné, že některé výrobky neprojdou kontrolou kvality a budou vyřazeny jakožto vadné výrobky. Logicky 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 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 vždy 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 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ž se hledají 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 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