Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
This work addresses the challenge of distributed Nash equilibrium computation in networked games with asymmetric communication, which is relevant for multi-agent systems with incomplete information.
The paper proposes a distributed Nash equilibrium seeking algorithm for networked games with non-doubly stochastic communication weights, proving almost sure convergence despite the lack of exact convergence due to asymmetric information exchange. The algorithm is extended to graphical games, and its efficacy is demonstrated via a social media behavioral simulation.
A distributed Nash equilibrium seeking algorithm is presented for networked games. We assume an incomplete information available to each player about the other players' actions. The players communicate over a strongly connected digraph to send/receive the estimates of the other players' actions to/from the other local players according to a gossip communication protocol. Due to asymmetric information exchange between the players, a non-doubly (row) stochastic weight matrix is defined. We show that, due to the non-doubly stochastic property, the total average of all players' estimates is not preserved for the next iteration which results in having no exact convergence. We present an almost sure convergence proof of the algorithm to a Nash equilibrium of the game. Then, we extend the algorithm for graphical games in which all players' cost functions are only dependent on the local neighboring players over an interference digraph. We design an assumption on the communication digraph such that the players are able to update all the estimates of the players who interfere with their cost functions. It is shown that the communication digraph needs to be a superset of a transitive reduction of the interference digraph. Finally, we verify the efficacy of the algorithm via a simulation on a social media behavioral case.