On search of Nash equilibrium in~quasiconcave~quadratic games

I. M. Minarchenko

Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 1, pp. 67-84.

Résumé

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.

Détail

Keywords: Nash equilibrium, quasiconcave functions, global optimization.

Bibliographie

[1] N. S. Vasil'ev, “Computing Nash equilibrium in quadratic games”, Computational Problems in Analysis of Large-Scale Systems, Problems of Cybernetics, 154, Nauchn. Sovet Kompleks. Probl. «Kibernetika» AN SSSR, M., 1989, 64–69 (Russian)

[2] A. S. Antipin, Gradient and Extra-Gradient Approaches in Bilinear Equilibrium Programming, Vychisl. Tsentr Dorodnitsyn. RAN, M., 2002 (Russian)

[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, 142 (2013), 1–46 | DOI | MR | Zbl

[4] Dreves A., “Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets”, Math. Methods Oper. Res., 80:2 (2014), 139–159 | DOI | MR | Zbl

[5] Haurie A., Krawczyk J. B., “Optimal charges on river effluent from lumped and distributed sources”, Environ. Model. Assess, 2:3 (1997), 177–189 | DOI

[6] Yin H., Shanbhag U. V., Mehta P. G., “Nash equilibrium problems with scaled congestion costs and shared constraints”, IEEE Trans. Autom. Control, 56:7 (2011), 1702–1708 | DOI | MR | Zbl

[7] Hobbs B. F., Pang J.-S., “Nash–Cournot equilibria in electric power markets with piecewise linear demand functions and joint constraints”, Oper. Res., 55:1 (2007), 113–127 | DOI | MR | Zbl

[8] Von Heusinger A., Kanzow C., “Relaxation methods for generalized Nash equilibrium problems with inexact line search”, J. Optim. Theory Appl., 143:1 (2009), 159–183 | DOI | MR | Zbl

[9] Dreves A., von Heusinger A., Kanzow C., Fukushima M., “A globalized Newton method for the computation of normalized Nash equilibria”, J. Glob. Optim., 56:2 (2013), 327–340 | DOI | MR | Zbl

[10] Rosen J. B., “Existence and uniqueness of equilibrium points for concave $n$-person games”, Econometrica, 33:3 (1965), 520–534 | DOI | MR | Zbl

[11] A. S. Antipin, “Equilibrium programming: Gradient methods”, Autom. Remote Control, 58:8 (1337), 1337–1347 | MR | Zbl

[12] S. I. Zukhovitskii, R. A. Polyak, and M. E. Primak, “Concave many-person games”, Ekon. Mat. Metody, 7:6 (1971), 888–900 (Russian) | MR

[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), Lect. Notes Comput. Sci., 9869, Springer, Cham, 2016, 509–521 | DOI | MR | Zbl

[14] Kakutani S., “A generalization of Brouwer's fixed point theorem”, Duke Math. J., 8:3 (1941), 457–459 | DOI | MR | Zbl

[15] Kim W. K., Lee K. H., “The existence of Nash equilibrium in $n$-person games with $C$-concavity”, Comput. Math. Appl., 44:8 (2002), 1219–1228 | DOI | MR | Zbl

[16] Yen L. H., Muu L. D., “A parallel subgradient projection algorithm for quasiconvex equilibrium problems under the intersection of convex sets”, Optimization, 71:15 (2022), 4447–4462 | DOI | MR

[17] Cruz Neto J. X., Lopes J. O., Soares P. A., “A minimization algorithm for equilibrium problems with polyhedral constraints”, Optimization, 65:5 (2016), 1061–1068 | DOI | MR | Zbl

[18] Boyd S., Vandenberghe L., Convex optimization, Camb. Univ. Press, Cambridge, 2004, 716 pp. | MR | Zbl

[19] Mangasarian O. L., “Pseudo-convex functions”, J. SIAM Control. Ser. A, 3:2 (1965), 281–290 | MR | Zbl

[20] Avriel M., Diewert W. E., Schaible S., Zang I., Generalized concavity, SIAM, Philadelphia, 2010, 342 pp. | MR | Zbl

[21] Papadimitriou C. H., “On the complexity of the parity argument and other inefficient proofs of existence”, J. Comput. Syst. Sci., 48:3 (1994), 498–532 | DOI | MR | Zbl

[22] Kiwiel K. C., “Convergence and efficiency of subgradient methods for quasiconvex minimization”, Math. Program., 90:1 (2001), 1–25 | DOI | MR | Zbl

[23] Murray R., Swenson B., Kar S., “Revisiting normalized gradient descent: Fast evasion of saddle points”, IEEE Trans. Autom. Control, 64:11 (2019), 4818–4824 | DOI | MR | Zbl

[24] Nikaidô H., Isoda K., “Note on non-cooperative convex game”, Pac. J. Math., 5:S1 (1955), 807–815 | DOI | MR

[25] Khamisov O. V., “A global optimization approach to solving equilibrium programming problems”, Optimization and optimal control, Ser. Comput. Oper. Res., 1, World Scientific, Singapore, 2003, 155–164 | MR | Zbl

[26] Algorithmic game theory, Camb. Univ. Press, Cambridge, 2007, 754 pp. | Zbl

[27] V. P. Bulatov and T. I. Belykh, “Numerical solution methods for multi-extremal problems connected with inverse problems in mathematical programming”, Russ. Math., 51:6 (2007), 11–17 | DOI | MR | Zbl

[28] Minarchenko I. M., Khamisov O. V., “On minimization of a quadratic function with one negative eigenvalue”, Optim. Lett., 15:4 (2021), 1447–1455 | DOI | MR

[29] The advanced interactive multidimensional modeling system, AIMMS, Haarlem, 2022 (accessed Jan. 13, 2023) aimms.com

[30] IBM ILOG CPLEX optimization studio, IBM, Armonk, 2022 (accessed Jan. 13, 2023) ibm.com/products/ilog-cplex-optimization-studio