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

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis,, John Wiley, (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.  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.  doi: 10.1073/pnas.38.10.886.  Google Scholar

[5]

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

[6]

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

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

[17]

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

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

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

[25]

R. T. Rockafellar and R. J. Wets, Variational Analysis,, Springer-Verlag, (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.  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.   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.  doi: 10.1016/j.ejor.2004.04.026.  Google Scholar

[2]

F. H. Clarke, Optimization and Nonsmooth Analysis,, John Wiley, (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.  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.  doi: 10.1073/pnas.38.10.886.  Google Scholar

[5]

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

[6]

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

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

[17]

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

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

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

[25]

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

[1]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[2]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[3]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[4]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[5]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445

[6]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[7]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[8]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[9]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[10]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[11]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[12]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[13]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[14]

Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

[15]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052

[16]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[17]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271

[18]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[19]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345

[20]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]