research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleA Graph-Theoretic Network Security Game
Bibtex cite IDRACTI-RU1-2005-42
Booktitle 1st Workshop on Internet and Network Economics (WINE 2005)
Year published 2005
Month December
Volume 1
Number 4
Pages 969-978
Keywords graph theory; Nash equilibria; network security games; viral infections.
Consider a network vulnerable to viral infection, where the security software can guarantee safety only to a limited part of it. We model this practical network scenario as a non-cooperative multi-player game on a graph, with two kinds of players, a set of attackers and a protector player, representing the viruses and the system security software, respectively. We are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. We obtain the following results: for certain families of graphs, mixed Nash equilibria can be computed in polynomially time. These families include, among others, regular graphs, graphs with perfect matchings and trees. The corresponding price of anarchy for any mixed Nash equilibria of the game is upper and lower bounded by a linear function of the number of vertices of the graph. (We define the price of anarchy to reflect the utility of the protector). Finally, we introduce a generalised version of the game. We show that the existence problem of pure Nash equilibria here is NP complete.
Mavronicolas, Marios
Papadopoulou, Viki
Philippou, Anna
Spirakis, Paul
fulltext.pdf (main file)
Publication ID356