Mixed strategy/cs

Úvod

V této kapitole budete seznámeni s konceptem smíšené strategie, kde bude postupně vysvětlen jeho význam a možnosti použití pro analýzu a řešení her. Kapitola se skládá z obsahu trojího typu odlišeného barvou.

Modrým zvýrazněním jsou označeny obecné definice a poznatky shrnující výklad.

Zelené zvýraznění ohraničuje výklad.

Oranžová značí procvičující otázky, na které naleznete odpověď na konci stránky.

Přesvědčení hráče

Pro srozumitelnější vysvětlení navazujícího konceptu smíšených strategií bude první část věnována podřízenému konstruktu teorie her - hráčově přesvědčení.

Na stadionu ve Wembley je po letech zase pekelně živo. V charitativní exhibiční show tak dobré, že se ji chystá přenášet i Česká televize, se před čáru na pokutový kop připravuje trojice naprosto legendárních hráčů. Trojka fotbalových es ozkouší kvality jednoho vylosovaného fanouška, který se pokusí chycením míče krom své prestiže získat i nějaké peníze pro dobrou věc. Na základě očíslovaných vstupenek je ze skandujícího davu vybrán Richard H., shodou okolností absolvent Vysoké školy ekonomické se silně rozvinutým smyslem pro statistiku a matematizaci čehokoliv a za každou cenu. Richard se chvilku po rozsvícení svého obličeje na videokostce nad stadionem pro 90 000 diváků ani nehne. Jen pozorně přejíždí zrakem po přeplněných tribunách, vyprázdněném, zeleném hřišti a hloučku extraligových hráčů připravených u brány. Několikrát se nadechne, vyrovná ramena, z kapsy od saka vytáhne kalkulačku, a neohroženě sestupuje k hřišti. Cestou dolů, skrze sprostě a anglicky křičící diváky mu zrovna běží hlavou: "Zatraceně Richarde, byls vybrán, abys reprezentoval tady na charitativní exhibici a postavil se velkejm hvězdám. Nebude zas taková ostuda, když ten míč nechytíš. Vždyť první kope Ronaldhino!"

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:
θ₂ = {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.

u₁(Věřit,θ₂) = 0.75 • 0 + 0.25 • 1 = 0.25
u₁(Nevěřit,θ₂) = 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řesvědčením hráče (belief) označujeme pravděpodobnostní ohodnocení nad strategiemi ostatních hráčů.

Příklad 1 Jaký bude předpokládaný výnos v případě, že Richard bude chytat druhý kop Beckhama? Beckhamovy strategie jsou podřízeny přesvědčení následovně θ₂ = {0.8, 0.2}. Přesvědčení o Richardových strategiích není definováno.
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ě θ₂ = {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í? θ₁ = {0.4, 0.6}; θ₂ = {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á profilu přesvědčení přiřazujícímu 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í θ₁ = {0, 0.5, 0.5}, θ₂ = {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/3, 1/3, 1/3} a θ₂ = {1/3, 1/3, 1/3} naopak můžeme označit jako naprosto smíšenou strategii.

O smíšené strategii (mixed strategy) hráče mluvíme, pokud se pro strategii rozhoduje právě na základě přesvědčení (pravděpodobnostního rozdělení).
Ryzí strategii (pure strategy) lze považovat za typ smíšené strategie, kde se pravděpodobnostní ohodnocení rovná jedné.

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, ž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.

Nashova rovnováha je takové řešení, ve kterém platí, že pokud se jeden z hráčů nebude držet své strategie, zatímco ostatní hráč(i) ano, jeho výhra se sníží nebo v nejlepším případě zůstane stejná
Každá hra má Nashovy rovnováhy, ať už v ryzích nebo smíšených strategiích.

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é, 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 θ₁ = {q, 1 - q} a θ₂ = {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.

u₁(Věřit, θ₂) = 1 • p + 0 • (1 - p) = p
u₁(Nevěřit, θ₂) = 0 • p + 1 • (1 - p) = 1 - p
u₂(Blufovat, θ₁) = 1 • q + 0 • (1 - q) = q
u₂(Neblufovat, θ₁) = 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

Smíšená strategie zajišťující Nashovo equilibrium se tedy nachází v podobě profilu ((q, 1 - q), (p, 1 - p)), tedy konkrétně vyčísleno ((0.5, 0.5), (0.5, 0.5)). Což znamená, že každý z hráčů by měl v polovině případů volit první strategii, v druhé polovině druhou. Richard zjišťuje, že bez zvláštních přesvědčení, je z povahy hry pro zajištění Nashovy rovnováhy nejvhodnější rovnoměrně rozdělit volené strategie mezi jednotlivé pokusy. Tedy v případě jeho problému tří penaltových kopů jednou zvolit první strategii, jednou druhou a napotřetí si nejspíš hodit mincí.

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ě

Pro nalezení rovnovážné smíšené strategie lze obecně doporučit následující postup:

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.

Pokusme se nyní nalézt rovnovážnou smíšenou strategii v obecnějším a komplikovanějším případu.

	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

Řešíme uvedenou podhru původní hry. Rovnovážnou smíšenou strategii definujme jako (p, 1 - p) x (q, 1 - q), z čehož nám po dopočtení vychází profil (1/4, 3/4) x (1/4, 3/4). Respektive (0, 1/4, 3/4) x (0, 1/4, 3/4) pro původní hru.

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

Příklad 6 Nalezněte rovnovážnou smíšenou strategii pro případ hry kámen, nůžky, papír. (příklad lze řešit odhadem)

Dovětek

Z předchozích příkladů je patrné, že hledání smíšené rovnovážné strategie není problematické v případě matic 2 x 2. Pro ruční řešení se s takovými maticemi setkáte nejčastěji. Případně, pokud je hra symetrická, je možné rovnovážnou smíšenou strategii ještě odvodit úvahou i u rozměrnějších her jako například u hry kámen, nůžky, papír. Problematičtější jsou ale rozlehlejší matice, u kterých je nezbytné hru chápat jako úlohu lineárního programování a řešit pomocí algoritmu (například simplexová metoda). Nebo musíme využít specializovaných alogritmů (například Lemke-Howson algoritmus).

Tím kapitola končí. A ptáte se, co se stalo toho večera ve Wembley? Richard strávil v brance hezké chvilky nad teorií her, při kterých si uvědomil spoustu nového o možnostech řešení a hledání rovnovážných stavů. Nakonec jej všechno to poznání přivedlo k myšlence, že nebude vůbec špatné dát na fotbalistu Čecha, a jeho oprýskané rukavice, které mají přinášet štěstí, si navléci. Když tak učinil, odložil solární kalkulačku s notýskem k jedné z brankových tyčí, zvedl hlavu od zeleného pažitu, rozhlédl se a zjistil, že stadión je už dávno prázdný. Zůstal tam úplně sám. Zatímco počítal a zkoušel všechny možnosti, Ronaldhino, Beckham a Suchopárek se rozhodli dát na charitu všechny peníze, co jim jejich sponzoři přidělili. Jen tak. Pro dobro věci. A hlavně aby všichni mohli být brzo doma.
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
u₁(Věřit,θ₂) = 0.2
u₁(Nevěřit,θ₂) = 0.8

Příklad 2
u₁(Věřit,θ₂) = 0.3
u₁(Nevěřit,θ₂) = 0.7

Příklad 3
u₁(θ₁,θ₂) = 0.4 • 0.7 • 0 + 0.4 • 0.3 • 1 + 0.6 • 0.7 • 1 + 0.6 • 0.3 • 0 = 0.54
u₂(θ₁,θ₂) = 0.7 • 0.4 • 1 + 0.7 • 0.6 • 0 + 0.3 • 0.4 • 0 + 0.3 • 0.6 • 1 = 0.46
u(θ₁,θ₂) = 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).

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.