Séminaire Modélisation, Optimisation, Dynamique

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

par Prof. Monica Cojocaru

Europe/Paris
XR203 (XLIM)

XR203

XLIM

FST-Université de Limoges 123 Av. Albert Thomas, 87000 Limoges
Description

In this paper, we introduce the Shadow Point function, a novel penalty function for Generalized Nash Equilibrium Problems, similar to the Nikaido-Isoda penalty function. We investigate the use of this function across two heuristic 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 compared, and the limitations of the algorithms are explored. Finally, we discuss potential remedies to these limitations, as well as additional ways to further optimize the methods.