(c) Graphicstock

Teorie her: Minimax, maximin a pistolový souboj

Když mladý John Nash zavolal von Neumannovi, aby mu předvedl svůj důkaz, že všechny konečné hry mají alespoň jednu rovnováhu, pokud jsou povoleny smíšené strategie, von Neumann ho odmítl. Proč se mu Nashův příspěvek nezamlouval?
Je pravda, že metoda, kterou Nash použil pro důkaz svého teorému, nebyla pro von Neumanna žádnou novinkou, on sám s ní dokonce přišel jako první. Je také pravda, že Nashův přístup byl nejspíš poněkud netaktní – v tu dobu se totiž také snažil radit Albertu Einsteinovi, jak se správně dělá fyzika. Ale von Neumanna tenhle mladý neomalený student, který se snažil prosadit v jeho oboru, nijak neohrožoval.
Myslím si, že von Neumannův nezájem měl hlubší příčinu. Von Neumann nejspíš nikdy o evoluční interpretaci teorie her příliš neuvažoval. Byl přesvědčen, že cílem zkoumání hry by mělo být jednoznačné racionální řešení. Idea Nashovy rovnováhy tento požadavek nesplňuje, protože většina her má rovnovah víc a často neexistuje žádný racionální důvod, proč si vybrat jednu a ne nějakou jinou. Jak von Neumann později poznamenal, kritérium nejlepší odpovědi (tedy Nashův přístup) nám říká jen to, že některé strategické profily nemohou být racionálním řešením hry, ale my chceme vědět, které strategické profily mohou být považovány za řešení.

Minimax a maximin
Von Neumann zřejmě soustředil svou pozornost výhradně na hry dvou hráčů s nulovým součtem, protože se jedná o jednu z mála tříd her, které splňují jeho ideál jedinečného racionálního řešení. Důkaz této skutečnosti nazval teorém o minimaxu, což je vlastně trochu zavádějící, protože racionálním řešením hry dvou osob s nulovým součtem je použití principu maximin. Tento princip říká, že máme nejdříve najít nejhorší možnou výplatu, kterou bychom mohli v průměru získat z každé smíšené strategie, a pak zvolit tu ze strategií, u které je tato nejhorší výplata největší.

Proč maximin?
Ironií osudu je, že von Neumannův teorém o minimaxu je přímým důsledkem Nashova důkazu, že všechny konečné hry mají alespoň jednu Nashovu rovnováhu. Abychom se o tom přesvědčili, musíme nejdříve najít Nashovu rovnováhu ve hře dvou hráčů s nulovým součtem. Alicinu rovnovážnou strategii nazveme řádek a Bobovu rovnovážnou strategii nazveme sloupec. Rovnovážné výplaty nazveme Alicina hodnota a Bobova hodnota.
Například ve hře Panna–orel jsou sloupec i řádek smíšenými strategiemi, které předepisují hrát pannu stejně často jako orla, a Alicina hodnota a Bobova hodnota jsou nulové výplaty, které oběma stranám tato strategie přináší. Alice si nemůže být jistá, že získá víc než Alicinu hodnotu, protože Bob by mohl pořád hrát jenom sloupec, a ona by tak musela pořád odpovídat řádkem. Ale zároveň si může být jistá, že když bude pořád hrát řádek, získá alespoň Alicinu hodnotu. Nejlepší Bobova odpověď na tuto strategii je totiž sloupec a pro hry s nulovým součtem platí, že nejlepší výsledek pro Boba je zároveň nejhorší výsledek pro Alici. Řádek je tedy pro Alici jedna z jejích maximinových strategií a Alicina hodnota je výplata daná maximinovou strategií.
Stejným způsobem dojdeme k závěru, že Bobova hodnota je Bobova výplata odpovídající maximinové strategii a sloupec je jedna z jeho maximinových strategií. Pokud je součet Aliciny hodnoty a Bobovy hodnoty nulový, znamená to, že je nulový i součet jejich maximinových výplat. Aby jeden hráč získal víc než svou maximinovou výplatu, musel by druhý hráč získat méně. Když tedy hrajeme hru pro dva hráče s nulovým součtem proti racionálnímu soupeři, je princip maximin nepřekonatelný.
Von Neumannův důkaz tohoto tvrzení se nazývá teorém o minimaxu. To proto, že pokud je součet Aliciny a Bobovy maximinové výplaty nulový, musí se Alicina minimaxová výplata rovnat její maximinové výplatě. To však v žádném případě neznamená, že by von Neumann doporučoval používat princip minimax, jak se občas mylně předpokládá. Bylo by totiž nesmyslné hledat nejlepší průměrnou výplatu ze všech smíšených strategií a potom si zvolit tu strategii, která minimalizuje vaši výplatu pro situaci, že by tento ideální případ nastal vždy.

Kámen–nůžky–papír
Tuhle hru zná každé malé dítě. Alice a Bob současně ukážou jeden ze tří symbolů, které představují jejich čisté strategie: kámen, nůžky, papír. O vítězi rozhodují tato pravidla:
kámen ztupí nůžky
nůžky rozstřihnou papír
papír obalí kámen
Pokud oba hráči ukážou stejný symbol, dochází k remíze. Funguje to tedy stejně, jako kdyby oba soupeři hráli loterii se stejnou šancí na výhru i na prohru, takže se jedná o hru s nulovým součtem.

Racionální řešení je zřejmé: každý hráč musí použít každou ze svých tří čistých strategií stejně často, a zajistit si tak, že jeho maximinový výnos bude nulový. Tato hra je zajímavá především tím, že je velmi obtížné najít evoluční proces, který by se k tomuto řešení přiblížil.

O’Neillova karetní hra

Barry O’Neill použil tuto hru v prvním laboratorním experimentu, který podpořil hypotézu principu maximin. Předchozí experimenty tuto hypotézu vyvracely. Význačný psycholog William Estes se o ní ve své zprávě o pokusech s von Neumannovou teorií vyjadřoval obzvlášť kriticky: „Teorie her nikdy nenahradí empiricky podloženou behaviorální teorii jako nástroj pro předpověď lidského chování v konfliktních situacích.“
Jenže pokusu, na němž založil Estes svou kritiku, se účastnili pouze dva jedinci. Oba navíc měli bohaté zkušenosti s experimenty se zpětnovazebním učením, na jejichž základě se Estes snažil obhájit dnes již zpochybněnou teorii „odpovídajících pravděpodobností“. Navíc ani jeden z účastníků nevěděl, že hraje proti skutečnému člověku. A i kdyby to věděli, teorém o minimaxu by jim nebyl nic platný, protože jim nikdo předem neřekl, jaké výplaty můžou získat. Hráli tedy hru s nedostatečnou informací, což je situace, na kterou se von Neumannova teorie nevztahuje.
O’Neill chtěl svůj experiment navrhnout tak, aby počítal s možností, že různí lidé mohou mít různé postoje k riziku. Například Kámen–nůžky–papír by nebyla hra s nulovým součtem, kdyby si Alice a Bob oba nemysleli, že remizovat je stejné jako mít poloviční šanci na výhru i na prohru. O’Neill tedy vytvořil hru, kde neexistuje remíza, ale která přitom není tak jednoduchá, aby bylo řešení na první pohled zřejmé.
Alice a Bob mají každý čtyři karty od kluka do esa. Navzájem si současně ukážou jednu kartu. Alice vyhraje, pokud oba ukážou eso nebo pokud ukážou rozdílné hodnoty, jinak vyhrává Bob.
Alicina maximinová strategie je taková smíšená strategie, která způsobí, že všechny Bobovy čisté strategie budou stejně dobré. Bude to tedy strategie, ve které Alice hraje všechny figury stejně často a eso dvakrát častěji. Bobova maximinová strategie je stejná, takže ve výsledku vyhraje Alice dvě pětiny her a Bob tři pětiny.

Souboj
Hra Na souboj má ze všech uvedených her asi největší šanci na vojenské uplatnění. Alice a Bob kráčejí naproti sobě a v rukou mají pistole nabité jedinou kulkou. Čím jsou k sobě blíž, tím vyšší je šance, že jeden druhého zasáhne. Výplatou každého hráče je jeho šance na přežití.
Jak moc by se měla Alice přiblížit k Bobovi, než vystřelí? To je pro ni otázka doslova života a smrti, protože pokud vystřelí a netrefí se, může Bob přijít až k ní a zastřelit ji z bezprostřední blízkosti. Ať je výsledek hry jakýkoli, vždycky někdo zemře, takže součet výplat je vždy jedna.
Je evidentní, že vystřelit dřív než ten druhý nemůže být pro žádného hráče Nashovou rovnováhou, protože by vždy bylo lepší odpovědí počkat před výstřelem o chvilku déle. Jak moc se tedy hráči přiblíží předtím, než oba zároveň vystřelí?
S pomocí teorému o minimaxu to zjistíme snadno. Hra Na souboj má sice součet jednotkový, ne nulový, ale teorém o minimaxu pořád platí (za předpokladu, že součet výplat je jedna, i když hráči vystřelí zároveň). Jediný rozdíl je v tom, že součet maximinových výplat obou hráčů už není nula, ale jedna. Takže pokud má Alice dvakrát lepší mušku než Bob, oba vystřelí současně, a to ve vzdálenosti, na kterou Alice zasáhne Boba ve dvou třetinách případů a Bob Alici v jedné třetině případů.

Tento text je úryvkem z knihy

Ken Binmore: Teorie her … a jak může změnit váš život
Argo a Dokořán 2018 (nové vydání)
O knize na stránkách vydavatele

obalka_knihy

Český kras: Krajina vytvářená řekami a rozpouštěním vápence

Na konci vrásnění je stlačování nahrazeno částečným roztahováním zvrásněného prostoru, jak se nakupené, několik desítek …

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *

Používáme soubory cookies pro přizpůsobení obsahu webu a sledování návštěvnosti. Data o používání webu sdílíme s našimi partnery pro cílení reklamy a analýzu návštěvnosti. Více informací

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close