Abstract
The generalized Nash equilibrium problem, where the feasible sets of the players may depend on the other players’ strategies, is emerging as an important modeling tool. However, its use is limited by its great analytical complexity. We consider several Newton methods, analyze their features and compare their range of applicability. We illustrate in detail the results obtained by applying them to a model for internet switching.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arrow K.J., Debreu G. (1954). Existence of an equilibrium for a competitive economy. Econometrica 22: 265–290
Başar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory, 2nd edn. Academic, London/New York (1989). (Reprinted in SIAM Series “Classics in Applied Mathematics, 1999)
Bensoussan A. (1974). Points de Nash dans le cas de fonctionnelles quadratiques et jeux differentiels lineaires a N personnes. SIAM J. Control 12: 460–499
Berridge, S., Krawczyk, J.B.: Relaxation algorithms in finding Nash equilibria. Economic working papers archives (1997), http://econwpa.wustl.edu/eprints/comp/papers/9707/9707002.abs
Cardell J.B., Cullen Hitt C., Hogan W.W. (1997). Market power and strategic interaction in electricity networks. Resour. Energy Econ. 19: 109–137
Chen, Y., Hobbs, B.F., Leyffer, S., Munson, T.S.: Leader-Follower Equilibria for Electric Power and NO x Allowances Markets. Preprint ANL/MCS-P1191-0804 (2004), Mathematics and Computer Science Division, Argonne National Laboratory, Argonne (2004)
Christensen P.W. (2002). A semi-smooth Newton method for elasto-plastic contact problems. Int. J. Solids Struct. 39: 2323–2341
Contreras J., Klusch M.K., Krawczyk J.B. (2004). Numerical solution to Nash-Cournot equilibria in coupled constraints electricity markets. IEEE T. Power Syst. 19: 195–206
De Luca T., Facchinei F., Kanzow C. (2000). A theoretical and numerical comparison of some semismooth algorithms for complementarity problems. Comput. Optim. Appl. 16: 173–205
Facchinei F., Fischer A., Kanzow C. (1998). On the accurate identification of active constraints. SIAM J. Optim. 8: 14–32
Facchinei F., Fischer A., Piccialli V. (2007). On generalized Nash games and variational inequalities. Oper. Res. Lett. 35: 159–164
Facchinei F., Kanzow C. (1997). A nonsmooth inexact Newton method for the solution of large-scalenonlinear complementarity problems. Math. Program. 76: 195–206
Facchinei F., Pang J.-S. (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York
Facchinei F., Pang and J.-S. (2006). Exact penalty functions for generalized Nash problems. In: Di Pillo, G., Roma, M. (eds) Large-scale nonlinear optimization, pp 115–126. Springer, Heidelberg
Fan J., Yuan Y. (2005). On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption. Computing 74: 23–39
Fischer A. (2002). Local behavior of an iterative framework for generalized equations with nonisolated solutions. Math. Program. 94: 91–124
Fukushima M., Pang J.-S. (2005). Quasi-variational inequalities, generalized Nash equilibria and multi-leader-follower games. Comput. Manage. Sci. 2: 21–56
Harker P.T. (1991). Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54: 81–94
Josephy, N.H.: Newton’s method for generalized equations. Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin, Madison (1979)
Kesselman, A., Leonardi, S., Bonifaci, V.: Game-Theoretic Analysis of Internet Switching with Selfish Users. In: Proceedings of the First International Workshop on Internet and Network Economics, WINE 2005. Lectures Notes in Computer Science, vol. 3828, pp 236–245
Krawczyk J.B., Uryasev S. (2000). Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assess. 5: 63–73
McKenzie L.W. (1959). On the existence of a general equilibrium for a competitive market. Econometrica 27: 54–71
Munson T.S., Facchinei F., Ferris M.C., Fischer A., Kanzow C. (2001). The semismooth algorithm for large scale complementarity problems. INFORMS J. Comput. 13: 294–311
Nikaido H., Isoda K. (1955). Note on noncooperative convex games. Pac. J. Math. 5: 807–815
Outrata J., Kočvara M., Zowe J. (1998). Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer, Dordrecht
Pang, J.-S.: Computing Generalized Nash Equilibria. Math. Program (2002) (submitted)
Robinson S.M. (1983). Generalized equations. In: Bachem, A., Grötschel, M., Korte, B. (eds) Mathematical Programming: The State of the Art, pp 346–367. Springer, Berlin
Robinson S.M. (1993). Shadow prices for measures of effectiveness. I.Linear Model Oper. Res. 41: 518–535
Robinson S.M. (1993). Shadow prices for measures of effectiveness. II. General Model Oper. Res. 41: 536–548
Rosen J.B. (1965). Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33: 520–534
Uryasev S., Rubinstein R.Y. (1994). On relaxation algorithms in computation of noncooperative equilibria. IEEE T Automat. Control 3: 1263–1267
Yamashita N., Fukushima M. (2001). On the rate of convergence of the Levenberg-Marquardt method. Computing 15(Suppl.): 239–249
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Stephen M. Robinson on the occasion of his 65th birthday, in honor of his fundamental contributions to mathematical programming.
The work of the first and third authors has been partially supported by MIUR-PRIN 2005 Research Program n.2005017083 “Innovative Problems and Methods in Nonlinear Optimization”.
Rights and permissions
About this article
Cite this article
Facchinei, F., Fischer, A. & Piccialli, V. Generalized Nash equilibrium problems and Newton methods. Math. Program. 117, 163–194 (2009). https://doi.org/10.1007/s10107-007-0160-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0160-2
Keywords
- Generalized Nash equilibrium
- Semismooth Newton method
- Levenberg–Marquardt method
- Nonisolated solution
- Internet switching