Rozsáhlá forma hra

Rozsáhlá forma hry je specifikace hry v teorii her. Tato forma představuje hru jako strom. Každý uzel (nazývaný rozhodovací uzel) představuje každý možný stav hry tak, jak se hraje. Hra začíná na jedinečném počátečním uzlu a protéká stromem po cestě určené hráči, dokud není dosaženo terminálového uzlu, kde hra končí a výplaty jsou přiřazeny všem hráčům. Každý neterminální uzel patří hráči; tento hráč si vybere mezi možnými tahy v tomto uzlu, každý možný tah je hranou vedoucí z tohoto uzlu do jiného uzlu.

Rozsáhlá forma je alternativou k běžné formě reprezentace. Na rozdíl od běžné formy umožňuje rozsáhlá forma explicitní modelování interakcí, ve kterých hráč během hry provede více než jeden tah a pohybuje se v závislosti na různých stavech.

Hra reprezentovaná v rozsáhlé podobě

Hra vpravo má dva hráče: 1 a 2. Čísla podle každého neterminálního uzlu označují, kterému hráči daný rozhodovací uzel patří. Čísla podle každého terminálního uzlu představují výplaty hráčům (např. 2,1 představuje výplatu 2 hráči 1 a výplatu 1 hráči 2). Popisky podle každého okraje grafu jsou název akce, kterou tento okraj představuje.

Počáteční uzel patří hráči 1, což značí, že tento hráč se pohybuje jako první. Hraje se podle stromu takto: hráč 1 si vybere mezi U a D; hráč 2 sleduje volbu hráče 1 a pak si vybere mezi U‘ a D‘ . Výplaty jsou specifikovány ve stromu. Čtyři koncové uzly stromu představují čtyři výsledky: (U,U‘), (U,D‘), (D,U‘) a (D,D‘). Výplaty spojené s každým výsledkem jsou následující (0,0), (2,1), (1,2) a (3,1).

Pokud hráč 1 hraje D, hráč 2 bude hrát U‘ pro maximalizaci své výplaty a tak hráč 1 dostane pouze 1. Pokud však hráč 1 hraje U, hráč 2 maximalizuje svou výplatu hraním D‘ a hráč 1 dostane 2. Hráč 1 preferuje 2 ku 1 a tak bude hrát U a hráč 2 bude hrát D‘ . To je dokonalá rovnováha v podhře.

Může se stát, že hráč má v určitém rozhodovacím uzlu na výběr z nekonečného počtu možných akcí. Zařízení, které toto představuje, je oblouk spojující dvě hrany vyčnívající z dotyčného rozhodovacího uzlu. Je-li akční prostor kontinuem mezi dvěma čísly, jsou dolní a horní oddělující čísla umístěna v dolní a horní části oblouku, obvykle s proměnnou, která se používá k vyjádření výplat. Nekonečný počet rozhodovacích uzlů, které by mohly vzniknout, je reprezentován jediným uzlem umístěným ve středu oblouku. Podobné zařízení se používá k reprezentaci akčních prostorů, které sice nejsou nekonečné, ale jsou dostatečně velké, aby se ukázalo jako nepraktické reprezentovat s hranou pro každou akci.

Hra s nekonečnými akčními prostory zastoupenými v rozsáhlé formě

Strom vlevo představuje takovou hru, buď s nekonečnými akčními prostory (jakékoliv reálné číslo mezi 0 a 5000) nebo s velmi velkými akčními prostory (možná jakékoliv celé číslo mezi 0 a 5000). To by bylo specifikováno jinde. Zde se bude předpokládat, že je to to druhé a pro konkrétnost se bude předpokládat, že reprezentuje dvě firmy zapojené do Stackelbergovy konkurence. Výnosy firmám jsou znázorněny vlevo, s q1 a q2 jako strategií, kterou přijmou a c1 a c2 jako některé konstanty (zde mezní náklady každé firmy). Nashovu rovnováhu této hry lze nalézt tak, že vezmeme první částečnou derivaci každé výplatní funkce s ohledem na následovníkovu (firma 2) strategickou proměnnou (q2) a najdeme její nejlepší odezvovou funkci, . Stejný postup lze udělat pro vůdce s tím rozdílem, že při výpočtu svého zisku ví, že firma 2 bude hrát výše uvedenou odezvu, a tak to může být nahrazeno do jeho maximalizačního problému. Pak může vyřešit pro q1 tak, že vezme první derivaci, čímž získá . Naplnění této funkce do nejlepší odezvové funkce firmy 2, a (q1*,q2*) je Nashova rovnováha. Například, pokud c1=c2=1000, Nashova rovnováha je (2000, 1000).

Doporučujeme:  Emoční kontrola

Výhodou reprezentace hry tímto způsobem je, že je jasné, jaké je pořadí hry. Strom jasně ukazuje, že hráč 1 se pohybuje jako první a hráč 2 tento tah pozoruje. V některých hrách se však hra takto nevyskytuje. Jeden hráč ne vždy dodržuje volbu druhého (například tahy mohou být souběžné nebo tah může být skrytý). Informační sada je sada uzlů rozhodnutí taková, že:

V extenzivní formě je informační množina označena tečkovanou čárou spojující všechny uzly v této množině nebo někdy smyčkou nakreslenou kolem všech uzlů v této množině.

Hra s nedokonalými informacemi zastoupenými v rozsáhlé formě

Pokud má hra informační sadu s více než jedním členem, pak se o této hře říká, že má nedokonalé informace. Hra s dokonalými informacemi je taková, že v jakékoli fázi hry každý hráč přesně ví, co se dříve ve hře odehrálo, tj. každá informační sada je singletonová sada. Každá hra bez dokonalých informací má nedokonalé informace.

Hra na levé straně je stejná jako výše uvedená hra s tím rozdílem, že hráč 2 neví, co hráč 1 dělá, když přijde hrát. První popsaná hra má perfektní informace; hra na levé straně ne. Pokud jsou oba hráči racionální a oba vědí, že oba hráči jsou racionální a vše, co je známo jakémukoli hráči, je známo každému hráči (tj. hráč 1 ví, že hráč 2 ví, že hráč 1 je racionální a hráč 2 to ví, atd. ad infinitum), bude se hrát v první hře takto: hráč 1 ví, že pokud bude hrát U, hráč 2 bude hrát D‘ (protože pro hráče 2 je výhodnější výplata 1 než výplata 0) a tak hráč 1 dostane 2. Pokud však hráč 1 bude hrát D, hráč 2 bude hrát U‘ (protože pro hráče 2 je výplata 2 lepší než výplata 1) a hráč 1 dostane 1. Proto v první hře bude rovnováha (U, D‘ ), protože hráč 1 preferuje příjem 2 ku 1 a tak bude hrát U a tak hráč 2 bude hrát D‘ .

Doporučujeme:  Hydroxyzin

Ve druhé hře je to méně jasné: hráč 2 nemůže sledovat tah hráče 1. Hráč 1 by chtěl oklamat hráče 2, aby si myslel, že hrál U, když ve skutečnosti hrál D, takže hráč 2 bude hrát D‘ a hráč 1 dostane 3. Ve skutečnosti ve druhé hře je dokonalá Bayesovská rovnováha, kde hráč 1 hraje D a hráč 2 hraje U‘ a hráč 2 drží víru, že hráč určitě bude hrát D. V této rovnováze je každá strategie racionální vzhledem k přesvědčení, které se drží, a každé přesvědčení je v souladu s hranými strategiemi. Všimněte si, jak nedokonalost informací mění výsledek hry.

Ve hrách s nekonečným počtem akčních prostorů a nedokonalými informacemi jsou nesamostatné informační sady v případě potřeby zastoupeny vložením tečkované čáry spojující (neudální) koncové body za výše popsaný oblouk nebo pomlčkou samotného oblouku. Ve výše popsané Stackelbergově hře, pokud by druhý hráč nepozoroval tah prvního hráče, by hra již neodpovídala Stackelbergovu modelu; byla by to Cournotova soutěž.

Může se stát, že hráč přesně neví, jaké jsou výplaty ze hry nebo jakého typu jsou jeho protivníci. Tento druh hry má neúplné informace. Je reprezentován v rozsáhlé formě zavedením pojmu přírodního výběru nebo Božího výběru. Vezměme si hru spočívající v tom, že zaměstnavatel zvažuje, zda přijme uchazeče o zaměstnání. Schopnost uchazeče o zaměstnání může být jedna ze dvou věcí: vysoká nebo nízká. Úroveň jeho schopností je náhodná; je to nízká schopnost s pravděpodobností 1/3 a vysoká schopnost s pravděpodobností 2/3. V tomto případě je výhodné modelovat přírodu jako jiného hráče, který si vybírá schopnosti uchazeče podle těchto pravděpodobností. Příroda však nemá žádné výplaty. Volba přírody je reprezentována ve stromu hry nevyplněným uzlem. Hrany vycházející z přírodního výběru uzlu jsou označeny s pravděpodobností, že se událost, kterou reprezentuje, stane. Toto znázornění je výsledkem Harsanyiho transformace.

Hra s neúplnými, ale dokonalými informacemi zastoupenými v rozsáhlé formě

Hra vlevo má neúplné informace. Počáteční uzel je uprostřed a není vyplněn, takže příroda se pohybuje první. Příroda vybírá se stejnou pravděpodobností typ hráče 1 (což se v této hře rovná výběru výplat v odehrané subhře), buď t1 nebo t2. Hráč 1 má pro ně odlišné soubory informací, tj. hráč 1 ví, jaký typ je (nemusí tomu tak být). Hráč 2 však volbu přírody nedodržuje. Nezná typ hráče 1; nicméně v této hře pozoruje jednání hráče 1, tj. má perfektní informace. Nyní je skutečně vhodné výše uvedenou definici perfektní informace změnit: v každé fázi hry každý hráč ví, co hráli ostatní hráči. V případě úplné informace každý hráč ví, co hrála příroda. Soubory informací jsou znázorněny jako dříve přerušovanými řádky.

Doporučujeme:  Fotony

V této hře, pokud příroda vybere t1 jako typ hráče 1, bude hraná hra jako úplně první popsaná hra, s tím rozdílem, že hráč 2 ji nezná (a samotný fakt, že se to prostříhá přes jeho informační sady, ji diskvalifikuje ze stavu subhry). Existuje jedna oddělující dokonalou Bayesovu rovnováhu, tj. rovnováhu, ve které různé typy dělají různé věci.

Pokud oba typy hrají stejnou akci (pooling), nelze udržet rovnováhu. Pokud oba hrají D, hráč 2 si může vytvořit pouze přesvědčení, že je na jednom z uzlů v informační sadě s pravděpodobností 1/2 (protože to je šance, že uvidí jeden z obou typů). Hráč 2 maximalizuje svou výplatu hraním D‘ . Pokud však hraje D‘ , typ 2 by dal přednost hře U. To nemůže být rovnováha. Pokud oba typy hrají U, hráč 2 si opět vytvoří přesvědčení, že je na jednom z uzlů s pravděpodobností 1/2. V tomto případě hráč 2 hraje D‘ , ale pak typ 1 dává přednost hře D.

Pokud typ 1 hraje U a typ 2 hraje D, hráč 2 bude hrát D‘ jakoukoli akci, kterou pozoruje, ale pak typ 1 preferuje D. Jediná rovnováha je tedy s typem 1, který hraje D, typem 2, který hraje U‘ a hráčem 2, který hraje U‘, pokud pozoruje D a randomizuje, pokud pozoruje U. Prostřednictvím svých akcí hráč 1 signalizoval svůj typ hráči 2.

Teorie her je známá jako matematická teorie. Je možné provést axiomatickou formulaci výše uvedené struktury stromu her.

Formálně je konečná hra v extenzivní formě strukturou
a)
kde:

, Omezení na je bijection.

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