Optimization Online


Solving linear generalized Nash equilibrium problems numerically

Axel Dreves (axel.dreves***at***unibw.de)
Nathan Sudermann-Merx (sudermann***at***kit.edu)

Abstract: This paper considers the numerical solution of linear generalized Nash equilibrium problems. Since many methods for nonlinear problems require the nonsingularity of some second order derivative, standard convergence conditions are not satisfied in our linear case. We provide new convergence criteria for a potential reduction algorithm that allow its application to linear generalized Nash equilibrium problems. Furthermore, we discuss a projected subgradient method and a penalty method that exploit some known Nikaido-Isoda function based constrained and unconstrained optimization reformulations of the linear generalized Nash equilibrium problem. Moreover, it is shown that normalized Nash equilibria can be obtained by solving a single linear program. All proposed algorithms are tested on randomly generated instances of economic market models that are introduced and analyzed in this paper. It is shown that these problems have some favorable properties that can be exploited to obtain their solutions. With the potential reduction algorithm and in particular with the projected subgradient method we are able to compute solutions with satisfying precision even for problems with up to ten thousand variables.

Keywords: Linear generalized Nash equilibrium problem, potential reduction algorithm, projected subgradient method, penalty method, economic market model

Category 1: Other Topics (Game Theory )



Entry Submitted: 09/08/2015
Entry Accepted: 09/08/2015
Entry Last Modified: 06/06/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society