2014, 10(4): 1091-1108. doi: 10.3934/jimo.2014.10.1091

A barrier function method for generalized Nash equilibrium problems

1. 

Institute of ORCT, School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

2. 

Institute of ORCT, School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024

Received  January 2013 Revised  December 2013 Published  February 2014

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.
Citation: Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091
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. doi: 10.1016/j.ejor.2004.04.026.

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis,, John Wiley, (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. doi: 10.1109/TPWRS.2003.820692.

[4]

G. Debreu, A social equilibrium existence theorem,, Proc. Natl. Acad. Sci. U. S. A., 38 (1952), 886. doi: 10.1073/pnas.38.10.886.

[5]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, I, (2003).

[6]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Vol II, (2003).

[7]

F. Facchinei, A. Fischer and V. Piccialli, On generalized Nash games and variational inequalities,, Oper. Res. Lett., 35 (2007), 159. 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. doi: 10.1137/S1052623496298194.

[9]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Math. Program., 117 (2009), 163. doi: 10.1007/s10107-007-0160-2.

[10]

M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm,, Comput. Manag. Sci., 8 (2011), 201. doi: 10.1007/s10287-009-0097-4.

[11]

G. Gürkan and J. S. Pang, Approximations of Nash equilibria,, Math. Program., 117 (2009), 223. 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. 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. 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. 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.

[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. doi: 10.1007/BF02592192.

[17]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM J. Control. Optim., 15 (1977), 959. 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. 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. 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. 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. 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. doi: 10.1007/BF01581275.

[23]

S. M. Robinson, Shadow prices for measures of effectiveness, I: Linear model,, Oper. Res., 41 (1993), 518. 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. doi: 10.1287/opre.41.3.536.

[25]

R. T. Rockafellar and R. J. Wets, Variational Analysis,, Springer-Verlag, (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. 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.

show all references

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. doi: 10.1016/j.ejor.2004.04.026.

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis,, John Wiley, (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. doi: 10.1109/TPWRS.2003.820692.

[4]

G. Debreu, A social equilibrium existence theorem,, Proc. Natl. Acad. Sci. U. S. A., 38 (1952), 886. doi: 10.1073/pnas.38.10.886.

[5]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, I, (2003).

[6]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Vol II, (2003).

[7]

F. Facchinei, A. Fischer and V. Piccialli, On generalized Nash games and variational inequalities,, Oper. Res. Lett., 35 (2007), 159. 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. doi: 10.1137/S1052623496298194.

[9]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Math. Program., 117 (2009), 163. doi: 10.1007/s10107-007-0160-2.

[10]

M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm,, Comput. Manag. Sci., 8 (2011), 201. doi: 10.1007/s10287-009-0097-4.

[11]

G. Gürkan and J. S. Pang, Approximations of Nash equilibria,, Math. Program., 117 (2009), 223. 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. 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. 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. 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.

[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. doi: 10.1007/BF02592192.

[17]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM J. Control. Optim., 15 (1977), 959. 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. 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. 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. 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. 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. doi: 10.1007/BF01581275.

[23]

S. M. Robinson, Shadow prices for measures of effectiveness, I: Linear model,, Oper. Res., 41 (1993), 518. 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. doi: 10.1287/opre.41.3.536.

[25]

R. T. Rockafellar and R. J. Wets, Variational Analysis,, Springer-Verlag, (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. 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.

[1]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018123

[2]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51

[3]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1

[4]

Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153

[5]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143

[6]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1

[7]

Lori Badea. Multigrid methods for some quasi-variational inequalities. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1457-1471. doi: 10.3934/dcdss.2013.6.1457

[8]

Yusuke Murase, Risei Kano, Nobuyuki Kenmochi. Elliptic Quasi-variational inequalities and applications. Conference Publications, 2009, 2009 (Special) : 583-591. doi: 10.3934/proc.2009.2009.583

[9]

Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics & Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1

[10]

Yurii Nesterov, Laura Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Discrete & Continuous Dynamical Systems - A, 2011, 31 (4) : 1383-1396. doi: 10.3934/dcds.2011.31.1383

[11]

Ouayl Chadli, Gayatri Pany, Ram N. Mohapatra. Existence and Iterative Approximation Method for solving Mixed Equilibrium Problem under Generalized Monotonicity in Banach Spaces. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019034

[12]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[13]

Laura Scrimali. Mixed behavior network equilibria and quasi-variational inequalities. Journal of Industrial & Management Optimization, 2009, 5 (2) : 363-379. doi: 10.3934/jimo.2009.5.363

[14]

Yusuke Murase, Atsushi Kadoya, Nobuyuki Kenmochi. Optimal control problems for quasi-variational inequalities and its numerical approximation. Conference Publications, 2011, 2011 (Special) : 1101-1110. doi: 10.3934/proc.2011.2011.1101

[15]

Qilin Wang, Shengji Li. Lower semicontinuity of the solution mapping to a parametric generalized vector equilibrium problem. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1225-1234. doi: 10.3934/jimo.2014.10.1225

[16]

Xiaolin Xu, Xiaoqiang Cai. Price and delivery-time competition of perishable products: Existence and uniqueness of Nash equilibrium. Journal of Industrial & Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843

[17]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control & Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010

[18]

Haisen Zhang. Clarke directional derivatives of regularized gap functions for nonsmooth quasi-variational inequalities. Mathematical Control & Related Fields, 2014, 4 (3) : 365-379. doi: 10.3934/mcrf.2014.4.365

[19]

O. Chadli, Z. Chbani, H. Riahi. Recession methods for equilibrium problems and applications to variational and hemivariational inequalities. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 185-196. doi: 10.3934/dcds.1999.5.185

[20]

Cheng-Dar Liou. Note on "Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method". Journal of Industrial & Management Optimization, 2012, 8 (3) : 727-732. doi: 10.3934/jimo.2012.8.727

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]