The rationality/computability trade-off in finite games

The computability of Nash equilibrium points of finite strategic form games is examined. When payoffs are computable there always exists an equilibrium in which all players use computable strategies, but there can be no algorithm that, given an arbitrary strategic form game, can compute its Nash equilibrium point. This is a consequence of the fact, established in this paper, that there is a computable sequence of games for which the equilibrium points do not constitute a computable sequence. Even for games with computable equilibrium points, best response functions of the players need not be computable. In contrast, approximate equilibria and error-prone responses are computable.