A barrier function method for generalized Nash equilibrium problems

Jian Hou; Liwei Zhang

doi:10.3934/jimo.2014.10.1091

Article Contents

2014, Volume 10, Issue 4: 1091-1108. Doi: 10.3934/jimo.2014.10.1091

This issue Previous Article A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs Next Article CVaR proxies for minimizing scenario-based Value-at-Risk

A barrier function method for generalized Nash equilibrium problems

Jian Hou^1, and
Liwei Zhang^2,

1.
Institute of ORCT, School of Mathematical Sciences, Dalian University of Technology, Dalian 116024
2.
Institute of ORCT, School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024

Received: January 2013

Revised: December 2013

Published: October 2014

Abstract Related Papers Cited by

Abstract

In this paper, we propose a barrier function method for the generalized Nash equilibrium problem (GNEP) which, in contrast to the standard Nash equilibrium problem (NEP), allows the constraints for each player may depend on the rivals' strategies. We solve a sequence of NEPs, which are defined by logarithmic barrier functions of the joint inequality constraints. We demonstrate, under suitable conditions, that any accumulation point of the solutions to the sequence of NEPs is a solution to the GNEP. Moreover, a semismooth Newton method is used to solve the NEPs and sufficient conditions for the local superlinear convergence rate of the semismooth Newton method are derived. Finally, numerical results are reported to illustrate that the barrier approach for solving the GNEP is practical.

Keywords:

Mathematics Subject Classification: Primary: 90C25, 90C30; Secondary: 49M15, 49M37.

Citation:

Related Papers

Cited by

References

[1]	M. Breton, G. Zaccour and M. Zahaf, A game-theoretic formulation of joint implementation of environmental projects, European J. Oper. Res., 168 (2006), 221-239.doi: 10.1016/j.ejor.2004.04.026.
[2]	F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley, New York, 1983.
[3]	J. Contreras, M. Klusch and J. B. Krawczyk, Numerical solutions to Nash-Cournot equilibria in coupled constraint electricity markets, IEEE. T. Power. Syst., 19 (2004), 195-206.doi: 10.1109/TPWRS.2003.820692.
[4]	G. Debreu, A social equilibrium existence theorem, Proc. Natl. Acad. Sci. U. S. A., 38 (1952), 886-893.doi: 10.1073/pnas.38.10.886.
[5]	F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, I, Springer-Verlag, New York, 2003.
[6]	F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol II, Springer-Verlag, New York, 2003.
[7]	F. Facchinei, A. Fischer and V. Piccialli, On generalized Nash games and variational inequalities, Oper. Res. Lett., 35 (2007), 159-164.doi: 10.1016/j.orl.2006.03.004.
[8]	F. Facchinei, A. Fischer and C. Kanzow, Regularity properties of a semismooth reformulation of variational inequalities, SIAM J. Optim., 8 (1998), 850-869.doi: 10.1137/S1052623496298194.
[9]	F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods, Math. Program., 117 (2009), 163-194.doi: 10.1007/s10107-007-0160-2.
[10]	M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm, Comput. Manag. Sci., 8 (2011), 201-218.doi: 10.1007/s10287-009-0097-4.
[11]	G. Gürkan and J. S. Pang, Approximations of Nash equilibria, Math. Program., 117 (2009), 223-253.doi: 10.1007/s10107-007-0156-y.
[12]	P. T. Harker, Generalized Nash games and quasi-variational inequalities, European J. Oper. Res., 54 (1991), 81-94.doi: 10.1016/0377-2217(91)90325-P.
[13]	A. V. Heusinger and C. Kanzow, Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions, Comput. Optim. Appl., 43 (2009), 353-377.doi: 10.1007/s10589-007-9145-6.
[14]	A. Kesselman, S. Leonardi and V. Bonifaci, Game-theoretic analysis of internet switching with selfish users, Theoret. Comput. Sci., 452 (2012), 107-116.doi: 10.1016/j.tcs.2012.05.029.
[15]	J. B. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications, Environ. Model. Assess., 5 (2000), 63-73.
[16]	T. D. Luca, F. Facchinei and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program., 75 (1996), 407-439.doi: 10.1007/BF02592192.
[17]	R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control. Optim., 15 (1977), 959-972.doi: 10.1137/0315061.
[18]	J. S. Pang, G. Scutari, F. Facchinei and C. Wang, Distributed power allocation with rate constraints in Gaussian parallel interference channels, IEEE Trans. Inform. Theory, 54 (2008), 3471-3489.doi: 10.1109/TIT.2008.926399.
[19]	J. S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Comput. Manag. Sci., 2 (2005), 21-56.doi: 10.1007/s10287-004-0010-0.
[20]	B. Panicucci, M. Pappalardo and M. Passacantando, On finite-dimensional generalized variational inequalities, J. Ind. Manag. Optim., 2 (2006), 43-53.doi: 10.3934/jimo.2006.2.43.
[21]	L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18 (1993), 227-244.doi: 10.1287/moor.18.1.227.
[22]	L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Program, 58 (1993), 353-367.doi: 10.1007/BF01581275.
[23]	S. M. Robinson, Shadow prices for measures of effectiveness, I: Linear model, Oper. Res., 41 (1993), 518-535.doi: 10.1287/opre.41.3.518.
[24]	S. M. Robinson, Shadow prices for measures of effectiveness, II: General model, Oper. Res., 41 (1993), 536-548.doi: 10.1287/opre.41.3.536.
[25]	R. T. Rockafellar and R. J. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998.doi: 10.1007/978-3-642-02431-3.
[26]	S. Uryasev and R. Y. Rubinstein, On relaxation algorithms in computation of noncooperative equilibria, IEEE Trans. Automat. Control., 39 (1994), 1263-1267.doi: 10.1109/9.293193.
[27]	J. Y. Wei and Y. Smeers, Spatial oligopolistic electricity models with cournot generators and regulated transmission prices, Oper. Res., 47 (1999), 102-112.