Strategie (teorie her)

V teorii her je strategie kompletní sada možností, které má hráč k dispozici, aby mohl hru hrát v jakékoli situaci . Strategie tedy plně definuje možnosti hráčova rozhodování. Prostor strategií je seznam všech možných alternativ, které jsou hráči dostupné. Hra v normálním tvaru, je určená třemi množinami. Mimo jiné i množinou všech prostorů strategii: \{X_1,X_2,...,Xn\}. Zde X_i označuje prostor strategií i-tého hráče . Strategický profil (občas nazvaný strategická kombinace) je prostor strategií pro každého hráče který plně určuje všechny akce ve hře. Profil strategie musí obsahovat pouze jednu strategii pro jednoho hráče.

Někdy dochází k záměně významu pojmu strategie a tah (anglicky move). Tah je akce vyvolaná hráčem v nějakém bodě během hry. +more Například v šachu je za tah považovat přesun jedné figurky podle daných pravidel (pohyb střelce z C1 na G5). Na druhou stranu strategie je soubor tahů, které tvoří komplexní způsob hraní hry na několik kol dopředu. Tah je tedy součástí strategie .

Pokud jsou množiny strategií jednotlivých hráčů konečné, hovoříme o konečných hrách, je-li množina strategií alespoň jednoho hráče nekonečná, jde o nekonečnou hru.

Prostor strategií

Účastníci hry jsou hráči, každý hráč vybírá optimální strategii ze svého prostoru strategií podle hodnot výplatní funkce. Hráčův prostor strategií tedy definuje, jaké strategie je možné hrát. +more Předpokládáme, že hráči jsou inteligentní (racionální), tj. že maximalizují hodnotu své výplatní funkce. Dále předpokládáme, že hráči mají dokonalé informace, tj. že znají množiny hráčů, prostorů strategií i výplatních funkcí .

Například v klasické hře kámen-nůžky-papír má jeden hráč k dispozici následující prostor strategií: * Hraju kámen * Hraju nůžky * Hraju papír

Každý z hráčů má tedy svou množinu přípustných řešení, kterou nazýváme prostorem strategií. Z této množiny volí hráči svoje rozhodnutí - strategii. +more Ukazatel, který zhodnotí důsledek volby strategie, se nazývá užitkovou funkci a hodnota tohoto ukazatele se nazývá výhra .

Výplatní funkce

Pro každého hráče je definována tzv. výplatní funkce, která každé kombinaci strategií hráčů přiřadí velikost výplaty tohoto hráče. +more Platba neboli výplata hry je výsledek hry jednotlivých hráčů v závislosti na jimi vybraných strategiích.

Pokud uvažujeme hru hranou v normální tvaru, pak budeme rozumět trojici množin \{\{1,2,. ,n\},\{S1,. +more,Sn\},\{Z1,. ,Zn\}\}, kde \{1,2,. ,n\} je množina hráčů, \{S_1,. ,S_n\} je množina prostorů strategií a \{Z_1,. ,Z_n\} je množina výplatních funkcí hráčů. Každému hráči i náleží strategie obsažené v příslušném S_i . Strategie je úplný popis jak odehrát hru a každému hráči poskytuje představu o návaznosti na kroky jeho spoluhráčů. Při hraní hry v normálním tvaru si každý hráč zvolí určitou strategii x_i\in S_i a sada všech zvolených strategií (všech hráčů) dává příslušnou hodnotu výplatní funkce Z_i(x_1,. ,x_n) pro hráče i. Všichni hráči znají strategie své i svých spoluhráčů a znají všechny hodnoty výplatních funkcí .

Inteligentní hráč

Teorie her předpokládá, že si hráč vybírá pouze efektivní strategie. Například ve hře nazvané vězňovo dilema se předpokládá, že žádný z hráčů se nechce nechat dobrovolně uvěznit. +more Očekává se, že hráč je konfrontován s určitým počtem situací a dokáže si je seřadit podle svých preferencí od nejvýhodnější po nejméně výhodnou. Toto seřazení musí být úplné, tj. musí pokrývat všechny situace, a tranzitivní, tj. pokud dá hráč přednost situaci A před situací B a situaci B před situací C, musí dát přednost situaci A před situací C. Na základě preferencí situací je odvozena užitková funkce (utility function) . Hráč je inteligentní (racionální) pouze tehdy, pokud maximalizuje hodnotu své výplatní funkce (tj. svoji výhru) . Naopak hráči, kteří se konfliktu (hry) účastní, ale výsledek hry je nezajímá, jsou nazýváni neinteligentními hráči. Tito hráči ve hře vystupují jako náhodný mechanismus, který ovlivňuje výsledky inteligentních hráčů. Často se pro neinteligentního hráče používá též termín příroda . Termín Příroda navrhl John Harsanyi (1967-1968), nositel Nobelovy ceny za ekonomii. Představme si situaci s neúplnou informací, která zvyšuje nutnost uvažování názoru hráče na preference ostatních hráčů, jeho názory na názory ostatních o jeho preferencích, jeho názory o jejich názorech, o jeho názorech na jejich preference, atd. A takto se spustí cyklický systém názorů. Právě Harsanyiho teorie neúplných informací nabízí způsob doplnění struktury, ve které je informace neúplná. Hlavní principem je výpočet očekávané hodnoty. Navrhl zavést apriorní tah fiktivního hráče, nazvaného právě Příroda, který určuje typ každého hráče. Typ každého hráče a tudíž i jeho preference jsou výsledkem hodnoty náhodné proměnné, vybrané Přírodou . Klasické modely teorie her považují strategie jednotlivých hráčů za ucelený souhrn jejich chování, takže jakmile hráč nějakou svoji strategii vybere, nemá možnost své jednání již korigovat .

Konfliktní hra

Základním pojmem teorie her je konfliktní situace. Tímto pojmem jsou označovány všechny situace, ve kterých jde o střet zájmů účastníků konfliktu. +more Dosažení cíle jednotlivých účastníků je omezováno nebo korigováno cíli a zájmy ostatních .

Konfliktní situace může mít charakter: * antagonistický * neantagonistický

V případě antagonistického konfliktu dosažení cíle jedním z účastníků zamezí pozitivnímu výsledku ostatních, úspěch každého z hráčů je možný pouze na úkor úspěšnosti ostatních hráčů. Antagonistické konfliktní situace musí vyhovovat následujícím podmínkám: * Zúčastnit se musí minimálně dva účastníci. +more * Každý z účastníků rozhodovací situace zná množinu alternativ svého chování, ale také zná množinu alternativ chování svého protivníka / protivníků. * Každý z účastníků rozhodovací situace dokáže ocenit efektivnost své volby ve všech možných případech, které by mohly nastat. * Každý z účastníků rozhodovací situace volí z množných alternativ nezávisle na volbách protivníků . Alespoň jeden účastník rozhodovací situace je inteligentní hráč, tzn. že jeho jednání je uvědomělé a volbou strategie sleduje určitý cíl. V případě neantagonistického konfliktu mají všichni účastníci možnost více či méně realizovat svoje cíle. V neantagonistickém konfliktu nejsou cíle hráčů protichůdné a hráči mohou i spolupracovat .

Optimální strategie

Optimální strategie je taková strategie, od níž žádná odchylka nemůže přinést hráči výhody, za předpokladu, že druhý hráč zachová svojí optimální strategii . Takto definované optimální strategie představují tzv. +more Nashovu rovnováhu (Nashovo rovnovážné řešení) a nazýváme je rovnovážnými strategiemi .

U her, které hrají dva inteligentní hráči, je poměrně snadné stanovit optimální strategii, neboť například u her s nulovým součtem (se sumou rovnou nule) je zisk jednoho hráče záporně vzatý „zisk“ druhého hráče. V případě her hraných proti přírodě však nastávají potíže .

Rozlišujeme dvě varianty rozhodování ve hře proti přírodě, které vznikají v antagonistickém konfliktu: * Rozhodování při riziku * Rozhodování při nejistotě .

Rozhodování při riziku

Jestliže hráč 1 zná (například na základě předchozí zkušenosti) pravděpodobnosti, s nimiž hráč 2 volí své strategie, pak se jedná o rozhodování při riziku .

Rozhodování při nejistotě

Jestliže však toto rozložení pravděpodobností hráč nezná, mluvíme o rozhodování při nejistotě.

Rozhodovací principy

V rozhodování o riziku a nejistotě využíváme Laplaceův princip. Ten navrhuje zvolit takovou strategii, která by byla optimální v případě, že by pravděpodobnosti, s nimiž nastanou různé stavy světa, byly shodné, tj. +more jako kdyby se jednalo o rozhodování za rizika se stejnými pravděpodobnosti přiřazenými jednotlivým stavům. * Maximinní (pesimistické) kriterium: Tento princip navrhuje pro jednotlivé možné strategie stanovit nejnižší hodnoty užitku a zvolit takovou strategii, pro kterou je toto minimum maximální. Rozhodovatel tedy předpokládá, že se jej okolní svět bude „snažit“ co nejvíce poškodit. * Maxmaxní (optimistické) kriterium: Tento princip navrhuje pro jednotlivé možné strategie stanovit nejvyšší hodnoty užitku a zvolit takovou strategii, pro kterou je toto maximum maximální. Rozhodovatel tedy předpokládá, že se mu okolní svět bude „snažit“ co nejvíce pomoci. * Hurwitzovo kritérium: Jde o konvexní kombinaci optimistického a pesimistického kritéria. Vhodná volba parametru \alpha umožní nastavit vhodný kompromis mezi oběma krajnostmi - často nepřijatelné podle opatrného, resp. nepřijatelné podle důvěřivého kritéria .

Ryzí a smíšená strategie

Řešením hry v případě her v maticovém stavu může být ryzí nebo smíšená strategie . Jedná se o antagonistický konflikt s konečným počtem strategií.

Ryzí strategie

Řešení hry v oboru čistých strategií znamená, že hráč dosáhne svého cíle pouze pomocí jediné své strategie. Ať se hra opakuje (má několik partií) nebo je hrána pouze jedenkrát (má jedinou partii), optimální chování hráče je dáno právě touto jedinou strategií. +more Ryzí optimální strategii hráče A budeme značit A_0 a tato strategie přinese hráči A maximální výhru, ať již hráč B volí jakoukoli strategii. Ryzí optimální strategii hráče B budeme značit B_0. Je to strategie, která zaručí hráči B minimální prohru, ať již hráčA volí jakoukoli strategii. Pro strategie i= 1, 2, . , m a j= 1, 2, . , n platí:.

M(A_i, B_0) \leq M(A_0, B_0) \leq M(A_0, B_j)

Lze tedy říci, že jakýkoliv hráč si pohorší, pokud se odkloní od své optimální ryzí strategie. Cena hry (v) je hodnota výplatní funkce M (A_0, B_0 ) . +more Pokud je cena hry nulová, jedná se o hru spravedlivou, pokud není, jedná se o hru nespravedlivou . První hráč vybírá nejvyšší z nejnižších výher, kterou nazýváme dolní cena hry. Druhý hráč naopak vybírá nejmenší z nejvyšších proher, tento výsledek hry je nazýván horní cena hry. Za předpokladu rovnosti dolní a horní ceny hry je evidentní, že oba hráči nemají lepší volbu strategií. Vyberou-li své strategie jinak, bude jejich výhra menší, resp. prohra větší. Takto vybraná dvojice strategií se nazývá sedlovým bodem hry.

Sedlový bod

Sedlový bod na grafu z=x2−y2 Hledáme-li optimální řešení antagonistického konfliktu hledáme vlastně stabilní řešení, stabilní v tom smyslu, že ani jednomu hráči se nevyplatí od této strategie „utéct“. +more Tj. má to být takové řešení, aby pokud pouze první hráč změní strategii a druhý hráč zůstane u své strategie, potom si první hráč pohorší. Stejně tak s druhým hráčem. Ze stanovení dolní ceny hry a horní ceny hry vyplývá, že optimální řešení antagonistického konfliktu (v ryzích strategiích) existuje, pokud platí:.

\begin{matrix} \\ \operatorname{Min} \\ { }^{j} \end{matrix} \ \begin{matrix} \\ \operatorname{Max} \\ { }^{i} \end{matrix} \ a_{ij} = \begin{matrix} \\ \operatorname{Max} \\ { }^{i} \end{matrix} \ \begin{matrix} \\ \operatorname{Min} \\ { }^{j} \end{matrix} \ a_{ij}

Pokud je tato rovnost splněna, existuje prvek v matici (hra je hraná v maticovém tvaru), který je nejmenší ve svém řádku a největší ve svém sloupci. Tento prvek nazýváme sedlový bod. +more Obecně hra v maticovém tvaru muže mít žádný, jeden nebo více sedlových bodů. Pokud nemá žádný, neexistuje optimální ryzí strategie, pokud má jeden, určuje optimální strategii, pokud jich má více, určuje alternativní optimální (rovnovážné) strategie. Maticová hra má řešení v oboru čistých strategií právě tehdy, když má sedlový bod. Z uvedené věty plyne, že řešit hru v oboru čistých strategií znamená nalézt sedlový bod hry. Odpovídající výhra, resp. prohra je cenou hry. Pokud se sedlový bod hry nepodaří nalézt, hra nemá v oboru čistých strategií řešení .

Smíšená strategie

Pokud se nám nepodařilo najít sedlový prvek, znamená to, že dosavadní výklad nebyl dostatečný pro nalezení rovnovážných strategií ve všech možných rozhodovacích situacích, které je možné vyjádřit jako maticovou hru. Lze to vysvětlit na hře kámen-nůžky-papír. +more Tato hra je hrou dvou hráčů, z nichž každý má k dispozici tři možné strategie. Podle pravidel kámen vyhrává nad nůžkami, nůžky nad papírem a papír nad kamenem. V případě, že oba hráči zvolí stejnou strategii, nastává remíza. V reálné situaci by hráči hru opakovali, od toho však v tomto okamžiku abstrahujeme a považujeme remízu za konečný výsledek hry. Hra kámen, nůžky, papír je hrou s konstantním (nulovým) součtem, která je charakterizována maticí:.

\begin{pmatrix}0 & +1 & -1 \\-1 & 0 & +1 \\+1 & -1 & 0 \end{pmatrix}

Je jednoduché si ověřit, že v této matici není možné najít sedlový prvek, takže ani není možné najít Nashovo rovnovážné řešení v ryzích strategiích. Přesto danou hru běžně dohrajeme a známe odpovídající rovnovážnou strategii, která spočívá v náhodném výběru z prostoru strategií. +more Pro oba hráče je rovnovážnou strategií vektor (1/3; 1/3; 1/3) kde čísla představují pravděpodobnosti, že hráč bude volit první, druhou nebo třetí strategii. Tento typ strategií nazýváme smíšenými (pravděpodobnostními) strategiemi. Také pro tyto strategie platí, že hráč, který se od rovnovážné strategie odchýlí (zvolí jiné pravděpodobnosti), nemůže nic získat, ale naopak může ztratit. Pokud maticová hra nemá řešení v ryzích strategiích, použijeme tzv. smíšeného rozšíření maticové hry. Prostory strategií nyní budou představovat vektory pravděpodobnosti, s jakou hráči zvolí jednotlivé strategie. Ryzí strategie jsou tedy zvláštním případem (podmnožinou) smíšených strategií, kdy jedna z pravděpodobností je rovna jedné, a ostatní pravděpodobnosti jsou rovny nule. Pro maticové hry platí důležitá věta. Tzv. základní věta maticových her: * Každá maticová hra má Nashovo rovnovážné řešení ve smíšených strategiích .

Odkazy

Reference

Související články

Teorie her * Simulace * Kognitivní věda * John Nash * Equilibrium * Souboj pohlaví * No-win situation * Dominantní strategie

Externí odkazy

[url=http://psh. ntkcz. +morecz/skos/PSH11427/html/cs]Rozcestník k nalezení materiálů o teorii her [/url] * [url=http://stanford. library. usyd. edu. au/entries/game-theory/]Podrobné informace o teorii her[/url].

Kategorie:Teorie her Kategorie:Diskrétní matematika Kategorie:Umělá inteligence Kategorie:Hry Her Kategorie:Aplikovaná matematika Kategorie:Počítače a šachy