On Structure and Computation of Generalized Nash Equilibria

Dorsch, Dominik;Jongen, Hubertus Th.;Shikhman, Vladimir
(2013) SIAM Journal on Optimization — Vol. 23, n° 1, p. 452-474 (2013)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 417.19 KB
Request a copy

Details

Authors
  • Dorsch, DominikRWTH Aachen University
    Author
  • Jongen, Hubertus Th.RWTH Aachen University
    Author
  • Shikhman, VladimirUCLouvain
    Author
Abstract
We consider generalized Nash equilibrium problems (GNEP) from a structural and computational point of view. In GNEP the players’ feasible sets may depend on the other players’ strategies. Moreover, the players may share common constraints. In particular, the latter leads to the stable appearance of Nash equilibria which are Fritz-John (FJ) points, but not Karush-Kuhn-Tucker (KKT) points. Basic in our approach is the representation of FJ points as zeros of an appropriate underdetermined system of nonsmooth equations. Here, additional nonsmooth variables are taken into account. We prove that the set of FJ points (together with corresponding active Lagrange multipliers) - generically - constitutes a Lipschitz manifold. Its dimension is (N-1)J_0, where N is the number of players and J_0 is the number of active common constraints. In a structural analysis of Nash equilibria the number (N-1)J_0 plays a crucial role. In fact, the latter number encodes both the possible degeneracies for the players’ parametric subproblems and the dimension of the set of Nash equilibria. In particular, in the nondegenerate case, the dimension of the set of Nash equilibria equals locally (N-1)J_0. For the computation of FJ points we propose a nonsmooth projection method (NPM) which aims at nding solutions of an underdetermined system of nonsmooth equations. NPM is shown to be well-dened for GNEP. Local convergence of NPM is conjectured for GNEP under generic assumptions and its proof is challenging. However, we indicate special cases (known from the literature) in which convergence holds.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Dorsch, D., Jongen, H. Th., & Shikhman, V. (2013). On Structure and Computation of Generalized Nash Equilibria. SIAM Journal on Optimization, 23(1), 452-474. https://doi.org/10.1137/110822670 (Original work published 2013)