An Adjustment Process-based Algorithm with Error Bounds for Approximating a Nash Equilibrium

Regarding the approximation of Nash equilibria in games where the players have a continuum of strategies, there exist various algorithms based on best response dynamics and on its relaxed variants: from one step to the next, a player's strategy is updated by using explicitly a best response to the strategies of the other players that come from the previous steps. These iterative schemes generate sequences of strategy profiles which are constructed by using continuous optimization techniques and they have been shown to converge in the following situations: in zero-sum games or, in non zero-sum ones, under contraction assumptions or under linearity of best response functions. In this paper, we propose an algorithm which guarantees the convergence to a Nash equilibrium in two-player non zero-sum games when the best response functions are not necessarily linear, both their compositions are not contractions and the strategy sets are Hilbert spaces. Firstly, we address the issue of uniqueness of the Nash equilibrium extending to a more general class the result obtained by Caruso, Ceparano, and Morgan [J. Math. Anal. Appl., 459 (2018), pp. 1208-1221] for weighted potential games. Then, we describe a theoretical approximation scheme based on a non-standard (non-convex) relaxation of best response iterations which converges to the unique Nash equilibrium of the game. Finally, we define a numerical approximation scheme relying on a derivative-free continuous optimization technique applied in a finite dimensional setting and we provide convergence results and error bounds.