Nomádva

Tématické příspěvky

Matematika, hry a Nashova rovnováha: Samuel Zajíček

Když se matematici podívají na něco úplně běžného, řekněme třeba žábu, která skočila z leknínu na leknín, zprvu sice možná ještě vidí něco jako skákající žábu a lekníny, ale když se nad situací zamyslí a nechají se vést svou přirozeností, za chvíli už je nezajímá ani žába ani lekníny, ale Otázka. Otázka je důležitá a matematická. Tak třeba: Jak daleko mohou být lekníny od sebe, aby žába dokázala skočit z jednoho na druhý? Nebo: jak máme po rybníce rozprostřít lekníny nejefektivněji tak, aby každé místo na hladině bylo dosažitelné suchými stehýnky? Nebo: Jaká je nejmenší pravděpodobnost s kterou musí na každém místě vyrůst leknín, aby mohla žába po nich přeskákat na druhý břeh?

Ono se ukáže, že tyhle otázky často nemají valného smyslu. Žába je žába a leknín je leknín, obojí se to různě mění, je to divné a neuchopitelné. Ale koho zajímá žába, že. Pěkně hmotný bod to je, a při odrazu má vždy rychlost v. A lekníny jsou kruhy o daném poloměru r. Nebo o nějaké distribuci poloměrů, pokud si to chceme hodně zesložitit (což zprvu chceme, ale pak zjistíme, že s tak složitým příkladem nepohneme, a tak to zase zjednodušíme). A další omezení a vyjasnění (Každé místo? Co tím myslíte, kolego?) třeba z poslední úlohy udělají následující: Jaká je nejnižší konstanta poissonovského rozložení středů kruhů o poloměru r+v2/2g, při níž skoro jistě existuje nekonečně velký souvislý cluster?

     Kolem takto formulované otázky se utvoří celá teorie, nakonec leccos je „v podstatě“ skákání žab přes rybník, třeba protékání vody houbou (nutno říct, že v tomto konkrétním příkladě šla historie naopak, od houby k leknínům, proto se teorii říká teorie perkolace – „protáhnutí skrz“), zátěž telefonní sítě (každý telefonát je jako leknín, a pokud vznikne nekonečný cluster, síť je vždy plná a přetíží se) nebo třeba šíření epidemií (když se lidi málo potkávají – je málo leknínů – tak epidemie zasáhne pouze jednu komunitu, když může žába přeskákat kamkoli, může i virus). A pak nastane ten nádherný Obrat, tak typický pro matematiku. Nikoli perkolace je modelem žáby, ale žába je modelem perkolace!

     Totéž matematici udělali s hrami. Uviděli někoho hrát nějakou hru (třeba sami sebe, i tohle oni svedou!) a začali se ptát: Co má hráč udělat, aby vyhrál? A může vždycky vyhrát, nebo ne?

     A samozřejmě zjistili, že tyto otázky nemají valného smyslu. Hráč je hráč a hra je hra, obojí se to různě mění, je to divné a neuchopitelné. Ale koho zajímá hra, že. Hra je pěkně soubor pravidel a hráč je stroj řídící se předem daným algoritmem. Ale co když se pravidla během hry mění? A jak dualitu hráčů a hry nějak skloubit? Jak stejným způsobem uchopit hru, kterou hraje jeden hráč a kterou hraje hráčů 22, přičemž pro různé hráče platí různá pravidla?

     Hledané uchopení spočívá v tom, že hru ztotožníme se všemi jejími možnými průběhy. U tahových her (a třeba všechny počítačové hry jsou tahové, tahem je minimálně jeden tik vnitřních hodin) je to jednoduché – hra je vlastně ekvivalentní stromu, kde každé větvení (pozor: matematický strom – zase jedna taková abstrakce – se může v jednom místě větvit třeba do nekonečně mnoha větví) odpovídá možným tahům hráče, který je v dané chvíli na tahu. U netahových je problém, ale kdo by si teď chtěl kazit radost diferenciálními rovnicemi; proto nás nebudou zajímat. Takže ještě jednou: hra je soubor možných průběhů, tj. hra je strom. Když pak reálně hra probíhá, vypadá to vlastně tak, že začneme v kořeni stromu a pak každý hráč, když na něj přijde řada, volí, kterou větví se vydá. A když už není kam se vydat (tj. jsme v listu stromu), hra končí. Nyní vidíme, že je potřeba ještě nějak rozdat ceny. Takže je nutno naší strukturu obohatit. Každému listu proto přiřadíme rozdání cen (payoff, výplata; medaile zpeněžíme a ostatní utřou), čímž vznikne nové pojetí hry: hra je strom, který má na každém větvení napsáno, kdo zrovna hraje, na každé větvi nějaké označení toho konkrétního tahu, a na listech uspořádanou n-tici výplat pro všech n hráčů hry.

     Abychom se nyní mohli zabývat otázkou, jak vyhrát, musíme lépe uchopit hráče. Hráč hraje. Co to znamená? Dle výše uvedeného v každém okamžiku hry volí, kterou větví se vydat. Řekli jsme, že hráč je stroj řídící se předem daným algoritmem – strategií. Strategie vlastně znamená do stromu, který popisuje hru, předem na každé větvení, které odpovídá mému tahu, zakreslit, kterou větev si zvolím (jak potáhnu; ve skutečnosti nemusím na každé větvení, některá si sám odříznu svým rozhodnutím). Hráči pak před začátkem hry zvolí z palety svých možných strategií, čímž u každého větvení mají předem zakreslené větve, které si vybrat. Hra pak vlastně vypadá tak, že vymažeme všechny nezakreslené větve, a zbude nám jen jedna souvislá cesta po stromu od kořene po list. Koukneme se na příslušný list a rozdáme odměny.

     Celé pojetí se dá samozřejmě téměř libovolně komplikovat. Kromě již zmíněné netahové hry můžeme mít hru, kdy její počátek nebo průběh je náhodný (modelem je třeba losování o to, kdo začne, nebo ruleta). Nebo můžeme dovolit hru, u níž nevíme, kde se ve hře vlastně nacházíme (nemáme úplnou informaci) a několik větvení nám splývá v jedno (protože druhým nevidíme do karet). Můžeme dovolit hráčům si strategii vybírat házením kostkou (a tím náhodně směšovat strategie). Můžeme dovolit hru opakovat (a hráčova strategie v následujícím běhu tedy může vycházet z minulých strategií ostatních hráčů).

     To jsou všechno důležité komplikace, nicméně to, co nás zajímalo, tedy co má hráč udělat, aby vyhrál, a zda může vyhrát vždy, je možné studovat už na těch nejjednodušších hrách, takže zvláště ti, kteří se hry chopili až po Obratu (jako třeba Nash), si nemusejí s komplikacemi dělat hlavu. Onen nádherný Obrat totiž mnoho her (třeba plácání báboviček nebo paci, paci, pacičky) jako hry zatratil, zatímco mnohá jiná jednání se modely hry stala. Kromě her jaksi tradičních, třeba šachů nebo karet nebo vrhcábů, se tak do této polohy dostala v zásadě jakákoli rozhodování (tahy), z nichž někdo něco má (výplatu). A jelikož se dosti mohutné množství moderních, povětšinou anglosaských myslitelů domnívá, že zadarmo ani kuře nehrabe (tedy vždy jde o medaili), a dokonce se i to kuře snaží maximalizovat svůj zisk (získat zlato a ne jen stříbro), dostal se pojem hry do středu sociálního a ekonomického uvažování. Homo economicus si vlastně neustále hraje – hurá!

     Co tedy nás coby matematiky a anglosaské ekonomy přesně zajímá na hrách? Výhra! A maximální možná!

     Ukazuje se, že okolo prosté výhry a prohry není situace příliš složitá, prostě pro každou jednoduchou hru (tahovou, dva hráči, konečnou, s úplnou informací, vždy možných jen spočetně mnoho tahů, jeden vyhrává a druhý prohrává) má jeden z hráčů možnost si vybrat takovou strategii, že ať si vybere protihráč jakoukoli jinou, tento hráč vyhraje (v principu tedy musí existovat taková výherní strategie pro šachy, a věří se, že tuto možnost má začínající hráč; ovšemže je tato strategie reálně nenalezitelná, koho to ale zajímá). Naopak hrajeme-li i docela triviální hru, ve které se nevyhrává, ale vyplácí se odměny, a nás zajímá, jak svou odměnu maximalizovat, začnou se dít podivuhodné věci.

Představme si následující hru (na webu ji najdete jako Vězňovo dilema): První hráč zvolí C nebo D. Druhý hráč nezávisle na prvním hráči také zvolí C nebo D.  Tím je hra dohrána a rozdělují se odměny. Pokud oba hráči zvolili C, dostanou oba 5 Kč. Pokud jeden zvolil C a druhý D, ten, kdo zvolil D, dostane 10 Kč, zatímco kdo C, nedostane nic. Pokud oba zvolí D, dostanou oba po 1 Kč. Jakou mají zvolit strategii, aby maximalizovali svou výhru?

     Zdálo by se, že by oba měli zvolit C. Na druhou stranu, uvažuje každý, pokud ten druhý zvolil C, mi se vyplatí zvolit D. Takže při souboru strategií [C,C] se mi vyplatí jednostranně svou strategii změnit. Stejně tak se mi ale vyplatí zvolit D, i když ten druhý volil D také – přece jenom, koruna je koruna. Takže při souboru strategií [C,D] se mi také vyplatí strategii změnit. Naopak při souboru strategií [D,D] se mi nic měnit nevyplatí, protože tím bych přišel i o tu korunu. Uvažuje-li tedy každý z hráčů racionálně a snaží-li se maximalizovat svou výhru, oba vždy zvolí D, což paradoxně žádná výhra není.

     Na této situaci jsou zajímavé dva momenty: Jak hráč uvažoval a jak to, že dospěl k takovému paradoxnímu výsledku. Hráč uvažoval jednostranně, nekooperoval. Kooperovat nemohl, řekli jsme, že jejich volby jsou nezávislé. A jak uvažoval? Vzal si všechny možné soubory strategií, a podíval se, jestli by si u každého souboru nemohl jednostrannou změnou polepšit. Pokud ano, tento soubor zahodil. Nakonec mu zůstal jen jeden soubor, [D,D]. U něj si žádnou jednostrannou změnou nepolepší.

     Souboru strategií, u kterého si jednostrannou změnou nemůžeme polepšit, se říká Nashova rovnováha. Ne u všech her musí existovat (pokud náhodně nesměšujeme strategie – pak existuje vždy alespoň jedna) a u některých jich může existovat více. To není ovšem tak důležité, jako tvrzení, že hledání Nashovy rovnováhy je to nejracionálnější, co můžeme při hře udělat.

     Ale jak to, že výše uvedená hra dospěla k tomu, že paradoxně ani jeden z hráčů nezískal maximální možnou výhru? Jde o to, že oba se chovali zcela racionálně, chtěli vyhrát co nejvíc, nicméně dělali to jednostranně, nekooperovali (taky jsme jim to zakázali!). Tato jednostrannost způsobila, že ačkoli nalezli Nashovu rovnováhu, tato rovnováha nebyla Pareto optimální :-)

     Co s tím? Kooperace vchází do hry (doslova) s jejím opakováním. To umožňuje závislost naší strategie na minulých strategiích nás i protihráče. První hrou nic nekončí, když protihráč volil D(efect) a náš hráč C(ooperate), tento sice nedostane nic, ale už ví, co je ten druhý za sviňku, a už mu nikdy nebude věřit a bude se chovat taky sobecky. Kdežto když protihráč volil C a náš hráč také, věří si i v dalších kolech a už po čtyřech kolech jsou na tom oba lépe než ona sviňka.

     Této strategii se říká půjčka za oplátku (tit for tat) a je to, zdá se, jedna z nejúčinnějších (a tedy v naší řeči nejracionálnějších) strategií pro opakované hry s Pareto suboptimální Nashovou rovnováhou. Mohou existovat i jiné strategie? Mohou. Můžeme vnést prvek odpuštění, můžeme být měkčí, tvrdší, cokoli. Po světě se dokonce hrají simulační počítačové turnaje, kde si můžete svou strategii ověřit proti soupeřům.

     Ať už ale zvolíme jakoukoli strategii, vždy to nakonec děláme s úmyslem maximalizovat svůj zisk. Kooperující nevychází k druhému člověku, ale zůstává u sebe, druhý hráč vystupuje pouze ve smyslu jím volené strategie a může být nahrazen počítačem. Ostatně i první hráč může být nahrazen počítačem, neboť jeho strategie je z definice racionality řešením optimalizační úlohy. A celá hra, jsouc nečasovou matematickou strukturou, je zvolením strategií rozhodnuta a počítač opět může rovnou říct, kdo vyhrál a kolik.

     Homo economicus si stále jenom hraje, řekli jsme. Ale vše ve hře může být nahrazeno počítačem. „Neunavujte se, pracuji za vás,“ říká stále robot, kterého vyrobil Myšpulín, aby za Bobíka dělal úplně všechno. Poté, co Bobík robota konečně rozbije, radí Pinďa s Fifinkou: „Víš co? Udělej z něho něco užitečného... třeba ledničku!“

 

Žádné komentáře