Network disconnection games: A game theoretic approach to checkpoint evaluation in networks

Abstract

We study a Network Security question that consists of learning where are the most important checkpoints to intercept an adversary traveling from an origin to a destination. For that we define a cooperative game where every player controls an arc, and is able to place a checkpoint on it. We assume that the adversary is trying to travel from s to t. If the adversary crosses a checkpoint there is no certainty that he will be detected, therefore the value of a coalition should reflect the number of checkpoints, in the coalition, that the adversary has to cross (the more, the better). This suggests defining the value of a coalition S as the maximum number of disjoint st-cuts included in S; this is a lower bound for the number of checkpoints in S that the adversary has to cross. The adversary can choose any shortest path (minimum cardinality) from s to t, so in any particular coalition one cannot know the exact number of checkpoints that he will cross, and thus we propose to work with a lower bound instead. We give a polynomial combinatorial algorithm for computing the nucleolus of this game. The nucleolus is an allocation of resources to each arc that reflects the contribution of each checkpoint to the common objective of detecting the adversary. The larger values in the nucleolus indicate the more important locations.