The rationality/computability trade-off in finite games

Kislaya Prasad

Journal of Economic Behavior & Organization, 2009, vol. 69, issue 1, 17-26

Abstract: 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.

Keywords: Nash; equilibrium; Bounded; rationality; Computability (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167-2681(08)00201-1
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jeborg:v:69:y:2009:i:1:p:17-26

Access Statistics for this article

Journal of Economic Behavior & Organization is currently edited by Houser, D. and Puzzello, D.

More articles in Journal of Economic Behavior & Organization from Elsevier
Bibliographic data for series maintained by Catherine Liu ().