The Nash equilibrium is the central solution concept for noncooperative games. In general, such an equilibrium requires randomized strategies of the players, and it is not unique. We study the number of equilibria for bimatrix games. Quint and Shubik conjectured in 1994 that nondegenerate n x n bimatrix games have at most 2^n-1 equilibria, which is the case for the simple "coordination game" where each player's payoffs are given by the identity matrix.

We present a class of counterexamples to this conjecture for n=6 (with a game that has 75 equilibria) and larger, with asymptotically more than 2.414^n equilibria. Compared with the earlier lower bound of 2^n, this is not far from the upper bound of about 2.6^n known from the Upper Bound Theorem for polytopes. This suggests that algorithms for determining all equilibria, which are useful in a game-theoretic analysis, are best implemented using vertex enumeration. Our construction is based on cyclic polytopes with a suitable permutation of their "facet labels" that are used to represent the complementarity condition of an equilibrium.

The talk will emphasize the geometric intuition behind the construction. No prior knowledge of the technical concepts is required.