Abstract
We show that ify is an odd integer between 1 and 2n − 1, there is ann × n bimatrix game with exactlyy Nash equilibria (NE). We conjecture that this 2n − 1 is a tight upper bound on the number of NEs in a “nondegenerate”n × n game.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Borm P, Gusberts A, Tijs SH (1988) A geometric-combinatorial approach to bimatrix games. Methods of Operations Research 59: 199–209
Eaves BC (1971) The linear complementarity problem. Management Science 17: 612–634
Gul F, Pearce D, Stacchetti E (1993) A bound on the proportion of pure strategy equilibria in generic games. Mathematics of Operations Research 18: 548–552
Harsanyi J (1973) Oddness of the number of equilibrium: A new proof. International Journal of Game Theory 2: 235–250
Jansen M (1981) Regularity and stability of equilibrium points of bimatrix games. Mathematics of Operations Research 6: 530–550
Lemke CE, Howson JT (1964) Equilibrium points in bimatrix games. SIAM Journal of Applied Math 12:413–423
Nash JF (1950) Equilibrium points in n-person games. Proceedings of the National Academy of Sciences USA 36:48–9
Nash JF (1953) Noncooperative games. Annals of Mathematics 54: 286–95
Quint T, Shubik M (1994) On the number of Nash equilibria in a bimatrix game. Cowles Foundation Discussion Paper 1089, Yale University
Quint T, Shubik M (1995) A bound on the number of Nash equilibria in a coordination game. Cowles Foundation Discussion Paper 1095 Yale University
Shapley LS (1974) A note on the Lemke-Howson algorithm. Mathematical Programming Study 1: 175–89
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Quint, T., Shubik, M. A theorem on the number of Nash equilibria in a bimatrix game. Int J Game Theory 26, 353–359 (1997). https://doi.org/10.1007/BF01263276
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01263276