A Game on a Distributed Network∗

Consider a distributed information network with harmful procedures called attackers (e.g., viruses); each attacker uses a probability distribution to choose a node of the network to damage. Opponent to the attackers is the system protector scanning and cleaning from attackers some part of the network (e.g., an edge or a simple path), which it chooses independently using an-other probability distribution. Each attacker wishes to maximize the proba-bility of escaping its cleaning by the system protector; towards a conflicting objective, the system protector aims at maximizing the expected number of cleaned attackers. In [8, 9], we model this network scenario as a non-cooperative strategic game on graphs. We focus on two basic cases for the protector; where it may choose a single edge or a simple path of the network. The two games obtained are called as the Path and the Edge model, respec-tively. For these games, we are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. For the Edge model we obtain the following results: ∗This work was partially supported by the IST Programs of the European Union under contrac