Abstract
We consider the generalized Nash equilibrium problem (GNEP), in which each player’s strategy set may depend on the rivals’ strategies through shared constraints. A practical approach to solving this problem that has received increasing attention lately entails solving a related variational inequality (VI). From the viewpoint of game theory, it is important to find as many GNEs as possible, if not all of them. We propose two types of parametrized VIs related to the GNEP, one price-directed and the other resource-directed. We show that these parametrized VIs inherit the monotonicity properties of the original VI and, under mild constraint qualifications, their solutions yield all GNEs. We propose strategies to sample in the parameter spaces and show, through numerical experiments on benchmark examples, that the GNEs found by the parametrized VI approaches are widely distributed over the GNE set.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22, 265–290 (1954)
Bertsekas, D.P.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003) (In collaboration with Nedić, A., Ozdaglar, A.E.)
Bremner, D., Fukuda, K., Marzetta, A.: Primal-dual methods for vertex and facet enumeration. Discrete Comput. Geom. 20, 333–357 (1998)
Contreras, J., Klusch, M., Krawczyk, J.B.: Numerical solutions to Nash-Cournot equilibria in coupled constraint electricity markets. IEEE Trans. Power Syst. 19, 195–206 (2004)
Dontchev, A.L., Rockafellar, R.T.: Robinson’s implicit function theorem and its extensions. Math. Program. 117, 129–147 (2008)
Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. 4OR 5, 173–210 (2007)
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
Facchinei, F., Pang, J.-S.: Exact penalty functions for generalized Nash problems. In: DiPillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization, pp. 15–126. Springer, Heidelberg (2006)
Facchinei, F., Fischer, A., Piccialli, V.: On generalized Nash games and variational inequalities. Oper. Res. Lett. 35, 159–164 (2007)
Facchinei, F., Fischer, A., Piccialli, V.: Generalized Nash equilibrium problems and Newton methods. Math. Program. 117, 163–194 (2008)
Ferris, M.C., Munson, T.S.: Complementarity problems in GAMS and the PATH solver. J. Econ. Dyn. Control 24, 165–188 (2000) ftp://ftp.cs.wisc.edu/math-prog/solvers/path/matlab
Fukushima, M.: Restricted generalized Nash equilibria and controlled penalty algorithm. Comput. Manag. Sci. (2009, to appear)
Harker, P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54, 81–94 (1991)
Harker, P.T., Pang, J.-S.: Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math. Program. 48, 161–220 (1990)
Hobbs, B.F.: Linear complementarity models of Nash-Cournot competition in bilateral and POOLCO power market. IEEE Trans. Power Syst. 16, 194–202 (2001)
Janin, R.: Directional derivative of the marginal function in nonlinear programming. Math. Program. Stud. 21, 110–126 (1984)
Josephy, N.H.: Newton’s method for generalized equations and the PIES energy model. Ph.D. Dissertation, Department of Industrial Engineering, University of Wisconsin-Madison (1979)
Krawczyk, J.B.: Numerical solutions to coupled-constraint (or generalized Nash) equilibrium problems. Comput. Manag. Sci. 4, 183–204 (2007)
Krawczyk, J.B., Uryasev, S.: Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assess. 5, 63–73 (2000)
Luo, Z.Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
Nikaido, H., Isoda, K.: Note on noncooperative convex games. Pac. J. Math. 5, 807–815 (1955)
Outrata, J.V., Zowe, Z.: A Newton method for a class of quasi-variational inequalities. Comput. Optim. Appl. 4, 5–21 (1995)
Pang, J.-S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21–56 (2005). Erratum. Comput. Manag. Sci. (to appear). DOI:10.1007/s10287-009-0093-8
Robinson, S.M.: Shadow prices for measures of effectiveness. I: Linear model. Oper. Res. 41, 518–535 (1993)
Robinson, S.M.: Shadow prices for measures of effectiveness. II: General model. Oper. Res. 41, 536–548 (1993)
Robinson, S.M.: Solution continuity in monotone affine variational inequalities. SIAM J. Optim. 18, 1046–1060 (2007)
Rockafellar, R.T.: Lagrange multipliers and optimality. SIAM Rev. 35, 183–238 (1993)
Rosen, J.B.: Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33, 520–534 (1965)
Uryasev, S., Rubinstein, R.Y.: On relaxation algorithms in computation of noncooperative equilibria. IEEE Trans. Autom. Control 39, 1263–1267 (1994)
Varian, H.R.: Microeconomic Analysis. Norton, New York (1992)
von Heusinger, A., Kanzow, C.: Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions. Comput. Optim. Appl. (2009). DOI:10.1007/s10589-007-9145-6
Wei, J.-Y., Smeers, Y.: Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices. Oper. Res. 47, 102–112 (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported in part by Grant-in-Aid for Scientific Research from Japan Society for the Promotion of Science, and by National Science Foundation grant DMS-0511283.
Rights and permissions
About this article
Cite this article
Nabetani, K., Tseng, P. & Fukushima, M. Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints. Comput Optim Appl 48, 423–452 (2011). https://doi.org/10.1007/s10589-009-9256-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-009-9256-3