I'M Only Human: Game Theory With Computationally Bounded Agents

Abstract

Rationality in games and decisions is traditionally understood as requiring that agents act optimally. However, as pointed out by Simon [64] acting optimally might be hard. We study how the analysis of games and behaviors changes when agents are assumed to be rational but computationally bounded, and thus cannot always act optimally. We first argue that some observed "irrational" human behaviors can be explained by viewing people as computationally bounded agents. We show that adding computation costs into interactive settings have some unintuitive consequences that might lead to behaviors that seem irrational at first. We then consider a dynamic decision problem, and show that some observed human behavior can be actually explained by modeling people as computationally bounded agents that are doing as well as they can, given their limitations. We then develop appropriate models of computationally bounded agents modeled as polynomial-time TM. We study the implications of these models and use these models to analyze different aspect of economic systems. We first develop a model appropriate for a repeated game setting and show that problems that are considered intractable, such as computing a NE in repeated games, actually become tractable in this model. We then develop a model of computational games, which are finite extensive-form games played by computationally bounded players and show an application of this model to the analyzing of cryptographic protocols from a game theoretic perspective.