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 & 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.  Google Scholar

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley, New York, 1983.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, I, Springer-Verlag, New York, 2003.  Google Scholar

[6]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol II, Springer-Verlag, New York, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

J. B. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications, Environ. Model. Assess., 5 (2000), 63-73. Google Scholar

[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.  Google Scholar

[17]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control. Optim., 15 (1977), 959-972. doi: 10.1137/0315061.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[22]

L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Program, 58 (1993), 353-367. doi: 10.1007/BF01581275.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

R. T. Rockafellar and R. J. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[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.  Google Scholar

[27]

J. Y. Wei and Y. Smeers, Spatial oligopolistic electricity models with cournot generators and regulated transmission prices, Oper. Res., 47 (1999), 102-112. Google Scholar

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

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley, New York, 1983.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, I, Springer-Verlag, New York, 2003.  Google Scholar

[6]

F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol II, Springer-Verlag, New York, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

J. B. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications, Environ. Model. Assess., 5 (2000), 63-73. Google Scholar

[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.  Google Scholar

[17]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control. Optim., 15 (1977), 959-972. doi: 10.1137/0315061.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[22]

L. Qi and J. Sun, A nonsmooth version of Newton's method, Math. Program, 58 (1993), 353-367. doi: 10.1007/BF01581275.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

R. T. Rockafellar and R. J. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[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.  Google Scholar

[27]

J. Y. Wei and Y. Smeers, Spatial oligopolistic electricity models with cournot generators and regulated transmission prices, Oper. Res., 47 (1999), 102-112. Google Scholar

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

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

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

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

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
[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy