cc 18: e1

Research Article

Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix

Download18 downloads
  • @ARTICLE{10.4108/eai.13-7-2018.158526,
        author={Farzad Salehisadaghiani and Lacra Pavel},
        title={Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix},
        journal={EAI Endorsed Transactions on Collaborative Computing: Online First},
        volume={},
        number={},
        publisher={EAI},
        journal_a={CC},
        year={2019},
        month={4},
        keywords={Nash equilibrium, communication graph, information exchange},
        doi={10.4108/eai.13-7-2018.158526}
    }
    
  • Farzad Salehisadaghiani
    Lacra Pavel
    Year: 2019
    Nash Equilibrium Seeking with Non-doubly Stochastic Communication Weight Matrix
    CC
    EAI
    DOI: 10.4108/eai.13-7-2018.158526
Farzad Salehisadaghiani1, Lacra Pavel1,*
  • 1: Department of Electrical and Computer Engineering, University of Toronto, 10 King’s College Road, Toronto, ON, M5S 3G4, Canada
*Contact email: pavel@control.utoronto.ca

Abstract

We propose a distributed Nash equilibrium seeking algorithm in a networked game, where each player has incomplete information on other players’ actions. Players keep estimates and communicate over a strongly connected digraph with their neighbours according to a gossip communication protocol. Due to the asymmetric information exchange between players, a non-doubly (row)-stochastic weight matrix is defined. We prove almost-sure convergence of the algorithm to a Nash equilibrium under diminishing step-sizes. We extend the algorithm to graphical games in which players’ cost functions are dependent only on their neighbouring players in an interference digraph. Given the interference digraph, a communication digraph is designed so that players exchange only their required information. The communication digraph is a subset of the interference digraph and a superset of its transitive reduction. Finally, we verify the efficacy of the algorithm via simulation on a social media behavioural case.