On the windfall of friendship: inoculation strategies on social networks

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: James Aspnes , Kevin Chang , Aleksandr Yampolskiy, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 2: Moshe Babaioff , Robert Kleinberg , Christos H. Papadimitriou, Congestion games with malicious players, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250926]
• 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: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 6: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 7: Gary William Flake , Steve Lawrence , C. Lee Giles , Frans M. Coetzee, Self-Organization and Identification of Web Communities, Computer, v.35 n.3, p.66-71, March 2002 [doi>10.1109/2.989932]
• 8: Chris Fleizach , Michael Liljenstam , Per Johansson , Geoffrey M. Voelker , Andras Mehes, Can you infect me now?: malware propagation in mobile phone networks, Proceedings of the 2007 ACM workshop on Recurring malcode, November 02-02, 2007, Alexandria, Virginia, USA [doi>10.1145/1314389.1314402]
• 9: Pierre Fraigniaud , Cyril Gavoille , Christophe Paul, Eclecticism shrinks even small worlds, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011793]
• 10: J. C. Frauenthal. Mathematical Modeling in Epidemiology. Springer-Verlag, 1980.
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 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: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 15: Jeffrey O. Kephart , Steve R. White, Measuring and Modeling Computer Virus Prevalence, Proceedings of the 1993 IEEE Symposium on Security and Privacy, p.2, May 24-26, 1993
• 16: Jeffrey O. Kephart , Steve R. White , David M. Chess, Computers and epidemiology, IEEE Spectrum, v.30 n.5, p.20-26, May 1993 [doi>10.1109/6.275061]
• 17: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 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: Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman, The dynamics of viral marketing, ACM Transactions on the Web (TWEB), v.1 n.1, p.5-es, May 2007 [doi>10.1145/1232722.1232727]
• 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: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 23: S. Milgram. The Small World Problem. Psychology Today, pages 60--67, 1967.
• 24: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, On the topologies formed by selfish peers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146403]
• 25: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, When selfish meets evil: byzantine players in a virus inoculation game, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146391]
• 26: M. E. J. Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. Physical Review E, 69, 2004.
• 27: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 28: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 29: Chenxi Wang , J. C. Knight , M. C. Elder, On computer viral infection and the effect of immunization, Proceedings of the 16th Annual Computer Security Applications Conference, p.246, December 11-15, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Economics, Human Factors, Security, Theory

Keywords:
equilibria, game theory, social networks, virus propagation, windfall of friendship