Interval Methods for Computing Strong Nash Equilibria of Continuous Games
DOI:
https://doi.org/10.7494/dmms.2015.9.1.63Keywords:
strong Nash equilibria, continuous games, interval computations, numerical game solvingAbstract
The problem of seeking strong Nash equilibria of a continuous game is considered. For some games, these points cannot be found analytically, only numerically. Interval methods provide us with an approach to rigorously verify the existence of equilibria in certain points. A proper algorithm is presented. We formulate and prove propositions, that give us features which have to be used by the algorithm (to the best knowledge of the authors, these propositions and properties are original). Parallelization of the algorithm is also considered, and numerical results are presented. As a particular example, we consider the game of “misanthropic individuals”, a game, invented by the first author, that may have several strong Nash equilibria depending on the number of players. Our algorithm is able to localize and verify these equilibria.
References
Aumann R.J. (1959). Acceptable points in general cooperative n-person games. In: Tucker A.W. & Luce R.D. (Eds.), Contributions to the Theory of Games IV. Annals of Mathematics Studies, 40, pp. 287–324. Princeton: Princeton University Press. DOI: http://doi.org/10.1515/9781400882168-018.
C-XSC. (2013). C-XSC: A C++ class library for extended scientific computing. URL: https://www2.math.uni-wuppertal.de/wrswt/xsc/cxsc.html [21.08.2026].
Gatti N., Rocco M. & Sandholm T. (2013). On the verification and computation of strong Nash equilibrium. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), Saint Paul, USA, May 6–10, 2013, vol. 1, pp. 723–730. Richland: International Foundation for Autonomous Agents and Multiagent Systems. DOI: http://doi.org/10.5555/2484920.2485034.
Hansen E.R. & Walster G.W. (2004). Global Optimization Using Interval Analysis. 2nd Edition. New York: Marcel Dekker. DOI: http://doi.org/10.1201/9780203026922.
Holzman R. & Law-Yone N. (1997). Strong equilibrium in congestion games. Games and Economic Behavior, 21(1–2), pp. 85–101. DOI: http://doi.org/10.1006/game.1997.0592.
Horáček J. & Hladík M. (2013). Computing enclosures of overdetermined interval linear systems. Reliable Computing, 19(2), pp. 142–155. URL: http://interval.louisiana.edu/reliable-computing-journal/volume-19/reliable-computing-19-pp-142-155.pdf [21.08.2026].
Horáček J. & Hladík M. (2014). Subsquares approach – A simple scheme for solving overdetermined interval linear systems. In: Wyrzykowski R., Dongarra J., Karczewski K. & Waśniewski J. (Eds.), Parallel Processing and Applied Mathematics. PPAM 2013. Lecture Notes in Computer Science, 8385, pp. 613–622. Berlin–Heidelberg: Springer. DOI: http://doi.org/10.1007/978-3-642-55195-6_58.
Jauernig K., Kołodziej J. & Stysło M. (2006). HGS-Nash evolutionary strategy as an effective method of detecting the Nash equilibria in n-person non-cooperative games. In: Proceedings of KAEiOG’06, Murzasichle, Poland, pp. 171–178.
Jaulin L., Kieffer M., Didrit O. & Walter E. (2001). Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics. London: Springer. DOI: http://doi.org/10.1007/978-1-4471-0249-6.
Kearfott R.B. (1996). Rigorous Global Search: Continuous Problems. Nonconvex Optimization and Its Applications, 13. Dordrecht: Kluwer Academic Publishers. DOI: http://doi.org/10.1007/978-1-4757-2495-0.
Kearfott R.B., Nakao M.T., Neumaier A., Rump S.M., Shary S.P. & van Hentenryck P. (2010). Standardized notation in interval analysis. Computational Technologies, 15(1), pp. 7–13. URL: http://www.ict.nsc.ru/jct/getfile.php?id=1345 [21.08.2026].
Kołodziej J., Jauernig K. & Cieślar A. (2006). HGSNash strategy as the decision-making method for water resource systems with external disagreement of interests. In: Proceedings of the Fifth International Conference on Parallel Computing in Electrical Engineering (PARELEC 2006), Białystok, Poland, September 13–17, 2006, pp. 313–318. Los Alamitos: IEEE Computer Society. DOI: http://doi.org/10.1109/PARELEC.2006.41.
Kubica B.J. (2012). A class of problems that can be solved using interval algorithms. Computing, 94(2–4), pp. 271–280. DOI: http://doi.org/10.1007/s00607-011-0173-9.
Kubica B.J. (2020). Interval methods for solving various kinds of quantified nonlinear problems. In: Kosheleva O., Shary S.P., Xiang G. & Zapatrin R. (Eds.), Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications. Studies in Computational Intelligence, 835, pp. 311–328. Cham: Springer. DOI: http://doi.org/10.1007/978-3-030-31041-7_17.
Kubica B.J. & Woźniak A. (2010). An interval method for seeking the Nash equilibria of non-cooperative games. In: Wyrzykowski R., Dongarra J., Karczewski K. & Waśniewski J. (Eds.), Parallel Processing and Applied Mathematics. PPAM 2009. Lecture Notes in Computer Science, 6068, pp. 446–455. Berlin–Heidelberg: Springer. DOI: http://doi.org/10.1007/978-3-642-14403-5_47.
Kubica B.J. & Woźniak A. (2012). Applying an interval method for a four agent economy analysis. In: Wyrzykowski R., Dongarra J., Karczewski K. & Waśniewski J. (Eds.), Parallel Processing and Applied Mathematics. PPAM 2011. Lecture Notes in Computer Science, 7204, pp. 477–483. Berlin–Heidelberg: Springer. DOI: http://doi.org/10.1007/978-3-642-31500-8_49.
Miettinen K. (1999). Nonlinear Multiobjective Optimization. International Series in Operations Research & Management Science, 12. Boston: Kluwer Academic Publishers. DOI: http://doi.org/10.1007/978-1-4615-5563-6.
Moore R.E., Kearfott R.B. & Cloud M.J. (2009). Introduction to Interval Analysis. Philadelphia: Society for Industrial and Applied Mathematics. DOI: http://doi.org/10.1137/1.9780898717716.
Nash J.F. Jr. (1950). Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1), pp. 48–49. DOI: http://doi.org/10.1073/pnas.36.1.48.
Nessah R. & Tian G. (2014). On the existence of strong Nash equilibria. Journal of Mathematical Analysis and Applications, 414(2), pp. 871–885. DOI: http://doi.org/10.1016/j.jmaa.2014.01.030.
OpenBLAS. (2013). OpenBLAS: An optimized BLAS library. URL: https://www.openmathlib.org/OpenBLAS/ [21.08.2026].
Rosenthal R.W. (1973). A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1), pp. 65–67. DOI: http://doi.org/10.1007/BF01737559.
Shary S.P. (2015). Konechnomernyy interval’nyy analiz [Finite-dimensional interval analysis]. Novosibirsk: Izdatel’stvo XYZ. URL: http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf [21.08.2026].
Ślepowrońska K. (1996). A parallel algorithm for finding Nash equilibria [Master’s Thesis]. Warsaw: Warsaw University of Technology, Institute of Control and Computation Engineering.
Steinhaus H. & Kuhn H.W. (1960). Definitions for a theory of games and pursuit. Naval Research Logistics Quarterly, 7(2), pp. 105–108. DOI: http://doi.org/10.1002/nav.3800070202.
