Abstrakt
We formalize a model of bounded rationality in extensive-form games called game-playing schemata. In this model, a strategy is represented as 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 strategy. We show how to construct a schema for every pure strategy and how to conveniently introduce its complexity.
We prove that Nash equilibria in schematic strategies always exist and computing them is PPAD-hard. For a class of strategies representable by planar schemata of logarithmic size, computing any extensive-form correlated equilibrium can be done in polynomial time.