Document Open Access Logo

The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game

Authors Laura Schmid , Krishnendu Chatterjee, Stefan Schmid

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.21.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Laura Schmid
  • IST Austria, Klosterneuburg, Austria
Krishnendu Chatterjee
  • IST Austria, Klosterneuburg, Austria
Stefan Schmid
  • Faculty of Computer Science, University of Vienna, Austria

Funding

  • Chatterjee, Krishnendu: Austrian Science Fund (FWF) NFN Grant S11407-N23 RiSE/ SHINE

Cite AsGet BibTex

Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.21

Abstract

The Price of Anarchy (PoA) is a well-established game-theoretic concept to shed light on coordination issues arising in open distributed systems. Leaving agents to selfishly optimize comes with the risk of ending up in sub-optimal states (in terms of performance and/or costs), compared to a centralized system design. However, the PoA relies on strong assumptions about agents' rationality (e.g., resources and information) and interactions, whereas in many distributed systems agents interact locally with bounded resources. They do so repeatedly over time (in contrast to "one-shot games"), and their strategies may evolve. Using a more realistic evolutionary game model, this paper introduces a realized evolutionary Price of Anarchy (ePoA). The ePoA allows an exploration of equilibrium selection in dynamic distributed systems with multiple equilibria, based on local interactions of simple memoryless agents. Considering a fundamental game related to virus propagation on networks, we present analytical bounds on the ePoA in basic network topologies and for different strategy update dynamics. In particular, deriving stationary distributions of the stochastic evolutionary process, we find that the Nash equilibria are not always the most abundant states, and that different processes can feature significant off-equilibrium behavior, leading to a significantly higher ePoA compared to the PoA studied traditionally in the literature.

Subject Classification

ACM Subject Classification
  • Theory of computation → Solution concepts in game theory
  • Theory of computation → Network games
  • Networks → Network algorithms
Keywords
  • Evolutionary Games
  • Virus Propagation
  • Price of Anarchy
  • Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Benjamin Allen and Martin A Nowak. Games on graphs. EMS surveys in mathematical sciences, 1(1):113-151, 2014. Google Scholar
  2. James Aspnes, Kevin Chang, and Aleksandr Yampolskiy. Inoculation Strategies for Victims of Viruses and the Sum-of-squares Partition Problem. In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 43-52, Philadelphia, PA, USA, 2005. Google Scholar
  3. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Locality-based Network Creation Games. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '14, pages 277-286, New York, NY, USA, 2014. ACM. Google Scholar
  4. Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, learning, and games. Cambridge university press, 2006. Google Scholar
  5. Krishnendu Chatterjee and Thomas A Henzinger. A survey of stochastic ω-regular games. Journal of Computer and System Sciences, 78(2):394-413, 2012. Google Scholar
  6. Christine Chung, Katrina Ligett, Kirk Pruhs, and Aaron Roth. The price of stochastic anarchy. In International Symposium on Algorithmic Game Theory, pages 303-314. Springer, 2008. Google Scholar
  7. Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H Papadimitriou, and Scott Shenker. On a network creation game. In Proc. 22nd annual symposium on Principles of distributed computing (PODC), pages 347-351. ACM, 2003. Google Scholar
  8. Chris Fleizach, Michael Liljenstam, Per Johansson, Geoffrey M Voelker, and Andras Mehes. Can you infect me now?: malware propagation in mobile phone networks. In Proceedings of the 2007 ACM workshop on Recurring malcode, pages 61-68. ACM, 2007. Google Scholar
  9. Drew Fudenberg and Lorens A. Imhof. Monotone imitation dynamics in large populations. Journal of Economic Theory, 140(1):229-245, 2008. Google Scholar
  10. Drew Fudenberg, Martin A Nowak, Christine Taylor, and Lorens A Imhof. Evolutionary game dynamics in finite populations with strong selection and weak mutation. Theoretical population biology, 70(3):352-363, 2006. Google Scholar
  11. Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127-1150, 2000. Google Scholar
  12. Josef Hofbauer and William H Sandholm. On the global convergence of stochastic fictitious play. Econometrica, 70(6):2265-2294, 2002. Google Scholar
  13. Josef Hofbauer and Karl Sigmund. Evolutionary games and population dynamics. Cambridge university press, 1998. Google Scholar
  14. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual Symposium on Theoretical Aspects of Computer Science (STOC), pages 404-413. Springer, 1999. Google Scholar
  15. Erez Lieberman, Christoph Hauert, and Martin A Nowak. Evolutionary dynamics on graphs. Nature, 433(7023):312, 2005. Google Scholar
  16. Thomas Locher, Patrick Moor, Stefan Schmid, and Roger Wattenhofer. Free Riding in BitTorrent is Cheap. In Proc. 5th Workshop on Hot Topics in Networks (HotNets), pages 85-90, 2006. Google Scholar
  17. Swarup Mohalik and Igor Walukiewicz. Distributed Games. In FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, pages 338-351. Springer, 2003. Google Scholar
  18. Martin A. Nowak. Evolutionary Dynamics, pages 123-143. Harvard University Press, 2006. Google Scholar
  19. Amir Pneuli and Roni Rosner. Distributed reactive systems are hard to synthesize. In Proc. 31st Annual Symposium on Foundations of Computer Science (FOCS), pages 746-757, 1990. Google Scholar
  20. Tim Roughgarden. The price of anarchy in games of incomplete information. ACM Transactions on Economics and Computation (TEAC), 3(1):6, 2015. Google Scholar
  21. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236-259, 2002. Google Scholar
  22. Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game. arXiv preprint arXiv:1906.00110, 2019. Google Scholar
  23. Satinder Singh, Vishal Soni, and Michael Wellman. Computing approximate Bayes-Nash equilibria in tree-games of incomplete information. In Proc. 5th ACM conference on Electronic Commerce (EC), pages 81-90. ACM, 2004. Google Scholar
  24. J Maynard Smith and George R Price. The logic of animal conflict. Nature, 246(5427):15, 1973. Google Scholar
  25. John Maynard Smith. Evolution and the Theory of Games. In Did Darwin Get It Right?, pages 202-215. Springer, 1988. Google Scholar
  26. Christine Taylor, Drew Fudenberg, Akira Sasaki, and Martin A Nowak. Evolutionary game dynamics in finite populations. Bulletin of mathematical biology, 66(6):1621-1644, 2004. Google Scholar
  27. Arne Traulsen, Martin A. Nowak, and Jorge M. Pacheco. Stochastic dynamics of invasion and fixation. Phys. Rev. E, 74:011909, July 2006. Google Scholar
  28. Arne Traulsen, Noam Shoresh, and Martin A Nowak. Analytical results for individual and group selection of any intensity. Bulletin of mathematical biology, 70(5):1410, 2008. Google Scholar
  29. Jörgen W Weibull. Evolutionary game theory. MIT press, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact