рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2022. Vol 41

Hybrid Global Search Algorithm with Genetic Blocks for Solving Hexamatrix Games

Author(s)
Andrei V. Orlov1

1Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russian Federation

Abstract
This work addresses the development of a hybrid approach to solving threeperson polymatrix games (hexamatrix games). On the one hand, this approach is based on the reduction of the game to a nonconvex optimization problem and the Global Search Theory proposed by A.S. Strekalovsky for solving nonconvex optimization problems with (d.c.) functions representable as a difference of two convex functions. On the other hand, to increase the efficiency of one of the key stages of the global search — constructing an approximation of the level surface of a convex function that generates the basic nonconvexity in the problem under study — operators of genetic algorithms are used. The results of the first computational experiment are presented.
About the Authors
Andrey V. Orlov, Cand. Sci. (Phys.–Math.), Assoc. Prof., Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, 664033, Russian Federation, anor@icc.ru
For citation
Orlov A. V. Hybrid Global Search Algorithm with Genetic Blocks for Solving Hexamatrix Games. The Bulletin of Irkutsk State University. Series Mathematics, 2022, vol. 41, pp. 40–56. https://doi.org/10.26516/1997-7670.2022.41.40
Keywords
polymatrix games of three players, hexamatrix games, Nash equilibrium, Global Search Theory, local search, level surface approximation, genetic algorithm
UDC
519.853.4
MSC
90C26
DOI
https://doi.org/10.26516/1997-7670.2022.41.40
References
  1. Audet C., Belhaiza S., Hansen P. Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games. J. Optim. Theory Appl., 2006, vol. 129, no. 3, pp. 349–372. https://doi.org/10.1007/s10957-006-9070-3
  2. Belhaiza S. Computing Perfect Nash Equlibria for Polymatrix Games. Les Cahiers du GERAD G-2012-24. Montreal, GERAD,2012.
  3. Bonnans J.-F., Gilbert J.C., Lemarechal C., Sagastizabal C.A. Numerical optimization: theoretical and practical aspects,. Springer, Berlin-Heidelberg, 2006.
  4. Eiben A.E., Smith J.E. Introduction to Evolutionary Computing. Springer, Berlin-Heidelberg, 2003.
  5. Golshteyn E., Malkov U., Sokolov N. The Lemke-Howson Algorithm Solving Finite Non-Cooperative Three-Person Games in a Special Setting. DEStech Trans. Comput. Sci. Eng. (optim), Supplementary volume, 2019, pp. 265–272.https://doi.org/10.12783/dtcse/optim2018/27938
  6. Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin, Springer-Verlag, 1993.
  7. Mazalov V. Mathematical game theory and applications. New York, John Wiley & Sons, 2014.
  8. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. New York, Springer-Verlag, 1994.
  9. Nocedal J., Wright S.J. Numerical optimization. Springer-Verlag, New York-Berlin- Heidelberg, 2000.
  10. Orlov A.V. Numerical solution of bilinear programming problems. Comput. Math. Math. Phys., 2008, vol. 48, pp. 225–241. https://doi.org/10.1134/S0965542508020061
  11. Orlov A.V. Hybrid genetic global search algorithm for seeking optimistic solutions in bilevel optimization problems. Bulletin of Buryat State University. Mathematics. Informatics., 2013, vol. 9, pp. 25–32 (in Russian).
  12. Orlov A.V. Finding the Nash equilibria in randomly generated hexamatrix games. Proceedings of the 14th International Symposium on Operational Research (SOR’17), Slovenia, Bled, September 27–29, 2017, Slovenian Society Informatika, Section for Operational Research, Ljubljana, 2017, pp. 507–512.
  13. Orlov A.V. The global search theory approach to the bilevel pricing problem in telecommunication networks. Kalyagin, V.A. et al. (Eds.) Computational Aspects and Applications in Large Scale Networks, Springer, Cham, 2018, pp. 57–73. https://doi.org/10.1007/978-3-319-96247-4_5
  14. Orlov A.V., Batbileg S. Oligopolistic banking sector of Mongolia and polymatrix games of three players. The Bulletin of Irkutsk State University. Series Mathematics, 2015, vol. 11, pp. 80–95. (in Russian)
  15. Orlov A.V., Strekalovsky A.S. Numerical search for equilibria in bimatrix games. Comput. Math. Math. Phys., 2005, vol. 45, pp. 947–960.
  16. Orlov A.V., Strekalovsky A.S. On a Local Search for Hexamatrix Games. CEUR Workshop Proceedings. DOOR-SUP 2016., 2016, vol. 1623, pp. 477–488.
  17. Orlov A.V., Strekalovsky A.S., Batbileg S. On computational search for Nash equilibrium in hexamatrix games. Optim. Lett., 2016, vol. 10, no. 2, pp. 369–381. https://doi.org/10.1007/s11590-014-0833-8
  18. Owen G. Game Theory. San Diego, Academic Press, 1995.
  19. Pang J.-S. Three modeling paradigms in mathematical programming. Math. Program.Ser.B., 2010, vol. 125, no. 2, pp. 297–323. https://doi.org/10.1007/s10107-010-0395-1
  20. Strekalovsky A.S. Elements of nonconvex optimization. Novosibirsk, Nauka Publ., 2003. (in Russian)
  21. Strekalovsky A.S. On Solving Optimization Problems with Hidden Nonconvex Structures. Rassias, T.M., Floudas, C.A., Butenko, S. (eds.) Optimization in Science and Engineering, New-York, Springer, 2014, pp. 465–502. https://doi.org/10.1007/978-1-4939-0808-0_23
  22. Strekalovsky A.S. On a Global Search in D.C. Optimization Problems. Jacimovic, M., Khachay, M., Malkova, V., Posypkin, M. (eds.) Optimization and Applications.OPTIMA 2019. Communications in Computer and Information Science, Springer, Cham, 2020, vol. 1145, pp. 222–236. https://doi.org/10.1007/978-3-030-38603-0_17
  23. Strekalovsky A.S., Enkhbat R. Polymatrix games and optimization problems. Autom. Remote Control, 2014, vol. 75, no. 4, pp. 632–645. https://doi.org/10.1134/S0005117914040043
  24. Strekalovsky A.S., Orlov A.V. Bimatrix games and bilinear programming. Moscow, Fizmatlit Publ., 2007. (in Russian)
  25. Strekalovsky A.S., Orlov A.V. Linear and quadratic-linear problems of bilevel optimization. Novosibirsk, SB RAS Publ., 2019. (in Russian)
  26. Strekalovsky A.S., Orlov A.V. Global Search for Bilevel Optimization with Quadratic Data. In: Dempe, S., Zemkoho, A. (eds.) Bilevel optimization: advances and next challenges, Springer Optimization and Its Applications, Springer, Cham, 2020, vol. 161, pp. 313–334. https://doi.org/10.1007/978-3-030-52119-6_11
  27. Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. New York, Springer-Verlag, 2000.
  28. Vasilyev I.L., Klimentova K.B., Orlov A.V. A parallel search of equilibrium points in bimatrix games. Numer. Methods Prog., 2007, vol. 8, no. 3, pp. 233–243. Available at: https://en.num-meth.ru/index.php/journal/article/view/265 https://en.num-meth.ru/index.php/journal/article/view/265. (accessed 2022, June 28). (in Russian)

Full text (english)