Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
DiCicco et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: