Inoculation strategies for bounded degree graphs

We study the inoculation game, 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 Θ ( n ) . Our main result is a tight upper bound of O ( n Δ ) on the PoA, where Δ is the maximum degree of the graph. Indeed, we provide constructions of graphs with maximum degree Δ for which the PoA is Ω ( n Δ ) . 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.