Network Disconnection Games

We study network security games arising from placing checkpoints on a set of arcs to intercept every path between two distinguished nodes s and t. First we study a two-person zero-sum game where one player, the attacker, chooses a set of arcs that intercepts every path from s to t, then a second player, the inspector, chooses an arc to inspect trying to find the attacker. We give combinatorial polynomial algorithms to find optimal strategies for both players. Here the Nash-equilibrium payoff gives a measure of the resilience of the network to this type of attack.

Then we study a study a cooperative game where every player controls an arc and is able to place a checkpoint on it. We also assume that there is an adversary trying to travel from s to t. The value of a coalition S is the maximum number of disjoint st-cuts included in S. This is the number of independent ways that a coalition can use to intercept every path between s and t. We assume that if the adversary crosses a checkpoint it will be detected with some probability, thus a coalition having different independent ways to intercept every st-path has a higher probability of success than a coalition that can intercept in only one way. We give polynomial combinatorial algorithms for testing membership to the core and for computing the nucleolus. This analysis shows which are the most important locations to put checkpoints.