×

A mixed 0-1 linear programming approach to the computation of all pure-strategy Nash equilibria of a finite \(n\)-person game in normal form. (English) Zbl 1407.91023

Summary: A main concern in applications of game theory is how to effectively select a Nash equilibrium, especially a pure-strategy Nash equilibrium for a finite \(n\)-person game in normal form. This selection process often requires the computation of all Nash equilibria. It is well known that determining whether a finite game has a pure-strategy Nash equilibrium is an NP-hard problem and it is difficult to solve by naive enumeration algorithms. By exploiting the properties of pure strategy and multilinear terms in the payoff functions, this paper formulates a new mixed 0-1 linear program for computing all pure-strategy Nash equilibria. To our knowledge, it is the first method to formulate a mixed 0-1 linear programming for pure-strategy Nash equilibria and it may work well for similar problems. Numerical results show that the approach is effective and this method can be easily distributed in a distributed way.

MSC:

91A10 Noncooperative games
90C10 Integer programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, X.; Deng, X., Settling the complexity of two-player Nash equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’06) · doi:10.1109/FOCS.2006.69
[2] Daskalakis, C.; Goldberg, P. W.; Papadimitriou, C. H., The complexity of computing a Nash equilibrium, Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC ’06), 71-78 (2006), New York, NY, USA: ACM, New York, NY, USA · Zbl 1301.68142 · doi:10.1145/1132516.1132527
[3] Lemke, C. E.; Howson, J. T., Equilibrium points of bimatrix games, Journal of the Society for Industrial and Applied Mathematics, 12, 413-423 (1964) · Zbl 0128.14804
[4] Rosenmüller, J., On a generalization of the Lemke-Howson algorithm to noncooperative \(n\)-person games, SIAM Journal on Applied Mathematics, 21, 73-79 (1971) · Zbl 0222.90053 · doi:10.1137/0121010
[5] Wilson, R., Computing equilibria of \(n\)-person games, SIAM Journal on Applied Mathematics, 21, 80-87 (1971) · Zbl 0205.23204 · doi:10.1137/0121011
[6] Nash, J. F., Equilibrium points in \(n\)-person games, Proceedings of the National Academy of Sciences of the United States of America, 36, 48-49 (1950) · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48
[7] Nash, J. F., Non-cooperative games, Annals of Mathematics, 54, 2, 286-295 (1951) · Zbl 0045.08202 · doi:10.2307/1969529
[8] Scarf, H., The approximation of fixed points of a continuous mapping, SIAM Journal on Applied Mathematics, 15, 1328-1343 (1967) · Zbl 0153.49401 · doi:10.1137/0115116
[9] Allgower, E. L.; Georg, K., Piecewise linear methods for nonlinear equations and optimization, Journal of Computational and Applied Mathematics, 124, 1-2, 245-261 (2000) · Zbl 0970.65055 · doi:10.1016/S0377-0427(00)00427-1
[10] Dang, C. Y., The D1-triangulation of Rn for simplicial algorithms for computing solutions of nonlinear equations, Mathematics of Operations Research, 16, 1, 148-161 (1991) · Zbl 0734.90121 · doi:10.1287/moor.16.1.148
[11] Eaves, B. C., Homotopies for computation of fixed points, Mathematical Programming, 3, 1-22 (1972) · Zbl 0276.55004
[12] Garcia, C. B.; Zangwill, W. I., Pathways to Solutions, Fixed Points, and Equilibria (1981), Englewood Cliffs, NJ, USA: Prentice Hall, Englewood Cliffs, NJ, USA · Zbl 0512.90070
[13] Kojima, M.; Yamamoto, Y., A unified approach to the implementation of several restart fixed point algorithms and a new variable dimension algorithm, Mathematical Programming, 28, 3, 288-328 (1984) · Zbl 0539.65036 · doi:10.1007/BF02612336
[14] van der Laan, G.; Talman, A. J. J., A restart algorithm for computing fixed points without an extra dimension, Mathematical Programming, 17, 1, 74-84 (1979) · Zbl 0411.90061 · doi:10.1007/BF01588226
[15] Todd, M. J., The Computation of Fixed Points and Applications. The Computation of Fixed Points and Applications, Lecture Notes in Economics and Mathematical Systems, 1 (1976), Berlin, Germany: Springer, Berlin, Germany · Zbl 0332.54003
[16] Garcia, C. B.; Lemke, C. E.; Luethi, H., Simplicial approximation of an equilibrium point of noncooperative \(n\)-person games, Mathematical Programming, 4, 227-260 (1973) · Zbl 0277.90092
[17] Doup, T. M.; Talman, A. J. J., A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices, Mathematical Programming, 37, 3, 319-355 (1987) · Zbl 0616.90084 · doi:10.1007/BF02591741
[18] Doup, T. M.; Talman, A. J. J., A continuous deformation algorithm on the product space of unit simplices, Mathematics of Operations Research, 12, 3, 485-521 (1987) · Zbl 0653.90078 · doi:10.1287/moor.12.3.485
[19] van der Laan, G.; Talman, A. J. J.; van der Heyden, L., Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling, Mathematics of Operations Research, 12, 3, 377-397 (1987) · Zbl 0638.90096 · doi:10.1287/moor.12.3.377
[20] van den Elzen, A. H.; Talman, A. J. J., A procedure for finding Nash equilibria in bi-matrix games, Zeitschrift für Operations Research: Mathematical Methods of Operations Research, 35, 1, 27-43 (1991) · Zbl 0729.90093 · doi:10.1007/BF01415958
[21] van den Elzen, A.; Talman, D., An algorithmic approach toward the tracing procedure for bi-matrix games, Games and Economic Behavior, 28, 1, 130-145 (1999) · Zbl 0939.91006 · doi:10.1006/game.1998.0688
[22] Harsanyi, J. C., The tracing procedure: a Bayesian approach to defining a solution for \(n\)-person noncooperative games, International Journal of Game Theory, 4, 1-2, 61-94 (1975) · Zbl 0319.90078 · doi:10.1007/BF01766187
[23] Herings, P. J.-J.; van den Elzen, A., Computation of the Nash equilibrium selected by the tracing procedure in \(n\)-person games, Games and Economic Behavior, 38, 1, 89-117 (2002) · Zbl 1013.91004 · doi:10.1006/game.2001.0856
[24] McKelvey, R. D.; McLennan, A., Computation of equilibria in finite games, Handbook of Computational Economics, 1, 87-142 (1996), Amsterdam, The Netherlands: North-Holland, Amsterdam, The Netherlands · Zbl 1126.91304
[25] Von Stengel, B., Computing equilibria for two-person games, Handbook of Game Theory with Economic Applications, 3, 1723-1759 (2002) · doi:10.1016/S1574-0005(02)03008-4
[26] Harsanyi, J. C.; Selten, R., A General Theory of Equilibrium Selection in Games, 1 (1988), Cambridge, Mass, USA: MIT Press, Cambridge, Mass, USA · Zbl 0693.90098
[27] Schanuel, S. H.; Simon, L. K.; Zame, W. R., The algebraic geometry of games and the tracing procedure, Game Equilibrium Models, 2, 9-43 (1991) · Zbl 0813.90134
[28] Herings, P. J.-J.; Peeters, R. J. A. P., A differentiable homotopy to compute Nash equilibria of \(n\)-person games, Economic Theory, 18, 1, 159-185 (2001) · Zbl 0986.91001 · doi:10.1007/PL00004129
[29] Govindan, S.; Wilson, R., A global Newton method to compute Nash equilibria, Journal of Economic Theory, 110, 1, 65-86 (2003) · Zbl 1042.91001 · doi:10.1016/S0022-0531(03)00005-X
[30] Smale, S., A convergent process of price adjustment and global Newton methods, Journal of Mathematical Economics, 3, 2, 107-120 (1976) · Zbl 0354.90018 · doi:10.1016/0304-4068(76)90019-7
[31] Herings, P. J.-J.; Peeters, R. J. A. P., Homotopy methods to compute equilibria in game theory, Economic Theory, 42, 1, 119-156 (2010) · Zbl 1185.91028 · doi:10.1007/s00199-009-0441-5
[32] Yin, S.; Ding, S. X.; Haghani, A.; Hao, H.; Zhang, P., A comparison study of basic data-driven fault diagnosis and process monitoring methods on the benchmark tennessee eastman process, Journal of Process Control, 22, 9, 1567-1581 (2012) · doi:10.1016/j.jprocont.2012.06.009
[33] Yin, S.; Ding, S. X.; Sari, A. H. A.; Hao, H., Data-driven monitoring for stochastic systems and its application on batch process, International Journal of Systems Science, 44, 7, 1366-1376 (2013) · Zbl 1278.93259 · doi:10.1080/00207721.2012.659708
[34] Zhang, H.; Shi, Y.; Wang, J., On energy-to-peak filtering for nonuniformly sampled nonlinear systems: a Markovian jump system approach, IEEE Transactions on Fuzzy Systems, 22, 1, 212-222 (2014) · doi:10.1109/TFUZZ.2013.2250291
[35] Yin, S.; Luo, H.; Ding, S., Real-time implementation of fault-tolerant control systems with performance optimization, IEEE Transactions on Industrial Electronics, 61, 5, 2402-2411 (2013)
[36] Zhang, H.; Zhang, X.; Wang, J., Robust gain-scheduling energy-to-peak control of vehicle lateral dynamics stabilisation, Vehicle System Dynamics (2014) · doi:10.1080/00423114.2013.879190
[37] Kostreva, M. M.; Kinard, L. A., A differentiable homotopy approach for solving polynomial optimization problems and noncooperative games, Computers & Mathematics with Applications, 21, 6-7, 135-143 (1991) · Zbl 0721.90071 · doi:10.1016/0898-1221(91)90168-4
[38] Herings, P. J.-J.; Peeters, R. J. A. P., A globally convergent algorithm to compute all Nash equilibria for \(n\)-person games, Annals of Operations Research, 137, 1, 349-368 (2005) · Zbl 1138.91310 · doi:10.1007/s10479-005-2265-4
[39] Datta, R. S., Finding all Nash equilibria of a finite game using polynomial algebra, Economic Theory, 42, 1, 55-96 (2010) · Zbl 1185.91025 · doi:10.1007/s00199-009-0447-z
[40] Sandholm, T.; Gilpin, A.; Conitzer, V., Mixed-integer programming methods for finding Nash equilibria, Proceedings of the 20th National Conference on Artificial Intelligence
[41] Avis, D.; Rosenberg, G. D.; Savani, R.; von Stengel, B., Enumeration of Nash equilibria for two-player games, Economic Theory, 42, 1, 9-37 (2010) · Zbl 1182.91013 · doi:10.1007/s00199-009-0449-x
[42] Gottlob, G.; Greco, G.; Scarcello, F., Pure Nash equilibria: hard and easy games, Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, ACM · Zbl 1134.91312
[43] Jiang, M., Finding pure Nash equilibrium of graphical game via constraints satisfaction approach, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, 483-494 (2007), New York, NY, USA: Springer, New York, NY, USA · Zbl 1176.91020
[44] Chapman, A. C.; Farinelli, A.; de Cote, E. M.; Rogers, A.; Jennings, N. R., A distributed algorithm for optimising over pure strategy Nash equilibria, Proceedings of the 24th AAAI Conference on Artificial Intelligence
[45] Gottlob, G.; Greco, G.; Mancini, T., Complexity of pure equilibria in bayesian games, Proceedings of the International Joint Conference on Artificial Intelligence
[46] Chapman, A. C., Control of large distributed systems using games with pure strategy Nash equilibria [Ph.D. thesis] (2009), University of Southampton
[47] Bubelis, V., On equilibria in finite games, International Journal of Game Theory, 8, 2, 65-79 (1979) · Zbl 0424.90091 · doi:10.1007/BF01768703
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.