Original title:
Výpočetní omezená racionalita
Translated title:
Computational Bounded Rationality
Authors:
Černý, Jakub ; Loebl, Martin (advisor) ; Hladík, Milan (referee) Document type: Master’s theses
Year:
2017
Language:
eng Abstract:
[eng][cze] This thesis formalizes a model of bounded rationality in extensive-form games called game-playing schemata. In this model, the strategies are repre- sented by a structure consisting of a deterministic finite automaton and two computational functions. The automaton represents a structured memory of the player, while the functions represent the ability of the player to identify efficient abstractions of the game. Together, the schema is a realization of a pure strategy which can be implemented by a player in order to play a given game. The thesis shows how to construct correctly playing schema for every pure strategy in any multi-player extensive-form game with perfect recall and how to evaluate its complexity. It proves that equilibria in schemata strategies always exist and computing them is PPAD-hard. Moreover, for a class of efficiently representable strategies, computing MAXPAY-EFCE can be done in polynomial time. 1Tato závěrečná práce formalizuje model omezené racionality hráčů v sekvenčních hrách nazvaný herní schémata. Ve zkoumaném modelu jsou strategie reprezentované strukturou skládající se z konečného automatu a dvou výpočetních funkcí. Zatímco konečný automat reprezentuje hráčovu strukturovanou pamět', výpočetní funkce reprezentují jeho schopnost efek- tivně abstrahovat danou hru. Schémata jsou realizacemi čistých strategií a mohou být hráčem implementovány za účelem hraní sekvenční hry. Práce ukazuje jak zkonstruovat korektně hrající schéma pro jakoukoli strategii v jakékoli sekvenční hře s vícero hráči a jak určit jeho složitost. Dokazuje, že ekvilibrium vždy existuje a jeho výpočet je PPAD-těžký. Navíc práce defin- uje třídu efektivně reprezentovatelných strategií, pomocí které lze spočítat MAXPAY-EFCE v polynomiálním čase. 1
Keywords:
algorithms; bounded rationality; computational complexity; Discrete finite automata; extensive-form games; algoritmy; extenzivní hry; Konečné automaty; omezená racionalita; výpočetní složitost
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/90480