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
- 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
- Belhaiza S. Computing Perfect Nash Equlibria for Polymatrix Games. Les Cahiers du GERAD G-2012-24. Montreal, GERAD,2012.
- Bonnans J.-F., Gilbert J.C., Lemarechal C., Sagastizabal C.A. Numerical optimization: theoretical and practical aspects,. Springer, Berlin-Heidelberg, 2006.
- Eiben A.E., Smith J.E. Introduction to Evolutionary Computing. Springer, Berlin-Heidelberg, 2003.
- 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
- Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin, Springer-Verlag, 1993.
- Mazalov V. Mathematical game theory and applications. New York, John Wiley & Sons, 2014.
- Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. New York, Springer-Verlag, 1994.
- Nocedal J., Wright S.J. Numerical optimization. Springer-Verlag, New York-Berlin- Heidelberg, 2000.
- 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
- 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).
- 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.
- 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
- 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)
- Orlov A.V., Strekalovsky A.S. Numerical search for equilibria in bimatrix games. Comput. Math. Math. Phys., 2005, vol. 45, pp. 947–960.
- 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.
- 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
- Owen G. Game Theory. San Diego, Academic Press, 1995.
- 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
- Strekalovsky A.S. Elements of nonconvex optimization. Novosibirsk, Nauka Publ., 2003. (in Russian)
- 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
- 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
- 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
- Strekalovsky A.S., Orlov A.V. Bimatrix games and bilinear programming. Moscow, Fizmatlit Publ., 2007. (in Russian)
- Strekalovsky A.S., Orlov A.V. Linear and quadratic-linear problems of bilevel optimization. Novosibirsk, SB RAS Publ., 2019. (in Russian)
- 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
- Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. New York, Springer-Verlag, 2000.
- 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)