A Distributed Nash Equilibrium Seeking in Networked Graphical Games
For researchers in distributed optimization and game theory, this work addresses the challenge of decentralized Nash equilibrium seeking under asymmetric information and limited communication, but the approach is incremental as it extends existing gossip-based methods to graphical games.
This paper proposes a distributed gossip algorithm for finding Nash equilibria in networked graphical games with partially-coupled cost functions and limited communication, proving almost sure convergence for diminishing step sizes and quantifying the effect of the communication graph's spectral properties on convergence rate.
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.