О поиске равновесия по Нэшу в квазивогнутых квадратичных играх

О поиске равновесия по Нэшу в квазивогнутых квадратичных играх

Минарченко И. М.
Дискретный анализ и исследование операций, 30, 1, 67–84 (2023)
Скачать статью

УДК 519.833.2
DOI: 10.33048/daio.2023.30.754

Аннотация:

Рассматривается задача поиска равновесия по Нэшу в играх с невогнутыми квадратичными функциями выигрыша. Анализируются условия, при которых функции выигрыша квазивогнуты по собственным переменным на соответствующих множествах стратегий, что гарантирует существование равновесной точки. Одним из таких условий, принимаемым в качестве основного предположения в данной работе, является наличие ровно одного положительного собственного числа у матриц целевых функций игроков. Предложен алгоритм поиска равновесия, который либо сходится к равновесной точке, либо показывает, что игра не имеет таковых. Показано, что для квазивогнутых игр часть этапов алгоритма значительно упрощается. Работа алгоритма продемонстрирована на примерах небольшой размерности. 
Ил. 1, библиогр. 30.

Литература:
  1. Васильев Н. С. О вычислении равновесия по Нэшу в квадратичных играх // Вопросы кибернетики. Вып. 154. Вычислительные вопросы анализа больших систем. М.: Науч. совет по комплекс. пробл. «Кибернетика» АН СССР, 1989. С. 64–69.
     
  2. Антипин А. С. Градиентный и экстраградиентный подходы в билинейном равновесном программировании. М.: Вычисл. центр им. А. А. Дородницына РАН, 2002. 130 с.
     
  3. Schiro D. A., Pang J.-S., Shanbhag U. V. On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method // Math. Program. Ser. A. 2013. V. 142. P. 1–46.
     
  4. Dreves A. Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets // Math. Methods Oper. Res. 2014. V. 80, No. 2. P. 139–159.
     
  5. Haurie A., Krawczyk J. B. Optimal charges on river effluent from lumped and distributed sources // Environ. Model. Assess. 1997. V. 2, No. 3. P. 177–189.
     
  6. Yin H., Shanbhag U. V., Mehta P. G. Nash equilibrium problems with scaled congestion costs and shared constraints // IEEE Trans. Autom. Control. 2011. V. 56, No. 7. P. 1702–1708.
     
  7. Hobbs B. F., Pang J.-S. Nash–Cournot equilibria in electric power markets with piecewise linear demand functions and joint constraints // Oper. Res. 2007. V. 55, No. 1. P. 113–127.
     
  8. Von Heusinger A., Kanzow C. Relaxation methods for generalized Nash equilibrium problems with inexact line search // J. Optim. Theory Appl. 2009. V. 143, No. 1. P. 159–183.
     
  9. Dreves A., von Heusinger A., Kanzow C., Fukushima M. A globalized Newton method for the computation of normalized Nash equilibria // J. Glob. Optim. 2013. V. 56, No. 2. P. 327–340.
     
  10. Rosen J. B. Existence and uniqueness of equilibrium points for concave $n$-person games // Econometrica. 1965. V. 33, No. 3. P. 520–534.
     
  11. Антипин А. С. Равновесное программирование: методы градиентного типа // Автоматика и телемеханика. 1997. № 8. С. 125–137.
     
  12. Зуховицкий С. И., Поляк Р. А., Примак М. Е. Вогнутые игры многих лиц // Экономика и мат. методы. 1971. Т. 7, № 6. С. 888–900.
     
  13. Minarchenko I. M. Search of Nash equilibrium in quadratic $n$-person game // Discrete optimization and operations research. Proc. 9th Int. Conf. (Vladivostok, Russia, Sept. 19–23, 2016). Cham: Springer, 2016. P. 509–521. (Lect. Notes Comput. Sci.; V. 9869).
     
  14. Kakutani S. A generalization of Brouwer’s fixed point theorem // Duke Math. J. 1941. V. 8, No. 3. P. 457–459.
     
  15. Kim W. K., Lee K. H. The existence of Nash equilibrium in $n$-person games with $C$-concavity // Comput. Math. Appl. 2002. V. 44, No. 8. P. 1219–1228.
     
  16. Yen L. H., Muu L. D. A parallel subgradient projection algorithm for quasiconvex equilibrium problems under the intersection of convex sets // Optimization. 2022. V. 71, No. 15. P. 4447–4462.
     
  17. Cruz Neto J. X., Lopes J. O., Soares P. A. A minimization algorithm for equilibrium problems with polyhedral constraints // Optimization. 2016. V. 65, No. 5. P. 1061–1068.
     
  18. Boyd S., Vandenberghe L. Convex optimization. Cambridge: Camb. Univ. Press, 2004. 716 p.
     
  19. Mangasarian O. L. Pseudo-convex functions // J. SIAM Control. Ser. A. 1965. V. 3, No. 2. P. 281–290.
     
  20. Avriel M., Diewert W. E., Schaible S., Zang I. Generalized concavity. Philadelphia: SIAM, 2010. 342 p.
     
  21. Papadimitriou C. H. On the complexity of the parity argument and other inefficient proofs of existence // J. Comput. Syst. Sci. 1994. V. 48, No. 3. P. 498–532.
     
  22. Kiwiel K. C. Convergence and efficiency of subgradient methods for quasiconvex minimization // Math. Program. 2001. V. 90, No. 1. P. 1–25.
     
  23. Murray R., Swenson B., Kar S. Revisiting normalized gradient descent: Fast evasion of saddle points // IEEE Trans. Autom. Control. 2019. V. 64, No. 11. P. 4818–4824.
     
  24. Nikaidô H., Isoda K. Note on non-cooperative convex game // Pac. J. Math. 1955. V. 5, No. S1. P. 807–815.
     
  25. Khamisov O. V. A global optimization approach to solving equilibrium programming problems // Optimization and optimal control. Singapore: World Scientific, 2003. P. 155–164. (Ser. Comput. Oper. Res.; V. 1).
     
  26. Algorithmic game theory. Cambridge: Camb. Univ. Press, 2007. 754 p.
     
  27. Булатов В. П., Белых Т. И. Численные методы решения многоэкстремальных задач, связанных с обратными задачами математического программирования // Изв. вузов. Математика. 2007. № 6. С. 14–20.
     
  28. Minarchenko I. M., Khamisov O. V. On minimization of a quadratic function with one negative eigenvalue // Optim. Lett. 2021. V. 15, No. 4. P. 1447–1455.
     
  29. The advanced interactive multidimensional modeling system. Haarlem: AIMMS, 2022. 
    Available at aimms.com (accessed Jan. 13, 2023).
     
  30. IBM ILOG CPLEX optimization studio. Armonk: IBM, 2022. 
    Available at ibm.com/products/ilog-cplex-optimization-studio (accessed Jan. 13, 2023).

Исследование выполнено в рамках государственного задания по программе фундаментальных исследований РФ на 2021–2030 гг. (проект № FWEU–2021–0006 [АААА–А21–121012090034–3]).

Минарченко Илья Михайлович
  1. Институт систем энергетики им Л. А. Мелентьева СО РАН, 
    ул. Лермонтова, 130, 664033 Иркутск, Россия

E-mail: minar@isem.irk.ru

Статья поступила 29 сентября 2022 г.
После доработки — 29 сентября 2022 г.
Принята к публикации 6 октября 2022 г.

Abstract:

The Nash equilibrium problem with nonconcave quadratic payoff functions is considered. We analyze conditions which provide quasiconcavity of payoff functions in their own variables on the respective strategy sets and, consequently, guarantee existence of an equilibrium point. One of such conditions is that the matrix of every payoff function has exactly one positive eigenvalue; this condition is viewed as a basic assumption in the paper. We propose an algorithm that either converges to an equilibrium point or declares that the game has no equilibria. It is shown that some stages of the algorithm are noticeably simplified for quasiconcave games. The algorithm is tested on small-scale instances.
Illustr. 1, bibliogr. 30.

References:
  1. N. S. Vasil’ev, Computing Nash equilibrium in quadratic games, in Problems of Cybernetics, No. 154. (Computational Problems in Analysis of Large-Scale Systems) (Nauchn. Sovet Kompleks. Probl. «Kibernetika» AN SSSR, Moscow, 1989), pp. 64–69 [Russian].
     
  2. A. S. Antipin, Gradient and Extra-Gradient Approaches in Bilinear Equilibrium Programming (Vychisl. Tsentr Dorodnitsyn. RAN, Moscow, 2002) [Russian].
     
  3. D. A. Schiro, J.-S. Pang, and U. V. Shanbhag, On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method, Math. Program., Ser. A, 142, 1–46 (2013).
     
  4. A. Dreves, Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets, Math. Methods Oper. Res. 80 (2), 139–159 (2014).
     
  5. A. Haurie and J. B. Krawczyk, Optimal charges on river effluent from lumped and distributed sources, Environ. Model. Assess. 2 (3), 177–189 (1997).
     
  6. H. Yin, U. V. Shanbhag, and P. G. Mehta, Nash equilibrium problems with scaled congestion costs and shared constraints, IEEE Trans. Autom. Control 56 (7), 1702–1708 (2011).
     
  7. B. F. Hobbs and J.-S. Pang, Nash–Cournot equilibria in electric power markets with piecewise linear demand functions and joint constraints, Oper. Res. 55 (1), 113–127 (2007).
     
  8. A. von Heusinger and C. Kanzow, Relaxation methods for generalized Nash equilibrium problems with inexact line search, J. Optim. Theory Appl. 143 (1), 159–183 (2009).
     
  9. A. Dreves, A. von Heusinger, C. Kanzow, and M. Fukushima, A globalized Newton method for the computation of normalized Nash equilibria, J. Glob. Optim. 56 (2), 327–340 (2013).
     
  10. J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games, Econometrica 33 (3), 520–534 (1965).
     
  11. A. S. Antipin, Equilibrium programming: Gradient methods, Avtom. Telemekh., No. 8, 125–137 (1997) [Russian] [Autom. Remote Control 58 (8), Pt. 2, 1337–1347 (1997)].
     
  12. S. I. Zukhovitskii, R. A. Polyak, and M. E. Primak, Concave many-person games, Ekon. Mat. Metody 7 (6), 888–900 (1971) [Russian].
     
  13. I. M. Minarchenko, Search of Nash equilibrium in quadratic $n$-person game, in Discrete Optimization and Operations Research (Proc. 9th Int. Conf., Vladivostok, Russia, Sept. 19–23, 2016) (Springer, Cham, 2016), pp. 509–521. (Lect. Notes Comput. Sci., Vol. 9869).
     
  14. S. Kakutani, A generalization of Brouwer’s fixed point theorem, Duke Math. J. 8 (3), 457–459 (1941).
     
  15. W. K. Kim and K. H. Lee, The existence of Nash equilibrium in $n$-person games with $C$-concavity, Comput. Math. Appl. 44 (8), 1219–1228 (2002).
     
  16. L. H. Yen and L. D. Muu, A parallel subgradient projection algorithm for quasiconvex equilibrium problems under the intersection of convex sets, Optimization 71 (15), 4447–4462 (2022).
     
  17. J. X. Cruz Neto, J. O. Lopes, and P. A. Soares, A minimization algorithm for equilibrium problems with polyhedral constraints, Optimization 65 (5), 1061–1068 (2016).
     
  18. S. Boyd and L. Vandenberghe, Convex Optimization (Camb. Univ. Press, Cambridge, 2004).
     
  19. O. L. Mangasarian, Pseudo-convex functions, J. SIAM Control, Ser. A, 3 (2), 281–290 (1965).
     
  20. M. Avriel, W. E. Diewert, S. Schaible, and I. Zang, Generalized Concavity (SIAM, Philadelphia, 2010).
     
  21. C. H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. Syst. Sci. 48 (3), 498–532 (1994).
     
  22. K. C. Kiwiel, Convergence and efficiency of subgradient methods for quasiconvex minimization, Math. Program. 90 (1), 1–25 (2001).
     
  23. R. Murray, B. Swenson, and S. Kar, Revisiting normalized gradient descent: Fast evasion of saddle points, IEEE Trans. Autom. Control 64 (11), 4818–4824 (2019).
     
  24. H. Nikaidô and K. Isoda, Note on non-cooperative convex game, Pac. J. Math. 5 (S1), 807–815 (1955).
     
  25. O. V. Khamisov, A global optimization approach to solving equilibrium programming problems, in Optimization and Optimal Control (World Scientific, Singapore, 2003), pp. 155–164. (Ser. Comput. Oper. Res., Vol. 1).
     
  26. Algorithmic Game Theory (Camb. Univ. Press, Cambridge, 2007).
     
  27. V. P. Bulatov and T. I. Belykh, Numerical solution methods for multiextremal problems connected with inverse problems in mathematical programming, Izv. Vyssh. Uchebn. Zaved., Mat., No. 6, 14–20 (2007) [Russian] [Russ. Math. 51 (6), 11–17 (2007)].
     
  28. I. M. Minarchenko and O. V. Khamisov, On minimization of a quadratic function with one negative eigenvalue, Optim. Lett. 15 (4), 1447–1455 (2021).
     
  29. The Advanced Interactive Multidimensional Modeling System (AIMMS, Haarlem, 2022). 
    Available at aimms.com (accessed Jan. 13, 2023).
     
  30. IBM ILOG CPLEX Optimization Studio (IBM, Armonk, 2022).
    Available at ibm.com/products/ilog-cplex-optimization-studio (accessed Jan. 13, 2023).