A Distributed Nash Equilibrium Seeking in Networked Graphical Games

Abstract

This paper considers a distributed gossip approach for finding a Nash equilibrium in networked games on graphs. In such games a player's cost function may be affected by the actions of any subset of players. An interference graph is employed to illustrate the partially-coupled cost functions and the asymmetric information requirements. For a given interference graph, network communication between players is considered to be limited. A generalized communication graph is designed so that players exchange only their required information. An algorithm is designed whereby players, with possibly partially-coupled cost functions, make decisions based on the estimates of other players' actions obtained from local neighbors. It is shown that this choice of communication graph guarantees that all players' information is exchanged after sufficiently many iterations. Using a set of standard assumptions on the cost functions, the interference and the communication graphs, almost sure convergence to a Nash equilibrium is proved for diminishing step sizes. Moreover, the case when the cost functions are not known by the players is investigated and a convergence proof is presented for diminishing step sizes. The effect of the second largest eigenvalue of the expected communication matrix on the convergence rate is quantified. The trade-off between parameters associated with the communication graph and the ones associated with the interference graph is illustrated. Numerical results are presented for a large-scale networked game.

Cited by in corpus (10)

• A Passivity-Based Approach to Nash Equilibrium Seeking over Networks
• A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
• Distributed Nash Equilibrium Seeking under Partial-Decision Information via the Alternating Direction Method of Multipliers
• Single-timescale distributed GNE seeking for aggregative games over networks via forward-backward operator splitting
• Distributed generalized Nash equilibria computation of monotone games via a preconditioned proximal point algorithm
• Network games with dynamic players: Stabilization and output convergence to Nash equilibrium
• Distributed Nash Equilibrium Seeking for Monotone Generalized Noncooperative Games by a Regularized Penalty Method
• Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
• Efficient Distributed Learning in Stochastic Non-cooperative Games without Information Exchange
• Online distributed algorithms for seeking generalized Nash equilibria in dynamic environments