Centre for Discrete and Applicable Mathematics

CDAM Research Report, LSE-CDAM-2005-18

December 2005

Enumeration of All Extreme Equilibria of Bimatrix Games with Integer Pivoting and Improved Degeneracy Check

Gabriel D. Rosenberg

The "Enumeration of All Extreme Equilibria of Bimatrix Games" algorithm of Audet et al. (2001) uses the best response condition of Nash Equilibria to create a search tree in which pure strategies are forced to be either a best response or played with zero probability. Finding sets of constraints with no feasible solution allows the algorithm to avoid searching all game supports and thereby speeds the enumeration process. This paper presents two new improvements to the EEE algorithm. First, the algorithm is implemented in Java using only integer arithmetic, as opposed to previous implementation using floating-point arithmetic. This exact solution of linear programs for the algorithm avoids potential rounding errors. Preliminary running time results of this implementation, determining the relative efficacy of objective functions for the lin- ear program search, and a comparison to another enumeration algorithm are reported. Second, the degeneracy check is improved, drastically cutting running time for certain classes of games and making the algorithm theoretically clearer. The new approach introduces constraints until the feasible set consists of only one strategy or is empty. The combination of these two improvements increases EEE's usefulness as a tool for bimatrix game solution.

A PDF file (609 kB) with the full contents of this report can be downloaded by clicking here.

Due to its size, this report is not available in hardcopy.

CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.

Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last modified: 20th December 2005

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk