The concept of a pure Nash equilibrium (NE) for a noncooperative game is simpler than that of a mixed NE, which always exists. However, pure NEs probably have more practical significance even though such a game may not have a pure NE. An efficient algorithm is presented here to determine whether an n -person game in normal form has a pure NE and, if so, to obtain all NEs. This algorithm uses the notion of regret, and the payoff matrix (PM) is transformed into a regret matrix (RM)—a loss matrix with an intuitive interpretation. The RM has the property that an action profile of the PM is a pure NE if and only if (0,· · ·,0) is the corresponding element of the RM. The computational complexity of the algorithm is O(N) in the number of individual utilities N in the PM, and so it is substantially faster than a total enumeration.
KeywordsPure Nash EquilibriaAlgorithm for Pure Nash EquilibriaRegret MatrixPareto Nash Equilibrium
Aumann, R. (1985). What Is Game Theory Trying to Accomplish? In K. Arrow, & S. Honkapohja (Eds.), Frontiers of Economics (pp. 5-46). Oxford: Blackwell.
Aumann, R., & Brandenburger, A. (1995) Epistemic Conditions for Nash Equilibrium. Econometrica, 63, 1161-1180. https://doi.org/10.2307/2171725
Barrios, O., Luna, D., & Balcazar, L. (2016) Design of an Efficient Algorithm to Find Pure Nash Equilibria on Strategic Games. IEEE Latin America Transactions, 14, 320-324. https://doi.org/10.1109/TLA.2016.7430096
Buttler, J., & Akchurina, N. (2013) Nash Equilibria in Normal Games via Optimization Methods. European Control Conference (ECC), Zurich, 17-19 July 2013, 724-729. https://doi.org/10.23919/ECC.2013.6669658
Chen, X. (2015). Decentralized Computation Offloading Game for Mobile Cloud Computing. IEEE Transactions on Parallel and Distributed Systems, 26, 974-983. https://doi.org/10.1109/TPDS.2014.2316834
Daskalakis, C., & Leyton-Brown, K. (2009). A Computational Perspective on Game-Theoretic Solution Concepts: A Tutorial. 10th ACM Conference on Electronic Commerce, CA: Stanford University, 6-10 July 2009. http://www.sigecom.org/ec09/slides/Equilibrium-Computation-Tutorial.pdf
Daskalakis, C., Christos, P., & Papadimitriou, H. (2009). The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing, 39, 195-259. https://doi.org/10.1137/070699652
DeDreu, C., Giacomantonio, M., Giffin, M., & Vecchiato, G. (2019). Psychological Constraints on Aggressive Predation in Economic Contests. Journal of Experimental Psychology: General, 148, 1767-1781. https://doi.org/10.1037/xge0000531
Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2017) Computing Approximate Nash Equilibria in Polymatrix Games. Algorithmica, 77, 487-514. https://doi.org/10.1007/s00453-015-0078-7
Farina, G., Kroer, C., & Sandholm, T. (2019). Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions. 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, 8-14 December 2019, 11 p. http://papers.nips.cc/paper/8764-optimistic-regret-minimization-for-extensive-form-games-via-dilated-distance-generating-functions.pdf
Fragkos, G., Tsiropoulou, E., & Papavassiliou, S. (2020). Artificial Intelligence Enabled Distributed Edge Computing for Internet of Things Applications. 2020 16th International Conference on Distributed Computing in Sensor Systems (DCOSS), Marina del Rey, 450-457. https://doi.org/10.1109/DCOSS49796.2020.00077
Gottlob, G., Greco, G., & Scarcello, F. (2005). Pure Nash Equilibria: Hard and Easy Games. Journal of Artificial Intelligence Research, 24, 357-406. https://doi.org/10.1613/jair.1683
Kastampolidou, K., & Andronikos, T. (2020). A Survey of Evolutionary Games in Biology. Advances in Experimental Medicine and Biology, 1194, 253-261. https://doi.org/10.1007/978-3-030-32622-7_23
Mishra, A., & Tsionas, M. (2020). A Minimax Regret Approach to Decision Making under Uncertainty. Journal of Agricultural Economics, 71, 698-718. https://doi.org/10.1111/1477-9552.12370
Myerson, R. (1991). Game Theory: Analysis of Conflict. Cambridge, MA: Harvard University Press.
Myerson, R. (1999). Nash Equilibrium and the History of Economic Theory. Journal of Economic Literature, 37, 1067-1082. https://doi.org/10.1257/jel.37.3.1067
Nahhas, A., & Corley, H. (2018). An Alternative Interpretation of Mixed Strategies in n-Person Normal Form Games via Resource Allocation. Theoretical Economics Letters, 8, 1854-1868. https://doi.org/10.4236/tel.2018.810122
Nash, J. (1951). Non-Cooperative Games. The Annals of Mathematics, 54, 286-295. https://doi.org/10.2307/1969529
Nash, J. (1953). Two-Person Cooperative Games. Econometrica, 21, 128-140. https://doi.org/10.2307/1906951
Papadimitriou, H. (1994). On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. Journal of Computer and System Sciences, 48, 498-532. https://doi.org/10.1016/S0022-0000(05)80063-7
Rubinstein, A. (1991). Comments on the Interpretation of Game Theory. Econometrica, 59, 909-924.
Taha, H. (2017). Operations Research: An Introduction (10th ed.). London: Pearson.
Von Neumann, J., & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton, NJ: Princeton University Press.
Yager, R. (2004). Decision Making Using Minimization of Regret. International Journal of Approximate Reasoning, 36, 109-128. https://doi.org/10.1016/j.ijar.2003.10.003
Zaman, F., Elsayed, S., Ray, T., & Sarkerr, R. (2018). Evolutionary Algorithms for Finding Nash Equilibria in Electricity Markets. IEEE Transactions on Evolutionary Computation, 22, 536-549. https://doi.org/10.1109/TEVC.2017.2742502
Zhang, S., Shan, G., Gao, H., & Jia, T. (2019). Rheumatoid Arthritis Analysis by Nash Equilibrium Game Analysis. Journal of Medical Imaging and Health Informatics, 9, 1382-1385. https://doi.org/10.1166/jmihi.2019.2760
Zhang, Y., Chen, T., & Chang, S. (2020). Existence of Solution to n-Person Non-Cooperative Games and Minimax Regret Equilibria with Set Payoffs. Applicable Analysis. https://doi.org/10.1080/00036811.2020.1813723