Complexity of equilibrium in competitive diffusion games on social networks

被引:32
作者
Etesami, Seyed Rasoul [1 ]
Basar, Tamer [1 ]
机构
[1] Univ Illinois, Coordinated Sci Lab, Urbana, IL 61801 USA
基金
美国国家科学基金会;
关键词
Competitive diffusion game; Pure-strategy Nash equilibrium; Sub-modular function; NP-hardness; Erdos-Renyi graphs; Social welfare; NASH EQUILIBRIA;
D O I
10.1016/j.automatica.2016.01.063
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, we consider the competitive diffusion game, and study the existence of its pure-strategy Nash equilibrium when defined over general undirected networks, We first determine the set of pure strategy Nash equilibria for two special but well-known classes of networks, namely the lattice and the hypercube. Characterizing the utility of the players in terms of graphical distances of their initial seed placements to other nodes in the network, we show that in general networks the decision process on the existence of pure-strategy Nash equilibrium is an NP-hard problem. Following this, we provide some necessary conditions for a given profile to be a Nash equilibrium. Furthermore, we study players' utilities in the competitive diffusion game over Erdos-Renyi random graphs and show that as the size of the network grows, the utilities of the players are highly concentrated around their expectation, and are bounded below by some threshold based on the parameters of the network. Finally, we obtain a lower bound for the maximum social welfare of the game with two players, and study sub-modularity of the players' utilities. Published by Elsevier Ltd.
引用
收藏
页码:100 / 110
页数:11
相关论文
共 36 条
[1]   Opinion Fluctuations and Disagreement in Social Networks [J].
Acemoglu, Daron ;
Como, Giacomo ;
Fagnani, Fabio ;
Ozdaglar, Asuman .
MATHEMATICS OF OPERATIONS RESEARCH, 2013, 38 (01) :1-27
[2]  
Acemoglu D, 2011, IEEE DECIS CONTR P, P2329, DOI 10.1109/CDC.2011.6160999
[3]  
Acemoglu Daron, 2014, ACM SIGMETRICS PERFO, V42
[4]   Combinatorial model and bounds for target set selection [J].
Ackerman, Eyal ;
Ben-Zwi, Oren ;
Wolfovitz, Guy .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (44-46) :4017-4022
[5]   A note on competitive diffusion through social networks [J].
Alon, Noga ;
Feldman, Michal ;
Procaccia, Ariel D. ;
Tennenholtz, Moshe .
INFORMATION PROCESSING LETTERS, 2010, 110 (06) :221-225
[6]  
Alon Noga, 2004, PROBABILISTIC METHOD
[7]  
[Anonymous], 1998, RANDOM GRAPHS
[8]  
[Anonymous], 2014, ARXIV14066625
[9]  
[Anonymous], 2013, IEEE T KNOWL DATA EN
[10]  
Basar T., 1999, Dynamic Noncooperative Game Theory, Vsecond