×

Some projection-like methods for the generalized Nash equilibria. (English) Zbl 1198.91026

Summary: A generalized Nash game is an \(m\)-person noncooperative game in which each player’s strategy depends on the rivals’ strategies. Based on a quasi-variational inequality formulation for the generalized Nash game, we present two projection-like methods for solving the generalized Nash equilibria in this paper. It is shown that under certain assumptions, these methods are globally convergent. Preliminary computational experience is also reported.

MSC:

91A10 Noncooperative games
91A06 \(n\)-person games, \(n>2\)
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22, 265–290 (1954) · Zbl 0055.38007
[2] Bensoussan, A.: Points de Nash dans le cas de fontionnelles quadratiques et jeux differentiels linĂ©aires a N persons. SIAM J. Control 12, 460–499 (1974) · Zbl 0286.90066
[3] Cash, J.: Solution set in a special case of generalized Nash equilibrium games. Kybernetika 37, 21–37 (2001)
[4] Cournot, A.A.: Researches into the Mathematical Principles of the Theory of Wealth. Macmillan, New York (1897) · JFM 28.0211.07
[5] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequality and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[6] Gafni, E.M., Bertsekas, D.P.: Two-metric projection problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99–110 (1984)
[7] Harker, P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54, 81–94 (1991) · Zbl 0754.90070
[8] Iusem, A.N.: An iterative algorithm for the variational inequality problem. Math. Appl. Comput. 13, 103–114 (1994) · Zbl 0811.65049
[9] Khobotov, E.N.: Modification of the extragradient method for solving variational inequalities and certain optimization problem. U.S.S.R. Comput. Math. Math. Phys. 17, 120–127 (1987) · Zbl 0665.90078
[10] Kocvara, M., Outrata, J.V.: On a class of quasi-variational inequalities. Optim. Methods Software 5, 275–295 (1995)
[11] Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Matecon 12, 747–756 (1976) · Zbl 0342.90044
[12] Marcotte, P.: Application of Khobotov’s algorithm to variational inequalities and network equilibrium problems. Inf. Syst. Oper. Res. 29, 258–270 (1991) · Zbl 0781.90086
[13] McKenzie, L.W.: On the existence of general equilibrium for a competitive market. Econometrica 27, 54–71 (1959) · Zbl 0095.34302
[14] Nash, J.F.: Equilibrium points in n-person games. Proc. Nat. Acad. Sci. U.S.A. 36, 48–49 (1950) · Zbl 0036.01104
[15] Nash, J.F.: Non-cooperative games. Ann. Math. 54, 286–295 (1951) · Zbl 0045.08202
[16] Outrata, J., Zowe, J.: A numerical approach to optimization problems with variational inequality constraints. Math. Program. 68, 105–130 (1995) · Zbl 0835.90093
[17] Pang, J.S.: Computing generalized Nash equilibria. Department of Mathematical sciences, The Johns Hopkins University (2002). Manuscript
[18] Pang, J.S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manage. Sci. 2, 21–56 (2005) · Zbl 1115.90059
[19] Robinson, S.M.: Shadow prices for measures of effectiveness. I. Linear Model. Oper. Res. 41, 518–535 (1993) · Zbl 0800.90666
[20] Robinson, S.M.: Shadow prices for measures of effectiveness. II. General Model. Oper. Res. 41, 536–548 (1993) · Zbl 0800.90667
[21] Sun, D.: An iterative method for solving variational inequality problems and complementarity problems. Numer. Math. J. Chin. Univ. 16, 145–153 (1994) · Zbl 0817.65048
[22] Toint, Ph.L.: Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space. IMA J. Numer. Anal. 8, 231–252 (1988) · Zbl 0698.65043
[23] von Heusinger, A., Kanzow, C.: Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions. Comput. Optim. Appl. (2007). doi: 10.1007/s10589-007-9145-6 · Zbl 1170.90495
[24] von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1944) · Zbl 0063.05930
[25] Wang, Y.J., Xiu, N.H., Wang, C.Y.: A new version of extragradient method for variational inequality problems. Comput. Math. Appl. 42, 969–979 (2001) · Zbl 0993.49005
[26] Wei, J.Y., Smeers, Y.: Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices. Oper. Res. 47, 102–112 (1999) · Zbl 1175.91080
[27] Xiu, N.H., Zhang, J.Z.: Some recent advances in projection-type methods for variational inequalities. J. Comput. Appl. Math. 152, 559–585 (2003) · Zbl 1018.65083
[28] Xiu, N.H., Wang, Y.J., Zhang, X.S.: Modified fixed-point equations and related iterative methods for variational inequalities. Comput. Math. Appl. 47, 913–920 (2004) · Zbl 1057.49013
[29] Zarantonello, E.H.: Projections on convex sets in Hilbert space and spectral theory. In: Zarantonello, E.H. (ed.) Contributions to Nonlinear Functional Analysis. Academic Press, New York (1971) · Zbl 0281.47043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.