Computability and Robustness of Equilibrium in Finite Games

Kislaya Prasad

No 1122, Computing in Economics and Finance 1999 from Society for Computational Economics

Abstract: This paper considers finite games in strategic form. It is shown that, when payoffs are computable, every game has a Nash equilibrium in which each player uses a strategy which is computable. There can, however, exist no algorithm that is guaranteed to find an equilibrium for every instance of a game with computable payoffs. In contrast, an approximate equilibrium is always computable (this is what Scarf type algorithms find). This paper develops the relationship between notions of robustness (or stability) of games and computability. The emphasis here is on notions of evolutionary stability, such as ESS. For finite symmetric games, in a model where players know only their own payoffs and form beliefs about the distribution of play of others, the two concepts are essentially identical.

Date: 1999-03-01
New Economics Papers: this item is included in nep-cmp and nep-gth
References: View complete reference list from 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:sce:scecf9:1122

Access Statistics for this paper

More papers in Computing in Economics and Finance 1999 from Society for Computational Economics CEF99, Boston College, Department of Economics, Chestnut Hill MA 02467 USA. Contact information at EDIRC.
Bibliographic data for series maintained by Christopher F. Baum (baum@bc.edu).