About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
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.