On some approaches to searching the Nash equilibrium in concave games

Andrey V. Chernov

Matematičeskaâ teoriâ igr i eë priloženiâ, Tome 9 (2017) no. 2, pp. 62-104

Résumé

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 numerical algorithms for searching the Nash equilibrium with convergence guaranteed without additional requirements concerning objective functionals such as convexity in “strange” variables or another similar hypotheses (in the sense of weak convexity, quasiconvexity and so on). We describe two approaches. The first one being obvious enough is based on usage of the Hooke–Jeeves method for minimization a residual function and presented as a “standard for comparison” in the sense of efficiency of numerical solution for possible alternative methods. The second one (to some extent) can be regarded as “a cross between” the relaxation algorithm and the Hooke–Jeeves method of configurations (but with considering specific character of the function being minimized). Its justification (at this moment for the case of one-dimensional sets of players strategies but with general enough requirements to objective functionals) is a main result of the paper. Moreover, we present results of numerical experiments with their discussion. We give the comparison with other algorithms which are known at present.

Détail

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