The Complexity of Computing Equilibria

Christos Papadimitriou

Chapter 14 in Handbook of Game Theory with Economic Applications, 2015, vol. 4, pp 779-810 from Elsevier

Abstract: In one of the most influential existence theorems in mathematics, John F. Nash proved in 1950 that any normal form game has an equilibrium. More than five decades later, it was shown that the computational task of finding such an equilibrium is intractable, that is, unlikely to be carried out within any feasible time limits for large enough games. This chapter develops the necessary background and formalism from the theory of algorithms and complexity developed in computer science, in order to understand this result, its context, its proof, and its implications.

Keywords: Normal form games; Nash equilibrium; Algorithms; Computational complexity; Polynomial-time algorithms; NP-complete problems; PPAD-complete problems (search for similar items in EconPapers)
JEL-codes: C72 (search for similar items in EconPapers)
Date: 2015
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/B9780444537669000148
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:gamchp:v:4:y:2015:i:c:p:779-810

DOI: 10.1016/B978-0-444-53766-9.00014-8

Access Statistics for this chapter

More chapters in Handbook of Game Theory with Economic Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().