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

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

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[4]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[5]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[6]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[7]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[8]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[9]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[10]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[11]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827
[12]

Jean Dolbeault, Maria J. Esteban, Michał Kowalczyk, Michael Loss. Improved interpolation inequalities on the sphere. Discrete & Continuous Dynamical Systems - S, 2014, 7 (4) : 695-724. doi: 10.3934/dcdss.2014.7.695
[13]

V. V. Zhikov, S. E. Pastukhova. Korn inequalities on thin periodic structures. Networks & Heterogeneous Media, 2009, 4 (1) : 153-175. doi: 10.3934/nhm.2009.4.153
[14]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25
[15]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[16]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[17]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[18]

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363
[19]

Luigi C. Berselli, Jishan Fan. Logarithmic and improved regularity criteria for the 3D nematic liquid crystals models, Boussinesq system, and MHD equations in a bounded domain. Communications on Pure & Applied Analysis, 2015, 14 (2) : 637-655. doi: 10.3934/cpaa.2015.14.637
[20]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences