Inoculation strategies for bounded degree graphs

In collaboration with Henry Poskanzer and Daniel Reichman

Abstract 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 \Theta(n). Our main result is a tight upper bound of O(\sqrt{n\Delta}) on the PoA, where \Delta is the maximum degree of the graph. Indeed, we provide constructions of graphs with maximum degree \Delta for which the PoA is \Omega(\sqrt{n\Delta}). 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.

Download paper here