15th February 2005
Rahul Savani, LSE,
"Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game".
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).
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.
Joint work with Bernhard von Stengel (LSE).