Teorie her je obor aplikované matematiky, který studuje strategické situace, kdy hráči volí různé akce ve snaze maximalizovat své výnosy. Teorie her byla nejprve vyvinuta jako nástroj pro pochopení ekonomického chování, nyní se používá v mnoha rozličných akademických oborech, od biologie po filozofii. Teorie her zaznamenala značný růst a její první formalizaci Johnem von Neumannem před a během studené války, hlavně díky její aplikaci na vojenskou strategii, především na koncept vzájemného zaručeného zničení. Počínaje 70. lety 20. století byla teorie her aplikována na chování zvířat, včetně vývoje druhů přirozeným výběrem. Kvůli zajímavým hrám, jako je vězňovo dilema, ve kterém vzájemné sobectví ubližuje všem, byla teorie her použita v politických vědách, etice a filozofii. A konečně, teorie her nedávno přitáhla pozornost počítačových vědců kvůli svému použití v umělé inteligenci a kybernetice.
Ačkoli je teorie her podobná teorii rozhodování, studuje rozhodnutí, která jsou činěna v prostředí, kde se různí hráči vzájemně ovlivňují. Jinými slovy, teorie her studuje volbu optimálního chování, když náklady a přínosy každé možnosti nejsou fixní, ale závisí na volbě ostatních jedinců.
Hry studované teorií her jsou přesně definované matematické objekty. Hra se skládá z množiny hráčů, množiny tahů (nebo strategií), které mají tito hráči k dispozici, a specifikace výplat pro každou kombinaci strategií. Existují dva způsoby reprezentace her, které jsou v literatuře běžné.
Běžná (nebo strategická forma) hra je matice, která ukazuje hráče, strategie a výplaty (viz příklad vpravo). Zde jsou dva hráči; jeden si vybere řadu a druhý sloupec. Každý hráč má dvě strategie, které jsou určeny počtem řad a počtem sloupců. Výplaty jsou poskytovány v interiéru. První číslo je výplata, kterou obdržel řadový hráč (hráč 1 v našem příkladu); druhé je výplata pro sloupcového hráče (hráč 2 v našem příkladu). Předpokládejme, že hráč 1 hraje nahoře a hráč 2 hraje vlevo. Pak hráč 1 dostane 4 a hráč 2 dostane 3.
Když je hra prezentována v normální formě, předpokládá se, že každý hráč jedná současně nebo alespoň, aniž by znal jednání druhého hráče. Pokud mají hráči nějaké informace o možnostech jiných hráčů, je hra obvykle prezentována v rozsáhlé formě.
Rozsáhlé formulářové hry se snaží zachytit hry s nějakým důležitým pořadím. Hry jsou zde prezentovány jako stromy (na obrázku vlevo). Každý vrchol (nebo uzel) zde představuje bod výběru pro hráče. Hráč je určen číslem uvedeným vrcholem. Čáry mimo vrchol představují možnou akci pro tohoto hráče. Výhry jsou specifikovány ve spodní části stromu.
Ve hře na obrázku jsou dva hráči. Hráč 1 se pohybuje jako první a vybírá buď F nebo U. Hráč 2 vidí tah hráče 1 a pak si vybere A nebo R. Předpokládejme, že Hráč 1 si vybere U a pak Hráč 2 si vybere A, pak Hráč 1 dostane 8 a Hráč 2 dostane 2.
Hry s extenzivním tvarem mohou také zachytit hry se současným pohybem. Buď je kolem dvou různých vrcholů nakreslena tečkovaná čára nebo kruh, aby je hráči reprezentovali jako součást stejné informační sady (tj. hráči nevědí, ve kterém bodě se nacházejí).
Symetrická hra je hra, kde odměna za hraní určité strategie závisí pouze na ostatních použitých strategiích, nikoliv na tom, kdo je hraje. Pokud lze identitu hráčů změnit, aniž by se změnila odměna za strategie, pak je hra symetrická. Mnohé z běžně studovaných her 2×2 jsou symetrické. Standardní reprezentace kuřete, vězňovo dilema a hon na jelena jsou symetrické hry.
Nejčastěji studované asymetrické hry jsou hry, kde nejsou stejné sady strategií pro oba hráče. Například hra s ultimátem a podobně hra s diktátorem mají různé strategie pro každého hráče. Je však možné, aby hra měla stejné strategie pro oba hráče, a přesto byla asymetrická. Například hra zobrazená vpravo je asymetrická, přestože má stejné sady strategií pro oba hráče.
Ve hrách s nulovým součtem se celkový přínos pro všechny hráče ve hře, pro každou kombinaci strategií, vždy přičte k nule (nebo neformálněji řečeno, hráč těží pouze na úkor ostatních). Poker je příkladem hry s nulovým součtem (ignoruje možnost výhry domu), protože jeden vyhraje přesně částku, kterou jeho protivníci prohrají. Ostatní hry s nulovým součtem zahrnují shodné pence a většinu klasických stolních her včetně go a šachů. Mnoho her studovaných teoretiky her (včetně dilematu slavného vězně) jsou hry s nenulovým součtem, protože některé výsledky mají čisté výsledky větší nebo menší než nula. Neformálně, ve hrách s nenulovým součtem, zisk jednoho hráče nemusí nutně odpovídat ztrátě jiného hráče.
Je možné přeměnit jakoukoli hru na hru s nulovým součtem přidáním dalšího falešného hráče (často nazývaného „deska“), jehož ztráty kompenzují čisté výhry hráčů.
Simultánní a sekvenční
Simultánní hry jsou hry, kde se oba hráči pohybují současně, nebo pokud se nepohybují současně, pozdější hráči nevědí o akcích předchozích hráčů (což je činí fakticky simultánními). Sekvenční hry (nebo dynamické hry) jsou hry, kde pozdější hráči mají určité znalosti o dřívějších akcích. Nemusí se jednat o dokonalé znalosti o každé akci dřívějších hráčů; může se jednat o velmi málo informací. Hráč může například vědět, že dřívější hráč neprovedl jednu konkrétní akci, zatímco neví, kterou z dalších dostupných akcí první hráč skutečně provedl.
Rozdíl mezi simultánními a sekvenčními hrami je zachycen v různých reprezentacích popsaných výše. Normální forma se používá pro reprezentaci simultánních her a extenzivní forma se používá pro reprezentaci sekvenčních her.
Perfektní informace a nedokonalé informace
Hra s nedokonalými informacemi (tečkovaná čára představuje neznalost ze strany hráče 2)
Důležitá podmnožina sekvenčních her se skládá z her s dokonalou informací. Hra je jednou z dokonalých informací, pokud všichni hráči znají tahy dříve provedené všemi ostatními hráči. Tudíž pouze sekvenční hry mohou být hrami s dokonalou informací, protože v souběžných hrách ne každý hráč zná akce ostatních. Většina her studovaných v teorii her jsou nedokonalé informační hry, i když některé zajímavé hry jsou hrami s dokonalou informací, včetně hry s ultimátem a stonožkovou hrou. Mnoho populárních her jsou hry s dokonalou informací včetně šachů, go a mankaly.
Dokonalé informace jsou často zaměňovány s úplnými informacemi, což je podobný koncept. Úplné informace vyžadují, aby každý hráč znal strategie a výplaty ostatních hráčů, ale ne nutně akce.
Z pochopitelných důvodů jsou hry, jak je studují ekonomové a herní hráči v reálném světě, zpravidla dokončeny v konečném počtu tahů. Čistí matematici nejsou tak omezeni a teoretici množin zejména studují hry, které trvají nekonečně mnoho tahů, přičemž vítěz (nebo jiná výplata) není znám, dokud nejsou všechny tyto tahy dokončeny.
Pozornost se obvykle nesoustředí ani tak na to, jaký je nejlepší způsob, jak takovou hru hrát, ale jednoduše na to, zda má jeden nebo druhý hráč vítěznou strategii. (Pomocí axiomu výběru lze dokázat, že existují hry – i s perfektními informacemi, a kde jediným výsledkem je „výhra“ nebo „prohra“ – pro které ani jeden hráč nemá vítěznou strategii.) Existence takových strategií má pro chytře navržené hry důležité důsledky v teorii deskriptivní množiny.
Hry v té či oné podobě jsou široce využívány v mnoha různých akademických disciplínách.
Ekonomové používají teorii her k analýze široké škály ekonomických jevů, včetně aukcí, smlouvání, duopolů a oligopolů, vytváření sociálních sítí a hlasovacích systémů. Tento výzkum se obvykle zaměřuje na konkrétní sady strategií známých jako rovnováha ve hrách. Tyto „koncepty řešení“ jsou obvykle založeny na tom, co vyžadují normy racionality. Nejznámější z nich je Nashova rovnováha. Sada strategií je Nashova rovnováha, pokud každá představuje nejlepší reakci na ostatní strategie. Pokud tedy všichni hráči hrají strategie v Nashově rovnováze, nemají žádnou motivaci se odchýlit, protože jejich strategie je nejlepší, jakou mohou udělat vzhledem k tomu, co dělají ostatní.
Výplaty ze hry jsou obecně považovány za reprezentaci užitečnosti jednotlivých hráčů. V modelových situacích často výplaty představují peníze, což pravděpodobně odpovídá užitečnosti jednotlivce. Tento předpoklad však může být chybný.
Prototypní práce o teorii her v ekonomii začíná představením hry, která je abstrakcí nějaké konkrétní ekonomické situace. Je vybrán jeden nebo více konceptů řešení a autor demonstruje, které strategie v prezentované hře jsou rovnováhy vhodného typu. Přirozeně by se člověk mohl ptát, k čemu by tyto informace měly být použity. Ekonomové a profesoři ekonomie navrhují dvě primární použití.
Třífázová stonožková hra
Prvním použitím je informovat nás o tom, jak se chová skutečná lidská populace. Někteří učenci věří, že nalezením rovnováhy her mohou předpovědět, jak se bude chovat skutečná lidská populace, když bude konfrontována se situacemi analogickými ke zkoumané hře. Tento konkrétní pohled na teorii her se stal terčem nedávné kritiky. Za prvé je kritizován, protože předpoklady vytvořené teoretiky her jsou často porušovány. Teoretici her mohou předpokládat, že hráči vždy jednají racionálně, aby maximalizovali své výhry (model Homo economicus), ale skuteční lidé často jednají buď iracionálně, nebo racionálně, aby maximalizovali výhry nějaké větší skupiny lidí (altruismus). Teoretici her reagují tím, že srovnávají své předpoklady s těmi, které se používají ve fyzice. Tudíž i když jejich předpoklady ne vždy platí, mohou považovat teorii her za rozumný vědecký ideál podobný modelům, které používají fyzici. Nicméně další kritika tohoto použití teorie her byla vznesena, protože některé experimenty prokázaly, že jednotlivci nehrají rovnovážné strategie. Například ve hře Stonožka, Hádej 2/3 průměrné hry a ve hře Diktátor lidé pravidelně nehrají Nashovu rovnováhu. Probíhá debata o významu těchto experimentů.
Alternativně někteří autoři tvrdí, že Nashova rovnováha neposkytuje předpovědi pro lidskou populaci, ale spíše poskytuje vysvětlení, proč populace, které hrají Nashovu rovnováhu, zůstávají v tomto stavu. Nicméně otázka, jak populace dosáhnou těchto bodů, zůstává otevřená.
Někteří teoretici her se obrátili na evoluční teorii her, aby tyto starosti vyřešili. Tyto modely nepředpokládají buď žádnou racionalitu, nebo omezenou racionalitu ze strany hráčů. Navzdory názvu evoluční teorie her nepředpokládá nutně přirozený výběr v biologickém smyslu. Evoluční teorie her zahrnuje jak biologickou, tak kulturní evoluci a také modely individuálního učení (například fiktivní dynamiku hry).
Na druhou stranu, někteří učenci nepovažují teorii her za prediktivní nástroj pro chování lidských bytostí, ale za návrh, jak by se lidé měli chovat. Protože Nashova rovnováha hry představuje nejlepší reakci na jednání ostatních hráčů, zdá se být vhodné hrát strategii, která je součástí Nashovy rovnováhy. Nicméně, toto použití teorie her se také stalo terčem kritiky. Za prvé, v některých případech je vhodné hrát nerovnovážnou strategii, pokud se očekává, že ostatní budou hrát také nerovnovážné strategie. Například, viz Hádej 2/3 průměru.
Za druhé, Vězňovo dilema představuje další potenciální protipříklad. Ve Vězňově dilematu vede každý hráč sledující své vlastní zájmy k tomu, že jsou na tom oba hráči hůře, než kdyby nesledovali své vlastní zájmy. Někteří učenci se domnívají, že to demonstruje selhání teorie her jako doporučení pro chování.
Na rozdíl od ekonomie jsou odměny za hry v biologii často interpretovány jako odpovídající kondici. Kromě toho byl důraz kladen méně na rovnováhu, která odpovídá pojmu racionality, ale spíše na ty, které by byly udržovány evolučními silami. Nejznámější rovnováha v biologii je známá jako Evoluční stabilní strategie neboli (ESS) a byla poprvé představena Johnem Maynardem Smithem (popsáno v jeho knize z roku 1982). Ačkoli její počáteční motivace nezahrnovala žádný z mentálních požadavků Nashovy rovnováhy, každá ESS je Nashovou rovnováhou.
V biologii byla teorie her použita k pochopení mnoha různých jevů. Poprvé byla použita k vysvětlení vývoje (a stability) přibližných poměrů pohlaví 1:1. Ronald Fisher (1930) naznačil, že poměry pohlaví 1:1 jsou výsledkem evolučních sil působících na jedince, kteří by mohli být považováni za snažící se maximalizovat počet svých vnoučat.
Biologové navíc použili evoluční teorii her a ESS k vysvětlení vzniku komunikace mezi zvířaty (Maynard Smith & Harper, 2003). Analýza signalizačních her a dalších komunikačních her poskytla určitý vhled do vývoje komunikace mezi zvířaty.
Konečně biologové použili hru jestřáb-holub (také známou jako kuře) k analýze bojového chování a teritoriality.
Počítačová věda a logika
Teorie her začíná hrát stále důležitější roli v logice a v informatice. Několik logických teorií má základ v herní sémantice. Kromě toho počítačoví vědci používají hry k modelování interaktivních výpočtů.
Výzkum v politologii také využil teorii her. Teoretické vysvětlení demokratického míru spočívá v tom, že veřejná a otevřená debata v demokraciích vysílá jasné a spolehlivé informace týkající se záměrů jiným státům. Naopak je obtížné poznat záměry nedemokratických vůdců, jaký účinek budou mít ústupky a zda budou sliby dodrženy. Tudíž vznikne nedůvěra a neochota k ústupkům, pokud alespoň jedna ze stran sporu bude nedemokratická.
Teorie her má ve filozofii několik využití. V reakci na dvě práce W.V.O. Quinea (1960, 1967) použil David Lewis (1969) teorii her k rozvoji filozofického popisu konvencí. Přitom poskytl první analýzu obecných znalostí a použil ji při analýze hry v koordinačních hrách. Kromě toho poprvé naznačil, že lze chápat význam ve smyslu signalizačních her. Tento pozdější návrh sledovalo od Lewise několik filozofů (Skyrms 1996, Grim et al. 2004).
V etice se někteří autoři pokusili pokračovat v projektu, započatém Thomasem Hobbesem, odvozování morálky z vlastních zájmů. Protože hry jako Vězeňské dilema představují zjevný konflikt mezi morálkou a vlastními zájmy, je vysvětlení, proč je spolupráce vyžadována vlastními zájmy, důležitou součástí tohoto projektu. Tato obecná strategie je součástí obecného pohledu na společenskou smlouvu v politické filosofii (pro příklady viz Gauthier 1987 a Kavka 1986).
A konečně, další autoři se pokusili použít evoluční teorii her, aby vysvětlili vznik lidských postojů k morálce a odpovídajícímu chování zvířat. Tito autoři se dívají na několik her včetně Vězeňského dilematu, Lovu jelenů a Nashovy vyjednávací hry jako na vysvětlení vzniku postojů k morálce (viz např. Skyrms 1996, 2004; Sober and Wilson 1999).
První známá diskuse o teorii her se objevila v dopise, který napsal James Waldegrave v roce 1713. V tomto dopise Waldegrave poskytuje řešení smíšené strategie minimax pro dvoučlennou verzi karetní hry le Her. Až publikace Antoina Augustina Cournota Výzkumy matematických principů teorie bohatství v roce 1838 se zabývala obecnou analýzou teorie her. V této práci Cournot zvažuje duopol a předkládá řešení, které je omezenou verzí Nashovy rovnováhy.
I když je Cournotova analýza obecnější než Waldegraveho, teorie her ve skutečnosti neexistovala jako unikátní obor, dokud John von Neumann v roce 1928 nevydal sérii prací. Tyto výsledky byly později rozšířeny v roce 1944 v knize Teorie her a ekonomického chování von Neumanna a Oskara Morgensterna. Tato hluboká práce obsahuje metodu pro hledání optimálních řešení pro hry s nulovým součtem pro dvě osoby. Během tohoto období byla práce na teorii her primárně zaměřena na kooperativní teorii her, která analyzuje optimální strategie pro skupiny jednotlivců za předpokladu, že mohou vynucovat dohody mezi nimi o správných strategiích.
V roce 1950 se objevila první diskuse o Vězňově dilematu a na této hře byl proveden experiment v korporaci RAND. Zhruba v té samé době John Nash vypracoval definici „optimální“ strategie pro hry pro více hráčů, kde žádné takové optimální nebylo dříve definováno, známou jako Nashova rovnováha. Tato rovnováha je dostatečně obecná, což umožňuje analýzu nespolupracujících her kromě kooperativních.
Teorie her zažila bouřlivou aktivitu v 50. letech 20. století, během které byly vyvinuty koncepty jádra, rozsáhlé formy hry, fiktivní hry, opakovaných her a Shapleyho hodnoty. Kromě toho se během této doby objevily první aplikace teorie her na filozofii a politické vědy.
V roce 1965 představil Reinhard Selten svůj koncept řešení subgame perfect equilibria, který dále zdokonalil Nashovu rovnováhu (později představil také třesoucí se ruku dokonalosti). V roce 1967 John Harsanyi vyvinul koncepty kompletních informací a bayesovských her. Spolu s Johnem Nashem a Reinhardem Seltenem získal v roce 1994 Cenu Švédské banky za ekonomické vědy na památku Alfreda Nobela.
V 70. letech 20. století byla teorie her rozsáhle aplikována v biologii, především díky práci Johna Maynarda Smithe a jeho evoluční stabilní strategii. Kromě toho byly zavedeny a analyzovány koncepty korelované rovnováhy, třesoucí se ruky dokonalosti a obecného poznání.
V roce 2005 získali herní teoretici Thomas Schelling a Robert Aumann Cenu Švédské banky za ekonomické vědy. Schelling pracoval na dynamických modelech, prvních příkladech evoluční teorie her. Aumann přispěl více k rovnovážné škole, rozvíjel rovnovážné zhrubnutí korelované rovnováhy a rozvíjel rozsáhlou analýzu předpokladu obecného poznání.
Normal-form game · Extensive-form game · Cooperative game · Information set · Preference
Nashova rovnováha · Podherní dokonalost · Bayesovská-Nashova · Dokonalá Bayesovská · Třesoucí se ruka · Správná rovnováha · Epsilonová rovnováha · Korelovaná rovnováha · Sekvenční rovnováha · Kvazidokonalá rovnováha · Evolučně stabilní strategie · Riziková dominance · Paretova efektivita
Dominantní strategie · Pure strategy · Mixed strategy · Tit for tat · Grim trigger · Collusion · Backward induction
Symetrická hra · Perfektní informace · Dynamická hra · Sekvenční hra · Opakovaná hra · Signalizační hra · Levné povídání · Hra s nulovým součtem · Mechanismus design · Vyjednávací problém · Stochastická hra · Nontransitivní hra · Globální hry
Vězeňské dilema · Cestovatelské dilema · Koordinační hra · Kuře · Dobrovolnické dilema · Aukce dolarů · Bitva pohlaví · Lov jelenů · Odpovídající mince · Hra s ultimátem · Menšinová hra · Kámen-nůžky-papír · Pirátská hra · Hra s diktátorem · Hra s veřejnými statky · Blotto hry ·Válka opotřebení ·El Farol Bar problém ·Stříhání dortů ·Cournot hra ·Deadlock ·Dinerovo dilema ·Hádej 2/3 průměru ·Kuhn poker ·Nash vyjednávací hra ·Screening hra ·Signalizační hra ·Trust hra ·Princezna a monstrum hra
Minimaxova věta · Purifikační věta · Folková věta · Zjevovací princip · Arrowova věta o nemožnosti