Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200418December 2004 
Arndt von Schemde
Abstract
This thesis provides a new geometriccombinatorial construction to characterise the Nash equilibria of a nondegenerate bimatrix game and their indices. Considering a nondegenerate m×n bimatrix game, the construction yields an (m1)simplex that is simplicially divided into (m1)simplices, reflecting the best reply structure of player II. Each (m1)simplex in the triangulation is divided into best reply regions of player I. This yields a division of the entire simplex 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 LemkeHowson algorithm follows paths that are defined by m1 labels of player I.
This representation of bimatrix games is shown to be related to Sperner's Lemma in dimension m1. In particular, the existence of Nash equilibria in nondegenerate 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 nondegenerate 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 wellknown 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 nonzero 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.
A PDF file (602 kB) with the full contents of this report can be downloaded by clicking here.
Because of its length (144) pages, this report is only available electronically.
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html