Solving linear generalized Nash equilibrium problems numerically

Axel Dreves, Nathan Sudermann-Merx

We will discuss several numerical approaches for the solution of generalized Nash equilibrium problems where the cost and constraint functions are affine linear. Exploiting duality theory it is possible to design an algorithm that can compute the entire solution set and terminates after finite time. Practically this algorithm is effective for small dimensional problems only. For larger problems we have to be satisfied to compute some solutions. Since we have no second order derivatives we will provide new convergence criteria for a potential reduction algorithm. Then we will compare this algorithm with some projected gradient method and a penalty approach that exploit Nikaido-Isoda function based optimization reformulations. All algorithms are tested on randomly generated instances of some economy market models.