Pure strategies in security games

Abstract

In the past decades game theory allowed to model mathematically conflicts between groups of players, each with their own agenda, and found ways to apply them in real life situations. One of such applications, which has been studied heavily in recent years, are security games. Their primary purpose is to help find a way to distribute scarce resources of an entity whose job is to minimize the potential chances of a successful attack on a system which is under its care. The underlying assumption is that the second player, whose task is to launch an successful attack on the system, has sufficient time to observe the way in which the resources are used to find any patterns, or regularities. These games have been successfully applied to several real life situations like the way checkpoints and canine units are deployed on the LAX airport, the way air field marshals are scheduled to fly on commercial airplanes, or the way patrol routs are made in the Boston port. All of these works concentrate on considering mixed strategies, that is using a random element to decide how the defender manages his resources. While this approach is understandable in the case of one player managing all of the resources, it becomes less obvious in the situation where multiple defenders, with knowledge of other players priorities and limited means to coordinate are given. The problem of finding what can be said about pure strategies in such a situation is the goal of this thesis. This thesis provides a brief overview of what is currently known about modeling security games. The contribution is the following: a model for a multiple defender security game with sequential resource allocation is presented and the notions of reasonable behavior are described; a polynomial algorithm for finding a reasonable move and predicting other players decisions is presented. Moreover, it is proven that even if the actual play of the other players differs from what was predicted, the result will still satisfy the assumption of rationality of the players. Finally, to emulate coordination among the players, the model is expanded by adding an additional player, called the Overseer, whose goal is to ensure that a set of targets is protected by deciding the order in which all the other players commit. It is shown that deciding whether such a sequence of players exist for a set of targets of any size can be reduced to a set of one element in polynomial time. A partial result for which this problem is in P class is shown