Skip to main content

Research Repository

Advanced Search

Connected Subgraph Defense Games

Akrida, Eleni C.; Deligkas, Argyrios; Melissourgos, Themistoklis; Spirakis, Paul G.

Connected Subgraph Defense Games Thumbnail


Argyrios Deligkas

Themistoklis Melissourgos

Paul G. Spirakis


We study a security game over a network played between a defender and k attackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. [11]. We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide characterizations of the Nash equilibria of this game and defense-optimal networks. This allows us to show that the equilibria of the game coincide independently from the coordination or not of the attackers. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs.


Akrida, E. C., Deligkas, A., Melissourgos, T., & Spirakis, P. G. (2019). Connected Subgraph Defense Games. In Algorithmic Game Theory (216-236). Springer Verlag.

Online Publication Date Sep 16, 2019
Publication Date 2019
Deposit Date Jun 20, 2020
Publicly Available Date Oct 26, 2021
Publisher Springer Verlag
Pages 216-236
Series Title Lecture Notes in Computer Science
Series Number 11801
Book Title Algorithmic Game Theory
ISBN 9783030304720


Accepted Book Chapter (460 Kb)

Copyright Statement
The final authenticated version is available online at

You might also like

Downloadable Citations