A Graph-Theoretic Network Security Game

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 improv