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.
gz-compressed POSTSCRIPT-file (103 kB, 15 pages)