An algorithm for Nash equilibria

Thu, 11/07/2019 - 12:00 / 14:00

207, Viale Romania, 32

Speaker: Jacqueline Morgan , Università di Napoli


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 relaxedvariants: 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. An algorithm will be presented 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 the entire 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(2018) for weighted potential games. Then, 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 will be presented. Finally, a numerical approximation scheme will be illustrated relying on a derivative-free continuous optimization technique applied in a finite dimensional setting.


Working paper: