Strategic monitor placement against malicious flows

Security Games have been widely adopted to model scenarios in which one player, the Defender, has to decide how to deploy her resources to minimize the loss that can be caused by an attack performed by another player, the Attacker, aiming at maximizing such loss. In the present paper, we focus on scenarios in which the Defender has lexicographic-like preferences on the targets, being primarily interested in defending the integrity of a subset of the targets and, only secondarily, to reduce the amount of the other damaged targets. Our central motivation for studying this problem comes from the need to reduce the impact of malicious flows in networks, that can be either physical, like cities, or virtual, e.g., social networks. In this work, we introduce a new class of security games to model these scenarios, characterizing it and proving the NP-hardness of computing a leader-follower equilibrium, which is the most appropriate solution concept for this setting. To compute such an equilibrium, we then provide an exact exponential-time algorithm, capable of exploiting the topological properties of the network. Finally, we show that, with opportune optimizations, this algorithm can work efficiently even on network of 10000 nodes.