Rahul Savani, London School of Economics

Title:  Long Lemke-Howson Paths

Abstract:   
The Lemke-Howson algorithm is the main algorithm for finding
one equilibrium of a bimatrix game.  In this paper 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.