Dokonalá rovnováha podhry - Subgame perfect equilibrium

Subgame Perfect Equilibrium
A koncepce řešení v herní teorie
Vztah
PodmnožinaNashova rovnováha
Protíná seEvolučně stabilní strategie
Význam
NavrhlReinhard Selten
PoužíváRozsáhlé hry ve formě
PříkladHra Ultimatum

v herní teorie, a subgame dokonalá rovnováha (nebo subgame dokonalá Nashova rovnováha) je upřesnění a Nashova rovnováha použito v dynamické hry. A profil strategie je subgame dokonalá rovnováha, pokud představuje Nashovu rovnováhu každého dílčí hra původní hry. Neformálně to znamená, že v kterémkoli bodě hry by chování hráčů od tohoto okamžiku mělo představovat Nashovu rovnováhu pokračující hry (tj. Podhry), bez ohledu na to, co se stalo dříve. Každý konečná rozsáhlá hra s dokonalým odvoláním má podhru dokonalou rovnováhu.[1]

Běžnou metodou pro určení dokonalé rovnováhy subgame v případě konečné hry je zpětná indukce. Zde se nejprve zváží poslední akce ve hře a určí se, jaké akce by měl za všech okolností podniknout poslední hybatel, aby maximalizoval svoji hru nástroj. Jeden pak předpokládá, že poslední akce provede tyto akce, a vezme v úvahu předposlední akce, přičemž znovu zvolí ty, které maximalizují užitečnost tohoto herce. Tento proces pokračuje, dokud jeden nedosáhne prvního tahu hry. Zbývající strategie jsou souborem všech subgame dokonalých rovnováh pro konečné hry s dokonalými informacemi o konečném horizontu.[1] Zpětnou indukci však nelze použít na hry o nedokonalý nebo neúplné informace protože to znamená proříznutí ne-singletonu informační sady.

Dokonalá rovnováha podhry nutně uspokojuje princip jednorázové odchylky.

Sada dokonalých rovnováh dílčí hry pro danou hru je vždy podmnožinou sady Nashových rovnováh pro danou hru. V některých případech mohou být sady identické.

The hra ultimátum poskytuje intuitivní příklad hry s menším počtem subgame dokonalých rovnováh než Nashovy rovnováhy.

Příklad

Stanovení dokonalé rovnováhy podhry pomocí zpětné indukce je uvedeno níže na obrázku 1. Strategie pro hráče 1 jsou dány {Up, Uq, Dp, Dq}, zatímco hráč 2 má strategie mezi {TL, TR, BL, BR}. V tomto příkladu jsou 4 dílčí hry se 3 správnými dílčími hrami.

Obrázek 1

Pomocí zpětné indukce provedou hráči pro každou dílčí hru následující akce:

  • Podhra pro akce p a q: Hráč 1 provede akci p s výplatou (3, 3), aby maximalizoval výplatu hráče 1, takže výplata pro akci L se stane (3,3).
  • Podhry pro akce L a R: Hráč 2 provede akci L pro 3> 2, takže výplata pro akci D bude (3, 3).
  • Podhry pro akce T a B: Hráč 2 provede akci T, aby maximalizoval výplatu hráče 2, takže výplata pro akci U se stane (1, 4).
  • Podhry pro akce U a D: Hráč 1 provede akci D, aby maximalizoval výplatu hráče 1.

Dokonalá rovnováha podhry je tedy {Dp, TL} s výplatou (3, 3).

Rozsáhlá hra s neúplnými informacemi je uvedena níže na obrázku 2. Všimněte si, že uzel pro hráče 1 s akcemi A a B a všechny následující akce je subgame. Uzly hráče 2 nejsou subgame, protože jsou součástí stejné sady informací.

Obrázek 2

První normální forma hry je normální forma reprezentace celé rozsáhlé hry. Na základě poskytnutých informací jsou (UA, X), (DA, Y) a (DB, Y) všechny Nashovy rovnováhy pro celou hru.

Druhá hra v normální formě je normální formou reprezentace dílčí hry, počínaje druhým uzlem hráče 1 s akcemi A a B. U druhé hry v normální formě je Nashova rovnováha dílčí hry (A, X).

Pro celou hru nejsou Nashovy rovnováhy (DA, Y) a (DB, Y) podhrou dokonalé ekvilibrie, protože tah hráče 2 nepředstavuje Nashovu rovnováhu. Nashova rovnováha (UA, X) je podhrou dokonalá, protože do své strategie zahrnuje podhru Nashova rovnováha (A, X).[2]

Chcete-li tuto hru vyřešit, nejprve najděte Nash Equilibria vzájemnou nejlepší odpovědí Subgame 1. Poté použijte zpětnou indukci a zapojte (A, X) → (3,4), aby se (3,4) stala přínosem pro Subgame 2.[2]

Přerušovaná čára naznačuje, že hráč 2 neví, zda hráč 1 bude hrát A nebo B v simultánní hře.

Subgame 1 je vyřešena a (3,4) nahradí celou Subgame 1 a hráč si vybere U -> (3,4) Řešení pro Subgame 1

Hráč 1 zvolí spíše U než D, protože 3> 2 pro výplatu hráče 1. Výsledná rovnováha je (A, X) → (3,4).

Řešení Subgame Perfect Equilibrium

Dokonalá rovnováha subhry prostřednictvím zpětné indukce je tedy (UA, X) s výplatou (3, 4).

V konečně opakovaných hrách

Pokud jde o konečně opakované hry, má-li jevištní hra pouze jednu jedinečnou Nashovu rovnováhu, dokonalou rovnováhou podhry je hrát bez zvážení minulých akcí a zacházet s aktuální podhrou jako s jednorázovou hrou. Příklad toho je konečně opakován Vězňovo dilema hra. Při použití zpětné indukce vyžaduje poslední dílčí hra v definitivně opakovaném Prisonerově dilematu, aby hráči hráli jedinečnou Nashovu rovnováhu (oba hráči přeběhli). Z tohoto důvodu budou všechny hry před poslední dílčí hrou hrát také Nashovu rovnováhu, aby maximalizovaly své výplaty v jednom období.

Pokud jevištní hra v definitivně opakované hře má několik Nashových rovnováh, lze vytvořit dokonalou rovnováhu podhry, aby bylo možné hrát Nashovy jevištní ekvilibrické akce prostřednictvím „mrkve a tyčinky“. Jeden hráč může použít Nash rovnováhu jedné fáze hry k pobídce k hraní jiné než Nashovy rovnovážné akce, zatímco může použít Nash rovnováhu scénické hry s nižší výplatou pro druhého hráče, pokud se rozhodne přeběhnout.[3]

Nalezení rovnováhy dokonalé subgame

Jedna hra, ve které je dobře známo řešení zpětné indukce, je piškvorky

Reinhard Selten dokázal, že každá hra, kterou lze rozdělit na „dílčí hry“ obsahující dílčí sadu všech dostupných možností v hlavní hře, bude mít podhru dokonalou strategii Nash Equilibrium (možná jako smíšená strategie dávat nedeterministická rozhodnutí o dílčích hrách). Dokonalost subgame se používá pouze u her úplné informace. Subgame perfection lze použít s rozsáhlá forma hry kompletní ale nedokonalé informace.

Dokonalá Nashova rovnováha podhry je obvykle odvozena z "zpětná indukce "z různých konečných výsledků hry, vyloučení větví, které by zahrnovaly hráče, který by provedl tah, který je." nedůvěryhodné (protože to není optimální) z toho uzel. Jedna hra, ve které je dobře známo řešení zpětné indukce, je piškvorky, ale teoreticky dokonce Jít má takovou optimální strategii pro všechny hráče. Problém vztahu mezi dokonalostí podhry a zpětnou indukcí vyřešil Kaminski (2019), který dokázal, že zobecněný postup zpětné indukce vytváří všechny podhry dokonalé rovnováhy ve hrách, které mohou mít nekonečnou délku, nekonečné akce jako každá sada informací a nedokonalé informace, pokud je splněna podmínka konečné podpory.

Zajímavým aspektem slova „důvěryhodný“ v předchozím odstavci je to, že jako celek (bez ohledu na nevratnost dosažení dílčích her) existují strategie, které jsou lepší než dokonalé strategie podhry, ale které nejsou důvěryhodné v tom smyslu, že by hrozba jejich provedení poškodí hráče vytvářejícího hrozbu a zabrání této kombinaci strategií. Například ve hře „kuře „Pokud má jeden hráč možnost vytrhnout volant ze svého vozu, měl by si ho vždy vzít, protože to vede k„ dílčí hře “, ve které je jeho racionálnímu protivníkovi vyloučeno dělat totéž (a oba je zabít). -ripper vždy vyhraje hru (čímž se jeho protivník odvrátí) a hrozba oponenta, že bude suicidálně následovat, není věrohodná.

Viz také

Reference

  1. ^ A b Osborne, M. J. (2004). Úvod do teorie her. Oxford University Press.
  2. ^ A b Joel., Watson (09.05.2013). Strategie: úvod do teorie her (Třetí vydání.). New York. ISBN  9780393918380. OCLC  842323069.
  3. ^ Takako, Fujiwara-Greve. Nespolupracující teorie her. Tokio. ISBN  9784431556442. OCLC  911616270.

externí odkazy