Том 30, номер 1, 2023 г., Стр. 67–84

УДК 519.833.2
Минарченко И. М.
О поиске равновесия по Нэшу в квазивогнутых квадратичных играх

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

Ключевые слова: равновесие по Нэшу, квазивогнутые функции, глобальная оптимизация.

DOI: 10.33048/daio.2023.30.754

Минарченко Илья Михайлович ¹
1. Институт систем энергетики им Л. А. Мелентьева СО РАН,
ул. Лермонтова, 130, 664033 Иркутск, Россия
е-mail: minar@isem.irk.ru

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

Литература

[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).

© И. М. Минарченко, 2023