Mixed strategy/cs
Contents
Úvod
Přesvědčení hráče
Pokračuje dál, přeskakuje sedačky a mračí se: "Možná bys ale mohl svůj gólmanský úkol formalizovat jako nějakou matematickou úlohu. To by tě i bavilo. Možná použít koncepty teorie her?"
Richarda dole u zábradlí míjí jeden z českých fanoušků, náhodou také nějaký fotbalista, a podává mu svoje gólmanské rukavice: "Já jsem Čech. Tyhle rukavice vám přinesou štěstí."
"Já zase Richard, děkuju," přebírá ošoupanou výstroj s logem Chelsea a suverenně ji zastrkává do kalhot. Jeho sebejistý úsměv značí, že je pro výhru v následujícím klání nebude potřebovat. Uvědomil si: "Fotbalista kopající penaltu má v zásadě jen dvě možnosti, jak kopnout. Buď se pokusí mne mást tělem, naznačí mi směr a pak kopne jeho opak. Nebo se blufovat nepokusí a náznak směru jeho těla bude odpovídat i hranému směru míče..."
Richard si postupně potřásá rukou s Ronaldhinem, Beckhamem a Janem Suchopárkem z pražské Slavie. Největšími fotbalisty všech dob. Pak se se skrývaným smíchem běží připravit do brány: "To je jasné. Vypíšu si všechny možnosti do bloku a prostě to spočítám! Konečně efektně uplatním něco, co jsem naučil na škole!"
Ronaldhino si nervózně kontroluje kopačky na suchý zip, odtušil, že netypický gólman nebude nejsnadnějším soupeřem. Stadion křičí nedočkavostí. Na trávník dopadávají první zapálené dýmovnice. Ty ale matematikovu koncentrovanou mysl v tandemu s precizně sepsanými zápisky a solárně napájenou kalkulačkou nemohou zastavit...
Ponechme napjatou atmosféru ve Wembley na chvíli stranou a rozeberme, s jakou logikou si Richard poznačoval do svého bloku.
| 1 RICHARD | |||
|---|---|---|---|
| 2 RONALDHINO | VĚŘIT | NEVĚŘIT | |
| BLUFOVAT | 1 0 | 0 1 | |
| NEBLUFOVAT | 0 1 | 1 0 | |
Ze zápisu je patrné, že se jedná o hru uspořádanou v normálové formě, neboli o výplatní matici dvou hráčů (Richarda a Ronaldhina) a jejich hratelných možností. Ronaldhino disponuje dvojicí strategií {BLUFOVAT, NEBLUFOVAT}, Richard oproti tomu {VĚŘIT a jít v naznačeném směru, NEVĚŘIT a jít v opačném směru}. V případě, že Richard míč chytí, rovná se jeho výplata jedné, Ronaldhinova nule. A naopak.
Touto formalizací problému, ale Richard nekončí, protože by mu s řešením problému zatím zvlášť nepomohla. Zaznamenaná hra je konfliktní, antagonistická a nemá žádné dominované strategie nebo Nashova equilibria. Těmito koncepty řešení se tedy ke zjištění nejvhodnější strategie nedobereme. Richard proto přemýšlí, jak do svého modelu hry zapracovat i všechny další informace, které jsou o fotbalu dostupné.
Tak například ví, že Ronaldhino a Beckham jsou hvězdy velkých klubů, protřelí blufaři, relativně málo hrající v naznačeném směru. Zatímco ale Suchopárek, podle statistik, zase blufuje jen výjimečně. Zároveň je jasné, že Richard sám nemá žádné zvláštní inklinace z hlediska důvěřivosti nebo nedůvěřivosti. Richard se proto pokouší využít všechny tyto nadstandardní informace, které je možno vyjádřit skrze sestavu pravděpodobností, o kterou bude rozhodování v rámci hry obohaceno.
| 1 RICHARD | |||
|---|---|---|---|
| 2 RONALDHINO | VĚRIT | NEVĚŘIT | |
| - | - | ||
| BLUFOVAT | 1 0 | 0 1 | |
| 75 % (0.75) | |||
| NEBLUFOVAT | 0 1 | 1 0 | |
| 25 % (0.25) | |||
Přiřazením profilu pravděpodobností ke každé protihráčově variantě Richard vlastně vložil do problému dimenzi poměrného přesvědčení o protihráči, respektive jeho strategiích. Ohodnocení strategie v rámci přesvědčení z logiky věci nabývá hodnot od nuly do jedné.
Zápis přesvědčení druhého hráče (Ronaldhina) se běžně zapisuje následujícím způsobem[1]:
θ2 = {0.75, 0.25}
Přidání dimenze přesvědčení umožňuje spočítat očekávaný výnos každé strategie. Očekávaný výnos je pak vlastně jen součtem zhodnocených výplat pro každou strategii.
u1(Věřit,θ2) = 0.75 • 0 + 0.25 • 1 = 0.25
u1(Nevěřit,θ2) = 0.75 • 0.5 • 1 + 0.25 • 0 = 0.75
Z očekávaných výnosů a za předpokladu jeho maximalizace je jasné, že pro Richarda je nejlepší Ronaldhinovi nevěřit. Naopak Ronaldhino nemůže využít specifického přesvědčení o Richardových preferencích a proto je mezi svými volbami indiferentní.
Příklad 2 A jaký bude předpokládaný výnos v případě třetí penalty, kopnuté Janem Suchopárkem? Suchopárkovy strategie jsou podřízeny následovně θ2 = {0.3, 0.7}. Přesvědčení o Richardových strategiích není definováno.
Příklad 3 Jaký bude předpokládaný výnos hry pro oba dva hráče v případě, že budou o obou hráčích známy následující přesvědčení? θ1 = {0.4, 0.6}; θ2 = {0.7, 0.3}. A jaký bude v takovém případě celkový výnos hry?
Smíšené strategie
Předchozím konceptem přesvědčení lze podložit následující terminologické rozdělení strategií, které se v teorii her používá.
Ryzí strategie (pure strategy) zavazuje hráče deterministicky bez možnosti pravděpodobnostního ohodnocení (respektive ohodnocení se vždy rovná jedné). Smíšená strategie (mixed strategy) odpovídá sestavě přesvědčení přiřazující ryzím strategiím specifické probabilistické ohodnocení. A ačkoliv množina ryzích strategií každého hráče je konečná, díky spojitosti probabilistického ohodnocení lze na základě konečného setu ryzích strategií definovat nekonečné množství přesvědčení a tedy i smíšených strategií. Zcela smíšená strategie (totally mixed strategy) představuje smíšenou strategii přiřazující nenulové ohodnocení všem ryzím strategiím hráče.
Například, máme-li hru dvou hráčů s trojicí možných ryzích strategií pro každého, pak přesvědčení θ1 = {0, 0.5, 0.5}, θ2 = {0.1, 0.4, 0.5} představují smíšenou strategii fakticky eliminující první strategii prvního hráče. Kombinaci přesvědčení θ1 = {1/3, 1/3, 1/3} a θ2 = {1/3, 1/3, 1/3} naopak můžeme označit jako naprosto smíšenou strategii.
Ryzí strategii (pure strategy) lze považovat za typ smíšené strategie, kde se pravděpodobnostní ohodnocení rovná jedné.[1]
Nashovo equilibrium ve smíšené strategii
Rozlišujeme Nashovu rovnováhu ryzí strategie a rovnováhu smíšené strategie. V ryzí rovnovážné strategii hrají všichni hráči ryzí strategie, zatímco ve smíšené rovnovážné strategii alespoň jeden z nich používá strategie smíšené. John Forbes Nash dokázal[2], že každá konečná hra má Nashovy rovnováhy, avšak nemusí jít o rovnováhu pouze v ryzích strategiích. Každá hra má tedy své Nashovo equilibrium alespoň v případě, že je hrána probabilisticky, jedná se pak o smíšenou rovnovážnou strategii.
Každá hra má Nashovy rovnováhy, v rámci ryzích nebo alespoň v rámci smíšených strategií.[2]
Richardova hra
Richard si je vědom, že dosáhl pomocí přesvědčení formalizace, díky které může vybrat racionálnější variantu. Zvolit strategii na základě očekávaného výnosu není špatné[4], problémem je však, že kvalita takového rozhodnutí se odvíjí od kvality použitého přesvědčení, kterým strategie ohodnotil. Proto začíná spíše uvažovat, zda-li se nemůže zaměřit pouze na původní model hry a ten analyticky rozebrat. Nemá-li například hra samotná žádného Nashova equilibria v ryzích strategiích, nebylo by možné jej nalézt právě pomocí kombinace probabilistických přesvědčení?
Zkusme si tedy ke každé ryzí strategii přiřadit proměnnou značící pravděpodobnost volby. U každého hráče si vystačíme pouze s jednou proměnnou, víme totiž, že ohodnocení všech strategií hráče se v součtu musí rovnat jedné a proto lze ohodnocení druhé strategie vyjádřit jako 1 - p, respektive 1 - q.
| RICHARD | |||
|---|---|---|---|
| RONALDHINO | VĚŘIT | NEVĚŘIT | |
| q | 1 - q | ||
| BLUFOVAT | 1 0 | 0 1 | |
| p | |||
| NEBLUFOVAT | 0 1 | 1 0 | |
| 1 - p | |||
Hledáme takové přesvědčení, které nám v rámci hráčových strategií poskytne stejnou váženou výplatu pro každou strategii a které bude v kombinaci s druhým splňovat podmínky Nashova equilibria. Máme zatím jen obecný popis takového systému přesvědčení (smíšené strategie), kde θ1 = {q, 1 - q} a θ2 = {p, 1 - p}. Stejně jako jsme počítali očekávaný výnos, využijme pro všechny strategie vyjádření do čtveřice následujících rovnic. V podstatě provádíme citlivostní analýzu.[4]
u1(Věřit, θ2) = 1 • p + 0 • (1 - p) = p
u1(Nevěřit, θ2) = 0 • p + 1 • (1 - p) = 1 - p
u2(Blufovat, θ1) = 1 • q + 0 • (1 - q) = q
u2(Neblufovat, θ1) = 0 • q + 1 • (1 - q) = 1 - q
Jak už bylo řečeno, nashově-rovnovážná smíšená strategie povede hráče k indiferentnímu výběru mezi jeho základními (ryzími strategiemi). V tomto typu hry dvou hráčů můžeme soustavu rovnic dopočítat srovnáním vyjádření pravděpodnosti první a druhé strategie každého hráče.
Pro p tedy: p = 1 - p
2p = 1
p = 0.5
A dále pro q:
q = 1 - q
2q = 1
q = 0.5
Ve světle zjištěné rovnovážné smíšené strategie můžeme prohlásit, že smíšená strategie z příkladu 3, o které Richard mohl uvažovat, by nebyla rovnovážná.
Hledání rovnovážné smíšené strategie obecně
1. Odstranění ze hry všech silně dominovaných strategií procedůrou iterovaného dominování.
2. Zaměření pozornosti pouze na vzniklou relevantní podhru původní hry.
3. Vyjádření smíšených pravděpodobností, díky kterým je hráč indiferentní mezi relevantními ryzími strategiemi.
4. Vyčíslit rovnice smíšených pravděpodobností, čímž je získán rovnovážný profil.
| X | Y | Z | |
|---|---|---|---|
| A | 0 5 | 2 3 | 2 3 |
| B | 2 3 | 0 5 | 3 2 |
| C | 5 0 | 3 2 | 2 3 |
V prvním kroku si ověřujeme, zda-li některá ze strategií není dominována ryzí nebou smíšenou strategií. Zjišťujeme, že lze smíšenou strategií (B,C) dominovat strategii A.
Důkaz o dominanci A je následující:
2p + 5(1 - 5) > 0
0p + 3(1 - p) > 2
3p + 2(1 - p) > 2
Vyjádřená omezení p:
p < 5/3
p < 1/3
p > 0
p omezené předchozími nerovnicemi lze nalézt. Strategie A tedy nebude součástí řešení. Po jejím odstranění si všímáme u strategií druhého hráče, že je strategie X je dominována Y. I tu můžeme tedy vyloučit. Zbývají nám relevantní strategie (B,C) x (Y,Z).
| Y | Z | |
|---|---|---|
| B | 0 5 | 3 2 |
| C | 3 2 | 2 3 |
Příklad 4 Uvažte následující hru a nalezněte všechna Nashova equilibria.
| X | Y | |
|---|---|---|
| A | 2 8 | 5 8 |
| B | 3 4 | 4 0 |
Příklad 5 Uvažte následující hru a nalezněte všechna Nashova equilibria.
| X | Y | |
|---|---|---|
| A | 2 4 | 5 -1 |
| B | 4 -1 | 4 0 |
Dovětek
S tím Richard sice vůbec nepočítal, ale za ty nově nabyté znalosti to určitě stojí. A navíc, získal přece rukavice Petra Čecha. A ty by na eBayi něco málo taky mohly hodit!
Výsledky příkladů
Příklad 1
u1(Věřit,θ2) = 0.2
u1(Nevěřit,θ2) = 0.8
Příklad 2
u1(Věřit,θ2) = 0.3
u1(Nevěřit,θ2) = 0.7
Příklad 3
u1(θ1,θ2) = 0.4 • 0.7 • 0 + 0.4 • 0.3 • 1 + 0.6 • 0.7 • 1 + 0.6 • 0.3 • 0 = 0.54
u2(θ1,θ2) = 0.7 • 0.4 • 1 + 0.7 • 0.6 • 0 + 0.3 • 0.4 • 0 + 0.3 • 0.6 • 1 = 0.46
u(θ1,θ2) = 0.54 + 0.46 = 1
Příklad 4
Hra má v ryzích strategiích dvojici NE (B,X) a (A,Y), kde pareto-optimální je (A,Y). V případě rovnovážné smíšené strategie pak dosáhneme přesvědčení (1/2, 1/2) x (1, 0).
Příklad 5
Hra nemá v ryzích strategiích žádné NE. Hledání smíšené rovnovážné strategie nás dovede k profilu (1/3, 2/3) x (1/6, 5/6).
Příklad 6
Opět hledáme takový mix pravděpodobností, který učiní hráče indiferentním mezi jeho strategiemi. Rovnovážným řešením je proto pro oba hráče přesvědčení (1/3, 1/3, 1/3).
Reference
- ↑ 1.0 1.1 1.2 1.3 1.4 Watson, Joel. Strategy: an introduction to game theory. Third Edition. xv, 491 pages. ISBN 978-039-3918-380.
- ↑ 2.0 2.1 Nash, John. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 1950, 36(1):48-49.
- ↑ Dlouhý, Martin. Úvod do teorie her. 2., přepracované vydání Praha: Oeconomica, 2009, 119 s. ISBN 978-80-245-1609-7.
- ↑ 4.0 4.1 Turban, Efraim. Fundamentals of Management Science /Základy vědy o řízení: an introduction to game theory. 4.Ed. Plano: Business Publications, Inc., 1988, 915 s. ISBN 02-560-6256-0. Cite error: Invalid
<ref>tag; name "turban" defined multiple times with different content
Doporučená literatura
1. Carmichael, Fiona. A guide to game theory: an introduction to game theory. 1st ed. New York: Financial Times Prentice Hall, 2005, xiii, 286 p. ISBN 02-736-8496-5.
2. Shomam, Kevin Leyton-Brown and Yoav. Essentials of game theory a concise, multidisciplinary introduction: an introduction to game theory. 1st ed. San 3. Rafael, Calif.: Morgan, 2008, 915 s. ISBN 978-159-8295-931.
3. Watson, Joel. Strategy: an introduction to game theory. Third Edition. xv, 491 pages. ISBN 978-039-3918-380.
