An Inverse-Adjusted Best Response Algorithm for Nash Equilibria

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, called $r_1$ and $r_2$, are not necessarily linear, neither the composition $r_1circ r_2$ nor $r_2circ r_1$ is a contraction, and the strategy sets are Hilbert spaces. First, 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 nonstandard (nonconvex) 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.