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.

By: Mourad Baïou, Francisco Barahona

Published in: RC25638 in 2016


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .