Two Heuristic Models for Solving Generalized Nash Equilibrium Problems using a Novel Penalty Function

Abstract

In this work, we solve Generalized Nash Equilibrium Problems using two novel heuristic models. We introduce the Shadow Point function, a novel penalty function for Generalized Nash Equilibrium Problems, similar to the Nikaido-Isoda penalty function to motivate the behavior of these two models. The first is an evolutionary-inspired algorithm which utilizes competitive selection and linear regression to motivate generation of new points. The other algorithm involves stochastic gradient descent of the Shadow Point function across mass numbers of agents to find solutions. These algorithms are evaluated on 2- and 3-player games in 2 and 3 dimensions, with both linear and non-linear shared constraints. The success of these algorithms is discussed, and the limitations of the algorithms are explored. Finally, we discuss potential remedies to these limitations, and additional ways to further optimize the methods.