Numerical methods for Nash equilibrium problems with descent criteria

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)