Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions. (English) Zbl 1170.90495

von Heusinger, Anna; Kanzow, Christian

Comput. Optim. Appl. 43, No. 3, 353-377 (2009).

Summary: We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.

MSC:

90C30	Nonlinear programming
91A10	Noncooperative games

Keywords:

generalized Nash equilibria; normalized Nash equilibria; joint constraints; regularized Nikaido-Isoda-function; constrained optimization reformulation; unconstrained optimization reformulation

References:

[1]	Adida, E., Perakis, G.: Dynamic pricing and inventory control: uncertainty and competition. Part B: an algorithm for the normalized Nash equilibrium. Operations Research Center, Sloan School of Management, MIT, Technical Report (December 2005) · Zbl 1233.90006
[2]	Adida, E., Perakis, G.: Dynamic pricing and inventory control: uncertainty and competition. Part A: existence of Nash equilibrium. Operations Research Center, Sloan School of Management, MIT, Technical Report (January 2006) · Zbl 1134.90002
[3]	Başar, T.: Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria. J. Econ. Dyn. Control 11, 531–549 (1987) · Zbl 0646.90100
[4]	Barzilai, J., Borwein, J.M.: Two point step size gradient method. IMA J. Numer. Anal. 8, 141–148 (1988) · Zbl 0638.65055
[5]	Bensoussan, A.: Points de Nash dans le cas de fonctionelles quadratiques et jeux differentiels lineaires a N personnes. SIAM J. Control 12, 460–499 (1974) · Zbl 0286.90066
[6]	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)
[7]	Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002) · Zbl 1002.65069
[8]	Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003) · Zbl 1062.90002
[9]	Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II. Springer, New York (2003) · Zbl 1062.90002
[10]	Facchinei, F., Fischer, A., Piccialli, V.: On generalized Nash games and variational inequalities. Oper. Res. Lett. 35, 159–164 (2007) · Zbl 1303.91020
[11]	Facchinei, F., Fischer, A., Piccialli, V.: Generalized Nash equilibrium problems and Newton methods. Math. Program. Ser. B (2007). doi: 10.1007/s10107-007-0160-2 · Zbl 1166.90015
[12]	Flåm, S.D., Antipin, A.S.: Equilibrium programming using proximal-like algorithms. Math. Program. 78, 29–41 (1997) · Zbl 0890.90150
[13]	Flåm, S.D., Ruszczyński, A.: Noncooperative convex games: computing equilibria by partial regularization. IIASA, Laxenburg, Austria, Working Paper 94-42 (May 1994)
[14]	Fletcher, R.: On the Barzilai-Borwein method. Department of Mathematics, University of Dundee, Dundee, United Kingdom, Numerical Analysis Report NA/207 (2001) · Zbl 1118.90318
[15]	Fukushima, M.: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99–110 (1992) · Zbl 0756.90081
[16]	Grippo, L., Sciandrone, M.: Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Comput. Optim. Appl. 23, 143–169 (2002) · Zbl 1028.90061
[17]	Gürkan, G., Pang, J.-S.: Approximations of Nash equilibria. Math. Program. Ser. B (2007). doi: 10.1007/s10107-007-0156-y · Zbl 1216.91003
[18]	Harker, P.T.: Generalized Nash games and quasivariational inequalities. Eur. J. Oper. Res. 54, 81–94 (1991) · Zbl 0754.90070
[19]	Hobbs, B.F.: Linear complementarity models of Nash-Cournot competition in bilateral and POOLCO power markets. IEEE Trans. Power Syst. 16, 194–202 (2001)
[20]	Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973) · Zbl 0256.90042
[21]	Kanzow, C., Fukushima, M.: Theoretical and numerical investigation of the D-gap function for box constrained variational inequalities. Math. Program. 83, 55–87 (1998) · Zbl 0920.90134
[22]	Kesselman, A., Leonardi, S., Bonifaci, V.: Game-theoretic analysis of Internet switching with selfish users. In: Lecture Notes in Computer Science, vol. 3828, pp. 236–245 (2005)
[23]	Krawczyk, J.B.: Coupled constraint Nash equilibria in environmental games. Resour. Energy Econ. 27, 157–181 (2005)
[24]	Krawczyk, J.B., Uryasev, S.: Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assess. 5, 63–73 (2000)
[25]	Li, S., Başar, T.: Distributed algorithms for the computation of noncooperative equilibria. Automatica 23, 523–533 (1987) · Zbl 0619.90092
[26]	Mastroeni, G.: Gap functions for equilibrium problems. J. Global Optim. 27, 411–426 (2003) · Zbl 1061.90112
[27]	Nikaido, H., Isoda, K.: Note on noncooperative convex games. Pac. J. Math. 5, 807–815 (1955) · Zbl 0171.40903
[28]	Pang, J.-S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21–56 (2005) · Zbl 1115.90059
[29]	Pang, J.-S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993) · Zbl 0784.90082
[30]	Peng, J.-M.: Equivalence of variational inequality problems to unconstrained optimization. Math. Program. 78, 347–356 (1997) · Zbl 0887.90171
[31]	Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993) · Zbl 0776.65037
[32]	Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090
[33]	Raydan, M.: On the Barzilai and Borwein choice of the steplength for the gradient method. IMA J. Numer. Anal. 13, 321–326 (1993) · Zbl 0778.65045
[34]	Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997) · Zbl 0898.90119
[35]	Rosen, J.B.: Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33, 520–534 (1965) · Zbl 0142.17603
[36]	Uryasev, S., Rubinstein, R.Y.: On relaxation algorithms in computation of noncooperative equilibria. IEEE Trans. Autom. Control 39, 1263–1267 (1994) · Zbl 0811.90117
[37]	Yamashita, N., Taji, K., Fukushima, M.: Unconstrained optimization reformulations of variational inequality problems. J. Optim. Theory Appl. 92, 439–456 (1997) · Zbl 0879.90180
[38]	Zhang, L., Han, J.: Unconstrained optimization reformulation of equilibrium problems. Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, China, Technical Report (2006)