Triangles of conflicts and hexamatrix games

Andrey V. Orlov

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 16 (2024) no. 4, pp. 69-94.

Résumé

The paper addresses one class of finite non-cooperative games (with finite numbers of strategies for each player) – Polymatrix Games of E.B. Yanovskaya. Namely, we study in detail the 3-players Polymatrix Games, the so-called Hexamatrix Games (HMG), which can be completely described by six matrices. A number of model examples of 3-sides real-life conflicts are presented and formulated as HMG. The possibility of using hexamatrix games to model economic relationships between three participants is demonstrated. To find a Nash Equilibrium in the formulated games, we use an optimization approach, when the problem is transformed into a nonconvex optimization problem with a bilinear structure. The latter is solved by the A.S. Strekalovsky’s Global Search Theory (GST) for (d.c.) optimization problems with objective functions represented as the difference of two convex functions.

Détail

Keywords: finite noncooperative games, Nash equilibrium, nonconvex optimization problems, local and global search algorithms, computational experiment.
Mots-clés : polymatrix games, hexamatrix game

Bibliographie

[1] Aleksei Savvateev, Teoriya igr. Lektsiya 2, https://www.youtube.com/watch?v=PoTvQ4MH7-s

[2] Aleksei Savvateev, Teoriya igr. Lektsiya 12, https://www.youtube.com/watch?v=ww8tgO0F6ww

[3] Bazara M., Shetti K., Nelineinoe programmirovanie. Teoriya i algoritmy, Mir, M., 1982

[4] Vasilev I.L., Klimentova K.B., Orlov A.V., “Parallelnyi globalnyi poisk ravnovesnykh situatsii v bimatrichnykh igrakh”, Vychislitelnye metody i programmirovanie, 8:2 (2007), 84–94 | MR

[5] Vasin A.A., Morozov V.V., Teoriya igr i modeli matematicheskoi ekonomiki, MAKS Press, M., 2005

[6] Golshtein E.G., Malkov U.Kh., Sokolov N.A., “Gibridnyi metod poiska resheniya bimatrichnykh igr”, Ekonomika i matematicheskie metody, 54:2 (2018), 89–103

[7] Orlov A.V., “Chislennoe issledovanie gibridnogo algoritma globalnogo poiska v geksamatrichnykh igrakh”, Vestnik Buryatskogo gosudarstvennogo universiteta. Matematika, informatika, 2023, no. 2, 14–29

[8] Orlov A.V., Batbileg S., “Oligopolisticheskii bankovskii sektor Mongolii i polimatrichnye igry trekh lits”, Izvestiya Irkutskogo gosudarstvennogo universiteta. Ser. Matematika, 11 (2015), 80–95 | Zbl

[9] Orlov A.V., Strekalovskii A.S., “O chislennom poiske situatsii ravnovesiya v bimatrichnykh igrakh”, Zhurn. vychisl. matem. i matem. fiziki, 45:6 (2005), 981–995

[10] Neiman Dzh., Fon Morgenshtern O., Teoriya igr i ekonomicheskoe povedenie, Nauka, M., 1970 | MR

[11] Partkhasaratkhi T., Ragkhavan T., Nekotorye voprosy teorii igr dvukh lits, Mir, M., 1974

[12] Petrosyan L.A., Zenkevich N.A., Semina E.A., Teoriya igr, Vysshaya shkola, M., 1998

[13] Sokolov N.P., Prostranstvennye matritsy i ikh prilozheniya, Fizmatlit, M., 1960

[14] Strekalovskii A.S., Elementy nevypukloi optimizatsii, Nauka, Novosibirsk, 2003

[15] Strekalovskii A.S., “Minimiziruyuschie posledovatelnosti v zadache DC optimizatsii s ogranicheniyami”, Trudy Instituta matematiki i mekhaniki UrO RAN, 29, no. 3, 2023, 185–209 | Zbl

[16] Strekalovskii A.S., Orlov A.V., Bimatrichnye igry i bilineinoe programmirovanie, Fizmatlit, M., 2007

[17] Strekalovskii A.S., Enkhbat R., “Polimatrichnye igry i zadachi optimizatsii”, Avtomatika i telemekhanika, 2014, no. 4, 51–66 | MR | Zbl

[18] Yanovskaya E.B., “Situatsii ravnovesiya v polimatrichnykh igrakh”, Litovskii matematicheskii sbornik, 8 (1968), 381–384 | MR | Zbl

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

[20] Batbileg S., Enkhbat R., “Global Optimization Approach to Game Theory”, J. of Mongolian Mathematical Society, 14 (2010), 2–11 | MR

[21] Batbileg S., Enkhbat R., “Global Optimization Approach to Nonzero Sum n Person Game”, Advanced Modeling and Optimization, 13:1 (2011), 59–66 | MR | Zbl

[22] Batbileg S., Tungalag N., Anikin A., Gornov A., Finkelstein E., “A global optimization algorithm for solving a four-person game”, Optimization Letters, 13 (2019), 587–596 | DOI | MR | Zbl

[23] Enkhbat R., Batbileg S., Anikin A., Tungalag N., Gornov A., “A Note on Solving 5-Person Game”, The Electronic International Journal of Advanced Modeling and Optimization, 19:2 (2017), 227–232 | Zbl

[24] Enkhbat R., Batbileg S., Tungalag N., Anikin A., Gornov A., “A Global Optimization Approach to Nonzero Sum Six-Person Game”, Frontiers in Games and Dynamic Games, 16, eds. D. Yeung, S. Luckraz, C. Leong, Birkhauser, Cham, 2020, 219–227 | DOI | MR | Zbl

[25] Enkhbat R., Tungalag N., Anikin A., Gornov A., “A Computational Method for Solving N-Person Game”, The Bulletin of Irkutsk State University. Series Mathematics, 20 (2017), 109–121 | DOI | MR | Zbl

[26] Enkhbat R., Tungalag N., Gornov A., Anikin A., “The Curvilinear Search Algorithm for Solving Three-Person Game”, DOOR-SUP 2016, CEUR Workshop Proceedings, 1623, eds. A. Kononov et al., 2016, 574–583

[27] Golshteyn E., Malkov U., Sokolov N., “Comparison of the Hybrid and Lemke-Howson Methods for Solving Bimatrix Games”, OPTIMA 2017 Conference, CEUR Workshop Proceedings, 1987, eds. Yu.G. Evtushenko et al., 2017, 224–232

[28] Golshteyn E., Malkov U., Sokolov N., “The Lemke-Howson Algorithm Solving Finite Non-Cooperative Three-Person Games in a Special Setting”, DEStech Transactions on Computer Science and Engineering, 2019, Suppl. vol., 265–272

[29] Kudryavtsev K., Malkov U., Zhukovskiy V., “Weak Berge Equilibrium”, MOTOR 2020, Communications in Computer and Information Science, eds. Y. Kochetov, I. Bykadorov, T. Gruzdeva, Springer, Cham, 2020, 231–243 | DOI | MR | Zbl

[30] Lemke C.E., Howson J.J., “Equilibrium points of bimatrix games”, Journal of the Society for Industrial and Applied Mathematics, 12 (1964), 413–423 | DOI | MR | Zbl

[31] Malkov U., Malkova V., “Effectiveness of Nash Equilibrium Search Algorithms in Four-Person Games in General and Multi-matrix Settings”, OPTIMA 2020, Communications in Computer and Information Science, 1340, eds. N.N. Olenev et al., Springer, Cham, 2020, 198–208 | DOI | MR | Zbl

[32] Mazalov V., Mathematical Game Theory and Applications, John Wiley Sons, 2014 | MR | Zbl

[33] Mills H., “Equilibrium points in finite games”, Journal of the Society for Industrial and Applied Mathematics, 8:2 (1960), 397–402 | DOI | MR | Zbl

[34] Orlov A.V., “Finding the Nash equilibria in randomly generated hexamatrix games”, Proc. of the 14th Intern. Symposium on Operational Research, SOR'17 (Bled, Slovenia, September 27-29, 2017), eds. L. Zadnik Stirn et. al., Slovenian Society Informatika, Section for Operational Research, Ljubljana, 2017, 507–512

[35] Orlov A.V., “Hybrid Global Search Algorithm with Genetic Blocks for Solving Hexamatrix Games”, The Bulletin of Irkutsk State University. Series Mathematics, 41 (2022), 40–56 | DOI | MR | Zbl

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

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

[38] Pang J.-S., “Three modeling paradigms in mathematical programming”, Mathematical Programming. Ser. B, 124:2 (2010), 297–323 | DOI | MR

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

[40] Quintas L.G., “A Note on Polymatrix Games”, International Journal of Game Theory, 18 (1989), 261–272 | DOI | MR | Zbl