Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game
- 23 December 2004
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 258-267
- https://doi.org/10.1109/focs.2004.28
Abstract
The Lemke-Howson algorithm is the classical algorithm for the problem NASH of finding one Nash equilibrium of a bimatrix game. It provides a constructive and elementary proof of existence of an equilibrium, by a typical "directed parity argument", which puts NASH into the complexity class PPAD. This paper presents a class of bimatrix games for which the Lemke-Howson algorithm takes, even in the best case, exponential time in the dimension d of the game, requiring \Omega ((\theta ^{{3 \mathord{\left/ {\vphantom {3 4}} \right. \kern-\nulldelimiterspace} 4}} )^d ) many steps, where 驴 is the Golden Ratio. The "parity argument" for NASH is thus explicitly shown to be inefficient. The games are constructed using pairs of dual cyclic polytopes with 2d suitably labeled facets in d-space.Keywords
This publication has 31 references indexed in Scilit:
- Playing large games using simple strategiesPublished by Association for Computing Machinery (ACM) ,2003
- Computing Normal Form Perfect Equilibria for Extensive Two-Person GamesEconometrica, 2002
- Chapter 45 Computing equilibria for two-person gamesPublished by Elsevier ,2002
- New Maximal Numbers of Equilibria in Bimatrix GamesDiscrete & Computational Geometry, 1999
- Chapter 2 Computation of equilibria in finite gamesHandbook of Computational Economics, 1996
- The d-Step Conjecture and Its RelativesMathematics of Operations Research, 1987
- On the expected number of linear complementarity cones intersected by random and semi-random raysMathematical Programming, 1986
- A note on the Lemke-Howson algorithmPublished by Springer Nature ,1974
- Bimatrix Equilibrium Points and Mathematical ProgrammingManagement Science, 1965
- Equilibrium Points of Bimatrix GamesJournal of the Society for Industrial and Applied Mathematics, 1964