рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2022. Том 41

Гибридный алгоритм глобального поиска с генетическими блоками для решения гексаматричных игр

Автор(ы)
А. В. Орлов1

1Институт динамики систем и теории управления им. В. М. Матросова СО РАН, Иркутск, Российская Федерация

Аннотация
Статья посвящена разработке гибридного подхода к решению полиматричных игр трех лиц (гексаматричных игр). С одной стороны, этот подход базируется на редукции игры к задаче невыпуклой оптимизации и Теории глобального поиска, созданной А. С. Стрекаловским для решения невыпуклых оптимизационных задач с (d.c.) функциями, представимыми в виде разности двух выпуклых функций. С другой стороны, для повышения эффективности одного из ключевых этапов глобального поиска — конструирования аппроксимации поверхности уровня выпуклой функции, задающей базовую невыпуклость в исследуемой задаче — используются операторы генетического алгоритма. Приведены результаты первого вычислительного эксперимента.
Об авторах
Орлов Андрей Васильевич, канд. физ.-мат. наук, доц., Институт динамики систем и теории управления им. В. М. Матросова СО РАН, Российская Федерация, 664033, г. Иркутск, anor@icc.ru
Ссылка для цитирования
Orlov A. V. Hybrid Global Search Algorithm with Genetic Blocks for Solving Hexamatrix Games // Известия Иркутского государственного университета. Серия Математика. 2022. Т. 41. C. 40–56. https://doi.org/10.26516/1997-7670.2022.41.40
Ключевые слова
полиматричные игры трех лиц, гексаматричные игры, равновесие Нэша, теория глобального поиска, локальный поиск, аппроксимация поверхности уровня, генетический алгоритм
УДК
519.853.4
MSC
90C26
DOI
https://doi.org/10.26516/1997-7670.2022.41.40
Литература
  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)

Полная версия (english)