On relaxation algorithms in computation of noncooperative equilibria

This paper considers a special class of numerical algorithms, the so-called relaxation algorithm, for Nash equilibrium points in noncooperative games. The relaxation algorithms have been studied by various authors for the deterministic case. Convergence conditions of this algorithm are based on fixed point theorems. For example, Basar (1987) and Li and Basar (1987) have proved its convergence for a two-player game via the contraction mapping theorem. For the quadratic case these conditions can be easily checked. For other nonlinear payoff functions it is sometimes difficult to check these convergence conditions. In this paper, the authors propose an alternative approach using the residual terms of the Nikaido-Isoda function. The convergence theorem is proved for nonsmooth weakly convex-concave Nikaido-Isoda functions. The family of weakly convex-concave functions is broad enough for applications, since if includes the family of smooth functions. When the payoff functions are twice continuously differentiable, the condition for the residual terms is reduced to strict positiveness of a matrix representing the difference of the Hessians of the Nikaido-Isoda function with respect to the first and second groups of variables. An analogous condition was used by Uryas'ev (1988) to prove convergence of the gradient-type algorithm for the Nash equilibrium problem. In this paper the authors discuss only the deterministic case; nevertheless this approach can be generalized for the stochastic Nash equilibrium problems with uncertainties in parameters.<
>