American Institute of Mathematical Sciences

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

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, 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.
Keywords: generalized Nash equilibrium problem, logarithmic barrier function, semismooth Newton method., Nash equilibrium problem, quasi-variational inequalities.
Mathematics Subject Classification: Primary: 90C25, 90C30; Secondary: 49M15, 49M3.
Citation: Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and 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-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.

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-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.

[1]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[2]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[3]

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

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

Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049
[6]

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
[7]

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

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics and Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[9]

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

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

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
[12]

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

Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[14]

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

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

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

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
[18]

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 and Optimization, 2020, 10 (1) : 75-92. doi: 10.3934/naco.2019034
[19]

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

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy