Game Theory for Networks. 6th International Conference, GameNets 2016, Kelowna, BC, Canada, May 11-12, 2016, Revised Selected Papers

Research Article

Strategic Seeding of Rival Opinions

Download
232 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-47509-7_1,
        author={Samuel Johnson and Jemin George and Raissa D’Souza},
        title={Strategic Seeding of Rival Opinions},
        proceedings={Game Theory for Networks. 6th International Conference, GameNets 2016, Kelowna, BC, Canada, May 11-12, 2016, Revised Selected Papers},
        proceedings_a={GAMENETS},
        year={2017},
        month={1},
        keywords={Social networks Opinion dynamics Game theory Nash equilibrium Computational complexity Approximation algorithm},
        doi={10.1007/978-3-319-47509-7_1}
    }
    
  • Samuel Johnson
    Jemin George
    Raissa D’Souza
    Year: 2017
    Strategic Seeding of Rival Opinions
    GAMENETS
    Springer
    DOI: 10.1007/978-3-319-47509-7_1
Samuel Johnson1,*, Jemin George2,*, Raissa D’Souza3,*
  • 1: HRL Laboratories, LLC
  • 2: United States Army Research Laboratory
  • 3: University of California
*Contact email: sdjohnson@hrl.com, jemin.george.civ@mail.mil, raissa@cse.ucdavis.edu

Abstract

We present a network influence game that models players strategically seeding the opinions of nodes embedded in a social network. A social learning dynamic, whereby nodes repeatedly update their opinions to resemble those of their neighbors, spreads the seeded opinions through the network. After a fixed period of time, the dynamic halts and each player’s utility is determined by the relative strength of the opinions held by each node in the network the other players. We show that the existence of a pure Nash equilibrium cannot be guaranteed in general. However, if the dynamics are allowed to progress for a sufficient amount of time so that a consensus among all of the nodes is obtained, then the existence of a pure Nash equilibrium can be guaranteed. The computational complexity of finding a pure strategy best response is shown to be -complete, but can be efficiently approximated to within a factor of optimal by a simple greedy algorithm.