Chapter 4: Two Heuristic Methods for Solving Generalized Nash Equilibrium Problems Using a Novel Penalty Function

In this chapter, we introduce two evolutionary algorithmic heuristics which utilize competitive selection, (linear and nonlinear) regression and stochastic gradient descent to evolve generations of new points toward identifying entire solution sets of generalized Nash games with jointly convex constraints. Both algorithms involve the so-called shadow point function, a novel penalty function for generalized Nash equilibrium problems (GNEPs), similar to the Nikaidô–Isoda penalty function in optimization. It is well known that GNEPs have in general entire sets of Nash equilibria, and the question of identification of the entire solution set for a given GNEP is still open, for large classes of GNEPs. Traditional optimization-based methods to solve GNEPs are based on KKT systems, quasi-variational inequalities and projected differential equations/inclusions, which are, with a few exceptions, only designed to find one point in the solution set rather than the set itself. Our algorithms are evaluated on 2- and 3-player games in 2 and 3 dimensions, with both linear and nonlinear shared constraints. The success of these algorithms is discussed and compared, and future work is outlined.