@inproceedings{5021fc5e9d094357ba2e264195a71f66,
title = "Complexity of equilibrium in diffusion games on social networks",
abstract = "We revisit the competitive diffusion game on undirected connected graphs and study the complexity of the existence of pure-strategy Nash equilibrium for such games. We first characterize the utility of each player based on the location of its initial seed placements. Using this characterization, we show that the utility of each player is a sub-modular function of its initial seed set. Following this, a simple greedy algorithm provides an initial seed placement within a constant factor of the optimal solution. We show NP-completeness of the decision on the existence of pure-strategy Nash equilibrium for general networks. Finally we provide some necessary conditions for a given profile to be a Nash equilibrium and obtain a lower bound for the maximum social welfare of the game with two players.",
keywords = "Competitive diffusion game, NP-hardness, greedy algorithm, pure Nash equilibrium, social welfare, sub-modular function",
author = "Etesami, {Seyed Rasoul} and Tamer Ba{\c s}ar",
year = "2014",
doi = "10.1109/ACC.2014.6859194",
language = "English (US)",
isbn = "9781479932726",
series = "Proceedings of the American Control Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "2065--2070",
booktitle = "2014 American Control Conference, ACC 2014",
address = "United States",
note = "2014 American Control Conference, ACC 2014 ; Conference date: 04-06-2014 Through 06-06-2014",
}