On solving generalized Nash equilibrium problems via optimization. (English) Zbl 1187.91011

Panicucci, Barbara; Pappalardo, Massimo; Passacantando, Mauro

Optim. Lett. 3, No. 3, 419-435 (2009).

Summary: This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido-Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.

MSC:

91A10	Noncooperative games
91A06	\(n\)-person games, \(n>2\)
90C30	Nonlinear programming

Keywords:

generalized Nash equilibrium problem; Nikaido-Isoda function; descent method

References:

[1]	Aubin J.P., Ekeland I.: Applied Nonlinear Analysis. Wiley, New York (1984) · Zbl 0641.47066
[2]	Auslender A.: Optimization. Méthodes Numériques. Masson, Paris (1976)
[3]	Cavazzuti E., Pappalardo M., Passacantando M.: Nash equilibria, variational inequalities, and dynamical systems. J. Optim. Theory Appl. 114, 491–506 (2002) · Zbl 1020.49003
[4]	Facchinei F., Fisher A., Piccialli V.: On generalized Nash games and variational inequalities. Oper. Res. Lett. 35, 159–164 (2007) · Zbl 1303.91020
[5]	Facchinei F., Kanzow C.: Generalized Nash equilibrium problems. 4OR 5, 173–210 (2007) · Zbl 1211.91162
[6]	Harker P.T.: Generalized Nash games and quasi-variational inequalities. Euro. J. Oper. Res. 54, 81–94 (1991) · Zbl 0754.90070
[7]	Nikaido H., Isoda K.: Note on non-cooperative convex games. Pac. J. Math. 5, 807–815 (1955) · Zbl 0171.40903
[8]	Panicucci, B., Pappalardo, M., Passacantando, M.: A globally convergent descent method for nonsmooth variational inequalities. Comput. Optim. Appl. (2007). doi: 10.1007/s10589-007-9132-y · Zbl 1170.90458
[9]	Solodov M.V., Tseng P.: Some methods based on the D-gap function for solving monotone variational inequalities. Comput. Optim. Appl. 17, 255–277 (2000) · Zbl 1168.49303
[10]	Uryasev S., Rubinstein R.Y.: On relaxation algorithms in computation of noncooperative equilibria. IEEE Trans. Automat. Contr. 39, 1263–1267 (1994) · Zbl 0811.90117
[11]	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
[12]	von Heusinger, A., Kanzow, C.: Relaxation methods for generalized Nash equilibrium problem with inexact line search. Preprint 282, Institute of Mathematics, University of Würzburg, Würzburg, February (2008) · Zbl 1182.91024
[13]	Zhu D.L., Marcotte P.: Modified descent methods for solving the monotone variational inequality problem. Oper. Res. Lett. 14, 111–120 (1993) · Zbl 0795.49011