Finding Nash equilibria of bimatrix games

This thesis concerns the computational problem of finding one Nash equilibrium of a bimatrix game, a two-player game in strategic form. Bimatrix games are among the most basic models in non-cooperative game theory, and finding a Nash equilibrium is important for their analysis. The Lemke—Howson algorithm is the classical method for finding one Nash equilib-rium of a bimatrix game. In this thesis, we present a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2d suitably labelled facets in d-space. The construc-tion is extended to two classes of non-square games where, in addition to exponentially long Lemke—Howson computations, finding an equilibrium by support enumeration takes exponential time on average. The Lemke—Howson algorithm, which is a complementary pivoting algorithm, finds at least one solution to the linear complementarity problem (LCP) derived from a bimatrix game. A closely related complementary pivoting algorithm by Lemke solves more general LCPs. A unified view of these two algorithms is presented, for the first time, as far as we know. Furthermore, we present an extension of the standard version of Lemke's algorithm that allows one more freedom than before when starting the algorithm