Рассматривается бескоалиционная игра двух лиц в нормальной форме с квадратичными функциями потерь игроков. Предполагается, что функция потерь каждого игрока является строго выпуклой квадратичной функцией собственной переменной. Зависимость потерь от переменной другого участника линейна и определяется соответствующим билинейным слагаемым. Задача поиска равновесия по Нэшу в рассматриваемой игре сводится к эквивалентной минимаксной задаче с помощью подхода Никайдо – Исода. Поскольку для данной игры не удаётся аналитически решить «внутреннюю» задачу максимизации, то полученная минимаксная задача представляется как задача минимизации невыпуклой неявно заданной функции на множестве ситуаций игры. «Внутренняя» задача максимизации, являющаяся выпуклой, заменяется двойственной по Лагранжу задачей, благодаря чему целевая функция исходной задачи оптимизации представляется в виде разности двух выпуклых функций (осуществляется d.c.-разложение), при этом функция, определяющая вогнутую часть разложения, по-прежнему задана неявно. В работе предлагается естественный способ линеаризации вогнутого слагаемого и, на основе этого, применение итеративного метода локального поиска для d.c.-функций. В данном методе очередная точка выбирается как решение выпуклой задачи оптимизации, в которой целевая функция получается из исходной целевой функции путём линеаризации вогнутого слагаемого в d.c.-разложении. В силу невыпуклости рассматриваемой нами задачи, предлагается использовать локальный поиск в сочетании с мультистартом. Известно, что минимальное значение целевой функции равно нулю и множество точек, где оно достигается, совпадает с множеством равновесий в исходной игре, благодаря чему можно легко проверить, является ли полученная локальным спуском стационарная точка равновесием по Нэшу. Приводятся результаты численного тестирования локального поиска для d.c.-функций и его сравнение с рядом существующих методов поиска равновесия на случайно сгенерированных задачах.

MSC

90C33

1. Антипин А. С. Градиентный и экстраградиентный подходы в билинейном равновесном программировании / А. С. Антипин. – М. : ВЦ им. А. А. Дородницына РАН, 2002. – 130 с.

2. Антипин А. С. Равновесное программирование: методы градиентного типа / А. С. Антипин // Автоматика и телемеханика. – 1997. – № 8. – С. 125–137.

3. Зуховицкий С. И. Вогнутые игры многих лиц / С. И. Зуховицкий, Р. А. Поляк, М. Е. Примак // Экономика и мат. методы. – 1971. – Т. 7, № 6. – С. 888–900.

4. Стрекаловский А. С. Биматричные игры и билинейное программирование / А. С. Стрекаловский, А. В. Орлов. – М. : Физматлит, 2007. – 224 с.

5. Dreves A. Finding All Solutions of Affine Generalized Nash Equilibrium Problems with One-dimensional Strategy Sets / A. Dreves // Math Meth Oper Res. – 2014. – Vol. 80. – P. 139–159.

6. Flam S. D. Finding Normalized Equilibrium in Convex–Concave Games / S. D. Flam, A. Ruszczynski // International Game Theory Review. – 2008. – Vol. 10, N 1. – P. 37–51.

7. Garg J. Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses / J. Garg, A. X. Jiang, R. Mehta // Lecture Notes in Computer Science. Internet and Network Economics. – 2011. – N 7090. – P. 399–407.

8. A. von Heusinger A. Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search / A. von Heusinger, C. Kanzow // J. Optim. Theory Appl. – 2009. – N 143. – P. 159–183.

9. Krawczyk J. Numerical Solutions to Coupled–Constraint (or Generalized Nash) Equilibrium Problems / J. Krawczyk // CMS. – 2007. – Vol. 4. – P. 183–204.

10. Krawczyk J. Relaxation Algorithms to Find Nash Equilibria with Economic Applications / J. Krawczyk, S. Uryasev // Environmental Modeling and Assessment. – 2000. – Vol. 5. – P. 63–73.

11. Mangasarian O. L. Equilibrium Points of Bimatrix Games / O. L. Mangasarian // Journal of the Society for Industrial and Applied Mathematics. – 1964. – Vol. 12. – P. 778–780.

12. Mills H. Equilibrium Points in Finite Games / H. Mills // Journal of the Society for Industrial and Applied Mathematics. – 1960. – Vol. 8, N 2. – P. 397–402.

13. Nikaido H. Note on Noncooperative Convex Games / H. Nikaido, K. Isoda // Pacific Journal of Mathematics. – 1955. – Vol. 5, N 5. – P. 807–815.

14. Quint T. A Theorem on the Number of Nash Equilibriua in a Bimatrix Game / T. Quint, M. Shubik // International Journal of Game Theory. – 1997. – N 26. – P. 353–359.

15. Rosen J. B. Existence and Uniqueness of Equilibrium Points for Concave N-Person Games / J. B. Rosen // Econometrica. – 1965. – Vol. 33, N 3. — P. 520–534.

16. Schiro D. A. On the Solution of Affine Generalized Nash Equilibrium Problems with Shared Constraints by Lemke’s Method / D. A. Schiro, J.-S. Pang, U. V. Shanbhag // Math. Program., Ser. A. – 2013. – Vol. 142. – P. 1–46.

17. Strekalovskiy A. S. Polymatrix Games and Optimization Problems / A. S. Strekalovskiy, R. Enkhbat // Automation and Remote Control. – 2014. – Vol. 75, N 4. – P. 632–645.

18. Strekalovskiy A. S. On Local Search in D.C. Optimization Problems / A. S. Strekalovsky // Applied Mathematics and Computation. – 2015. – N 255. – P. 73–83.