Prestižní časopis Nature zveřejnil studii stochastických her, jejímž spoluautorem je student Matfyzu Štěpán Šimsa.
Nyní posluchač druhého ročníku magisterské informatiky byl členem čtyřčlenného vědeckého týmu, který se shodou několika okolností dal před více než dvěma lety dohromady na výzkumném institutu IST Austria (Institute of Science and Technology Austria). Právě náhoda má přitom ústřední roli také v samotném výzkumu, na kterém Štěpán Šimsa několik měsíců intenzivně spolupracoval.
Na IST Austria přišel jako stážista v dubnu 2016, aby pod vedením profesora Krishnendu Chatterjeeho napsal bakalářskou práci. Záhy dostal nabídku podílet se na zajímavém výzkumu zaměřeném na kooperaci ve stochastických hrách. „Když jsem na IST nastoupil, výzkumná skupina už měla první výsledky. A já jsem začal pracovat na dalších variantách problému,“ popisuje český student, který měl v rámci projektu na starosti hlavně programování počítačových simulací a ověřování hypotéz.
Stochastické hry spadají do oblasti aplikované matematiky známé jako teorie her. Ta zkoumá rozhodovací procesy ve složitých konfliktních situacích a pomocí matematických modelů a výpočtů se snaží nalézat co nejlepší strategie pro hráče. Její poznatky nalézají uplatnění v široké škále oblastí od ekonomie a sociologie až třeba po biologii nebo vojenství.
Štěpán Šimsa (foto: archiv Š.Š.)
Specifikem stochastických her je prvek náhody v podobě nečekaných událostí, které do hry vstupují a nutí hráče rozhodovat se za nejistoty. „Zajímavé situace nastávají, když jsou zájmy jedince v protikladu k zájmům společnosti. Sobecké chování ale zároveň vede k nižším výdělkům všech, což hezky popisuje známý příklad vězňova dilematu. Z dřívějšího výzkumu se ví, že opakovaná interakce může kooperaci navýšit. Naše studie se zabývá situací, kdy mají rozhodnutí jedinců vliv nejen na jejich přímé výdělky, ale i na prostředí, které pak výdělky dále ovlivňuje. Přirozený scénář vypadá tak, že kooperace prostředí zlepšuje, a tedy navyšuje budoucí výdělky, a naopak nekooperativní akce prostředí zhoršuje,“ přibližuje Štěpán Šimsa výchozí premisy výzkumu.
Tým zkoumal varianty vězňova dilematu a díky kombinaci poznatků z teorie stochastických her a evoluční teorie her se mu podařilo ukázat, že závislost prostředí na akcích hráčů může spolupráci výrazně navýšit. „Kombinace evoluční teorie her s teorií stochastických her se ve vědě objevuje poprvé a přínosné je tedy už jen její uvážení. Jednou ze základních otázek evoluční teorie her je právě to, jakým způsobem se kooperace vyvíjí a co ji podporuje. V přírodě je totiž kooperace velmi běžná i v situacích, které zdánlivě připomínají vězňovo dilema, což by ale znamenalo, že není racionální. Náš výzkum ukazuje, že uvážení stochastických her může kooperaci navýšit ještě výrazně více než obyčejné opakování hry,“ vysvětluje Šimsa.
Výsledky nyní skupina prezentuje na stránkách časopisu Nature. Štěpán Šimsa navíc získané poznatky využil ve své bakalářské práci, kterou před dvěma lety úspěšně obhájil. „Za pár týdnů budu své poznatky a simulace předávat novému stážistovi. S týmem zatím další spolupráci nechystáme, ale bylo mi několikrát naznačeno, že by o mě byl zájem, pokud bych se rozhodl pro doktorské studium na IST Austria,“ říká talentovaný student, kterého na podzim čekají na Matfyzu státnice a obhajoba diplomové práce.
Vězňovo dilema je jednoduchá hra modelující reálnou situaci dvou spoluviníků vyslýchaných policií. Ti mají možnost (současně, nezávisle na sobě) toho druhého buď zradit, nebo s ním spolupracovat. Nejlepší by bylo druhého zradit, zatímco on by se rozhodl kooperovat. O něco horší je spolupráce obou a po ní zrada obou. Nejhorší je kooperovat a být zrazen. Z toho vidíme, že nezávisle na tom, co udělá druhý hráč, se vyplatí ho zradit (vždy to vede k vyššímu výdělku). A paradox je v tom, že u racionálních hráčů to vede nevyhnutelně k tomu, že oba zradí, což je ale pro oba horší, než kdyby spolu kooperovali.
Situace se změní, když se hra mezi stejnými hráči opakuje. Potom rozhodnutí hráče ovlivňuje i budoucí kola (protihráč si pamatuje, jestli jsem kooperoval, nebo zradil), a tak může být zrada dobrá pro aktuální tah, ale škodlivá pro ty budoucí. Strategie „vždy zraď“ sice v každém kole dosáhne nejlepšího možného výsledku, ale to ještě neznamená, že jde o nejlepší taktiku. Jedna z úspěšnějších strategií je například ta zvaná Tit for Tat (oko za oko), kdy hráč v prvním kole kooperuje a v každém dalším kole opakuje poslední tah protihráče. Při opakovaném vězňově dilematu přestává být jasné, jak strategie porovnávat. Právě k tomu slouží evoluční teorie her. Ta vlastně simuluje evoluci: nechává proti sobě strategie soupeřit, přičemž strategie s vyššími výdělky mají vyšší šanci na reprodukci. Jak je strategie dobrá, se potom posuzuje podle jejího průměrného zastoupení napříč generacemi.
Stochastická teorie her se zabývá hrami, ve kterých se hráči nacházejí v každém kole v nějakém stavu. Na základě aktuálního stavu hry (akcí, které hráči dané kolo udělají), a případně s využitím náhody, se určí stav, ve kterém hráči budou v následujícím kole. Stav hry také definuje výdělky jednotlivých hráčů na základě akcí, které zahrají. To je možné demonstrovat na příkladu stochastické hry, kterou se zabývá právě výzkum v časopisu Nature: Máme dva stavy, v obou se hraje vězňovo dilema. V prvním mají hráči vyšší výdělky než v druhém. Na začátku jsou v prvním stavu. Vždy, když oba kooperují, jsou následující tah v prvním stavu, ale když alespoň jeden z nich zradí, budou ve druhém stavu. A právě takovýto trest za zradu vede k vyšší kooperaci hráčů. A to dokonce natolik, že výdělky hráčů, kterých se průměrně dosáhne v evolučním modelu popsaném výše, jsou vyšší, než kdyby se hrálo celou dobu v prvním, výdělečnějším stavu.
Další informace o výzkumu: https://natureecoevocommunity.nature.com/users/114534-christian-hilbe/posts/34929-a-stochastic-journey-to-stochastic-games