O'Reilly logo

Handbook of Game Theory by Shmuel Zamir, Petyon Young

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 14

The Complexity of Computing Equilibria

Christos Papadimitriou*    * University of California, Berkeley, USA

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required