Numerical methods for Nash equilibrium problems with descent criteria

• Grant number: 21/05007-0
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: July 01, 2021
• End date: July 31, 2023
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Gabriel Haeser
• Grantee: Oliver Kolossoski
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 18/24293-0 - Computational methods in optimization, AP.TEM

Abstract

The objective of this work is to develop an augmented Lagrangian-based method for finding a solution point for the two-player Nash equilibrium prioblem. In the literature, the methods for this kind of problem use the optimality conditions theory for finding stationary points via the Karush-Kuhn-Tucker (KKT) conditions, with the aid of some qualification constraint. Although these conditions are necessary for a limit point of the sequence generated by the algorithm to be an equilibrium point, such conditions are not sufficient, as is shown in Haeser et. al., in recent works. Because of that, methods based on KKT conditions for Nash equilibrium problems may often find saddle points or local maxima instead of finding solutions for the problem. The method proposed here will make use of the minimization structure of the optimization subproblems generated by the augmented Lagrangian approach to find a stopping criterion based on a descent property, rather than relying on the indirect KKT conditions. We also aim to study the possibility of using sequential optimality conditions, similar to the ones developed by Haeser et. al., in recent works, for other kinds of problems. In this work, we aim to establish the convergence properties of this algorithm, as well as proving its good performance when compared with the other methods in the literature for this kind of problem. (AU)