15th February 2005 <br>
Rahul Savani, LSE, <br>
"Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game".
<br>
Abstract:<br>

A bimatrix game is a two-player game in strategic form, 
a basic model in game theory. A Nash equilibrium is a pair of 
(possibly randomized) strategies, one for each player, 
so that no player can do better by unilaterally changing 
his or her strategy. The problem of finding one Nash equilibrium 
of a bimatrix game is considered as 
"one of the most important concrete open questions on the 
boundary of P [polynomial-time computability] today" (Papadimitriou, 2001).
<br><br>

In this talk, which will introduce the main concepts and geometric tools, 
we show that the commonly used Lemke-Howson algorithm for finding one 
equilibrium of a bimatrix game is NOT polynomial. This question had 
been open for some time. The algorithm is a pivoting method similar to the 
simplex algorithm for linear programming. We present a class of square 
bimatrix games for which the shortest Lemke-Howson path grows 
exponentially in the dimension of the game d. We construct the games 
using pairs of dual cyclic polytopes with 2d facets in d-space.
<br><br>
Joint work with Bernhard von Stengel (LSE).