On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke's method

Dane A. Schiro, Jong Shi Pang, Uday V. Shanbhag

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players' variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e.; common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke's method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen's normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke's method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke's scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.

Original languageEnglish (US)
Pages (from-to)1-46
Number of pages46
JournalMathematical Programming
Issue number1-2
StatePublished - Dec 2013

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke's method'. Together they form a unique fingerprint.

Cite this