New maximal numbers of equilibria in bimatrix games

Bernhard von Stengel

Abstract:
This paper presents a new lower bound of 2.414^d/sqrt(d) on the maximal number of Nash equilibria in dxd bimatrix games, a central concept in game theory. The proof uses an equivalent formulation of the problem in terms of pairs of polytopes with 2d facets in d-space. It refutes a recent conjecture that 2^d-1 is an upper bound, which was proved for d<5. The first counterexample is a 6x6 game with 75 equilibria. The case d=5 remains open. The result carries the lower bound closer to the previously known upper bound of 2.6^d/sqrt(d).

In:
Discrete and Computational Geometry 21 (1999), 557-568.

PDF-file (125 kB, 12 pages)

gz-compressed POSTSCRIPT-file (103 kB, 15 pages)


Earlier version:

B. von Stengel (1997), New Lower Bounds for the Number of Equilibria in Bimatrix Games. Technical Report 264, Department of Computer Science, ETH Zurich. Abstract, gz-compressed POSTSCRIPT-file (115 kB, 17 pages).


BvSBack to Bernhard von Stengel's list of publications