Hybrid global search algorithm with genetic blocks for solving hexamatrix games

Andrei V. Orlov

The Bulletin of Irkutsk State University. Series Mathematics, Tome 41 (2022), pp. 40-56

Résumé

This work addresses the development of a hybrid approach to solving three-person 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.

Détail

Keywords: polymatrix games of three players, Nash equilibrium, Global Search Theory, local search, level surface approximation, genetic algorithm.
Mots-clés : hexamatrix games

Bibliographie

[1] Audet C., Belhaiza S., Hansen P., “Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games”, J. Optim. Theory Appl., 129:3 (2006), 349–372 | DOI | MR | Zbl

[2] Belhaiza S., Computing Perfect Nash Equlibria for Polymatrix Games, Les Cahiers du GERAD G-2012-24, GERAD, Montreal, 2012 | MR

[3] Bonnans J.-F., Gilbert J. C., Lemarechal C., Sagastizabal C. A., Numerical optimization: theoretical and practical aspects, Springer, Berlin-Heidelberg, 2006 | MR | Zbl

[4] Eiben A. E., Smith J. E., Introduction to Evolutionary Computing, Springer, Berlin-Heidelberg, 2003 | MR | Zbl

[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, 265–272 | DOI

[6] Horst R., Tuy H., Global optimization. Deterministic approaches, Springer-Verlag, Berlin, 1993 | MR

[7] Mazalov V., Mathematical game theory and applications, John Wiley Sons, New York, 2014 | MR | Zbl

[8] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, New York, 1994 | MR

[9] Nocedal J., Wright S. J., Numerical optimization, Springer-Verlag, New York–Berlin–Heidelberg, 2000 | MR

[10] Orlov A. V., “Numerical solution of bilinear programming problems”, Comput. Math. Math. Phys., 48 (2008), 225–241 | DOI | MR | Zbl

[11] Orlov A. V., “Hybrid genetic global search algorithm for seeking optimistic solutions in bilevel optimization problems”, Bulletin of Buryat State University. Mathematics. Informatics, 9 (2013), 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, 507–512

[13] Orlov A. V., “The global search theory approach to the bilevel pricing problem in telecommunication networks”, Computational Aspects and Applications in Large Scale Networks, eds. Kalyagin V.A. et al., Springer, Cham, 2018, 57–73 | DOI | MR

[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, 11 (2015), 80–95 (in Russian) | Zbl

[15] Orlov A. V., Strekalovsky A. S., “Numerical search for equilibria in bimatrix games”, Comput. Math. Math. Phys., 45 (2005), 947–960 | MR | Zbl

[16] Orlov A. V., Strekalovsky A. S., “On a Local Search for Hexamatrix Games”, DOOR-SUP 2016, CEUR Workshop Proceedings, 1623, 2016, 477–488 | MR

[17] Orlov A. V., Strekalovsky A. S., Batbileg S., “On computational search for Nash equilibrium in hexamatrix games”, Optim. Lett., 10:2 (2016), 369–381 | DOI | MR | Zbl

[18] Owen G., Game Theory, Academic Press, San Diego, 1995 | MR | Zbl

[19] Pang J.-S., “Three modeling paradigms in mathematical programming”, Math. Program. Ser. B, 125:2 (2010), 297–323 | DOI | MR | Zbl

[20] Strekalovsky A. S., Elements of nonconvex optimization, Nauka Publ, Novosibirsk, 2003 (in Russian)

[21] Strekalovsky A. S., “On Solving Optimization Problems with Hidden Nonconvex Structures”, Optimization in Science and Engineering, eds. Rassias T.M., Floudas C.A., Butenko S., Springer, New-York, 2014, 465–502 | DOI | MR | Zbl

[22] Strekalovsky A. S., “On a Global Search in D.C. Optimization Problems”, Optimization and Applications, OPTIMA 2019, Communications in Computer and Information Science, 1145, eds. Jacimovic M., Khachay M., Malkova V., Posypkin M., Springer, Cham, 2020, 222–236 | DOI | MR | Zbl

[23] Strekalovsky A. S., Enkhbat R., “Polymatrix games and optimization problems”, Autom. Remote Control, 75:4 (2014), 632–645 | DOI | MR | Zbl

[24] Strekalovsky A. S., Orlov A. V., Bimatrix games and bilinear programming, Fizmatlit Publ, M., 2007 (in Russian) | Zbl

[25] Strekalovsky A. S., Orlov A. V., Linear and quadratic-linear problems of bilevel optimization, SB RAS Publ, Novosibirsk, 2019 (in Russian)

[26] Strekalovsky A. S., Orlov A. V., “Global Search for Bilevel Optimization with Quadratic Data”, Bilevel optimization: advances and next challenges, Springer Optimization and Its Applications, 161, eds. Dempe S., Zemkoho A., Springer, Cham, 2020, 313–334 | DOI | MR | Zbl

[27] Strongin R. G., Sergeyev Ya.D., Global optimization with non-convex constraints. Sequential and parallel algorithms, Springer-Verlag, New York, 2000 | MR

[28] Vasilyev I. L., Klimentova K. B., Orlov A. V., “A parallel search of equilibrium points in bimatrix games”, Numer. Methods Prog., 8:3 (2007), 233–243 (in Russian) (accessed 2022, June 28) https://en.num-meth.ru/index.php/journal/article/view/265