  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.
