Sanjeev Goyal
ABSTRACT
We develop a game-theoretic framework for the study of competition between firms who have budgets to "seed" the initial adoption of their products by consumers located in a social network. The payoffs to the firms are the eventual number of adoptions of their product through a competitive stochastic diffusion process in the network. This framework yields a rich class of competitive strategies, which depend in subtle ways on the stochastic dynamics of adoption, the relative budgets of the players, and the underlying structure of the social network.
We identify a general property of the adoption dynamics --- namely, decreasing returns to local adoption --- for which the inefficiency of resource use at equilibrium (the Price of Anarchy) is uniformly bounded above, across all networks. We also show that if this property is violated the Price of Anarchy can be unbounded, thus yielding sharp threshold behavior for a broad class of dynamics.
We also introduce a new notion, the Budget Multiplier, that measures the extent that imbalances in player budgets can be amplified at equilibrium. We again identify a general property of the adoption dynamics --- namely, proportional local adoption between competitors --- for which the (pure strategy) Budget Multiplier is uniformly bounded above, across all networks. We show that a violation of this property can lead to unbounded Budget Multiplier, again yielding sharp threshold behavior for a broad class of dynamics.
Supplemental Material
- Ballester, C., A. Calvo-Armengol, and Y. Zenou (2006),Who's Who in Networks. Wanted: The Key Player, Econometrica, 74, 5, 1403--1417.Google Scholar
Cross Ref
- Bharathi, S., D. Kempe and M. Salek (2007),Competitive Influence Maximization in Social Networks, Internetand Network Economics Lecture Notes in Computer Science, 4858, 306--311. Google ScholarDigital Library
- Borodin, A., Filmus, Y., Oren, J. (2010)Threshold Models for Competitive Influence in Social Networks, Proc. Workshop on Internet and Network Economics (WINE) Google ScholarDigital Library
- Butters, G. (1977), Equilibrium Distribution of Prices and Advertising, Review of Economic Studies, 44, 465--492.Google ScholarCross Ref
- Chasparis, G. and Shamma, J. (2010),Control of Preferences in Social Networks", 49th IEEE Conference on Decision and Control.Google ScholarCross Ref
- Coleman, J. (1966), Medical Innovation: A Diffusion Study.Second Edition, Bobbs-Merrill. New York.Google Scholar
- Conley, T. and C. Udry (2010), Learning about a New Technology:Pineapple in Ghana. American Economic Review, .Google Scholar
- Carnes, T., Nagarajan, C., Wild, S.,van Zuylen, A. (2007),Maximizing Influence in a Competitive Social Network:A Follower's Perspective. Proc. Ninth ACM Conference on Electronic Commerce (EC), pages 351--360. Google ScholarDigital Library
- Dubey, P., Garg, R., De Meyer, B. (2006), Competingfor Customers in a Social Network: The Quasi-linear Case. Proc. Workshop on Internet and Network Economics (WINE) Google ScholarDigital Library
- Dubey, P. (1986), Inefficiency of Nash Equilibria. Mathematics of Operations Research., 11, 1, 1 V8. Google ScholarDigital Library
- Feick, L.F. and L.L. Price (1987), The Market Maven:A Diffuser of Marketplace Information. Journal of Marketing, 51(1), 83--97.Google ScholarCross Ref
- Foster, A.D. and M.R. Rosenzweig (1995), Learning by Doing and Learning from Others: Human Capital and Technical Change in Agriculture. Journal of Political Economy, 103(6), 1176--1209.Google ScholarCross Ref
- Galeotti, A., and S. Goyal (2009), Influencing the Influencers: a Theory of Strategic Diffusion,Rand Journal of Economics, 40, 3,Google Scholar
- Godes D. and D. Mayzlin (2004), Using Online Conversations to Study Word of Mouth Communication. Marketing Science, 23(4), 545--560. Google ScholarDigital Library
- Granovetter, M. (1978), Threshold Models of Collective Behavior, American Journal of Sociology,83, 6, 1420--1443.Google ScholarCross Ref
- Grossman, G. and C. Shapiro (1984), Informative Advertising with Differentiated Products. Review of Economic Studies, 51,63--82.Google ScholarCross Ref
- Heidari, H. (2012),A Note on the Competitive Contagion Problem.Personal communication.Google Scholar
- Koutsoupias, E., and C. H. Papadimitriou (1999), Worst-case Equilibria, STACS. Google ScholarDigital Library
- Kempe, D., J. Kleinberg, E. Tardos. (2003), Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining. Google ScholarDigital Library
- Kempe, D., J. Kleinberg, E. Tardos (2005), Influential Nodesin a Diffusion Model for Social Networks. Proc. 32nd International Colloquium on Automata,Languages and Programming (ICALP). Google ScholarDigital Library
- Mossel, E., Roch, S. (2007),Submodularity of Influence in Social Networks: From Local to Global. SIAM J. Computing, 39(6):2176--2188. Google ScholarDigital Library
- Reingen, P.H., B.L. Foster, J.J. Brown and S.B. Seidman (1984),Brand Congruence in Interpersonal Relations:A Social Network Analysis. The Journal of Consumer Research, 11(3), 771--783.Google ScholarCross Ref
- Roughgarden, T., Tardos, E. (2000),How Bad is Selfish Routing? Proc. 41st Annual IEEE Symposiumon Foundations of Computer Science (FOCS). Google ScholarDigital Library
- Skaperdas, S. (1996), Contest Success Functions, Economic Theory, 7, 2, 283--290.Google ScholarCross Ref
- Tullock, G. (1967), The Welfare Costs of Tariffs,Monopolies, and Theft, Western Economic Journal 5, 3,224--232.Google Scholar
- Tullock, G. (1980), Efficient Rent Seeking, Towards a theory of the rent-seeking society, edited by Buchanan, J., Tollison, R., and Tullock, G., Texas A&M University Press.Google Scholar
- Vetta, A. (2002), Nash Equilibria in Competitive Societies with Applications to Facility Location, Traffic Routing and Auctions. Proceedings of the 43rd Symposium on the Foundations of Computer Science (FOCS), 416--425. Google ScholarDigital Library
Index Terms
- Competitive contagion in networks
Recommendations
Core-competitive Auctions
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and ComputationOne of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is ...
Trading networks with price-setting agents
EC '07: Proceedings of the 8th ACM conference on Electronic commerceIn a wide range of markets, individual buyers and sellers often trade through intermediaries, who determine prices via strategic considerations. Typically, not all buyers and seller shave access to the same intermediaries, and they trade at ...
New models for competitive contagion
AAAI'14: Proceedings of the Twenty-Eighth AAAI Conference on Artificial IntelligenceIn this paper, we introduce and examine two new models for competitive contagion in networks, a game-theoretic generalization of the viral marketing problem. In our setting, firms compete to maximize their market share in a network of consumers whose ...
Comments