Název: Výpočetní omezená racionalita
Překlad názvu: Computational Bounded Rationality
Autoři: Černý, Jakub ; Loebl, Martin (vedoucí práce) ; Hladík, Milan (oponent)
Typ dokumentu: Diplomové práce
Rok: 2017
Jazyk: eng
Abstrakt: [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
Klíčová slova: algoritmy; extenzivní hry; Konečné automaty; omezená racionalita; výpočetní složitost; algorithms; bounded rationality; computational complexity; Discrete finite automata; extensive-form games

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/90480

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-365076


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce