A decentralized descent method for the numerical solution of the Nash equilibrum problem

Abstract:

In a game of N players, each player seeks to maximize his payoff by choosing an appropriate strategy. A Nash equilibrium is a vector of strategies of all players, such that no player can improve his situation by unilaterally changing his strategy. In each stage of a game, a player might want to choose a strategy that maximizes his payoff given the rival players do not change their strategy. This is called the best answer or proximal response and defines a fixed point iteration when applied repeatedly. We analyse conditions for convergence of a relaxed proximal response method with respect to the network structure of the game. Furthermore, employing the Nikaido-Isoda function, the method can also be viewed as a descent method, allowing for line searches.