Список выпусков > Серия «Математика». 2017. Том 20
Вычислительный метод для игр с ненулевой суммой для N-лиц
Рассматривается игра с ненулевой суммой для N-игроков. Хорошо известно, что игра может быть сведена к глобальной задаче оптимизации [5 7 14]. Обобщая результаты, полученные Миллсом [5], мы имеем условия глобальной оптимальности для равновесия по Нэшу. Для отыскания равновесий по Нэшу в построенной игре используется подход, базирующийся на ее редукции к невыпуклой задаче оптимизации для решения последней применяется алгоритм глобального поиска, мы применяем Curvilinear Multistart Algorithm [2 3], специально модифицированный для нашей редуцированной задачи невыпуклой оптимизации. Предложенный алгоритм протестирован на играх с тремя и четырьмя игроками. Кроме того, мы рассматривали маркетинговую задачу соревнования по ценам трех компаний на хлебном рынке Улан-Батора. Приводятся и анализируются результаты вычислительного эксперимента.
1. Strekalovsky A.S. Global Optimality Conditions for Nonconvex Optimization. Journal of Global Optimization, 1998, vol. 12, pp. 415-434.
2. Enkhbat R., Tungalag N., Gornov A., Anikin A. The Curvilinear Search Algorithm for Solving Three-Person Game. Proc. DOOR 2016. CEUR-WS, 2016, vol. 1623. p. 574-583. URL: http://ceur-ws.org/Vol-1623/paperme4.pdf.
3. Gornov A., Zarodnyuk T. Computing technology for estimation of convexity degree of the multiextremal function. Machine learning and data analysis, 2014, vol. 10, no 1, pp. 1345-1353. URL: http://jmlda.org
4. Mangasarian O.L., Stone H. Two-Person Nonzero Games and Quadratic Programming. J. Mathemat. Anal. Appl., 1964, vol. 9, pp. 348-355.
5. Mills H. Equilibrium Points in Finite Games. J. Soc. Indust. Appl. Mathemat., 1960, vol. 8, no 2, pp. 397-402.
6. Von Neumann J., Morgenstern O. Theory of games and economic behavior. Princeton University Press, 1944.
7. Melvin Dresher (1981) The Mathematics of Games of Strategy. Dover Publications.
8. Vorobyev N.N. Noncooperative games. Moscow, Nauka Publ., 1984.
9. Germeyer YU.B. Introduction to Operation Reseach. Moscow, Nauka Publ., 1976.
10. Strekalovsky A.S., Orlov A.V. Bimatrix Game and Bilinear Programming. Moscow, Nauka Publ., 2007.
11. Owen G. Game Theory. Saunders, Philadelphia, 1971.
12. Gibbons R. Game Theory for Applied Economists. Princeton University Press., 1992.
13. Horst R., Tuy H. Global Optimization. Springer-Verlag, 1993.
14. Howson J.T. Equilibria of Polymatrix Games. Management Sci., 1972, vol. 18, pp. 312-318.
15. Strekalovsky A.S., Enkhbat R. Polymatrix games and optimization problems. Automation and Remote Control, 2014, vol. 75, no 4, pp. 632-645.
16. Orlov A.V., Strekalovsky A.S.,Batbileg S. On computational search for Nash equilibrium in hexamatrix games. Optimization Letters, 2014, vol. 10, no 2, pp. 369-381.
17. Problem 3.4. https://www.dropbox.com/s/137aaahvbniau9q/problem_4_data.txt.