Security Games

Security is one of the major societal concerns. Important infrastructure like airports, trains, digital networks, or banks must be protected against unpredictable events and intruders. Since security resources are limited, it is impossible to surveil all potential targets 24/7. The available resources must be deployed selectively, raising the question of how to utilize them optimally.

Game Theory

Game theory studies interactive decision-making. A game is a situation where the outcome depends on the choices of intelligent decision-makers, called players. Security games are played by two players, Defender and Attacker, where the Defender commits to a certain defending strategy and the Attacker strives to maximize the damage by exploiting the best attack opportunities. The instruments of game theory provide rigorous methods for constructing optimal defending strategies achieving the best possible protection.

Patrolling Games

Patrolling games are a special type of security games where a mobile Defender moves among vulnerable targets and aims to detect possible ongoing intrusions initiated by the Attacker. As an example, consider a public transport inspector operating in a subway, a security guard at an airport terminal, or a drone patrolling a military base. The task is to construct a moving strategy for the Defender minimizing the expected damage caused by the Attacker.

What We Do

Formal Methods

We construct appropriate formal models for real-world patrolling scenarios.
We identify classes of Defender’s strategies that are powerful enough to achieve a good protection and, at the same time, are algorithmically tractable.
We study fundamental game-theoretic questions such as the existence and type of optimal/suboptimal strategies. We analyze the complexity of the associated decision problems.

Algorithms & Experiments

We develop algorithms synthesizing high-quality Defender’s strategies in real-world-scale scenarios in reasonable time on customary hardware.
We combine the methods of linear programming, differentiable programming, and also stochastic programming.