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. 1 Tato 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

Permalink: http://www.nusl.cz/ntk/nusl-365076


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses