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

- SODA 2005 proceedings version: PDF.
- Technical report: PDF.
- Journal version:
**PDF**.

## 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