Volume 30, No 1, 2023, P. 67-84

UDC 519.833.2
I. M. Minarchenko
On search of Nash equilibrium in quasiconcave quadratic games

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.

Keywords: Nash equilibrium, quasiconcave functions, global optimization.

DOI: 10.33048/daio.2023.30.754

Ilya M. Minarchenko ¹
1. Melentiev Energy Systems Institute SB RAS,
130 Lermontov Street, 664033 Irkutsk, Russia
e-mail: minar@isem.irk.ru

Received September 29, 2022
Revised September 29, 2022
Accepted October 6, 2022

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