An Approach to Bounded Rationality - Ben-Sasson, Eli; Kalai, Adam Tauman; Kalai, Ehud (Advances in Neural Information Processing Systems 19 (NIPS), 2007)
Many interactions in complex environments, e.g., chess, are affected by computational limitations. An extreme example is the factoring game, where the first player chooses a large number and sends it to the second player who then attempts to factor it. Ignoring computational considerations, the second player can factor any number and win, but with computational considerations the game seems to favor the first player. This well-known issue in game-theory falls under the term bounded rationality, yet there is no general model of playing games with computational limitations. (Prior work focused mainly on the case of finite automata playing repeated games like prisoner's dilemma.) We propose an extremely simple model of a game with additional costs (computational or otherwise) for each strategy. We illustrate that this model fits nicely into existing concepts in game theory such as zero-sum games, potential games, and submodular games, showing that natural learning dynamics continue to converge to equilibrium.