Game theory applications in security
Creators: name: Yolmeh, Abdolmajid
Publisher: name: No Publisher Supplied
Year: 2021

description: In this dissertation, we study the applications of game theory in determining protection strategies for various infrastructures. The game models are played between a defender (she) and an adversary (he). The defender seeks to minimize the damage to the infrastructure network, while the adversary aims to maximize it. This dissertation is divided into two parts. In the first part, we consider the resource allocation game models, and in the second part, we study patrolling and search games.In the area of resource allocation games, we address some of the existing limitations in literature. One such limitation is that most of these models assume that the parameters of the game are either deterministic or follow a known distribution. Whereas in reality, some parameters of the game may be uncertain with no known distribution or distributional information about them may be unreliable. To this end, we study one-shot security games under uncertainty about target valuations. We propose a model in which both players use a robust approach to contend with the uncertainty of target valuations. We show that the Nash equilibrium for this model is of threshold type and develop closed-form solutions to characterize the equilibrium point. We then apply our model to a real case of assigning funds for security to 10 urban areas in the United States.Another limitation is the lack of models that address hierarchical decision making. Protecting infrastructures and their users against intentional attacks involves making both strategic and operational decisions in an organization's hierarchy. Although usually analyzed separately, these decisions influence each other. To address this issue, we develop a two-stage game model. In the first stage, the players make investment decisions and in the second stage, they decide which sites to defend/attack. We distinguish between two types of games that arise in the second stage: Maximal Damage game and Infiltration/Harassment game. We prove that the solution to this game under budget constraints is unique. In fact, when the second stage game is of Infiltration/Harassment type, the invest-defend game has a unique closed-form solution that is very intuitive. The results reveal that an increase in defense investments on a target site decreases the probability of both defending and attacking that target. However, an increase in attack investments increases the probability of both defending and attacking that target. Similarly, an increase in the defender's (attacker's) investment efficiency leads to a decrease (increase) in investments of both the defender and the attacker. We also apply the proposed model to a real case. The results from real data demonstrate that the attacker's penalty from a failed attack is an important factor in determining the defender's optimal distribution of investments and defense probabilities. The defender's second stage defense decisions complement the first stage investment decisions. That is, among target sites that receive little or zero investment, the most important one is covered with a relatively high defense probability in the second stage. Moreover, as the attacker's budget increases, the defense investments shift from less important sites to the more important ones. We also investigate the overarching protection options in the resource allocation models. An overarching protection refers to an option that protects multiple targets at the same time, e.g., emergency response, border security and intelligence. Most of the defensive resource allocation models with overarching protections assume that there is only one overarching protection option that protects all targets. However, this may not be realistic, for example, emergency response investment may cover only a certain region. To address this issue, we develop a new resource allocation model to accommodate generalized overarching protections against intentional attacks. The model also considers multiple natural disaster types. We show that our proposed model is a convex optimization problem and therefore can be solved to optimality in polynomial time. Furthermore, the overall country-level resource allocation problem can be decomposed into smaller city-level subproblems, thus resulting in a more efficient algorithm. The numerical experiments demonstrate the performance of the proposed approach. Patrolling and search games are usually played on a graph where players make decisions over a time horizon. In patrolling games, the defender controls a set of patrollers and directs them to follow a walk on the graph to minimize the damage of attacks of the adversary, while the adversary selects a target and a time to attack. In order to successfully destroy a target site, the adversary needs some preparation time without being interrupted by the patrollers. Most patrolling game models assume that the site values are either the same or that they do not change over time. However, this is not a realistic assumption. Particularly in the case of soft targets, these values may correspond to the occupancy level of a site, thus, as such may be different and may change over time. We propose new models with time-dependent node values and node-based attack times. We solve these models numerically using algorithms like column generation, and column and row generation. We apply these algorithms to a real case of an urban rail network in a major US city. The results show the efficiency of the proposed solution approach. They also demonstrate a diminishing returns for additional patrollers. In search games, a Hider hides a set of objects in a set of potential hiding locations. The Searcher controls a set of search teams and directs them to follow a walk on the network and find the hidden objects such that an objective function is optimized. Most search game models assume that the hiding places are identical and the players' objective is to optimize the search time. However, there are some cases in which the players may differentiate the hiding places from each other and the objective is to optimize a weighted search time. To address this, we introduce a new discrete search game with consideration given to the weights at different locations. We show that, under certain conditions, the game has a closed-form Nash equilibrium. For the general case, we develop an algorithm based on column and row generation. We show that the Searcher's subproblem is NP-hard and propose a branch and price algorithm to solve it. We also present a polynomial time algorithm for the Hider's subproblem. Numerical experiments investigate the performance of the approach and reveal insights on the properties of this game.