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

«Известия Иркутского государственного университета»

Журнал ИГУ

Список выпусков > Серия «Математика» . 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.

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