BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Author
Kubica Bartłomiej Jacek (Warsaw University of Technology), Woźniak Adam (Warsaw University of Technology)
Title
Interval Methods for Computing Strong Nash Equilibria of Continuous Games
Source
Decision Making in Manufacturing and Services, 2015, vol. 9, nr 1, s. 63-78, bibliogr. 25 poz.
Keyword
Teoria gier, Zastosowanie teorii gier, Algorytmy
Game theory, Application of game theory, Algorithms
Note
summ.
Abstract
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)
Full text
Show
Bibliography
Show
  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.
Cited by
Show
ISSN
2300-7087
Language
eng
URI / DOI
http://dx.doi.org/10.7494/dmms.2015.9.1.63
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu