Distributed Nash Equilibrium Seeking Over Random Graphs

Dear Editor, This letter is concerned with the distributed Nash equilibrium (NE) seeking in an N-player game over random graphs. We develop a distributed stochastic forward-backward (DSFB) algorithm based on local information exchange between agents. We prove that the DSFB algorithm can converge to an NE almost surely, and analyze the convergence rate of the proposed algorithm. Compared with the existing works on distributed NE seeking, the communication graph in this letter is supposed to be time-varying and stochastic, which makes the NE seeking algorithm more suitable for practical scenarios, but brings a great challenge in both the design and convergence analysis of the algorithm. Besides, by establishing a variational inequality on NE, we relax the co-coercivity or strong monotonicity assumption on the extended pseudo-gradient.