Inoculation strategies for victims of viruses and the sum-of-squares partition problem

James Aspnes, Kevin Chang, and Aleksandr Yampolskiy. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. Journal of Computer and System Sciences, 72(6):1077–1093, September 2006. An ealier version appeared in Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2005, pp. 43–52. Available as YALEU/DCS/TR-1295, July 2004.

Abstract

We propose a simple game for modeling containment of the spread of viruses in a graph of n nodes. Each node must choose to either install anti-virus software at some known cost C, or risk infection and a loss L if a virus that starts at a random initial point in the graph can reach it without being stopped by some intermediate node. The goal of individual nodes is to minimize their individual expected cost. We prove many game theoretic properties of the model, including an easily-applied characterization of Nash equilibria, culminating in our showing that allowing selfish users to choose Nash equilibrium strategies is highly undesirable, because the price of anarchy is an unacceptable Θ(n) in the worst case. This shows in particular that a centralized solution can give a much better total cost than an equilibrium solution. Though it is NP-hard to compute such a social optimum, we show that the problem can be reduced to a previously unconsidered combinatorial problem that we call the sum-of-squares partition problem. Using a greedy algorithm based on sparse cuts, we show that this problem can be approximated to within a factor of O(log²n), giving the same approximation ratio for the inoculation game.

BibTeX

Download
@article(AspnesCY2006,
title="Inoculation strategies for victims of viruses and the sum-of-squares partition problem",
author="James Aspnes and Kevin Chang and Aleksandr Yampolskiy",
journal=jcss,
volume=72,
number=6,
pages={1077--1093},
month=sep,
year=2006,
)

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page