Econometrica · 2006 · 135 citations · 41 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsGame TheoryAlgorithmic Game TheoryCombinatorial Game TheoryMatrix ComputationNash EquilibriumNoncooperative Game TheoryComputational Game TheoryComputational Methods For EquilibriumEquilibrium ComputationExponential Time ComplexityMatrix GamesNash Equilibrium ComputationNash Equilibrium ProblemsPolytope Enumeration
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 2d 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.
41
John F. Nash · Annals of Mathematics · 1951 · 6.6K citations
Concrete Mathematics: A Foundation for Computer Science
Ronald Graham, Donald E. Knuth, Oren Patashnik et al. · Computers in Physics · 1989 · 2.5K citations
Noam Nisan, Amir Ronen · Games and Economic Behavior · 2001 · 1.4K citations