Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2004-14 August 2004

Abstract

The problem NASH is that of finding one Nash equilibrium of a bimatrix game. The computational complexity of this problem is a long-standing open question. The Lemke-Howson algorithm is the classical algorithm for NASH. In an earlier paper, this algorithm was shown to be exponential, even in the best case, for square bimatrix games using dual cyclic polytopes. However the games constructed there are easily solved by another standard method, support enumeration. In this paper we present "challenge instances" for NASH.We extend the use of dual cyclic polytopes and construct a class of games which are shown to be hard to solve for both the Lemke-Howson algorithm and support enumeration. Other general methods for NASH are discussed. It is not obvious that they could solve these games efficiently.

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

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2004-14, 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@cdam.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

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