We consider the problem of monitoring a set of targets, using
scarce monitoring resources (e.g., sensors) that are subject to adversarial attacks. In particular, we propose a constant-sum Stackelberg game
in which a defender (leader) chooses among possible monitoring locations, each covering a subset of targets, while taking into account the
monitor failures induced by a resource-constrained attacker (follower).
In contrast to the previous Stackelberg security models in which the defender uses mixed strategies, here, the defender must commit to pure
strategies. This problem is highly intractable as both players’ strategy
sets are exponentially large. Thus, we propose a solution methodology
that automatically partitions the set of adversary’s strategies and maps
each subset to a coverage policy. These policies are such that they do
not overestimate the defender’s payoff. We show that the partitioning
problem can be reformulated exactly as a mixed-integer linear program
(MILP) of moderate size which can be solved with off-the-shelf solvers.
We demonstrate the effectiveness of our proposed approach in various
settings. In particular, we illustrate that even with few policies, we are
able to closely approximate the optimal solution and outperform the