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-76
Booktitle Lecture Notes in Computer Science
Year published 2005
Month November
Pages 969-978
DOI 10.1007/11600930_98
Consider a network vulnerable to viral infection. The system security software can guarantee safety only to a limited part of the network. Such limitations result from economy costs or processing costs. The problem raised is to which part of the network the security software should be installed, so that to secure as much as possible the network. 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. Each attacker player chooses a node of the graph (or a set of them, via a probability distribution) to infect. The protector player chooses independently, in a basic case of the problem, a simple path or an edge of the graph (or a set of them, via a probability distribution) and cleans this part of the network from attackers. Each attacker wishes to maximize the probability of escaping its cleaning by the protector. In contrast, the protector aims at maximizing the expected number of cleaned attackers. We call the two games obtained from the two basic cases considered, as the Path and the Edge model, respectively. For these two games, we are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. We obtain the following results: • The problem of existence of a pure Nash equilibrium is NP-complete for the Path model. This opposed to that, no instance of the Edge model possesses a pure Nash equilibrium, proved in [7]. • In [7] a characterization of mixed Nash equilibria for the Edge model is provided. However, that characterization only implies an exponential time algorithm for the general case. Here, combining it with clever exploration of properties of various practical families of graphs, we compute, in polynomial time, mixed Nash equilibria on corresponding graph instances. These graph families include, regular graphs, graphs that can be decomposed, in polynomially time, into vertex disjoint r-regular subgraphs, graphs with perfect matchings and trees. • We utilize the notion of social cost [6] for measuring system performance on such scenario; here is defined to be the utility of the protector. We prove that the corresponding Price of Anarchy in any mixed Nash equilibria of the game is upper and lower bounded by a linear function of the number of vertices of the graph.
Mavronicolas, Marios
Papadopoulou, Viki
Philippou, Anna
Spirakis, Paul
WINE.pdf (main file)
Publication ID628