A geometric-combinatorial approach to index and stability in bimatrix games

This thesis provides a new geometric-combinatorial construction to characterise the Nash equilibria of a non-degenerate bimatrix game and their indices. Considering a non-degenerate m x n bimatrix game, the construction yields an (m — 1)-simplex X^ that is simplicially divided into (m — l)-simplices, reflecting the best reply structure of player II. Each (m — 1)-simplex in the triangulation is divided into best reply regions of player I. This yields a division of XA into regions with labels 1,..., m. In this representation, the Nash equilibria are represented by completely labelled points, and the index is the local orientation of the m regions around completely labelled points. For a missing label of player I, the Lemke-Howson algorithm follows paths in XA that are defined by m — 1 labels of player I. This representation of bimatrix games is shown to be related to Sperner's Lemma in dimension m — 1. In particular, the existence of Nash equilibria in non-degenerate bimatrix games is equivalent to Brouwer's fixed point theorem. The construction yields a new strategic characterisation of the index, conjectured by Hofbauer (2000). It is shown that a Nash equilibrium in a non-degenerate bimatrix game has index +1 if and only if one can add strategies to the game such that the equilibrium is the unique equilibrium of the extended game. The construction can be extended to outside option equilibrium components in bimatrix games. The characterisation for such components is shown to be similar to the well-known Index Lemma. As a consequence, index zero boundary labellings allow triangulations that do not contain a completely labelled simplex. The game theoretic counterpart applies to outside option equilibrium components. It is shown that an outside option equilibrium component is hyperessential if and only if it has non-zero index. This question had been open for some time. It is also shown how equilibrium components of arbitrary index can be constructed by means of outside options in bimatrix games