Finding Nash equilibria of bimatrix games

Savani, Rahul (2006) Finding Nash equilibria of bimatrix games. PhD thesis, London School of Economics and Political Science.

Preview

PDF Download (462kB) | Preview

Abstract

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.

Item Type:	Thesis (PhD)
Additional Information:	© 2006 Rahul Sanjay Janacek Savani
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics Collections > LSE History of Thought theses
Supervisor:	Von Stengel, Bernhard
URI:	http://etheses.lse.ac.uk/id/eprint/128

Actions (login required)

Record administration - authorised staff only