Abstract
We study a game-theoretic model for the diffusion of competing products in social networks. Particularly, we consider a simultaneous non-cooperative game between competing firms that try to target customers in a social network. This triggers a competitive diffusion process, and the goal of each firm is to maximize the eventual number of adoptions of its own product. We study issues of existence, computation and performance (social inefficiency) of pure strategy Nash equilibria in these games. We mainly focus on 2-player games, and we model the diffusion process using the known linear threshold model. Nonetheless, many of our results continue to hold under a more general framework for this process.
Work supported by the project ALGONOW of the research funding program Thales (co-financed by the European Social Fund-ESF and Greek national funds). A full version of this work with all missing proofs is available at the authors’ websites.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Feldman, M., Procaccia, A.D., Tennenholtz, M.: A note on competitive diffusion through social networks. Information Processing Letters (IPL) 110(6), 221–225 (2010)
Apt, K.R., Markakis, E.: Diffusion in Social Networks with Competing Products. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol. 6982, pp. 212–223. Springer, Heidelberg (2011)
Bharathi, S., Kempe, D., Salek, M.: Competitive Influence Maximization in Social Networks. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 306–311. Springer, Heidelberg (2007)
Borodin, A., Filmus, Y., Oren, J.: Threshold Models for Competitive Influence in Social Networks. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 539–550. Springer, Heidelberg (2010)
Carnes, T., Nagarajan, C., Wild, S.M., van Zuylen, A.: Maximizing influence in a competitive social network: A follower’s perspective. In: 9th International Conference on Electronic Commerce (ICEC), pp. 351–360 (2007)
Chen, N.: On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics (SIDMA) 23(3), 1400–1415 (2009)
Chien, S., Sinclair, A.: Convergence to approximate Nash equilibria in congestion games. Games and Economic Behavior 71(2), 315–327 (2011)
Domingos, P., Richardson, M.: Mining the network value of customers. In: 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 57–66 (2001)
Goldenberg, J., Libai, B., Muller, E.: Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters 12(3), 211–223 (2001)
Goyal, S., Kearns, M.: Competitive contagion in networks. In: 44th ACM Symposium on Theory of Computing (STOC), pp. 759–774 (2012)
Granovetter, M.S.: Threshold models of collective behavior. The American Journal of Sociology 83(6), 1420–1443 (1978)
Immorlica, N., Kleinberg, J., Mahdian, M., Wexler, T.: The role of compatibility in the diffusion of technologies through social networks. In: Proceedings of the 8th ACM Conference on Electronic Commerce (EC), pp. 75–83 (2007)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence in a social network. In: 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 137–146 (2003)
Kostka, J., Oswald, Y.A., Wattenhofer, R.: Word of Mouth: Rumor Dissemination in Social Networks. In: Shvartsman, A.A., Felber, P. (eds.) SIROCCO 2008. LNCS, vol. 5058, pp. 185–196. Springer, Heidelberg (2008)
Leskovec, J., Adamic, L., Huberman, B.: The dynamics of viral marketing. ACM Transactions on the Web (TWEB) 1(1), Article No. 5 (2007)
Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14, 124–143 (1996)
Morris, S.: Contagion. The Review of Economic Studies 67(1), 57–78 (2000)
Mossel, E., Roch, S.: On the submodularity of influence in social networks. In: Symposium on Theory of Computing (STOC), pp. 128–134 (2007)
Schelling, T.C.: Micromotives and Macrobehavior. Norton, New York (1978)
Simon, S., Apt, K.R.: Choosing products in social networks (2012) (manuscript), http://arxiv.org/abs/1202.2209
Takehara, R., Hachimori, M., Shigeno, M.: A comment on pure-strategy Nash equilibria in competitive diffusion games. Information Processing Letters (IPL) 112(3), 59–60 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tzoumas, V., Amanatidis, C., Markakis, E. (2012). A Game-Theoretic Analysis of a Competitive Diffusion Process over Social Networks. In: Goldberg, P.W. (eds) Internet and Network Economics. WINE 2012. Lecture Notes in Computer Science, vol 7695. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35311-6_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-35311-6_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35310-9
Online ISBN: 978-3-642-35311-6
eBook Packages: Computer ScienceComputer Science (R0)