research-article

On the windfall of friendship: inoculation strategies on social networks

Authors:

Yvonne Anne Oswald,

Roger WattenhoferAuthors Info & Claims

EC '08: Proceedings of the 9th ACM conference on Electronic commerce

Pages 294 - 301

https://doi.org/10.1145/1386790.1386836

Published: 08 July 2008 Publication History

Abstract

This paper studies a virus inoculation game on social networks. A framework is presented which allows the measuring of the windfall of friendship, i.e., how much players benefit if they care about the welfare of their direct neighbors in the social network graph compared to purely selfish environments. We analyze the corresponding equilibria and show that the computation of the worst and best Nash equilibrium is NP-hard. Intriguingly, even though the windfall of friendship can never be negative, the social welfare does not increase monotonically with the extent to which players care for each other. While these phenomena are known on an anecdotal level, our framework allows us to quantify these effects analytically.

References

[1]

J. Aspnes, K. Chang, and A. Yampolskiy. Inoculation Strategies for Victims of Viruses and the Sum-of-Squares Partition Problem. In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.

Digital Library

[2]

M. Babaioff, R. Kleinberg, and C. H. Papadimitriou. Congestion Games with Malicious Players. In Proc. 18th ACM Conference on Electronic Commerce (EC), 2007.

Digital Library

[3]

N. T. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Hafner Press, 1975.

[4]

R. Blundell, W. Newey, and T. Persson (Eds). Advances in Economics and Econometrics (Chapter 1: The Economics of Social Networks). 2006.

[5]

A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, andS. Shenker. On a Network Creation Game. In Proc. 22nd Annual Symposium on Principles of Distributed Computing (PODC), 2003.

Digital Library

[6]

J. Feigenbaum, C. H. Papadimitriou, and S. Shenker. Sharing the Cost of Multicast Transmissions. J. Comput. Syst. Sci., 63(1):21--41, 2001.

Digital Library

[7]

G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee. Self-Organization and Identification of Web Communities. Computer, 35(3):66--71, 2002.

Digital Library

[8]

C. Fleizach, M. Liljenstam, P. Johansson, G. M. Voelker, andA. Mehes. Can You Infect Me Now? Malware Propagation in Mobile Phone Networks. In Proc. 2007 ACM Workshop on Recurring Malcode (WORM), 2007.

Digital Library

[9]

P. Fraigniaud, C. Gavoille, and C. Paul. Eclecticism Shrinks Even Small Worlds. In Proc. 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), 2004.

Digital Library

[10]

J. C. Frauenthal. Mathematical Modeling in Epidemiology. Springer-Verlag, 1980.

[11]

M. R. Garey and D. S. Johnson. Computers and Intractability : A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979.

Digital Library

[12]

S. M. Kakade, M. Kearns, and L. E. Ortiz. Graphical Economics. In Proc. 17th Annual Conference on Learning Theory (COLT), 2004.

[13]

R. M. Karp. Reducibility Among Combinatorial Problems. Complexity of Computer Computations, pages 85--103, 1972.

[14]

M. Kearns, M. Littman, and S. Singh. Graphical Models for Game Theory. In Proc. Conference on Uncertainty in Artificial Intelligence (UAI), 2001.

Digital Library

[15]

J. O. Kephart and S. R. White. Measuring and Modeling Computer Virus Prevalence. In Proc. IEEE Symposium on Security and Privacy, 1993.

Digital Library

[16]

J. O. Kephart, S. R. White, and D. M. Chess. Computers and Epidemiology. IEEE Spectrum, 30(5):20--26, 1993.

Digital Library

[17]

J. Kleinberg. The Small-World Phenomenon: An Algorithmic Perspective. In Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000.

Digital Library

[18]

J. Kleinberg. Complex Networks and Decentralized Search Algorithms. In Proc. International Congress of Mathematicians (ICM), 2006.

[19]

J. Kleinberg. Algorithmic Game Theory. Chapter 24 : Cascading Behavior in Networks: Algorithmic and Economic Issues. N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Eds), Cambridge University Press, 2007.

[20]

J. Leskovec, L. A. Adamic, and B. A. Huberman. The Dynamics of Viral Marketing. ACM Transactions on the Web, 2007.

Digital Library

[21]

D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic Routing in Social Networks. In Proc. National Academy of Sciences, number 33, pages 11623--11628. National Acad Sciences, 2005.

[22]

G. S. Manku, M. Naor, and U. Wieder. Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks. In Proc. 36th ACM Symposium on Theory of Computing (STOC), 2004.

Digital Library

[23]

S. Milgram. The Small World Problem. Psychology Today, pages 60--67, 1967.

[24]

T. Moscibroda, S. Schmid, and R. Wattenhofer. On the Topologies Formed by Selfish Peers. In Proc. 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2006.

Digital Library

[25]

T. Moscibroda, S. Schmid, and R. Wattenhofer. When Selfish Meets Evil: Byzantine Players in a Virus Inoculation Game. In Proc. 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2006.

Digital Library

[26]

M. E. J. Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. Physical Review E, 69, 2004.

[27]

T. Roughgarden. Selfish Routing and the Price of Anarchy. MIT Press, 2005.

Digital Library

[28]

T. Roughgarden and Éva Tardos. How Bad is Selfish Routing? Journals of the ACM, 49(2):236--259, 2002.

Digital Library

[29]

C. Wang, J. C. Knight, and M. C. Elder. On Computer Viral Infection and the Effect of Immunization. In Proc. 16th Annual Computer Security Applications Conference (ACSAC), 2000.

Digital Library

Cited By

DiCicco MPoskanzer HReichman D(2025)Inoculation strategies for bounded degree graphsTheoretical Computer Science10.1016/j.tcs.2025.115142(115142)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2025.115142
Maiti ADey P(2024)On Binary Networked Public Goods Game with AltruismLATIN 2024: Theoretical Informatics10.1007/978-3-031-55601-2_19(289-303)Online publication date: 6-Mar-2024
https://doi.org/10.1007/978-3-031-55601-2_19
Li JDeng XCheng YPan YXia XYang ZXie JAgmon NAn BRicci AYeoh W(2023)Altruism, Collectivism and Egalitarianism: On a Variety of Prosocial Behaviors in Binary Networked Public Goods GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598691(609-624)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598691
Show More Cited By

Index Terms

On the windfall of friendship: inoculation strategies on social networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the Windfall and price of friendship: Inoculation strategies on social networks

This article investigates selfish behavior in games where players are embedded in a social context. A framework is presented which allows us to measure the Windfall of Friendship, i.e., how much players benefit (compared to purely selfish environments) ...
When selfish meets evil: byzantine players in a virus inoculation game
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing

Over the last years, game theory has provided great insights into the behavior of distributed systems by modeling the players as utility-maximizing agents. In particular, it has been shown that selfishness causes many systems to perform in a globally ...
On the efficiency of equilibria in generalized second price auctions
EC '11: Proceedings of the 12th ACM conference on Electronic commerce

In sponsored search auctions, advertisers compete for a number of available advertisement slots of different quality. The auctioneer decides the allocation of advertisers to slots using bids provided by them. Since the advertisers may act strategically ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '08: Proceedings of the 9th ACM conference on Electronic commerce

July 2008

332 pages

ISBN:9781605581699

DOI:10.1145/1386790

General Chair:
Lance Fortnow
Northwestern University, USA
,
Program Chairs:
John Riedl
University of Minnesota, USA
,
Tuomas Sandholm
Carnegie-Mellon University, USA

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '08

Sponsor:

EC '08: ACM Conference on Electronic Commerce

July 8 - 12, 2008

Il, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
374
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

DiCicco MPoskanzer HReichman D(2025)Inoculation strategies for bounded degree graphsTheoretical Computer Science10.1016/j.tcs.2025.115142(115142)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2025.115142
Maiti ADey P(2024)On Binary Networked Public Goods Game with AltruismLATIN 2024: Theoretical Informatics10.1007/978-3-031-55601-2_19(289-303)Online publication date: 6-Mar-2024
https://doi.org/10.1007/978-3-031-55601-2_19
Li JDeng XCheng YPan YXia XYang ZXie JAgmon NAn BRicci AYeoh W(2023)Altruism, Collectivism and Egalitarianism: On a Variety of Prosocial Behaviors in Binary Networked Public Goods GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598691(609-624)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598691
Cordasco GGargano LRescigno A(2023)Immunization in the Threshold Model: A Parameterized Complexity StudyAlgorithmica10.1007/s00453-023-01118-y85:11(3376-3405)Online publication date: 7-Apr-2023
https://doi.org/10.1007/s00453-023-01118-y
Olteanu AHumbert MHuguenin KHubaux J(2019)The (Co-)Location Sharing GameProceedings on Privacy Enhancing Technologies10.2478/popets-2019-00172019:2(5-25)Online publication date: 4-May-2019
https://doi.org/10.2478/popets-2019-0017
Meier DPignolet YSchmid SWattenhofer R(2019)On the Windfall and price of friendshipComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.bjp.2013.12.00462(221-236)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.bjp.2013.12.004
Huguenin KBilogrevic IMachado JMihaila SShokri RDacosta IHubaux J(2018)A Predictive Model for User Motivation and Utility Implications of Privacy-Protection Mechanisms in Location Check-InsIEEE Transactions on Mobile Computing10.1109/TMC.2017.274195817:4(760-774)Online publication date: 1-Apr-2018
https://doi.org/10.1109/TMC.2017.2741958
Yao QWu XZhang X(2015)Diffusion of Information in Mobile Social NetworksProceedings of the 2015 IEEE International Conference on Mobile Services10.1109/MobServ.2015.44(254-260)Online publication date: 27-Jun-2015
https://dl.acm.org/doi/10.1109/MobServ.2015.44
Humbert MAyday EHubaux JTelenti A(2015)On Non-cooperative Genomic PrivacyFinancial Cryptography and Data Security10.1007/978-3-662-47854-7_24(407-426)Online publication date: 16-Jul-2015
https://doi.org/10.1007/978-3-662-47854-7_24
Simpson MSrinivasan VThomo AJia YRokne JWu XEster MXu G(2014)Clearing contamination in large networksProceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.5555/3191835.3191920(425-428)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.5555/3191835.3191920
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.

Figures

Tables

Media

View Table of Conten