Nash Equilibrium Seeking Over Networks

The problem of Nash equilibrium seeking is investigated in a networked game. The game is defined as being played by a collection of a finite number of players whose cost functions are dependent on the actions of any subset of players in the network. This dependency is captured by a graph referred to as an interference graph. According to the topology of this graph, we design distributed algorithms to find a Nash equilibrium of the game. We focus on distributed algorithms since the players are only aware of imperfect information about some local playersâ actions. The players are allowed to communicate with the local neighbors, through a communication graph, to update their information as iterations proceed. Based on the topology of the interference graph, we find a limit over the communication graph for the sake of dissemination of the required information between the players. The proposed algorithms are based on projected gradient-based method by using diminishing and constant step sizes. The aim of using different step sizes is to leverage various aspects of convergence such as accuracy and speed. It is shown that while, the diminishing step sizes drive the algorithm as close as possible to the Nash equilibrium of the game, a large number of iterations is required as the step sizes diminish after each iteration. The algorithms with constant step sizes, on the other hand, are not harmed by this issue, however, the iterates of those algorithms fluctuate around the Nash equilibrium of the game and never reach the exact point but with an error. To remedy this problem for the algorithms with constant step sizes, we derive a novel method similar to ADMM techniques used in the context of distributed consensus optimization problems. A penalty term is considered for the projected gradient algorithm to annihilate the error term. Finally, we focus on games with coupled constraints in which, playersâ actions belong to a set which is dependent on the other playersâ actions in the network. Our objective is to find a generalized Nash equilibrium in a special subclass of games referred to as jointly convex games. We consider the coupled constraints to be affine equality constraints which are shared between all players. The proposed ADMM technique is then employed to derive a projected gradient-based method to find a variational equilibrium of the game which is in fact identical to the generalized Nash equilibrium.Ph.D