On some general scheme of constructing iterative methods for searching the Nash equilibrium in concave games

Andrey V. Chernov

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 13 (2021) no. 3, pp. 75-121

Résumé

\language=0 The subject of the paper is finite-dimensional concave games id est noncooperative $n$-person games with objective functionals concave with respect to ‘their own’ variables. For such games we investigate the problem of designing iterative algorithms for searching the Nash equilibrium with convergence guaranteed without requirements concerning objective functionals such as smoothness and as convexity in ‘strange’ variables or another similar hypotheses (in the sense of weak convexity, quasiconvexity and so on). In fact, we prove some assertion analogous to the theorem on convergence of $M$-Fejér iterative process for the case when an operator acts in a finite-dimensional compact and nearness to an objective set is measured with the help of arbitrary continuous function. Then, on the base of this assertion we generalize and develope the approach suggested by the author formerly to searching the Nash equilibrium in concave games. The last one can be regarded as “a cross between” the relaxation algorithm and the Hooke–Jeeves method of configurations (but taking into account a specific character of the the residual function being minimized). Moreover, we present results of numerical experiments with their discussion.

Détail

Keywords: finite-dimensional concave game, Nash equilibrium, searching iterative algorithm.