Difference between revisions of "Extensive form/cs"

From Simulace.info
Jump to: navigation, search
m (→‎Metody řešení)
m (Oprava odkazu)
 
(32 intermediate revisions by the same user not shown)
Line 4: Line 4:
 
[[File:homework dilemma.jpg]]
 
[[File:homework dilemma.jpg]]
  
−
Obrázek výše představuje jednoduchou "hru", kdy se žák rozhoduje, zda vypracovat či nevypracovat domácí úlohu zadanou učitelem. Užitky (vpravo v závorkách) se uvádějí vždy za posledním rozhodovacím krokem. Rozhodovací krok představuje každý uzel v grafu.
+
Obrázek výše představuje jednoduchou "hru", kdy se žák rozhoduje, zda vypracovat či nevypracovat domácí úlohu zadanou učitelem. Očekávané zisky (vpravo v závorkách) se uvádějí vždy za posledním rozhodovacím krokem. Rozhodovací krok představuje každý uzel v grafu.
  
 
=== Akce vs. strategie ===
 
=== Akce vs. strategie ===
−
Akcí je právě jedno rozhodnutí. U statických her se rozhoduje zda je výhodnější provést to, či ono, což je samo o sobě výsledkem. Dynamické hry obsahují více uzlů, tedy více akcí ke kterým je nutné učinit rozhodnutí, a to ještě '''před zahájením samotné hry'''. Hovoříme tedy o strategii. '''Strategie je plán akcí''' pro veškeré situace, které mohou nastat. <ref name="kalovcova">KÁLOVCOVÁ, K. Lecture 6. In: KÁLOVCOVÁ, Katarína. VŠE. ''Introduction to Game Theory'' [online]. 2015 [cit. 2015]. Dostupné z: http://home.cerge-ei.cz/kalovcova/teachingVSE_GT_S2015.html</ref>
+
Akcí je právě jedno rozhodnutí. U statických her se rozhoduje zda je výhodnější provést to, či ono, což je samo o sobě výsledkem. Dynamické hry obsahují více uzlů, tedy více akcí ke kterým je nutné učinit rozhodnutí, a to ještě '''před zahájením samotné hry'''. Hovoříme tedy o strategii. '''Strategie je plán akcí''' pro veškeré situace, které mohou nastat. <ref name="kalovcova">KÁLOVCOVÁ, K. Lecture 6. In: KÁLOVCOVÁ, Katarína. VŠE. ''Introduction to Game Theory'' [online]. 2015 [cit. 2015]. Dostupné z: http://home.cerge-ei.cz/kalovcova/files/VSE_gT_s2015/lecture6.pdf</ref>
  
−
== Metody řešení ==
+
== Postup řešení ==
−
Nejčastěji se používá stejná metoda nejlepších reakcí jako v případě statických her s tím rozdílem, že se neporovnávají akce, nýbž strategie. Strategii lze vyjádřit zvýrazněním cesty od kořene grafu až k jednomu z jeho posledních potomků.
+
Nejčastěji se používá stejná metoda hledání nejlepších reakcí jako v případě statických her s tím rozdílem, že se neporovnávají akce, nýbrž strategie. <ref name="kalovcova"></ref> Strategii lze vyjádřit zvýrazněním cesty od kořene grafu až k jednomu z jeho posledních potomků.
  
 
[[File:strategie.jpg]]
 
[[File:strategie.jpg]]
  
 
V předešlém případě značíme červeně vyznačenou strategii takto: '''<Zadat úkol, Zkontrolovat úkol>; <Nevypracovat úkol>''' nebo zkráceně: '''<Z, Z>; <N>'''.
 
V předešlém případě značíme červeně vyznačenou strategii takto: '''<Zadat úkol, Zkontrolovat úkol>; <Nevypracovat úkol>''' nebo zkráceně: '''<Z, Z>; <N>'''.
−
Tato strategie však není kompletní, protože v ní nejsou zahrnuty veškeré situace, které mohou nastat, tj. pokud se žák rozhodne vypracovat úkol, učitel nebude mít pro tuto možnost stanovenou strategii. Pojďme si tedy ukázat, jak postupovat správně při hledání optimálního řešení dynamických her.
+
Tato strategie však není kompletní, ani optimální. Kompletní protože v ní nejsou zahrnuty veškeré situace, které mohou nastat, tj. pokud se žák rozhodne vypracovat úkol, učitel nebude mít pro tuto možnost stanovenou strategii a optimální protože učitel by měl větší zisk (užitek) v případě kdy by úkol nekontroloval (4 je víc než -5). Pojďme si tedy ukázat, jak postupovat správně při hledání optimálního řešení dynamických her.
  
  
 
=== Zpětná indukce ===
 
=== Zpětná indukce ===
 
Předchozí příklad je příkladem hry s nekompletní informací, tj. v situaci, kdy se učitel rozhoduje zda úkol zkontrolovat, či nikoliv, tak nemá informaci o tom, zda žák úkol vypracoval nebo ne.
 
Předchozí příklad je příkladem hry s nekompletní informací, tj. v situaci, kdy se učitel rozhoduje zda úkol zkontrolovat, či nikoliv, tak nemá informaci o tom, zda žák úkol vypracoval nebo ne.
−
K tomuto typu příkladů se ještě vrátíme, ale pro začátek si vysvětlíme metodu zpětné indukce na příkladu tzv. Escalation game.
+
K tomuto typu příkladů se ještě vrátíme, ale pro začátek si vysvětlíme metodu zpětné indukce na příkladu tzv. [[Escalation game]].
  
 
Dva státy se dostanou do sporu o území. Jeden ze států může buď pohrozit válkou nebo přenechat území druhému státu. Druhý stát se může nechat hrozbou zastrašit a území se vzdát nebo odporovat (také pohrozit válkou). První se může vzdát a nebo skutečně vyhlásit válku. Graficky lze hru znázornit takto:
 
Dva státy se dostanou do sporu o území. Jeden ze států může buď pohrozit válkou nebo přenechat území druhému státu. Druhý stát se může nechat hrozbou zastrašit a území se vzdát nebo odporovat (také pohrozit válkou). První se může vzdát a nebo skutečně vyhlásit válku. Graficky lze hru znázornit takto:
Line 26: Line 26:
 
[[File:escalation game.jpg]]
 
[[File:escalation game.jpg]]
  
−
Postupujeme od posledního rozhodovacího uzlu směrem ke kořenu stromu, přičemž můžeme daný rozhodovací uzel považovat za samostatnou "podhru" nezávislou na zbytku stromu a řešit ji stejně jako statickou hru.
+
[[File:Extensive3.png|250px|thumb|right| Ukázka pěti podher v rozhodovacím stromu
 +
 
 +
''Zdroj: [[Extensive form]]'']]
 +
Postupujeme od posledního rozhodovacího uzlu směrem ke kořenu stromu (odtud termín zpětná indukce), přičemž můžeme daný rozhodovací uzel považovat za samostatnou "podhru" nezávislou na zbytku stromu a řešit ji stejně jako statickou hru.
 +
 
 +
{{ambox
 +
| text      = Řešení rozšířené formy se označuje termínem '''dokonalá rovnováha podher''' (Subgame Perfect Nash Equilibrium) a znamená, že všechny podhry musí mít [[Nash equilibrium/cs|Nashovu rovnováhu]].
 +
}}
  
 
[[File:krok 1.jpg]]
 
[[File:krok 1.jpg]]
  
−
Stát 2 se může v posledním kroku rozhodnout pro válku nebo mír, za cenu toho, že bude vypadat jako zbabělec a navíc přijde o území bez snahy ho získat. Užitek -1 je vyšší než -2, proto se stát 2 rozhodne pro válku. Nyní můžeme postoupit v rozhodovacím stromu o úroveň výše a opět řešit "podhru" jako statickou.
+
Stát 2 se může v posledním kroku (podhře) rozhodnout pro válku nebo mír, za cenu toho, že bude vypadat jako zbabělec a navíc přijde o území bez snahy ho získat. Očekávaný zisk -1 je vyšší než -2, proto se stát 2 rozhodne pro válku. Nyní můžeme postoupit v rozhodovacím stromu o úroveň výše a opět řešit "podhru" jako statickou.
  
 
[[File:krok 2.jpg]]
 
[[File:krok 2.jpg]]
  
−
Stát 1 je na řadě a má možnost odporovat nebo ustoupit, když bude odporovat, tak již ví, že stát 2 mu vyhlásí válku a užitek obou států bude -1. Pokud Stát 1 ustoupí, jeho užitek bude -2, protože přijde o území bez snahy ho získat a bude vypadat jako zbabělec. Stát 1 tedy zvolí odpor.
+
Stát 1 je na řadě a má možnost odporovat nebo ustoupit, když bude odporovat, tak již ví, že stát 2 mu vyhlásí válku a zisk obou států bude -1. Pokud Stát 1 ustoupí, jeho zisk bude -2, protože přijde o území bez snahy ho získat a bude vypadat jako zbabělec. Stát 1 tedy zvolí odpor.
  
 
[[File:krok 3.jpg]]
 
[[File:krok 3.jpg]]
  
−
Stejně postupujeme v posledním kroce: 0 je víc než -1, proto Stát 1 raději ustoupí. Sice přijde o území, ale alespoň ušetří životy lidí, kteří by padly v jinak nevyhnutelné válce.
+
Stejně postupujeme v posledním kroce: 0 je víc než -1, proto Stát 1 raději ustoupí. Sice přijde o území, ale alespoň ušetří životy lidí, kteří by zemřeli v jinak nevyhnutelné válce.
  
 
Výsledek značíme jako strategii ve všech možných situacích: '''<Ustoupit, Vyhlásit válku>; <Odporovat>'''
 
Výsledek značíme jako strategii ve všech možných situacích: '''<Ustoupit, Vyhlásit válku>; <Odporovat>'''
Line 44: Line 51:
 
[[File:výsledek.jpg]]
 
[[File:výsledek.jpg]]
  
−
  Pomůcka: Strategie musí vždy obsahovat stejný počet akcí jako je počet uzlů v rozhodovacím stromu!
+
{{ambox
 +
| text      = Strategie hry s kompletními informacemi musí vždy obsahovat stejný počet akcí jako je počet uzlů v rozhodovacím stromu! <ref name="spaniel">SPANIEL, William. How NOT to Write a Subgame Perfect Equilibrium. In: ''Youtube'' [online]. Zveřejněno 16. 09. 2012. Dostupné z: https://www.youtube.com/watch?v=LSHa1pcy6v8</ref>
 +
}}
 +
 
 +
=== Hry s (ne)kompletními informacemi ===
 +
Vraťme se k příkladu uvedenému na začátku tohoto textu. Žák má možnost domácí úkol (ne)vypracovat a učitel (ne)zkontrolovat. Po tahu žáka učitel neví v jaké části stromu se nachází, jeho znalost předchozích akcí je nekompletní. Přerušovaná čára značí jeden informační set, tj. jeden rozhodovací uzel. Ať už se hráč nachází v jedné či druhé části, jeho rozhodnutí bude vždy stejné, protože neví v které části se právě nachází.
 +
 
 +
Z toho plyne, že hra s nekompletní informací musí splňovat tyto podmínky:
 +
* Alespoň jeden z hráčů nezná celou historii hry,
 +
* alespoň jeden informační set není jedináček (obsahuje alespoň dva uzly grafu),
 +
* všechny uzly v rámci informačního setu musí vést ke stejným rozhodovacím možnostem (pokud jeden uzel vede k možnostem '''nahoru''', '''dolů''' a druhý k '''nahoru''' a '''doprava''', pak se jedná o dva různé informační sety).
 +
 
  
−
=== Vpředná indukce ===
+
Grafické znázornění hry s nekompletními informacemi je téměř stejné jako u hry s kompletními informacemi. Pouze se navíc přidá přerušovaná čára značící, že se jedná o jeden informační set a pravděpodobnost p a p-1, že se nacházíme v horní/dolní části stromu, tj. pravděpodobnost s kterou žák vypracoval/nevypracoval domácí úkol (viz níže).
  
−
== Subgame perfect equilibrium ==
+
[[File:imperfect information.jpg]]
  
−
== Hry s (ne)kompletními informacemi ==
+
Pro výpočet řešení / rovnováhy (používáme termín [[Weak perfect Bayesian equilibrium]] - WPBE) sečteme očekávané zisky <math>OZ</math> pro případy kdy učitel zkontroluje (Z) / nezkontroluje (N) domácí úkol:
−
Vraťme se k příkladu uvedenému na začátku tohoto textu. Žák má možnost domácí úkol (ne)vypracovat a učitel (ne)zkontrolovat. Po tahu žáka učitel neví v jaké části stromu se nachází, jeho znalost předchozích akcí je nekompletní. Přerušovaná čára značí jeden informační set, tj. jeden rozhodovací uzel. Ať už se hráč nachází v jedné či druhé části, jeho rozhodnutí bude vždy stejné, protože neví v které části se nachází.
 
  
−
Z toho plyne, že hra s nekompletní informací musí splňovat tyto podmínky:
+
<math>OZ(Z)=5p-5(p-1)</math>
−
* Alespoň jeden z hráčů nezná celou historii hry
+
 
−
* Alespoň jeden informační set není jedináček (obsahuje alespoň dva uzly grafu)
+
<math>OZ(Z)=5</math>
−
* Všechny uzly v rámci informačního setu musí vést ke stejným rozhodovacím možnostem (pokud jeden uzel vede k možnostem '''nahoru''', '''dolů''' a druhý k '''nahoru''' a '''doprava''', pak se jedná o dva různé informační sety)
+
 
 +
 
 +
<math>OZ(N)=4p+4(p-1)</math>
 +
 
 +
<math>OZ(N)=8p-4</math>
 +
 
 +
Poněvadž pravděpodobnost <math>p</math> se pohybuje v intervalu <math><0, 1></math>, pak <math>OZ(N)</math> nikdy nebude větší než <math>OZ(Z)</math>.
 +
Pravděpodobnost zde představuje přesvědčení hráče o předchozím jednání druhého hráče. Pokud tedy hráč (učitel) věří, že žák vypracoval úkol s pravděpodobností 60%, pak dosadíme za p = 0,6.
 +
V tomto konkrétním případě neexistují žádné argumenty, které by přesvědčily učitele, že je výhodnější úkol nezkontrolovat. Protože si žák takto může odvodit, že racionální učitel bude úkol kontrolovat, je pro něj výhodné jej vypracovat. Výsledná strategie (WPBE) je '''<Vypracovat úkol>; <Zkontrolovat úkol>''' a '''<math>p=1</math>, <math>p-1=0</math>'''.
 +
 
 +
{{ambox
 +
| text      = Podmínkou WPBE je, že akce musí být konzistentní s hráčovým přesvědčením a vice versa. Protože žák ví, že bude učitel úkol kontrolovat, uvedeme ve výsledku toto přesvědčení přiřazením pravděpodobnosti <math>p=1</math>.
 +
}}
 +
 
 +
Tuto hru můžeme rovněž zapsat a řešit jako hru statickou, protože hráč 2 nezná krok hráče 1, jedná se o podobnou situaci jakoby se oba hráči rozhodovali současně.
 +
 
 +
[[File:Klasická forma.jpeg]]
 +
 
 +
Hra má celkem dvě [[Nash equilibrium/cs|Nashovy rovnováhy]] v případě řešení jako statické hry. Hra má však pouze jedno WPBE v případě řešení jako dynamické hry, protože hráčova strategie musí být konzistentní, tj. učitel se nemůže jednou rozhodnout pro kontrolu úkolu a podruhé ne. Zde je vidět, že velmi záleží na tom, zda se hráči střídají v rozhodování nebo ne.
 +
 
 +
== Problémy příslibů ==
 +
Problémy příslibů ([[Commitment problems]]) nastávají v hrách (situacích), kdy hráč tvrdí (slibuje), že učiní určitý krok, pokud druhý hráč zvolí určitou variantu. Tento určitý krok by byl však pro prvního hráče méně výhodný než jiný krok. Vědomě tedy slibuje, že raději obětuje část svého zisku. [[Teorie her]] vysvětluje, proč takovým slibům není pro racionálního člověka vhodné věřit.
  
−
=== Postup řešení ===
+
Názorný příklad uvádí William Spaniel <ref name="spaniel2">SPANIEL, William. Commitment Problems. In: ''Youtube'' [online]. Zveřejněno 20. 09. 2012. Dostupné z: https://www.youtube.com/watch?t=263&v=rmPDAJIpQr0</ref> ve svém výukovém videu na příkladu policejní kontroly.
−
Grafické znázornění je téměř stejné jako u hry s kompletní informací. Pouze se navíc přidá přerušovaná čára značící, že se jedná o jeden informační set a pravděpodobnost p a p-1, že se nacházíme v horní/dolní části stromu, tj. žák vypracoval/nevypracoval domácí úkol (viz níže).
 
  
−
[[File:imperfect information.jpg]]
+
V hypotetickém příkladu zastaví policejní hlídka vozidlo a chce provést kontrolu vozidla pro podezření z převozu zakázaných látek. Řidič má však právo prohlídku odmítnout a vyžádat si příjezd K9-jednotky (protidrogové). Pokud prohlídku přijme, policista má pak na výběr provést rychlou prohlídku nebo důkladnou. Preference obou hráčů jsou pak následující:
  
−
== Příklady ==
+
*'''Řidič:''' rychlá prohlídka > počkat na protidrogové > důkladná prohlídka
 +
*'''Policista:''' důkladná prohlídka > rychlá prohlídka > počkat na protidrogové
 +
{{Ambox
 +
| text = Řidič preferuje dlouhé čekání na protidrogové, protože důkladná prohlídka by zahrnovala důkladné rozebrání některých dílů auta a možnost poškození. Protidrogové má k dispozici trénované psy na odhalování zakázaných látek, proto by rozebrání auta nebylo nutné. Důkladná prohlídka dává policistovi největší šanci k nalezení zakázaných látek, čekání na protidrogové mu zabere nejvíc času.
 +
}}
  
−
=== The Centipede Game ===
+
Graficky znázorníme hru následovně:
  
−
=== Commitment Problems ===
+
[[File:commitment problem.jpg | 400px]]
  
−
=== Tying Hands (Burning Bridges) ===
+
Před zahájením prohlídky řekne policista řidiči: ''"Pro nás oba je výhodnější rychlá prohlídka, než čekání na příjezd protidrogového"''. A policista má pravdu. Zisk 2 pro policistu je více než 1 v případě čekání a zisk 3 je více než 2 pro řidiče. Nicméně problém tkví v tom, že jakmile se policista dostane do bodu, kdy se může rozhodnout, už jej nezajímá alternativa čekání na protidrogové, ale rozhoduje se pouze mezi důkladnou a rychlou prohlídkou. Je patrné, že větší zisk získá v případě důkladné prohlídky a proto ji také zvolí. Řidič se nechal ošálit (neuvažoval, že policista bude jednat racionálně, byť nečestně - porušením slibu). Výsledná strategie je '''<Počkat na protidrogové>; <Důkladná prohlídka>'''. Řidič raději zvolí variantu s nižším možným užitkem, protože nemůže vědět, zda policista svůj příslib dodrží.
  
 
== Zdroje ==
 
== Zdroje ==
 
<references/>
 
<references/>

Latest revision as of 10:55, 15 June 2015

Úvod

Klasická matice hry v normálním tvaru je vhodná pro grafické znázornění situací, kdy se hráči rozhodují ve stejný okamžik. V případě, kdy se hráči střídají v rozhodování, taková reprezentace již není dostačující, proto se používá tzv. rozšířená forma, která tyto situace zobrazuje pomocí rozhodovacího stromu.

Homework dilemma.jpg

Obrázek výše představuje jednoduchou "hru", kdy se žák rozhoduje, zda vypracovat či nevypracovat domácí úlohu zadanou učitelem. Očekávané zisky (vpravo v závorkách) se uvádějí vždy za posledním rozhodovacím krokem. Rozhodovací krok představuje každý uzel v grafu.

Akce vs. strategie

Akcí je právě jedno rozhodnutí. U statických her se rozhoduje zda je výhodnější provést to, či ono, což je samo o sobě výsledkem. Dynamické hry obsahují více uzlů, tedy více akcí ke kterým je nutné učinit rozhodnutí, a to ještě před zahájením samotné hry. Hovoříme tedy o strategii. Strategie je plán akcí pro veškeré situace, které mohou nastat. [1]

Postup řešení

Nejčastěji se používá stejná metoda hledání nejlepších reakcí jako v případě statických her s tím rozdílem, že se neporovnávají akce, nýbrž strategie. [1] Strategii lze vyjádřit zvýrazněním cesty od kořene grafu až k jednomu z jeho posledních potomků.

Strategie.jpg

V předešlém případě značíme červeně vyznačenou strategii takto: <Zadat úkol, Zkontrolovat úkol>; <Nevypracovat úkol> nebo zkráceně: <Z, Z>; <N>. Tato strategie však není kompletní, ani optimální. Kompletní protože v ní nejsou zahrnuty veškeré situace, které mohou nastat, tj. pokud se žák rozhodne vypracovat úkol, učitel nebude mít pro tuto možnost stanovenou strategii a optimální protože učitel by měl větší zisk (užitek) v případě kdy by úkol nekontroloval (4 je víc než -5). Pojďme si tedy ukázat, jak postupovat správně při hledání optimálního řešení dynamických her.


Zpětná indukce

Předchozí příklad je příkladem hry s nekompletní informací, tj. v situaci, kdy se učitel rozhoduje zda úkol zkontrolovat, či nikoliv, tak nemá informaci o tom, zda žák úkol vypracoval nebo ne. K tomuto typu příkladů se ještě vrátíme, ale pro začátek si vysvětlíme metodu zpětné indukce na příkladu tzv. Escalation game.

Dva státy se dostanou do sporu o území. Jeden ze států může buď pohrozit válkou nebo přenechat území druhému státu. Druhý stát se může nechat hrozbou zastrašit a území se vzdát nebo odporovat (také pohrozit válkou). První se může vzdát a nebo skutečně vyhlásit válku. Graficky lze hru znázornit takto:

Escalation game.jpg

Ukázka pěti podher v rozhodovacím stromu Zdroj: Extensive form

Postupujeme od posledního rozhodovacího uzlu směrem ke kořenu stromu (odtud termín zpětná indukce), přičemž můžeme daný rozhodovací uzel považovat za samostatnou "podhru" nezávislou na zbytku stromu a řešit ji stejně jako statickou hru.

Řešení rozšířené formy se označuje termínem dokonalá rovnováha podher (Subgame Perfect Nash Equilibrium) a znamená, že všechny podhry musí mít Nashovu rovnováhu.

Krok 1.jpg

Stát 2 se může v posledním kroku (podhře) rozhodnout pro válku nebo mír, za cenu toho, že bude vypadat jako zbabělec a navíc přijde o území bez snahy ho získat. Očekávaný zisk -1 je vyšší než -2, proto se stát 2 rozhodne pro válku. Nyní můžeme postoupit v rozhodovacím stromu o úroveň výše a opět řešit "podhru" jako statickou.

Krok 2.jpg

Stát 1 je na řadě a má možnost odporovat nebo ustoupit, když bude odporovat, tak již ví, že stát 2 mu vyhlásí válku a zisk obou států bude -1. Pokud Stát 1 ustoupí, jeho zisk bude -2, protože přijde o území bez snahy ho získat a bude vypadat jako zbabělec. Stát 1 tedy zvolí odpor.

Krok 3.jpg

Stejně postupujeme v posledním kroce: 0 je víc než -1, proto Stát 1 raději ustoupí. Sice přijde o území, ale alespoň ušetří životy lidí, kteří by zemřeli v jinak nevyhnutelné válce.

Výsledek značíme jako strategii ve všech možných situacích: <Ustoupit, Vyhlásit válku>; <Odporovat>

Výsledek.jpg

Strategie hry s kompletními informacemi musí vždy obsahovat stejný počet akcí jako je počet uzlů v rozhodovacím stromu! [2]

Hry s (ne)kompletními informacemi

Vraťme se k příkladu uvedenému na začátku tohoto textu. Žák má možnost domácí úkol (ne)vypracovat a učitel (ne)zkontrolovat. Po tahu žáka učitel neví v jaké části stromu se nachází, jeho znalost předchozích akcí je nekompletní. Přerušovaná čára značí jeden informační set, tj. jeden rozhodovací uzel. Ať už se hráč nachází v jedné či druhé části, jeho rozhodnutí bude vždy stejné, protože neví v které části se právě nachází.

Z toho plyne, že hra s nekompletní informací musí splňovat tyto podmínky:

  • Alespoň jeden z hráčů nezná celou historii hry,
  • alespoň jeden informační set není jedináček (obsahuje alespoň dva uzly grafu),
  • všechny uzly v rámci informačního setu musí vést ke stejným rozhodovacím možnostem (pokud jeden uzel vede k možnostem nahoru, dolů a druhý k nahoru a doprava, pak se jedná o dva různé informační sety).


Grafické znázornění hry s nekompletními informacemi je téměř stejné jako u hry s kompletními informacemi. Pouze se navíc přidá přerušovaná čára značící, že se jedná o jeden informační set a pravděpodobnost p a p-1, že se nacházíme v horní/dolní části stromu, tj. pravděpodobnost s kterou žák vypracoval/nevypracoval domácí úkol (viz níže).

Imperfect information.jpg

Pro výpočet řešení / rovnováhy (používáme termín Weak perfect Bayesian equilibrium - WPBE) sečteme očekávané zisky 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 OZ} pro případy kdy učitel zkontroluje (Z) / nezkontroluje (N) domácí úkol:

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 OZ(Z)=5p-5(p-1)}

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 OZ(Z)=5}


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 OZ(N)=4p+4(p-1)}

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 OZ(N)=8p-4}

Poněvadž pravděpodobnost 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 p} se pohybuje v intervalu 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 <0, 1>} , pak 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 OZ(N)} nikdy nebude větší než 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 OZ(Z)} . Pravděpodobnost zde představuje přesvědčení hráče o předchozím jednání druhého hráče. Pokud tedy hráč (učitel) věří, že žák vypracoval úkol s pravděpodobností 60%, pak dosadíme za p = 0,6. V tomto konkrétním případě neexistují žádné argumenty, které by přesvědčily učitele, že je výhodnější úkol nezkontrolovat. Protože si žák takto může odvodit, že racionální učitel bude úkol kontrolovat, je pro něj výhodné jej vypracovat. Výsledná strategie (WPBE) je <Vypracovat úkol>; <Zkontrolovat úkol> a 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 p=1} , 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 p-1=0} .

Podmínkou WPBE je, že akce musí být konzistentní s hráčovým přesvědčením a vice versa. Protože žák ví, že bude učitel úkol kontrolovat, uvedeme ve výsledku toto přesvědčení přiřazením pravděpodobnosti 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 p=1} .

Tuto hru můžeme rovněž zapsat a řešit jako hru statickou, protože hráč 2 nezná krok hráče 1, jedná se o podobnou situaci jakoby se oba hráči rozhodovali současně.

Klasická forma.jpeg

Hra má celkem dvě Nashovy rovnováhy v případě řešení jako statické hry. Hra má však pouze jedno WPBE v případě řešení jako dynamické hry, protože hráčova strategie musí být konzistentní, tj. učitel se nemůže jednou rozhodnout pro kontrolu úkolu a podruhé ne. Zde je vidět, že velmi záleží na tom, zda se hráči střídají v rozhodování nebo ne.

Problémy příslibů

Problémy příslibů (Commitment problems) nastávají v hrách (situacích), kdy hráč tvrdí (slibuje), že učiní určitý krok, pokud druhý hráč zvolí určitou variantu. Tento určitý krok by byl však pro prvního hráče méně výhodný než jiný krok. Vědomě tedy slibuje, že raději obětuje část svého zisku. Teorie her vysvětluje, proč takovým slibům není pro racionálního člověka vhodné věřit.

Názorný příklad uvádí William Spaniel [3] ve svém výukovém videu na příkladu policejní kontroly.

V hypotetickém příkladu zastaví policejní hlídka vozidlo a chce provést kontrolu vozidla pro podezření z převozu zakázaných látek. Řidič má však právo prohlídku odmítnout a vyžádat si příjezd K9-jednotky (protidrogové). Pokud prohlídku přijme, policista má pak na výběr provést rychlou prohlídku nebo důkladnou. Preference obou hráčů jsou pak následující:

  • Řidič: rychlá prohlídka > počkat na protidrogové > důkladná prohlídka
  • Policista: důkladná prohlídka > rychlá prohlídka > počkat na protidrogové
Řidič preferuje dlouhé čekání na protidrogové, protože důkladná prohlídka by zahrnovala důkladné rozebrání některých dílů auta a možnost poškození. Protidrogové má k dispozici trénované psy na odhalování zakázaných látek, proto by rozebrání auta nebylo nutné. Důkladná prohlídka dává policistovi největší šanci k nalezení zakázaných látek, čekání na protidrogové mu zabere nejvíc času.

Graficky znázorníme hru následovně:

Commitment problem.jpg

Před zahájením prohlídky řekne policista řidiči: "Pro nás oba je výhodnější rychlá prohlídka, než čekání na příjezd protidrogového". A policista má pravdu. Zisk 2 pro policistu je více než 1 v případě čekání a zisk 3 je více než 2 pro řidiče. Nicméně problém tkví v tom, že jakmile se policista dostane do bodu, kdy se může rozhodnout, už jej nezajímá alternativa čekání na protidrogové, ale rozhoduje se pouze mezi důkladnou a rychlou prohlídkou. Je patrné, že větší zisk získá v případě důkladné prohlídky a proto ji také zvolí. Řidič se nechal ošálit (neuvažoval, že policista bude jednat racionálně, byť nečestně - porušením slibu). Výsledná strategie je <Počkat na protidrogové>; <Důkladná prohlídka>. Řidič raději zvolí variantu s nižším možným užitkem, protože nemůže vědět, zda policista svůj příslib dodrží.

Zdroje

  1. ↑ 1.0 1.1 KÁLOVCOVÁ, K. Lecture 6. In: KÁLOVCOVÁ, Katarína. VŠE. Introduction to Game Theory [online]. 2015 [cit. 2015]. Dostupné z: http://home.cerge-ei.cz/kalovcova/files/VSE_gT_s2015/lecture6.pdf
  2. ↑ SPANIEL, William. How NOT to Write a Subgame Perfect Equilibrium. In: Youtube [online]. Zveřejněno 16. 09. 2012. Dostupné z: https://www.youtube.com/watch?v=LSHa1pcy6v8
  3. ↑ SPANIEL, William. Commitment Problems. In: Youtube [online]. Zveřejněno 20. 09. 2012. Dostupné z: https://www.youtube.com/watch?t=263&v=rmPDAJIpQr0
Retrieved from "http://www.simulace.info/index.php?title=Extensive_form/cs&oldid=9919"