More Web Proxy on the site http://driver.im/

research-article

Competitive contagion in networks

Authors:

Michael KearnsAuthors Info & Claims

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

Pages 759 - 774

https://doi.org/10.1145/2213977.2214046

Published: 19 May 2012 Publication History

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.

Supplementary Material

JPG File (stoc_9a_1.jpg)

Download
15.05 KB

MP4 File (stoc_9a_1.mp4)

Download
137.22 MB

References

[1]

Ballester, C., A. Calvo-Armengol, and Y. Zenou (2006),Who's Who in Networks. Wanted: The Key Player, Econometrica, 74, 5, 1403--1417.

[2]

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.

Digital Library

[3]

Borodin, A., Filmus, Y., Oren, J. (2010)Threshold Models for Competitive Influence in Social Networks, Proc. Workshop on Internet and Network Economics (WINE)

Digital Library

[4]

Butters, G. (1977), Equilibrium Distribution of Prices and Advertising, Review of Economic Studies, 44, 465--492.

[5]

Chasparis, G. and Shamma, J. (2010),Control of Preferences in Social Networks", 49th IEEE Conference on Decision and Control.

[6]

Coleman, J. (1966), Medical Innovation: A Diffusion Study.Second Edition, Bobbs-Merrill. New York.

[7]

Conley, T. and C. Udry (2010), Learning about a New Technology:Pineapple in Ghana. American Economic Review, .

[8]

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.

Digital Library

[9]

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)

Digital Library

[10]

Dubey, P. (1986), Inefficiency of Nash Equilibria. Mathematics of Operations Research., 11, 1, 1 V8.

Digital Library

[11]

Feick, L.F. and L.L. Price (1987), The Market Maven:A Diffuser of Marketplace Information. Journal of Marketing, 51(1), 83--97.

[12]

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.

[13]

Galeotti, A., and S. Goyal (2009), Influencing the Influencers: a Theory of Strategic Diffusion,Rand Journal of Economics, 40, 3,

[14]

Godes D. and D. Mayzlin (2004), Using Online Conversations to Study Word of Mouth Communication. Marketing Science, 23(4), 545--560.

Digital Library

[15]

Granovetter, M. (1978), Threshold Models of Collective Behavior, American Journal of Sociology,83, 6, 1420--1443.

[16]

Grossman, G. and C. Shapiro (1984), Informative Advertising with Differentiated Products. Review of Economic Studies, 51,63--82.

[17]

Heidari, H. (2012),A Note on the Competitive Contagion Problem.Personal communication.

[18]

Koutsoupias, E., and C. H. Papadimitriou (1999), Worst-case Equilibria, STACS.

Digital Library

[19]

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.

Digital Library

[20]

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).

Digital Library

[21]

Mossel, E., Roch, S. (2007),Submodularity of Influence in Social Networks: From Local to Global. SIAM J. Computing, 39(6):2176--2188.

Digital Library

[22]

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.

[23]

Roughgarden, T., Tardos, E. (2000),How Bad is Selfish Routing? Proc. 41st Annual IEEE Symposiumon Foundations of Computer Science (FOCS).

Digital Library

[24]

Skaperdas, S. (1996), Contest Success Functions, Economic Theory, 7, 2, 283--290.

[25]

Tullock, G. (1967), The Welfare Costs of Tariffs,Monopolies, and Theft, Western Economic Journal 5, 3,224--232.

[26]

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.

[27]

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.

Digital Library

Cited By

Zehmakan AZhou XZhang ZDastani MSichman JAlechina NDignum V(2024)Viral Marketing in Social Networks with Competing ProductsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663069(2047-2056)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663069
Fedrigo A(2024)Threshold Protocol Game on Graphs with Magic Square-Generalization LabelingsGames10.3390/g1506004215:6(42)Online publication date: 3-Dec-2024
https://doi.org/10.3390/g15060042
Fedrigo A(2024)End Behavior of the Threshold Protocol Game on Complete and Bipartite GraphsGames10.3390/g1506004115:6(41)Online publication date: 2-Dec-2024
https://doi.org/10.3390/g15060041
Show More Cited By

Index Terms

Competitive contagion in networks
1. Theory of computation

Recommendations

Core-competitive Auctions
EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation

One 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 commerce

In 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 Intelligence

In 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing

May 2012

1310 pages

ISBN:9781450312455

DOI:10.1145/2213977

General Chair:
Howard Karloff
AT&T Labs--Research
,
Program Chair:
Toniann Pitassi
University of Toronto

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'12

Sponsor:

SIGACT

STOC'12: Symposium on Theory of Computing

May 19 - 22, 2012

New York, New York, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
226
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)5

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zehmakan AZhou XZhang ZDastani MSichman JAlechina NDignum V(2024)Viral Marketing in Social Networks with Competing ProductsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663069(2047-2056)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663069
Fedrigo A(2024)Threshold Protocol Game on Graphs with Magic Square-Generalization LabelingsGames10.3390/g1506004215:6(42)Online publication date: 3-Dec-2024
https://doi.org/10.3390/g15060042
Fedrigo A(2024)End Behavior of the Threshold Protocol Game on Complete and Bipartite GraphsGames10.3390/g1506004115:6(41)Online publication date: 2-Dec-2024
https://doi.org/10.3390/g15060041
Archbold JClohessy SHerath DGriffiths NOyebode O(2024)An agent-based model of the spread of behavioural risk-factors for cardiovascular disease in city-scale populationsPLOS ONE10.1371/journal.pone.030305119:5(e0303051)Online publication date: 28-May-2024
https://doi.org/10.1371/journal.pone.0303051
Tsakas N(2024)Optimal influence under observational learningMathematical Social Sciences10.1016/j.mathsocsci.2024.01.011128(41-51)Online publication date: Mar-2024
https://doi.org/10.1016/j.mathsocsci.2024.01.011
Liao HBi SWu JZhang WZhou MMao RChen W(2023)Popularity Ratio Maximization: Surpassing Competitors through Influence PropagationProceedings of the ACM on Management of Data10.1145/35893091:2(1-26)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589309
Kishore AMachi LKuhlman CMachi DRavi S(2022)A Framework for Simulating Multiple Contagions Over Multiple NetworksComplex Networks & Their Applications X10.1007/978-3-030-93413-2_21(241-252)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-93413-2_21
Tsaras DTrimponias GNtaflos LPapadias D(2021)Collective influence maximization for multiple competing products with an awareness-to-influence modelProceedings of the VLDB Endowment10.14778/3450980.345098114:7(1124-1136)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.14778/3450980.3450981
Gelper Svan der Lans Rvan Bruggen G(2021)Competition for Attention in Online Social NetworksManagement Science10.1287/mnsc.2019.356467:2(1026-1047)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1287/mnsc.2019.3564
Zhang HChen YZhao H(2020)Evolutionary information dynamics over social networks: a reviewInternational Journal of Crowd Science10.1108/IJCS-09-2019-00264:1(45-59)Online publication date: 11-Jan-2020
https://doi.org/10.1108/IJCS-09-2019-0026
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents