Game Theory for Networks. 7th International EAI Conference, GameNets 2017 Knoxville, TN, USA, May 9, 2017, Proceedings

Research Article

Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix

Download
194 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-67540-4_1,
        author={Farzad Salehisadaghiani and Lacra Pavel},
        title={Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix},
        proceedings={Game Theory for Networks. 7th International EAI Conference, GameNets 2017 Knoxville, TN, USA, May 9, 2017, Proceedings},
        proceedings_a={GAMENETS},
        year={2017},
        month={9},
        keywords={},
        doi={10.1007/978-3-319-67540-4_1}
    }
    
  • Farzad Salehisadaghiani
    Lacra Pavel
    Year: 2017
    Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
    GAMENETS
    Springer
    DOI: 10.1007/978-3-319-67540-4_1
Farzad Salehisadaghiani1,*, Lacra Pavel1,*
  • 1: University of Toronto
*Contact email: farzad.salehisadaghiani@mail.utoronto.ca, pavel@control.utoronto.ca

Abstract

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, there is no exact convergence. Then, we present an almost sure convergence proof of the algorithm to a Nash equilibrium of the game. Moreover, 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.