Games for the Optimal Deployment of Security Forces

Corine Maartje Laan

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

104 Downloads (Pure)

Abstract

In this thesis, we develop mathematical models for the optimal deployment of security forces addressing two main challenges: adaptive behavior of the adversary and uncertainty in the model. We address several security applications and model them as agent-intruder games. The agent represents the security forces which can be the coast guard, airport control, or military assets, while the intruder represents the agent's adversary such as illegal fishermen, terrorists or enemy submarines.

To determine the optimal agent's deployment strategy, we assume that we deal with an intelligent intruder. This means that the intruder is able to deduce the strategy of the agent. To take this into account, for example by using randomized strategies, we use game theoretical models which are developed to model situations in which two or more players interact. Additionally, uncertainty may arise at several aspects. For example, there might be uncertainty in sensor observations, risk levels of certain areas, or travel times. We address this uncertainty by combining game theoretical models with stochastic modeling, such as queueing theory, Bayesian beliefs, and stochastic game theory.

This thesis consists of three parts. In the first part, we introduce two game theoretical models on a network of queues. First, we develop an interdiction game on a network of queues where the intruder enters the network as a regular customer and aims to route to a target node. The agent is modeled as a negative customer which can inspect the queues and remove intruders. By modeling this as a queueing network, stochastic arrivals and travel times can be taken into account. The second model considers a non-cooperative game on a queueing network where multiple players decide on a route that minimizes their sojourn time. We discuss existence of pure Nash equilibria for games with continuous and discrete strategy space and describe how such equilibria can be found.

The second part of this thesis considers dynamic games in which information that becomes available during the game plays a role. First, we consider partially observable agent-intruder games (POAIGs). In these types of games, both the agent and the intruder do not have full information about the state space. However, they do partially observe the state space, for example by using sensors. We prove the existence of approximate Nash equilibria for POAIGs with an infinite time horizon and provide methods to find (approximate) solutions for both POAIGs with a finite time horizon and POAIGs with an infinite time horizon. Second, we consider anti-submarine warfare operations with time dependent strategies where parts of the agent's strategy becomes available to the intruder during the game. The intruder represents an enemy submarine which aims to attack a high value unit. The agent is trying to prevent this by the deployment of both frigates and helicopters.

In the last part of this thesis we discuss games with restrictions on the agent's strategy. We consider a special case of security games dealing with the protection of large areas for a given planning period. An intruder decides on which cell to attack and an agent selects a patrol route visiting multiple cells from a finite set of patrol routes, such that some given operational conditions on the agent's mobility are met. First, this problem is modeled as a two-player zero-sum game with probabilistic constraints such that the operational conditions are met with high probability. Second, we develop a dynamic variant of this game by using stochastic games. This ensures that strategies are constructed that consider both past actions and expected future risk levels. In the last chapter, we consider Stackelberg security games with a large number of pure strategies. In order to construct operationalizable strategies we limit the number of pure strategies that is allowed in the optimal mixed strategy of the agent. We investigate the cost of these restrictions by introducing the price of usability and develop algorithmic approaches to calculate such strategies efficiently.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Boucherie, Richardus J., Supervisor
  • Barros, A.I., Co-Supervisor
  • Monsuur, H., Co-Supervisor
Thesis sponsors
Award date25 Jan 2019
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-4700-0
DOIs
Publication statusPublished - 25 Jan 2019

Fingerprint

Game
Theoretical Model
Queue
Uncertainty
Horizon
Stochastic Games
Queueing Networks
Travel Time
Nash Equilibrium
Strategy
State Space
Customers
Attack
Probabilistic Constraints
Restriction
Adaptive Behavior
Queueing Theory
Sensor
Mixed Strategy
Dynamic Games

Keywords

  • Game theory
  • Stochastic models
  • Security applications

Cite this

Laan, Corine Maartje. / Games for the Optimal Deployment of Security Forces. Enschede : University of Twente, 2019. 171 p.
@phdthesis{c56e8ec1e75048619f92fe0910cbef31,
title = "Games for the Optimal Deployment of Security Forces",
abstract = "In this thesis, we develop mathematical models for the optimal deployment of security forces addressing two main challenges: adaptive behavior of the adversary and uncertainty in the model. We address several security applications and model them as agent-intruder games. The agent represents the security forces which can be the coast guard, airport control, or military assets, while the intruder represents the agent's adversary such as illegal fishermen, terrorists or enemy submarines.To determine the optimal agent's deployment strategy, we assume that we deal with an intelligent intruder. This means that the intruder is able to deduce the strategy of the agent. To take this into account, for example by using randomized strategies, we use game theoretical models which are developed to model situations in which two or more players interact. Additionally, uncertainty may arise at several aspects. For example, there might be uncertainty in sensor observations, risk levels of certain areas, or travel times. We address this uncertainty by combining game theoretical models with stochastic modeling, such as queueing theory, Bayesian beliefs, and stochastic game theory.This thesis consists of three parts. In the first part, we introduce two game theoretical models on a network of queues. First, we develop an interdiction game on a network of queues where the intruder enters the network as a regular customer and aims to route to a target node. The agent is modeled as a negative customer which can inspect the queues and remove intruders. By modeling this as a queueing network, stochastic arrivals and travel times can be taken into account. The second model considers a non-cooperative game on a queueing network where multiple players decide on a route that minimizes their sojourn time. We discuss existence of pure Nash equilibria for games with continuous and discrete strategy space and describe how such equilibria can be found.The second part of this thesis considers dynamic games in which information that becomes available during the game plays a role. First, we consider partially observable agent-intruder games (POAIGs). In these types of games, both the agent and the intruder do not have full information about the state space. However, they do partially observe the state space, for example by using sensors. We prove the existence of approximate Nash equilibria for POAIGs with an infinite time horizon and provide methods to find (approximate) solutions for both POAIGs with a finite time horizon and POAIGs with an infinite time horizon. Second, we consider anti-submarine warfare operations with time dependent strategies where parts of the agent's strategy becomes available to the intruder during the game. The intruder represents an enemy submarine which aims to attack a high value unit. The agent is trying to prevent this by the deployment of both frigates and helicopters.In the last part of this thesis we discuss games with restrictions on the agent's strategy. We consider a special case of security games dealing with the protection of large areas for a given planning period. An intruder decides on which cell to attack and an agent selects a patrol route visiting multiple cells from a finite set of patrol routes, such that some given operational conditions on the agent's mobility are met. First, this problem is modeled as a two-player zero-sum game with probabilistic constraints such that the operational conditions are met with high probability. Second, we develop a dynamic variant of this game by using stochastic games. This ensures that strategies are constructed that consider both past actions and expected future risk levels. In the last chapter, we consider Stackelberg security games with a large number of pure strategies. In order to construct operationalizable strategies we limit the number of pure strategies that is allowed in the optimal mixed strategy of the agent. We investigate the cost of these restrictions by introducing the price of usability and develop algorithmic approaches to calculate such strategies efficiently.",
keywords = "Game theory, Stochastic models, Security applications",
author = "Laan, {Corine Maartje}",
year = "2019",
month = "1",
day = "25",
doi = "10.3990/1.9789036547000",
language = "English",
isbn = "978-90-365-4700-0",
series = "DSI Ph.D. Series",
publisher = "University of Twente",
number = "002",
address = "Netherlands",
school = "University of Twente",

}

Laan, CM 2019, 'Games for the Optimal Deployment of Security Forces', Doctor of Philosophy, University of Twente, Enschede. https://doi.org/10.3990/1.9789036547000

Games for the Optimal Deployment of Security Forces. / Laan, Corine Maartje.

Enschede : University of Twente, 2019. 171 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - Games for the Optimal Deployment of Security Forces

AU - Laan, Corine Maartje

PY - 2019/1/25

Y1 - 2019/1/25

N2 - In this thesis, we develop mathematical models for the optimal deployment of security forces addressing two main challenges: adaptive behavior of the adversary and uncertainty in the model. We address several security applications and model them as agent-intruder games. The agent represents the security forces which can be the coast guard, airport control, or military assets, while the intruder represents the agent's adversary such as illegal fishermen, terrorists or enemy submarines.To determine the optimal agent's deployment strategy, we assume that we deal with an intelligent intruder. This means that the intruder is able to deduce the strategy of the agent. To take this into account, for example by using randomized strategies, we use game theoretical models which are developed to model situations in which two or more players interact. Additionally, uncertainty may arise at several aspects. For example, there might be uncertainty in sensor observations, risk levels of certain areas, or travel times. We address this uncertainty by combining game theoretical models with stochastic modeling, such as queueing theory, Bayesian beliefs, and stochastic game theory.This thesis consists of three parts. In the first part, we introduce two game theoretical models on a network of queues. First, we develop an interdiction game on a network of queues where the intruder enters the network as a regular customer and aims to route to a target node. The agent is modeled as a negative customer which can inspect the queues and remove intruders. By modeling this as a queueing network, stochastic arrivals and travel times can be taken into account. The second model considers a non-cooperative game on a queueing network where multiple players decide on a route that minimizes their sojourn time. We discuss existence of pure Nash equilibria for games with continuous and discrete strategy space and describe how such equilibria can be found.The second part of this thesis considers dynamic games in which information that becomes available during the game plays a role. First, we consider partially observable agent-intruder games (POAIGs). In these types of games, both the agent and the intruder do not have full information about the state space. However, they do partially observe the state space, for example by using sensors. We prove the existence of approximate Nash equilibria for POAIGs with an infinite time horizon and provide methods to find (approximate) solutions for both POAIGs with a finite time horizon and POAIGs with an infinite time horizon. Second, we consider anti-submarine warfare operations with time dependent strategies where parts of the agent's strategy becomes available to the intruder during the game. The intruder represents an enemy submarine which aims to attack a high value unit. The agent is trying to prevent this by the deployment of both frigates and helicopters.In the last part of this thesis we discuss games with restrictions on the agent's strategy. We consider a special case of security games dealing with the protection of large areas for a given planning period. An intruder decides on which cell to attack and an agent selects a patrol route visiting multiple cells from a finite set of patrol routes, such that some given operational conditions on the agent's mobility are met. First, this problem is modeled as a two-player zero-sum game with probabilistic constraints such that the operational conditions are met with high probability. Second, we develop a dynamic variant of this game by using stochastic games. This ensures that strategies are constructed that consider both past actions and expected future risk levels. In the last chapter, we consider Stackelberg security games with a large number of pure strategies. In order to construct operationalizable strategies we limit the number of pure strategies that is allowed in the optimal mixed strategy of the agent. We investigate the cost of these restrictions by introducing the price of usability and develop algorithmic approaches to calculate such strategies efficiently.

AB - In this thesis, we develop mathematical models for the optimal deployment of security forces addressing two main challenges: adaptive behavior of the adversary and uncertainty in the model. We address several security applications and model them as agent-intruder games. The agent represents the security forces which can be the coast guard, airport control, or military assets, while the intruder represents the agent's adversary such as illegal fishermen, terrorists or enemy submarines.To determine the optimal agent's deployment strategy, we assume that we deal with an intelligent intruder. This means that the intruder is able to deduce the strategy of the agent. To take this into account, for example by using randomized strategies, we use game theoretical models which are developed to model situations in which two or more players interact. Additionally, uncertainty may arise at several aspects. For example, there might be uncertainty in sensor observations, risk levels of certain areas, or travel times. We address this uncertainty by combining game theoretical models with stochastic modeling, such as queueing theory, Bayesian beliefs, and stochastic game theory.This thesis consists of three parts. In the first part, we introduce two game theoretical models on a network of queues. First, we develop an interdiction game on a network of queues where the intruder enters the network as a regular customer and aims to route to a target node. The agent is modeled as a negative customer which can inspect the queues and remove intruders. By modeling this as a queueing network, stochastic arrivals and travel times can be taken into account. The second model considers a non-cooperative game on a queueing network where multiple players decide on a route that minimizes their sojourn time. We discuss existence of pure Nash equilibria for games with continuous and discrete strategy space and describe how such equilibria can be found.The second part of this thesis considers dynamic games in which information that becomes available during the game plays a role. First, we consider partially observable agent-intruder games (POAIGs). In these types of games, both the agent and the intruder do not have full information about the state space. However, they do partially observe the state space, for example by using sensors. We prove the existence of approximate Nash equilibria for POAIGs with an infinite time horizon and provide methods to find (approximate) solutions for both POAIGs with a finite time horizon and POAIGs with an infinite time horizon. Second, we consider anti-submarine warfare operations with time dependent strategies where parts of the agent's strategy becomes available to the intruder during the game. The intruder represents an enemy submarine which aims to attack a high value unit. The agent is trying to prevent this by the deployment of both frigates and helicopters.In the last part of this thesis we discuss games with restrictions on the agent's strategy. We consider a special case of security games dealing with the protection of large areas for a given planning period. An intruder decides on which cell to attack and an agent selects a patrol route visiting multiple cells from a finite set of patrol routes, such that some given operational conditions on the agent's mobility are met. First, this problem is modeled as a two-player zero-sum game with probabilistic constraints such that the operational conditions are met with high probability. Second, we develop a dynamic variant of this game by using stochastic games. This ensures that strategies are constructed that consider both past actions and expected future risk levels. In the last chapter, we consider Stackelberg security games with a large number of pure strategies. In order to construct operationalizable strategies we limit the number of pure strategies that is allowed in the optimal mixed strategy of the agent. We investigate the cost of these restrictions by introducing the price of usability and develop algorithmic approaches to calculate such strategies efficiently.

KW - Game theory

KW - Stochastic models

KW - Security applications

U2 - 10.3990/1.9789036547000

DO - 10.3990/1.9789036547000

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4700-0

T3 - DSI Ph.D. Series

PB - University of Twente

CY - Enschede

ER -

Laan CM. Games for the Optimal Deployment of Security Forces. Enschede: University of Twente, 2019. 171 p. (DSI Ph.D. Series; 002). https://doi.org/10.3990/1.9789036547000