Computability of Nash Equilibrium

Hidetoshi Tashiro ()
Additional contact information
Hidetoshi Tashiro: Hitotsubashi University, Graduate School of Economics

A chapter in ICM Millennium Lectures on Games, 2003, pp 349-357 from Springer

Abstract: Summary This paper considers the computability of the Nash equilibria of a game, i.e. the possibility of an algorithm to play the game with respect to Nash equilibria. We consider a two-person game, in which both players have countably many feasible actions and their particular payoff functions are computable in the sense that there are algorithms to compute the values of ones for any given action profile. It is proved that there exists no algorithm to decide whether or not a given action profile is a Nash equilibrium. Moreover, we show that the set of the Nash equilibria is not empty, but there exists no algorithm to enumerate it allowing repetitions. These results mean that no Nash equilibrium of the game cannot be computed by any human being in practice, although the existence of the Nash equilibria can be proved in theory. Indeed, it is impossible to supply the players with algorithms regarding how they should decide whether or not a given action profile is a Nash equilibrium of the game or how they should enumerate all Nash equilibria. On the other hand, I show that if players’s payoff functions are any rational number valued polynomials bounded from the above with rational number coefficients, then the Nash equilibria of the game are computable.

Keywords: Nash equilibrium; Computability; algorithm (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-3-662-05219-8_22

Ordering information: This item can be ordered from
http://www.springer.com/9783662052198

DOI: 10.1007/978-3-662-05219-8_22

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().