Multistage Games/cs

Úvod

Pojmem vícekolové hry rozumíme situaci, kdy hráči hrají sérii jednorázových her, které na sebe volně navazují. Hráči dle výsledku předchozích her rozhodují o svých následujících tazích a snaží se dosáhnout požadovaného zisku.

Jako příklad můžeme vzít poslance, kteří se na pravidelných schůzkách Poslanecké sněmovny snaží prosadit nebo ovlivnit návrh projednávaných zákonů. To, jak se jim to podaří, bude mít v důsledku vliv na voliče v následujících volbách a na výsledný prospěch poslance.

Vícekolové hry patří mezi hry v rozšířené formě, kdy hráči rozhodují konfliktní situaci po tazích. Rozhodnutí jednoho hráče o volbě jeho strategie ovlivňují předchozí tahy ostatních hráčů. Celá hra je procesem sekvence rozhodnutí jednotlivých hráčů.

Definice

Vícekolová hra je konečná posloupnost jednorázových her, kde každá z nich je hra s úplnou ale nedokonalou informací. Tyto hry jsou hrány postupně stejnými hráči a celkový zisk je určen dle výsledků jednotlivých her. Je zde předpoklad, že každá hra je hrána v odlišnou dobu, tedy že hra č.1 je hrána v době č.1, hra č.2 v době č.2, atd. Předpokladem také je, že výsledek každé hry je znám všem hráčům.

Je důležité si uvědomit, že hráči, když vědí, že bude následovat další kolo, mohou plánovat a podmínit si své budoucí tahy. Jejich tahy budou velice pravděpodobně založeny na základě výsledků aktuálního kola či na základě výsledků již kol proběhlých.

Základní předpoklady

U každé hry v rozšířené formě bychom si měli ujasnit určité okolnosti dané hry a vícekolové hry nejsou výjimkou.

Jedná se především o tyto parametry:

• Hráče, kteří hru hrají,
• kdy je hráč na tahu,
• jaké má hráč možnosti při každém svém tahu,
• co hráč ví/zná při každém svém tahu,
• zisk, který je možné získat při jakékoliv kombinaci tahů.

Vyjasnění si těchto bodů nám pomůže lépe porozumět každé proběhlé či probíhající hře.

Pro vícekolové hry platí mimo jiné následující tři parametry:

• V každém kole Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} znají všichni hráči všechny tahy, provedené v předchozích kolech,
• každý hráč má v každém z kol nanejvýš jeden tah a
• žádná z informačních sad pro právě hrané kolo nepopisuje plánované tahy jednotlivých hráčů.

Typy

Níže jsou popsány dva typy vícekolových her dle G. Noldeka.

Obecně se při vícekolových hrách mluví především o prvním typu vícekolové hry, tedy hry s pozorovanými akcemi.

Vícekolové hry s pozorovanými akcemi

Předpokladem této hry je, že každý hráč zná historii předešlých kol.

Parametry pro každé kolo:

• počet hráčů: i=1..n
• aktuální kolo: k = 1..n
• historie předešlého kola: h0..hn

1) Hra začíná v kole k=1. Protože se jedná o první kolo, tahy v této hře nejsou ovlivněny jinými hrami. Historie předchozího kola h0 je tedy rovna nule. Jednotliví hráči provedou své tahy a kolo končí. Výsledek tohoto kola je zapsán jako h1, což je vstup pro navazující kolo.

2) Ve druhém kole (k=2) hráči znovu provedou své tahy, tentokrát jsou ale jejich tahy ovlivněny výsledkem kola předchozího (h1). V závislosti na historii je hra ukončena nebo pokračuje dalším kolem. Výsledek kola je označen jako h2.

3) Hra pokračuje až do posledního kola, kde k=n. Poslední kolo je buď předem známo, nebo je určeno historií předešlého kola.

Historie hn, po které již nenásleduje další kolo, se nazývá ukončovací historie (terminal history).

Vícekolové hry s dokonalou informací

V případě této hry provádí svůj tah v každém kole pouze jediný hráč. I zde je předpokladem, že každý hráč zná historii předešlých kol.

1) Hra začíná v kole k=1. Hráč č.1 provede tah a toto kolo je ukončeno.

2) V kole k=2 hraje hráč č.2, který provede svůj tah. Tento tah může ale i nemusí reagovat na výsledek předchozího kola, kdy hrál hráč č.1. Pokud toto kolo není poslední, hra pokračuje dalším kolem, kdy hraje další hráč.

Pokud hru hrají více než dva hráči, hráči nemusí hrát v definovaném pořadí po sobě, ale mohou se v tazích náhodně střídat.

Pokud u této hry známe počet kol, je zde možné vytvořit strategii na základě zpětné indukce, kdy analyzujeme hru zpětně od nejlepšího možného tahu posledního hráče. Na základě zpětné indukce je také možné určit Nashovu rovnováhu vícekolové hry.

Ukázka vícekolové hry

Mějme dva hráče, kteří hrají hru typu vězňovo dilema. Každý z hráčů tedy může buď mluvit a přiznat se (B,D), nebo zapírat a spoléhat na to, že druhý hráč udělá to samé (A,C).

Po dohrání této hry (a odpykání si patřičných let) se oba hráči dostávají k možnosti odplaty a ocitají se v situaci, kdy každý z nich se může přidat do gangu (G) nebo zůstat sám (S). Situace je znázorněna v následující matici.

Pokud oba hráči zvolí S, tak bez ohledu na výsledek předešlé hry si každý půjde svou cestou a zisk obou bude 0. Pokud oba vstoupí do gangu (G), budou spolu bojovat, utrží ztrátu a jejich výsledný zisk bude -3. Třetí situace je, když jeden z hráčů zvolí vstup do gangu (G) a druhý zůstane sám (S). Ten co bude sám se neubrání a utrpí velkou ztrátu -4. Druhý hráč, který se stal součástí gangu, je pouze mírně zraněn, a jeho zisk z této hry je -1.

Pokud budeme každou z výše uvedených her hrát samostatně, hráči nebudou hry brát v souvislostech a budou se snažit v každé dosáhnout nejlepšího výsledku. Pokud ale hráč ví, že hry budou na sebe navazovat, má možnost vytvořit si strategii a chovat se podle ní.

Vezměme si hráče 1. Hráč 1 se rozhodne, že v 1. hře bude hrát B (mluvit) a ve 2. hře bude hrát S (sám) pouze v tom případě, pokud hráč 2 bude v první hře hrát C (zapírat). V tomto případě by hráč 1 měl z první hry zisk 6 a z druhé hry 0.

Pokud ale hráč 2 v první hře bude mluvit (D), hráč 1 má naplánováno, že v druhé hře bude hrát G (gang). Dá se očekávat, že obdobně bude mít připravenou strategii i hráč 2.

Tuto strategii lze obecně zapsat takto:

 Pokud ve hře 1,2, ..., t−1 nastane určitá situace, pak ve hře t zvolím akci a.

Stromový graf hry v rozšířené formě. Zdroj:

Pokud se podíváme znovu na první hru, tak tato hra má čtyři možné výsledky. Každý hráč by měl mít naplánovanou strategii pro další hru pro každý z těchto výsledků, protože nikdy neví, jak bude hrát protihráč. Všechny možné situace je dobré pro přehlednost znázornit např. pomocí stromového grafu. Ukázka realizace takovéhoto grafu je znázorněna na přiloženém obrázku.

Celkový získ

Při určení celkového zisku vícekolové hry je nutné počítat s během času a s očekávaným snižováním hodnoty zisku budoucí hry (která se bude konat např. za rok nebo se nemusí konat vůbec) oproti hře, konané dříve. Celkový zisk se počítá obdobně, jako výpočet současné hodnoty v podnikové ekonomice.

Vezměme příklad, kdy máme dvě hry, jedna byla hrána dnes a druhá až za dva roky. Zisk z obou her je stejný, např. 10. Hodnota zisku z druhé hry je ale nižší než ze hry, hrané dnes, protože aktuální zisk má pro nás větší hodnotu. Pokud budeme brát, že zisk jsou peněžní prostředky, tak dnes je můžeme investovat (např. uložit na vkladový účet) a do zítřka nám přinesou výnos (úrok). Budoucí zisk je nižší právě o tento získaný úrok.

Druhou možností odůvodnění snížení hodnoty budoucího zisku je pravděpodobnost konání budoucí hry. Nikdy si nemůžeme být 100% jisti, že se další hra bude konat. Zisk z první hry je spolehlivější a má větší hodnotu, než zisk z druhé hry, u které je určitá pravděpodobnost, že se nebude konat (a tedy nezískáme žádný zisk/peníze).

Strategie

Pro zvolení vhodné strategie pro všechny hráče je u vícekolových her zavedena tzv. sekvenční rovnováha. Sekvenční rovnováha určuje strategii pro každého hráče a zároveň rozložení pravděpodobnosti pro každý z uzlů v informační sadě. Více viz Bayovská rovnováha.

Strategii pro vícekolovou hru lze také určit pomocí dokonalé rovnováhy podher.

Dokonalé rovnováha podher (Subgame Perfect Equilibrium)

Zdroj:

Sada strategií ve vícekolové hře s pozorovanými akcemi má dokonalou rovnováhu podher, pokud obsahuje Nashovu rovnováhu v každé podhře originální hry.

Dokonalá rovnováha podher se používá při řešení opakujících se her a je jí možné určit pomocí zpětné indukce. Racionálně uvažující hráči by měli hrát racionální strategie, mezi které bezpochyby koncept dokonalé rovnováhy podher patří. Na přiloženém obrázku je znázorněna dvoukolová hra dvou hráčů. Celkový počet možných ryzích strategií je zde 1024 (32x32).