Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2004-03

March 2004


Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game

Rahul Savani and Bernhard von Stengel

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, 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/4})^d)$ many steps, where $\theta$ 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.


A PDF file (250 kB) with the full contents of this report can be downloaded by clicking here.

(This paper supersedes the earlier paper Long Lemke-Howson Paths, which is obsolete.)

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2004-03, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk


Introduction to the CDAM Research Report Series.
CDAM Homepage.


Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html