×
Audet, C.; Belhaiza, S.; Hansen, P.

Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games. (English) Zbl 1122.91009

J. Optim. Theory Appl. 129, No. 3, 349-372 (2006).
The autors study the problem of extreme Nash equilibria in bimatrix games and in their special generalization to \(n\)-person games, called polymatrix games . The first obtained result says that such games can be expressed as parametric linear 0-1 programs. Next this is used to construct the \(E\chi\)-MIP algorithm for the complete enumeration of the extreme equilibria in bimatrix and polymatrix games. This algorithm is numeracally illustrated for 3-person polymatrix games of size \(m\times m\times m\) with \(m\) up to 13. Also, it is compared with an another EEE algorithm of Audet in computational results on randomly generated bimatrix games for sizes \(n\times n\) for \(n\) up to 14.
Reviewer: Tadeusz Radzik (Jelenia Góra)

Cited in 1 Review
Cited in 14 Documents

MSC:

91A10 Noncooperative games
91A05 2-person games
91A06 \(n\)-person games, \(n>2\)
91B50 General equilibrium theory

Keywords:

Nash equilibria
PDF BibTeX XML Cite
\textit{C. Audet} et al., J. Optim. Theory Appl. 129, No. 3, 349--372 (2006; Zbl 1122.91009)
Full Text: DOI

References:

[1] NASH, J. F., Equilibrium Points in n-Person Games, Proceedings of the National Academy of Sciences, Vol. 36, pp. 48–49, 1950. · Zbl 0036.01104
[2] MILLHAM, C. B., On Nash Subsets of Bimatrix Games, Naval Research Logistics Quarterly, Vol. 74, pp. 307–317, 1974. · Zbl 0366.90132
[3] AUDET, C., HANSEN, P., JAUMARD, B., and SAVARD, G., Enumeration of All Extreme Equilibrium Strategies of Bimatrix Games, SIAM Journal on Statistical and Scientific Computing, Vol. 23, pp. 323–338, 2001. · Zbl 0996.91004
[4] MILLS, H., Equilibrium Points in Finite Games, SIAM Journal on Applied Mathematics, Vol. 8, pp. 397–402, 1960. · Zbl 0099.15201
[5] MANGASARIAN, O. L., and STONE, H., Two-Person Nonzero-Sum Games and Quadratic Programming, Journal of Mathematical Analysis and Applications, Vol. 9, pp. 348–355, 1964. · Zbl 0126.36505
[6] MANGASARIAN, O. L., Equilibrium Points of Bimatrix Games, SIAM Journal on Applied Mathematics, Vol. 12, pp. 778–780, 1964. · Zbl 0132.14002
[7] VOROBEV, N. N., Equilibrium Points in Bimatrix Games, Theoriya Veroyatnostej i ee Primwneniya, Vol. 3, pp. 318–331, 1958 [English Version: Theory of Probability and Its Applications, Vol. 3, pp. 297–309, 1958].
[8] KEIDING, H., On the Maximal Number of Nash Equilibria in a Bimatrix Game, Games and Economic Behavior, Vol. 21, pp. 148–160, 1997. · Zbl 0911.90352
[9] VON STENGEL, B., New Maximal Numbers of Equilibria in Bimatrix Games, Discrete and Computational Geometry, Vol. 21, pp. 557–568, 1998. · Zbl 0956.91003
[10] KUHN, H. W., An Algorithm for Equilibrium Points in Bimatrix Games, Proceedings of the National Academy of Sciences, Vol. 47, pp. 1657–1662, 1961. · Zbl 0171.40902
[11] LEMKE, C. E., and HOWSON, T. T., Equilibrium Points of Bimatrix Games, SIAM Journal on Applied Mathematics, Vol. 12, pp. 413–423, 1961. · Zbl 0128.14804
[12] DICKHAUT, J., and KAPLAN, T., A Program for Finding Nash Equilibria, Mathematica Journal, Vol. 1, pp. 87–93, 1991.
[13] MCKELVEY, R. D., and MCLENNAN, A., Computation of Equilibria in Finite Games, Handbook of Computational Economics, Edited by H. M. Amman, D. A. Kendrick, and J. Rust, Elsevier, Amsterdam, Holland, Vol. 1, pp. 87–142, 1996. · Zbl 1126.91304
[14] WINKELS, R., An Algorithm to Determine all Equilibrium Points of a Bimatrix Games, Game Theory and Related Topics, Edited by O. Moeschlin and D. Pallaschke, North Holland Publishing Company, Amsterdam, Holland, 1972.
[15] AUDET, C., Optimisation Globale Structurée: Propriétés, Equivalences et Résolution, PhD Thesis, École Polytechnique de Montréal, pp. 91–109, 1997.
[16] JÚDICE, J., and MITRA, G., Reformulations of Mathematical Programming Problems as Linear Complementarity Problems and Investigation of Their Solution Methods, Journal of Optimization Theory and Applications, Vol. 57, pp. 123–149, 1988. · Zbl 0619.90076
[17] AUDET, C., HANSEN, P., JAUMARD, B., and SAVARD, G., Links between Linear Bilevel and Mixed 0-1 Programming Problems, Journal of Optimization Theory and Applications, Vol. 93, pp. 273–300, 1997. · Zbl 0901.90153
[18] HOWSON, J. T., Equilibria of Polymatrix Games, Management Science, Vol. 18, pp. 312–318, 1972. · Zbl 0228.90058
[19] QUINTAS, L. G., A Note on Polymatrix Games, International Journal of Game Theory, Vols. 18–19, pp. 261–272, 1989. · Zbl 0679.90099
[20] COTTLE, R. W., and DANTZIG, G. B., Complementary Pivot Theory of Mathematical Programming, Mathematics of the Decision Scienes, Part 1, Vol. 11, pp. xxx–xxx, 1968. · Zbl 0155.28403
[21] YANOVSKAYA, E. B., Equilibrium Points in Polymatrix Games, Latvian Mathematical Collection, Vol. 8, pp. 381–384, 1968. · Zbl 0205.49002
[22] COTTLE, R. W., and DANTZIG, G. B., Linear Programming Extensions, Princeton University Press, Princeton, New Jersey, 1963.
[23] LEMKE, C. E., Bimatrix Games Equilibrium Points and Mathematical Programming, Management Science, Vol. 11, pp.xxx-xxx, 1965. · Zbl 0139.13103
[24] EAVES, C. B., Polymatrix Games with Joint Constraints, SIAM Journal on Applied Mathematics, Vol. 24, pp. 418–423, 1973. · Zbl 0253.90067
[25] HOWSON, J. T., and ROSENTHAL, R. W., Bayesian Equilibria of Finite Two-Person Games with Incomplete Information, Management Science, Vol. 21, pp. 313–315, 1974. · Zbl 0306.90088
[26] MYERSON, R. B., Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, Massachusetts, 1997. · Zbl 0729.90092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.