Inoculation Strategies for Bounded Degree Graphs

作     者：DiCicco, Mason Poskanzer, Henry Reichman, Daniel 

作者机构：Computer Science Department Worcester Polytechnic Institute United States 

出 版 物：《SSRN》 

年 卷 期：2024年

核心收录：

主　　题：Undirected 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(Formula presented) 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 Ω(Formula presented). 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. © 2024, The Authors. All rights reserved.