An algorithm for equilibrium selection in generalized Nash equilibrium problems

Recently a new solution concept for generalized Nash equilibrium problems was published by the author. This concept selects a reasonable equilibrium out of the typically infinitely many. The idea is to model the process of finding a compromise by solving parametrized generalized Nash equilibrium problems. In this paper we propose an algorithmic realization of the concept. The model produces a solution path, which is under suitable assumptions unique. The algorithm is a homotopy method that tries to follow this path. We use semismooth Newton steps as corrector steps in our algorithm in order to approximately solve the generalized Nash equilibrium problems for each given parameter. If we have a unique solution path, we need three additional theoretical assumptions: a stationarity result for the merit function, a coercivity condition for the constraints, and an extended Mangasarian-Fromowitz constraint qualification. Then we can prove convergence of our semismooth tracing algorithm to the unique equilibrium to be selected. We also present convincing numerical results on a test library of problems from literature. The algorithm also performs well on a number of problems that do not satisfy all the theoretical assumptions.