Pokm09: Vložení učebního textu

2022-05-29T14:02:10Z

Vložení učebního textu

New page

{{DISPLAYTITLE:''Teorie her/cs''}}
= Úvod =
Teorie her je jedna z disciplín aplikované matematiky zabývající se komplexními systémy. Těmi jsou konfliktní situace (“hry”) mezi několika různými stranami (“hráči”) <ref name="dlouhyfiala">Dlouhý, Martin; Fiala, Petr Úvod do teorie her Oeconomica, 2007. [Cit. 29-05-2022]. ISBN 978-80-245-1273-0 </ref>.

K popisu rozhodovacího procesu několika osob během jedné hry je převážně využíván matematický aparát, avšak v některých situacích se kvůli komplexnosti těchto systémů musíme spolehnout pouze na empirické (simulační) řešení, neboť ne vždy musí analytické řešení být k dispozici <ref name="dlouhyfiala"/>.

= Co je to “hra”? =

Základním myšlenkou hry je tatáž, či velmi podobná té, jakou si představíme u společenských her <ref name="owen">Owen, Guillermon. Game Theory. Emerald Group Publishing, 2013. [Cit. 29-05-2022]</ref>.

Po vypuknutí hry můžeme definovat posloupnosti kroků/tahů, kterými hráči hrají danou hru <ref name="owen"/>. V rámci každého tahu hráči vybírají, jakými kroky ze všech jim dostupných se budou ubírat <ref name="owen"/>. Tato volba může být v některých problémech omezena či upravena náhodou (hodem kostky, zamícháním balíčku karet atd.). Klasickým příkladem her jsou šachy, ve kterých náhoda nehraje žádnou roli (kromě rozlosování toho, kdo začne jako první), bridge, ve kterém náhoda sice již ovlivňuje hru, ale zkušenosti a um jsou stále důležité, a ruleta, při které jde jen o náhodu a umění v ní nehraje žádnou roli <ref name="owen"/>.

Na rozdílu šachů a bridge můžeme popsat ještě jeden z důležitých faktorů her <ref name="owen"/>. V šachách všichni hráči vědí, jaké všechny kroky předcházeli aktuálnímu stavu hry, zatímco u bridge tuto znalost nemáme. Tedy v některých hrách může nastat situace, že nevíme, jaký z možných tahů soupeř zahrál <ref name="owen"/>. Pokud chce hráč zakládat rozhodování na hře ostatních hráčů, ne vždy může mít k dispozici všechny informace, a tedy nemusí vědět, v jakém přesném stavu se hra právě nachází <ref name="owen"/>. Na základě kompletnosti dostupných informací hráčů dělíme hry na hry s [[#Hry s úplnými informacemi|úplnými]] a [[#Hry s neúplnými informacemi|neúplnými]] informacemi.

Na konci hry ještě běžné probíhá nějaké vyhodnocení. Vítězný hráč bývá odměněn, ať už ve formě peněz, prestiže, nebo zadostiučinění <ref name="owen"/>.

= Co je to “strategie”? =

Strategií se v teorii her myslí samotný algoritmus, podle kterého se v každém stavu hry rozhodneme, jaký krok provedeme <ref name="jfriev">Frieb J, 2007. [online] https://web.archive.org/web/20070221142004/http://www2.ef.jcu.cz/~jfrieb/rmp/data/teorie_oa/TEORIE%20HER.pdf [Cit. 29-05-2022].[Arch. 21-02-2007].</ref><ref name="nust>Nust.na. 2022. [online] https://www.nust.na/sites/default/files/documents/MEN311S-2016-UNIT%207%20(GAME%20THEORY%20AND%20STRATEGIC%20DECISION%20MAKING).pdf [Cit. 29-05-2022]</ref>, proto se také těmto strategiím přidává přívlastek rozhodovací.

Rozhodovací strategie dále můžeme dělit dle toho, jak pracují se ziskem v dané hře. Pokud se hráč bude rozhodovat podle strategie, která maximalizuje očekávaný zisk, tak této strategii říkáme optimální <ref name="nust"/>. Pokud pro daného hráče v dané hře existuje strategie, která je optimální nehledě na tahy ostatních hráčů, říkáme této strategii dominantní, popř. ryzí <ref name="fudenbergtirole">Fudenberg, Drew; Tirole, Jean. Game Theory. MIT Press, 1991. [Cit. 29-05-2022]</ref>.

V některých typech her však může být významným prvkem náhoda, popř. nedostatek informací, pak velmi často nastává situace, že dominantní strategie neexistuje ([[#Kámen-nůžky-papír|kámen-nůšky-papír]]). V těchto případech se využívá pravděpodobnostního ohodnocení jednotlivých možných stavů a následných odměn. Těmto strategiím se pak říká pravděpodobnostní nebo také smíšené <ref name="dlouhyfiala"/>.

O strategii více pojednává článek [[Decision_strategies/cs|Rozhodovací strategie]].

= Historie =

== Starověk ==
První příklad z teorie her se dá najít již ve starověké Babylonii, a to v Babylonském Talmudu <ref name="walker"/>. Babylonský Talmud byl soupisem starověkého práva a obyčejů, sepsaný během prvních pár století našeho letopočtu, a slouží jako základ Židovského náboženství, trestního a občanského práva. V něm je popsán tzv. “marriage contract problem”, který udává příklady rozdělení jmění muže mezi zbývající ženy po jeho smrti. Mnoha vzdělancům se závěry tohoto problému, popsané v Babylonském Talmudu, zdály nesmyslné a dokázány byly jako možné až v roce 1985, kdy vyšly jako výsledky adekvátně definovaných her <ref name="walker">Walker, Paul. An Outline of the History of Game Theory. 1995. Doi: 10.22004/ag.econ.263767</ref>.
== Novověk ==
Další významná známka o principech teorie her se neobjevuje až do 13. listopadu 1713, kdy James Waldergrave poslal Pierre-Remond de Montmortovi první známé řešení hry dvou hráčů za použití minimax smíšené strategie <ref name="walker"/>. Bohužel tuto strategii neaplikoval na žádné další problémy, protože si myslel, že jsou smíšené strategie pro běžné hry pravděpodobně neaplikovatelné <ref name="walker"/>.

V 19. století se objevuje první náznak [[Nash_equilibrium/cs|Nashova equilibria]] v práci Augustina Cournota, Mathematical Principles of the Theory of Wealth <ref name="walker"/>.

Na začátku 20. století se objevují první teorie Teorie her. Tou úplně první je pravděpodobně Zermanova teorie z roku 1913 popisující hru šachy <ref name="walker"/>.

V letech 1921 a 1927 pracoval Emile Borel na poznání strategických her a definoval první myšlenky smíšených strategií <ref name="walker"/>.

Konečně, v roce 1928, John von Neumann publikoval článek “Zur Theorie der Gesselschaftsspiele” a tím položil první základy celému oboru matematiky Teorie Her <ref name="walker"/> <ref name="tuckerluce">Tucker, William Albert; Luce, Duncan Robert. Contributions to the Theory of Games. Volume 4. Princeton University Press, 1959. [Cit. 29-05-2022]</ref>.

= Typy her =

Hry se často dělí na statické/dynamické a s neúplnými/úplnými informacemi.

== Statické hry / Jednorázové hry ==

V rámci statických her zvolí všichni hráči svoji strategii a následně je zjištěno, jaký je výsledek hry <ref name="tadelis"/>. Tyto hry se dají popsat dvěma kroky:

# krok: Všichni hráči si naráz, nezávisle, bez jakékoli komunikace zvolí svůj tah dle své strategie,
# krok: Všichni hráči se zachovají dle své zvolené strategie, je posouzen výsledek hry a rozděleny odměny <ref name="tadelis"/>.

Příkladem by mohla být ideální hra [[#Kámen-nůžky-papír|kámen-nůšky-papír]] , kdy hráči naráz zvolí a zahrají svojí strategii (kámen/nůžky/papír), hra je vyhodnocena a vítěz je znám hned.

[[One-shot_games/cs|Samostatný článek o statických hrách]]

== Dynamické hry / Opakované hry ==

Dynamickými hrami jsou hry, kde probíhá opakované střetnutí strategií hráčů <ref name="tadelis"/>. V podstatě se jedná o mnohokolové statické hry, kde se v 2.kole posoudí pouze dílčí výsledky a jsou rozděleny dílčí odměny, a tyto hry se opakují, dokud není naplněn jejich cíl <ref name="tadelis"/>.

Jedná se například o většinu deskových her (Monopoly, Dostihy a sázky, Člověče nezlob se a další).

[[Repeated_games/cs|Samostatný článek o dynamických hrách]]

== Hry s úplnými informacemi ==

V tomto typu her mají všichni hráči k dispozici stejné znalosti o:

* všech možných krocích ostatních hráčů,
* všech možných výsledcích dané hry,
* co mají všechny možné kombinace možných kroků všech hráčů za výsledek,
* preference zvolení kroků ostatními hráči.

[[#Statické hry / Jednorázové hry|Statické hry]] s úplnými informaci jsou těmi nejjednoduššími hrami. V praxi se s nimi příliš nepotkáme, ale umožňují nám položit první základy tohoto oboru <ref name="tadelis">Tadelis, Steven. Game Theory: An Introduction. Princeton University Press, 2013. [Cit. 29-05-2022]</ref>.

== Hry s neúplnými informacemi ==

Hrami s neúplnými informacemi myslíme hry, kde hráči nemají stejné znalosti alespoň o jedné z informací o hře (viz [[#Hry s úplnými informacemi|hry s úplnými informacemi]]).

Například na aukci mají všichni hráči informaci o vyvolávající ceně a minimálním příhozu, ale nevědí, jaké možnosti mají ostatní hráči, kolik mají financí, ani jaký je jejich cíl. <ref name="levin">Levin, Jonathan. Games of Incomplete Information. 2002. [online] https://web.stanford.edu/~jdlevin/Econ%20203/Bayesian.pdf [Cit. 29-05-2022]</ref>

== Další dělení ==

Dalšími možnými děleními jsou dělení na základě počtu hráčů, počtu možných strategií, součtu zisku všech hráčů, dle počtu ekvilibrií a zda hráči spolupracují, či ne.

= Zápisy her =

== Normální forma ==

Normální forma je maticovým zápisem hry <ref name="fudenbergtirole"/>. K použití tohoto zápisu musíme znát množinu všech hráčů, jejich tahů a preferencí <ref name="fudenbergtirole"/>. Je vhodný k převážně k zápisu her dvou hráčů (první hráč má strategie ve sloupcích, druhý v řádcích), při větším počtu hráčů se ztrácí přehlednost matic <ref name="fudenbergtirole"/>. Výhodou oproti rozšířené formě je snadnost nalezení ekvilibrií <ref name="fudenbergtirole"/>.

[[Normal_form/cs|Samostatný článek o normální formě]]

== Rozšířená forma ==

Rozšířená forma je stromový zápis hry ([[https://teorie-grafu.cz/zakladni-pojmy/stromy.php|strom]] je souvislý, acyklický graf) <ref name="fudenbergtirole"/>. Na rozdíl od normální formy umožňuje i zápis her s nekompletními informacemi <ref name="fudenbergtirole"/>. Jednotliví hráči jsou rozděleny do různých vrstev grafu <ref name="fudenbergtirole"/>.

[[Extensive_form/cs|Samostatný článek o rozšířené formě]]

= Pojmenované problémy =

== Cournotův model ==

Cournotův model je ekonomický model popisující duopol <ref name="fudenbergtirole"/>. V rámci teorie her bychom ji zařadili to statických her s úplnými informacemi (firmy mají stejnou lin. funkci mezních nákladů) <ref name="fudenbergtirole"/>. Jedná se o model, kde si firmy konkurují množstvím vyrobených produktů. Pokud všechny firmy správně odhadnou strategii ostatních konkurentů, vzniká v něm tzv. Cournotova rovnováha (podmnožina rovnovah později známých jako [[Nash_equilibrium/cs|Nashovy rovnováhy]] ) <ref name="fudenbergtirole"/>.

[[File:Cournotova_rovnovaha.png]]

Grafické znázornění Cournotovy rovnováhy v bodě C (v průsečíku reakčních křivek).

== Matching pennies ==

Jedná se o hru dvou hráčů, ve které hráči 1 a 2 mají minci a tajně na ni zvolí “panna”, nebo “orel”, poté naráz ukáží svůj výběr. Pokud zvolili rozdílné strany, získává obě mince hráč 1, pokud stejné získává je hráč 2<ref name="tadelis"/>.

Maticový zápis hry:

[[File:Matching_pennies.png]]

Je vidět, že hra nemá ryzí [[Nash_equilibrium/cs|Nashovo ekvilibrium]] (neexistuje [[Normal_form/cs#.C4.8Cist.C3.A1_a_sm.C3.AD.C5.A1en.C3.A1_strategie|ryzí strategie]] na nejlepší reakci, nejlepší reakce)<ref name="tadelis"/>.

Avšak hra má [[Nash_equilibrium/cs|Nashovo ekvilibrium]] ve [[Mixed_strategy/cs|smíšené strategii]]: kdy každý hráč zvolí každou stranu mince se stejnou pravděpodobností, tím vznikne celkové ekvilibrium, při kterém celkový zisk každého z hráčů je 0<ref name="tadelis"/>.

== Kámen-nůžky-papír ==

Jedná se v rámci teorie her o velmi podobou hru k [[#Matching pennies|matching pennies]] , jen s tou změnou, že hra má 3 strategie na místo 2 <ref name="tadelis">Tadelis, Steven. Game Theory: An Introduction. Princeton University Press, 2013. [Cit. 29-05-2022]</ref>.

Maticový zápis:

[[File:Rock-Paper-Scissors.png]]

Je opět vidět, že tato hra nemá žádné ryzí [[Nash_equilibrium/cs|Nashovo ekvilibrium]].

[[Nash_equilibrium/cs|Nashovo ekvilibrium]] pro smíšené strategie nastane znovu v případě, že každý z hráčů bude hrát všechny strategie se stejnou pravděpodobností (1/3)<ref name="tadelis"/>.

== Vězňovo dilema ==

[[Prisoner%27s_dilemma/cs|Článek na téma Vězňovo dilema]]

== Hra kuře ==

[[The_Chicken_Game/cs|Článek na téma Hra kuře]]

== Bitva pohlaví ==

[[The_Battle_of_Sexes/cs|Článek na téma Bitva pohlaví]]

== Vickreyova aukce ==

[[Vickrey_auction/cs|Článek na téma Vickreyova aukce]]

== Vězňovo dilema (více hráčů) ==

[[N-player_prisoner%27s_dilemma/cs|Článek na téma Vězňovo dilema více hráčů]]

= Literatura =
<references />

Game theory/cs - Revision history

Pokm09: Vložení učebního textu