Hard-to-Solve Bimatrix Games
Rahul Savani, Bernhard von Stengel
Econometrica · 2006 · Volume 74 · Issue 2
DOI: 10.1111/j.1468-0262.2006.00667.x
Abstract
The Lemke–Howson algorithm is the classical method for finding one Nash equilibrium of a bimatrix game. This paper presents a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimensiondof the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2dsuitably labeled facets ind-space. The construction is extended to nonsquare games where, in addition to exponentially long Lemke–Howson computations, finding an equilibrium by support enumeration takes on average exponential time.
Keywords
Bimatrix game, computational complexity, Lemke–Howson algorithm, Nash equilibrium, support enumeration
Enable JavaScript for citation tools and additional paper interactions.