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 an approach to rigorously verify the existence of equilibria in certain points. A proper algorithm is presented. We formulate and prove propositions, giving us features that 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 considered, also, and numerical results are presented. As a particular example, we consider the game of "misanthropic individuals", a game (invented by the frst 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 games, in A. W. Tuckar and R. D. Luce (Eds), Contributions to the Theory of Games IV, Princeton University Press.
C-XSC (2013). C++ eXtended Scientific Computing library, http://www.xsc.de.
Gatti, N., Rocco, M. and Sandholm, T. (2013). On the verification and computation of strong Nash equilibrium, Proceedings of 2013 international conference on Autonomous agents and multi-user systems, International Foundation for Autonomous Agents and Multiagent Systems.
Hansen, E. and Walster, W. (2004). Global Optimization Using Interval Analysis, Marcel Dekker, New York.
Holzman, R. and Law-Yone, N. (1997). Strong equilibrium in congestion games, Games and economic behavior 21(1): 85-101.
Horacek, J. and Hladik, M. (2013). Computing enclosures of overdetermined interval linear systems, Reliable Computing 19(3): 142-155.
Horacek, J. and Hladik, M. (2014). Subsquares approach - a simple scheme for solving overdetermined interval linear systems, Lecture Notes in Computer Science 8385: 613-622. PPAM 2013 (10th International Conference on Parallel Processing and Applied Mathematics) Proceedings.
Jauernig, K., Kołodziej, J. and Stysło, M. (2006). HGSNash evolutionary strategy as an effective method of detecting the Nash equilibria in n-person non-cooperative games, Proceedings of KAEiOG'06, Murzasichle, pp. 171-178.
Jaulin, L., Kieffer, M., Didrit, O. and Walter, E. (2001). Applied Interval Analysis, Springer, London.
Kearfott, R. B. (1996). Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht.
Kearfott, R. B., Nakao, M. T., Neumaier, A., Rump, S. M., Shary, S. P. and van Hentenryck, P. (2010). Standardized notation in interval analysis, Vychislennyie tiehnologii (Computational technologies) 15(1): 7-13.
Kołodziej, J., Jauernig, K. and Cieślar, A. (2006). HGSNash strategy as the decision making method for water resource systems with external disagreement of interests, Proceedings of PARELEC'06, Wrocław, pp. 313-318.
Kubica, B. J. (2012). A class of problems that can be solved using interval algorithms, Computing 94: 271-280. SCAN 2010 (14th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics) Proceedings.
Kubica, B. J. (2015). Interval methods for solving various kinds of quantified nonlinear problems, Lecture Notes in Computer Science . SCAN 2014 Proceedings, submitted.
Kubica, B. J. and Woźniak, A. (2010). An interval method for seeking the Nash equilibria of non-cooperative games, Lecture Notes in Computer Science 6068: 446-455. PPAM 2009 Proceedings.
Kubica, B. J. and Woźniak, A. (2012). Applying an interval method for a four agent economy analysis, Lecture Notes in Computer Science 7204: 477-483. PPAM 2011 (9th International Conference on Parallel Processing and Applied Mathematics) Proceedings.
Miettinen, K. (1999). Nonlinear multiobjective optimization, Vol. 12, Kluwer Academic Publishers, Dordrecht.
Moore, R. E., Kearfott, R. B. and Cloud, M. J. (2009). Introduction to Interval Analysis, SIAM, Philadelphia.
Nash, J. F. (1950). Equilibrium points in n-person games, Proceedings of National Association of Science 36: 48-49.
Nessah, R. and Tian, G. (2014). On the existence of strong Nash equilibria, Journal of Mathematical Analysis and Applications 414(2): 871-885.
OpenBLAS (2013). OpenBLAS library, http://xianyi.github.com/OpenBLAS/.
Rosenthal, R. W. (1973). A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory 2(1): 65-67.
Shary, S. P. (2013). Finite-dimensional Interval Analysis, XYZ. electronic book (in Russian), http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf (accessed 2014.05.15).
Ślepowrońska, K. (1996). A parallel algorithm for finding Nash equilibria. Master's thesis (in Polish) under supervision of A. Woźniak, ICCE WUT.
Steinhaus, H. (1960). Definitions for a theory of games and pursuit, Naval Research Logistics Quarterly 7: 105-107.
Downloads
Published
How to Cite
Issue
Section
License
Remeber to prepeare, sign and scan copyright statement
The content of the journal is freely available according to the Creative Commons License Attribution 4.0 International (CC BY 4.0)
Accepted 2015-07-15
Published 2016-02-17
