Past work in security games has mainly focused on the problem static resource allocation; how to optimally deploy a given fixed team of resources. My research aims to address the challenge of integrating operational planning into security games, where resources are heterogeneous and the defender is tasked with optimizing over both the investment into these resources, as well as their deployment in the field. This allows the defender to design more adaptive strategies, reason about the efficiency of their use of these resources as well as their effectiveness in their deployment. This thesis explores the challenges in integrating these two optimization problems in both the single stage and multi-stage setting and provides a formal model of this problem, which we refer to as the Simultaneous Optimization of Resource Teams and Tactics (SORT) as a new fundamental research problem in security games that combines strategic and tactical decision making. The main contributions of this work are solution methods to the SORT problem under various settings as well as exploring various types of tradeoffs that can arise in these settings. These include managing budget for investment in resources as well as capacity constraints on use of resources. My work addresses scenarios when the tactical decision problem (optimal deployment) is difficult, and thus evaluating the performance of any given team is difficult. Additionally, I address domains where we are tasked with making repeated strategic level decision and where, due to changing domain features, fluctuations in time dependent processes or the realization of uncertain parameters in the problem, it becomes necessary to re-evaluate and adapt to new information.

We consider the problem of allocating scarce security resources among heterogeneous targets to thwart a possible attack. It is well known that deterministic solutions to this problem being highly predictable are severely suboptimal. To mitigate this predictability, the game-theoretic security game model was proposed which randomizes over pure (deterministic) strategies, causing confusion in the adversary. Unfortunately, such mixed strategies typically involve randomizing over a large number of strategies, requiring security personnel to be familiar with numerous protocols, making them hard to operationalize. Motivated by these practical considerations, we propose an easy to use approach for computing strategies that are easy to operationalize and that bridge the gap between the static solution and the optimal mixed strategy. These strategies only randomize over an optimally chosen subset of pure strategies whose cardinality is selected by the defender, enabling them to conveniently tune the trade-off between ease of operationalization and efficiency using a single design parameter. We show that the problem of computing such operationalizable strategies is NP-hard, formulate it as a mixed-integer optimization problem, provide an algorithm for computing epsilon-optimal equilibria, and an efficient heuristic. We evaluate the performance of our approach on the problem of screening for threats at airport checkpoints and show that the Price of Usability, i.e., the loss in optimality to obtain a strategy that is easier to operationalize, is typically not high.

We consider the problem of dynamically allocating screening resources of different efficacies (e.g., magnetic or X-ray imaging) at checkpoints (e.g., at airports or ports) to successfully avert an attack by one of the screenees. Previously, the Threat Screening Game model was introduced to address this problem under the assumption that screenee arrival times are perfectly known. In reality, arrival times are uncertain, which severely impedes the implementability and performance of this approach. We thus propose a novel framework for dynamic allocation of threat screening resources that explicitly accounts for uncertainty in the screenee arrival times. We model the problem as a multistage robust optimization problem and propose a tractable solution approach using compact linear decision rules combined with robust reformulation and constraint randomization. We perform extensive numerical experiments which showcase that our approach outperforms (a) exact solution methods in terms of tractability, while incurring only a very minor loss in optimality, and (b) methods that ignore uncertainty in terms of both feasibility and optimality.

Green security — protection of forests, fish and wildlife — is a critical problem in environmental sustainability. We focus on the problem of optimizing the defense of forests againstillegal logging, where often we are faced with the challenge of teaming up many different groups, from national police to forest guards to NGOs, each with differing capabilities and costs. This paper introduces a new, yet fundamental problem: SimultaneousOptimization of Resource Teams and Tactics (SORT). SORT contrasts with most previous game-theoretic research for green security — in particular based onsecurity games — that has solely focused on optimizing patrolling tactics, without consideration of team formation or coordination. We develop new models and scalable algorithms to apply SORT towards illegal logging in large forest areas. We evaluate our methods on a variety of synthetic examples, as well as a real-world case study using data from our on-going collaboration in Madagascar.