Enumeration of All Extreme Equilibria of Bimatrix Games

The set of equilibrium points of a bimatrix game is the union of polytopes that are not necessarily disjoint. Knowledge of the vertices of these polytopes (extreme equilibria) is sufficient to identify all equilibria. We present an algorithm that enumerates all extreme equilibria by exploiting complementary slackness optimality conditions of two pairs of parameterized linear programming problems. The algorithm is applied to randomly generated problems of size up to 29 × 29 when both dimensions are equal, and up to 700 × 5 when the second dimension is fixed. The number of extreme equilibria grows exponentially with problem size but remains moderate for the instances considered. Therefore, the results could be useful for further study of refinements of Nash equilibria.