Interval Methods for Computing Strong Nash Equilibria of Continuous Games

• Autorzy: Bartłomiej Jacek Kubica , Adam Woźniak
• Języki publikacji: EN

Abstrakty

EN

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. (original abstract)

Słowa kluczowe

EN

Game theory; Application of game theory; Algorithms

PL

Teoria gier; Zastosowanie teorii gier; Algorytmy

• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2015
• Tom: 9
• Numer: nr 1
• Strony: 63--78

Twórcy

autor

Bartłomiej Jacek Kubica

• Warsaw University of Technology

autor

Adam Woźniak

• Warsaw University of Technology

Bibliografia

• 1. Aumann, R.J., 1959. Acceptable points in general cooperative games. In: A.W. Tuckar, R.D. Luce (eds), Contributions to the Theory of Games IV, Princeton University Press.
• 2. C-XSC, 2013. C++ eXtended Scientific Computing library, http://www.xsc.de.
• 3. Gatti, N., Rocco, M., 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.
• 4. Hansen, E., Walster, W., 2004. Global Optimization Using Interval Analysis, Marcel Dekker, New York.
• 5. Holzman, R., Law-Yone, N., 1997. Strong equilibrium in congestion games. Games and Economic Behavior, 21(1), pp. 85-101.
• 6. Horacek, J., Hladik, M., 2013. Computing enclosures of overdetermined interval linear systems. Reliable Computing, 19(3), pp. 142-155.
• 7. Horacek, J., Hladik, M., 2014. Subsquares approach - a simple scheme for solving overdetermined interval linear systems. Lecture Notes in Computer Science, 8385, pp. 613-622. PPAM 2013 (10th International Conference on Parallel Processing and Applied Mathematics) Proceedings.
• 8. 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. Proceedings of KAEiOG'06, Murzasichle, pp. 171-178.
• 9. Jaulin, L., Kieffer, M., Didrit, O., Walter, E., 2001. Applied Interval Analysis. Springer, London.
• 10. Kearfott, R.B., 1996. Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht.
• 11. Kearfott, R.B., Nakao, M.T., Neumaier, A., Rump, S.M., Shary, S.P., van Hentenryck, P., 2010. Standardized notation in interval analysis. Vychislennyie tiehnologii (Computational technologies), 15(1) pp. 7-13.
• 12. Kołodziej, J., Jauernig, K., Cieslar, A., 2006. HGS-Nash strategy as the decision-making method for water resource systems with external disagreement of interests. Proceedings of PARELEC'06, Wrocław, pp. 313-318.
• 13. Kubica, B.J., 2012. A class of problems that can be solved using interval algorithms. Computing, 94, pp. 271-280. SCAN 2010 (14th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics) Proceedings.
• 14. Kubica, B.J., 2015. Interval methods for solving various kinds of quantified nonlinear problems. Lecture Notes in Computer Science. SCAN 2014 Proceedings, submitted.
• 15. Kubica, B.J., Wozniak, A., 2010. An interval method for seeking the Nash equilibria of non-cooperative games. Lecture Notes in Computer Science, 6068, pp. 446-455. PPAM 2009 Proceedings.
• 16. Kubica, B.J., Wozniak, A., 2012. Applying an interval method for a four agent economy analysis. Lecture Notes in Computer Science, 7204, pp. 477-483. PPAM 2011 (9th International Conference on Parallel Processing and Applied Mathematics) Proceedings.
• 17. Miettinen, K., 1999. Nonlinear multiobjective optimization, Vol. 12. Kluwer Academic Publishers, Dordrecht.
• 18. Moore, R.E., Kearfott, R.B., Cloud, M.J., 2009. Introduction to Interval Analysis. SIAM, Philadelphia.
• 19. Nash, J.F., 1950. Equilibrium points in n-person games. Proceedings of National Association of Science, 36, pp. 48-49.
• 20. Nessah, R., Tian, G., 2014. On the existence of strong Nash equilibria. Journal of Mathematical Analysis and Applications, 414(2), pp. 871-885.
• 21. OpenBLAS, 2013. OpenBLAS library, http://xianyi.github.com/OpenBLAS/.
• 22. Rosenthal, R.W., 1973. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1), pp. 65-67.
• 23. Sharyy, S.P., 2015. Konechnomernyy interval'nyy analiz [Finite-dimensional Interval Analysis], Izdatel'stvo XYZ, Novosibirsk. Electronic book: http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf (accessed 2014.05.15)
• 24. Slepowronska, K., 1996. A parallel algorithm for finding Nash equilibria. Master's thesis (in Polish) under supervision of A. Wozniak, ICCE WUT.
• 25. Steinhaus, H., 1960. Definitions for a theory of games and pursuit. Naval Research Logistics Quarterly, 7, pp. 105-107.

Identyfikatory

DOI

10.7494/dmms.2015.9.1.63