Inoculation strategies for bounded degree graphs

We analyze a game-theoretic abstraction of epidemic containment played on an undirected graph $G$: each player is associated with a node in $G$ and can either acquire protection from a contagious process or risk infection. After decisions are made, an infection starts at a random node $v$ and propagates through all unprotected nodes reachable from $v$. It is known that the price of anarchy (PoA) in $n$-node graphs can be as large as $\mathrm{\Theta }(n)$. Our main result is a tight bound of order $\sqrt{n\mathrm{\Delta }}$ on the PoA, where $\mathrm{\Delta }$ is the maximum degree of the graph. We also study additional factors that can reduce the PoA, such as higher thresholds for contagion and varying the costs of becoming infected vs. acquiring protection.