Full text  Click to download. 
Citation  In Proc. of the ACMSIAM Symposium on Discrete Algorithms (SODA 05), pp. 43  52.

Authors  James Aspnes
Kevin Chang Aleksandr Yampolskiy 
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 antivirus software at some known cost C, or risk infection and a loss of 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 \theta(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 NPhard to compute such a social optimum, we show that the problem can be reduced to a previously unconsidered combinatorial problem that we call the sumofsquares 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^2 n) giving the same approximation ratio for the inoculation game.