On Structure and Computation of Generalized Nash Equilibria

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 to 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)\left| J_0 \right|$, where $N$ is the number of players and $\left| J_0 \right|$ is the number of active common constraints. In a structural analysis of Nash equilibria the number $(N-1)\left| J_0 \right|$ plays a crucial role. In fact, this 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 locally equals $(N-1)\left| J_0 \right|$. For the computation of FJ points we propose a nonsmooth projection method (NPM) which aims at finding solutions of an underdetermined system of nonsmooth equations. NPM is shown to be well defined 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.