zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Gap function approach to the generalized Nash equilibrium problem. (English) Zbl 1188.91021
Summary: We consider an optimization reformulation approach for the generalized Nash equilibrium problem (GNEP) that uses the regularized gap function of a quasi-variational inequality (QVI). The regularized gap function for QVI is in general not differentiable, but only directionally differentiable. Moreover, a simple condition has yet to be established, under which any stationary point of the regularized gap function solves the QVI. We tackle these issues for the GNEP in which the shared constraints are given by linear equalities, while the individual constraints are given by convex inequalities. First, we formulate the minimization problem involving the regularized gap function and show the equivalence to GNEP. Next, we establish the differentiability of the regularized gap function and show that any stationary point of the minimization problem solves the original GNEP under some suitable assumptions. Then, by using a barrier technique, we propose an algorithm that sequentially solves minimization problems obtained from GNEPs with the shared equality constraints only. Further, we discuss the case of shared inequality constraints and present an algorithm that utilizes the transformation of the inequality constraints to equality constraints by means of slack variables. We present some results of numerical experiments to illustrate the proposed approach.

91A10Noncooperative games
91A06$n$-person games, $n>2$
90C33Complementarity and equilibrium problems; variational inequalities (finite dimensions)
Full Text: DOI
[1] Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. 4OR: Q. J. Oper. Res. 5, 173--210 (2007) · Zbl 1211.91162 · doi:10.1007/s10288-007-0054-4
[2] Hobbs, B.F., Pang, J.S.: Nash-Cournot equilibrium in electric power markets with piecewise linear demand functions and joint constraints. Oper. Res. 55, 113--127 (2007) · Zbl 1167.91356 · doi:10.1287/opre.1060.0342
[3] 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. 6, 373--375 (2009) · Zbl 1115.90059 · doi:10.1007/s10287-004-0010-0
[4] Haurie, A., Krawczyk, J.B.: Optimal charges on river effluent from lumped and distributed sources. Environ. Model. Assess. 2, 93--106 (1997)
[5] Krawczyk, J.B.: Coupled constraint Nash equilibria in environmental games. Resource Energy Econ. 27, 157--181 (2005) · doi:10.1016/j.reseneeco.2004.08.001
[6] Krawczyk, J.B., Uryasev, S.: Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assess. 5, 63--73 (2000) · doi:10.1023/A:1019097208499
[7] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[8] Harker, P.T.: A variational inequality approach for the determination of oligopolistic market equilibrium. Math. Program. 30, 105--111 (1984) · Zbl 0559.90015 · doi:10.1007/BF02591802
[9] 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) · Zbl 0734.90098 · doi:10.1007/BF01582255
[10] Facchinei, F., Pang, J.S.: Exact penalty functions for generalized Nash problems. In: Di Pillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization, pp. 115--126. Springer, Heidelberg (2006) · Zbl 1201.91006
[11] Fukushima, M.: Restricted generalized Nash equilibria and controlled penalty algorithm. Comput. Manag. Sci. (to appear) · Zbl 1253.91010
[12] Rosen, J.B.: Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33, 520--534 (1965) · Zbl 0142.17603 · doi:10.2307/1911749
[13] Facchinei, F., Fischer, A., Piccialli, P.: Generalized Nash equilibrium problems and Newton methods. Math. Program. 117, 163--194 (2009) · Zbl 1166.90015 · doi:10.1007/s10107-007-0160-2
[14] von Heusinger, A., Kanzow, C., Fukushima, M.: Newton’s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation. Technical Report 2009-006, Department of Applied Mathematics and Physics, Kyoto University (2009) · Zbl 1237.91021
[15] Nabetani, K., Tseng, P., Fukushima, M.: Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints. Comput. Optim. Appl. (to appear) · Zbl 1220.90136
[16] von Heusinger, A., Kanzow, C.: Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions. Comput. Optim. Appl. 43, 353--377 (2009) · Zbl 1170.90495 · doi:10.1007/s10589-007-9145-6
[17] Harker, P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54, 81--94 (1991) · Zbl 0754.90070 · doi:10.1016/0377-2217(91)90325-P
[18] Bensoussan, A.: Points de Nash dans le cas de fontionnelles quadratiques et jeux differentiels linéaires a n personnes. SIAM J. Control 12, 460--499 (1974) · Zbl 0286.90066 · doi:10.1137/0312037
[19] Fukushima, M.: A class of gap functions for quasi-variational inequality problems. J. Ind. Manag. Optim. 3, 165--171 (2007) · Zbl 1170.90487
[20] Fukushima, M.: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99--110 (1992) · Zbl 0756.90081 · doi:10.1007/BF01585696
[21] Auslender, A.: Optimisation: Méthodes Numériques. Masson, Paris (1976)
[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. Springer, Berlin (2005)