On relaxation algorithms in computation of noncooperative equilibria
- 1 June 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 39 (6), 1263-1267
- https://doi.org/10.1109/9.293193
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- On the anti-monotonicity of differential mappings connected with general equilibrium problemOptimization, 1988
- Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibriaJournal of Economic Dynamics and Control, 1987
- Distributed algorithms for the computation of noncooperative equilibriaAutomatica, 1987
- Iterative Techniques for the Nash Solution in Quadratic Games with Unknown ParametersSIAM Journal on Control and Optimization, 1986
- Note on non-cooperative convex gamePacific Journal of Mathematics, 1955