research-article

Better vaccination strategies for better people

Authors:

David KempeAuthors Info & Claims

EC '10: Proceedings of the 11th ACM conference on Electronic commerce

Pages 179 - 188

https://doi.org/10.1145/1807342.1807370

Published: 07 June 2010 Publication History

Abstract

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(log^1.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)).

References

[1]

Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy. Approximability of the firefighter problem: Computing cuts over time. In Proc. 20th Intl. Symp. on Algorithms and Computation, pages 974--983, 2009.

Digital Library

[2]

Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Thomas Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. In Proc. 45th IEEE Symp. on Foundations of Computer Science, pages 295--304, 2004.

Digital Library

[3]

Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. In Proc. 35th ACM Symp. on Theory of Computing, 2004.

Digital Library

[4]

James Aspnes, Kevin L. Chang, and Alexksandr Yamposlkiy. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. Journal of Computer and System Sciences, 72(6):1077--1093, 2006.

Digital Library

[5]

Albert-László Barabási, Réka Albert, and Hawoong Jeong. Mean-field theory for scale-free random networks. Physica A, 272:173--187, 1999.

[6]

P. Chen and D. Kempe. Altruism and selfishness in traffic routing. In Proc. 9th ACM Conf. on Electronic Commerce, pages 140--149, 2008.

Digital Library

[7]

Fan Chung. Spectral Graph Theory. American Mathematical Society, 1997.

[8]

Zoltán Dezső and Albert-László Barabási. Halting viruses in scale-free networks. Physical Review E, 65, 2002.

[9]

Josep Díaz, Dieter Mitsche, Navin Rustagi, and Jared Saia. On the power of mediators. In Proc. 5th Workshop on Internet and Network Economics (WINE), pages 455--462, 2009.

Digital Library

[10]

Guy Even, Joseph Naor, Satish Rao, and Baruch Schieber. Fast approximate graph partitioning algorithms. SIAM J. on Computing, 28(6):2187--2214, 1999.

Digital Library

[11]

Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. on Computing, 25:235--251, 1996.

Digital Library

[12]

Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Multiway cuts in node weighted graphs. Journal of Algorithms, 50:49--61, 2004.

Digital Library

[13]

Michel X. Goemans, Vahab Mirrokni, and Adrian Vetta. Sink equilibria and convergence. In Proc. 46th IEEE Symp. on Foundations of Computer Science, pages 142--154, 2005.

Digital Library

[14]

A. Hayrapetyan, D. Kempe, M. Pál, and Z. Svitkina. Unbalanced graph cuts. In Proc. 13th European Symp. on Algorithms, pages 191--202, 2005.

Digital Library

[15]

Matthew O. Jackson. Social and Economic Networks. Princeton University Press, 2008.

Digital Library

[16]

Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Proc. 17th Annual Symp. on Theoretical Aspects of Computer Science, pages 404--413. Springer, 1999.

Digital Library

[17]

Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, and Eli Upfal. Stochastic models for the web graph. In Proc. 41st IEEE Symp. on Foundations of Computer Science, pages 57--65, 2000.

Digital Library

[18]

John Ledyard. Public goods: A survey of experimental resesarch. In J. Kagel and A. Roth, editors, Handbook of Experimental Economics, pages 111--194. Princeton University Press, 1997.

[19]

David Levine. Modeling altruism and spitefulness in experiments. Review of Economic Dynamics, 1:593--622, 1998.

[20]

Dominic Meier, Yvonne Anne Oswald, Stefan Schmid, and Roger Wattenhofer. On the windfall of friendship: Inoculation strategies on social networks. In Proc. 9th ACM Conf. on Electronic Commerce, pages 294--301, 2008.

Digital Library

[21]

Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer. When selfish meets evil: Byzantine players in a virus inoculation game. In Proc. 25th ACM Symp. on Principles of Distributed Computing, pages 35--44, 2006.

Digital Library

[22]

Zoya Svitkina and Eva Tardos. Min-max multiway cut. In Proc. 7th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2004.

[23]

Duncan Watts and Steven Strogatz. Collective dynamics of small-world networks. Nature, 393:440--442, 1998.

Cited By

DiCicco MPoskanzer HReichman D(2025)Inoculation strategies for bounded degree graphsTheoretical Computer Science10.1016/j.tcs.2025.115142(115142)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2025.115142
Sun LRao YWu LZhang XLan YNazir A(2023)Fighting False Information from Propagation Process: A SurveyACM Computing Surveys10.1145/356338855:10(1-38)Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1145/3563388
Cordasco GGargano LRescigno A(2023)Immunization in the Threshold Model: A Parameterized Complexity StudyAlgorithmica10.1007/s00453-023-01118-y85:11(3376-3405)Online publication date: 7-Apr-2023
https://doi.org/10.1007/s00453-023-01118-y
Show More Cited By

Index Terms

Better vaccination strategies for better people
1. Applied computing
  1. Physical sciences and engineering
    1. Mathematics and statistics
2. Mathematics of computing
  1. Discrete mathematics

Recommendations

Toward optimal vaccination strategies for probabilistic models
WWW '11: Proceedings of the 20th international conference companion on World wide web

Epidemic outbreaks such as the recent H1N1 influenza show how susceptible large communities are toward the spread of such outbreaks. The occurrence of a widespread disease transmission raises the question of vaccination strategies that are appropriate ...
Altruism, selfishness, and spite in traffic routing
EC '08: Proceedings of the 9th ACM conference on Electronic commerce

In this paper, we study the price of anarchy of traffic routing, under the assumption that users are partially altruistic or spiteful. We model such behavior by positing that the "cost" perceived by a user is a linear combination of the actual latency ...
Altruism and Its Impact on the Price of Anarchy

We study the inefficiency of equilibria for congestion games when players are (partially) altruistic. We model altruistic behavior by assuming that player i's perceived cost is a convex combination of α_i times his direct cost and α_i times the social ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '10: Proceedings of the 11th ACM conference on Electronic commerce

June 2010

400 pages

ISBN:9781605588223

DOI:10.1145/1807342

General Chair:
David C. Parkes
Harvard University, USA
,
Program Chairs:
Chrysanthos Dellarocas
Boston University, USA
,
Moshe Tennenholtz
Technion and Microsoft Israel R&D Center

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '10

Sponsor:

SIGecom

EC '10: ACM Conference on Electronic Commerce

June 7 - 11, 2010

Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
363
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

DiCicco MPoskanzer HReichman D(2025)Inoculation strategies for bounded degree graphsTheoretical Computer Science10.1016/j.tcs.2025.115142(115142)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2025.115142
Sun LRao YWu LZhang XLan YNazir A(2023)Fighting False Information from Propagation Process: A SurveyACM Computing Surveys10.1145/356338855:10(1-38)Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1145/3563388
Cordasco GGargano LRescigno A(2023)Immunization in the Threshold Model: A Parameterized Complexity StudyAlgorithmica10.1007/s00453-023-01118-y85:11(3376-3405)Online publication date: 7-Apr-2023
https://doi.org/10.1007/s00453-023-01118-y
Arghal RBidokhti SSarkar S(2022)Optimal Capacity-Constrained COVID-19 Vaccination for Heterogeneous Populations2022 IEEE 61st Conference on Decision and Control (CDC)10.1109/CDC51059.2022.9992682(5620-5626)Online publication date: 6-Dec-2022
https://doi.org/10.1109/CDC51059.2022.9992682
Yang YChen PLee YFanchiang Y(2022)On the firefighter problem with spreading vaccination for maximizing the number of saved nodes: the IP model and LP rounding algorithmsOptimization Letters10.1007/s11590-022-01963-w17:8(1853-1872)Online publication date: 30-Dec-2022
https://doi.org/10.1007/s11590-022-01963-w
Cordasco GGargano LRescigno A(2022)Parameterized Complexity of Immunization in the Threshold ModelWALCOM: Algorithms and Computation10.1007/978-3-030-96731-4_23(275-287)Online publication date: 16-Mar-2022
https://doi.org/10.1007/978-3-030-96731-4_23
Yu SDignum FLomuscio AEndriss UNowé A(2021)Design and Analysis of Networks under Strategic BehaviorProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464261(1848-1849)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464261
Cordasco GGargano LRescigno A(2021)Vertex Separation in Networks2021 Eighth International Conference on Social Network Analysis, Management and Security (SNAMS)10.1109/SNAMS53716.2021.9732127(1-8)Online publication date: 6-Dec-2021
https://doi.org/10.1109/SNAMS53716.2021.9732127
Zhang LXia JCheng FQiu JZhang X(2020)Multi-Objective Optimization of Critical Node Detection Based on Cascade Model in Complex NetworksIEEE Transactions on Network Science and Engineering10.1109/TNSE.2020.29729807:3(2052-2066)Online publication date: 1-Jul-2020
https://doi.org/10.1109/TNSE.2020.2972980
Li JPardalos PXin BChen J(2019)The bi-objective critical node detection problem with minimum pairwise connectivity and cost: theory and algorithmsSoft Computing10.1007/s00500-019-03824-8Online publication date: 14-Feb-2019
https://doi.org/10.1007/s00500-019-03824-8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten