TY - GEN
T1 - Better vaccination strategies for better people
AU - Chen, Po-An
AU - David, Mary
AU - Kempe, David
PY - 2010
Y1 - 2010
N2 - In this paper, we study the vaccination of graphs against the outbreak of infectious diseases, in the following natural model generalizing a model by Aspnes et al.: An infectious disease breaks out at a random node of the graph and propagates along the edges of the graph. Vaccinated nodes cannot be infected, nor pass on the infection, whereas all other nodes do. The decisions on which nodes get vaccinated must be made before the random outbreak location is known. There is a cost associated with vaccination and a different cost with getting infected. In this model, we provide two results. First, we improve the approximation guarantee for finding the best vaccination strategy from O(log1.5 n) to O(log z) (where z is the support size of the outbreak distribution), by rounding a natural linear program with region-growing techniques. Second, we analyze the impact of autonomy on the part of the nodes: while a benevolent authority may suggest which nodes should be vaccinated, nodes may opt out after being chosen. We analyze the "Price of Opting Out" in this sense under partially altruistic behavior. Individuals base their decisions on their own cost and the societal cost, the latter scaled by some factor β. If the altruism parameter is β=0, it is known that the Price of Anarchy and Price of Stability can be Θ(n). We show that with positive altruism, Nash Equilibria may not exist, but the Price of Opting Out is at most 1/β (whereas the Price of Anarchy can remain at Θ(n)).
AB - In this paper, we study the vaccination of graphs against the outbreak of infectious diseases, in the following natural model generalizing a model by Aspnes et al.: An infectious disease breaks out at a random node of the graph and propagates along the edges of the graph. Vaccinated nodes cannot be infected, nor pass on the infection, whereas all other nodes do. The decisions on which nodes get vaccinated must be made before the random outbreak location is known. There is a cost associated with vaccination and a different cost with getting infected. In this model, we provide two results. First, we improve the approximation guarantee for finding the best vaccination strategy from O(log1.5 n) to O(log z) (where z is the support size of the outbreak distribution), by rounding a natural linear program with region-growing techniques. Second, we analyze the impact of autonomy on the part of the nodes: while a benevolent authority may suggest which nodes should be vaccinated, nodes may opt out after being chosen. We analyze the "Price of Opting Out" in this sense under partially altruistic behavior. Individuals base their decisions on their own cost and the societal cost, the latter scaled by some factor β. If the altruism parameter is β=0, it is known that the Price of Anarchy and Price of Stability can be Θ(n). We show that with positive altruism, Nash Equilibria may not exist, but the Price of Opting Out is at most 1/β (whereas the Price of Anarchy can remain at Θ(n)).
KW - altruism
KW - anarchy
KW - approximation
KW - inoculation
KW - selfishness
KW - stability
KW - vaccination
UR - http://www.scopus.com/inward/record.url?scp=77954708173&partnerID=8YFLogxK
U2 - 10.1145/1807342.1807370
DO - 10.1145/1807342.1807370
M3 - Conference contribution
AN - SCOPUS:77954708173
SN - 9781605588223
T3 - Proceedings of the ACM Conference on Electronic Commerce
SP - 179
EP - 187
BT - EC'10 - Proceedings of the 2010 ACM Conference on Electronic Commerce
T2 - 11th ACM Conference on Electronic Commerce, EC'10
Y2 - 7 June 2010 through 11 June 2010
ER -