Premium
Hard‐to‐Solve Bimatrix Games
Author(s) -
Savani Rahul,
Stengel Bernhard
Publication year - 2006
Publication title -
econometrica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 16.7
H-Index - 199
eISSN - 1468-0262
pISSN - 0012-9682
DOI - 10.1111/j.1468-0262.2006.00667.x
Subject(s) - polytope , nash equilibrium , dimension (graph theory) , class (philosophy) , mathematics , exponential function , enumeration , combinatorics , computation , game theory , mathematical economics , mathematical optimization , computer science , algorithm , mathematical analysis , artificial intelligence
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 dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2 d suitably labeled facets in d ‐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.