An interdiction game on a queueing network with multiple intruders

Corine Maartje Laan, Tom van der Mijden, Ana Isabel Barros, Richard Boucherie, Herman Monsuur

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
3 Downloads (Pure)

Abstract

Security forces are deployed to protect networks that are threatened by multiple intruders. To select the best deployment strategy, we analyze an interdiction game that considers multiple simultaneous threats. Intruders route through the network as regular customers, while interdictors arrive at specific nodes as negative customers. When an interdictor arrives at a node where an intruder is present, the intruder is removed from the network. Intruders and interdictors compete over the value of this network, which is the throughput of unintercepted intruders. Intruders attempt to maximize this throughput by selecting a fixed route through the network, while the interdictors aim to minimize the throughput selecting their arrival rate at each node. We analyze this game and characterize optimal strategies. For special cases, we obtain explicit formulas to evaluate the optimal strategies and use these to compute optimal strategies for general networks. We also consider the network with probabilistic routing of intruders and show that for this case, the value and optimal strategies of the interdictor of the resulting game remain the same.
Original languageEnglish
Pages (from-to)1069-1080
JournalEuropean journal of operational research
Volume260
Issue number3
DOIs
Publication statusPublished - Aug 2017

Fingerprint

Queueing networks
Queueing Networks
Throughput
Game
Optimal Strategy
Customers
Vertex of a graph
Explicit Formula
Routing
Maximise
Minimise
Optimal strategy
Evaluate

Cite this

Laan, Corine Maartje ; van der Mijden, Tom ; Barros, Ana Isabel ; Boucherie, Richard ; Monsuur, Herman. / An interdiction game on a queueing network with multiple intruders. In: European journal of operational research. 2017 ; Vol. 260, No. 3. pp. 1069-1080.
@article{b7e75a3e29904233a19da7eee75b5331,
title = "An interdiction game on a queueing network with multiple intruders",
abstract = "Security forces are deployed to protect networks that are threatened by multiple intruders. To select the best deployment strategy, we analyze an interdiction game that considers multiple simultaneous threats. Intruders route through the network as regular customers, while interdictors arrive at specific nodes as negative customers. When an interdictor arrives at a node where an intruder is present, the intruder is removed from the network. Intruders and interdictors compete over the value of this network, which is the throughput of unintercepted intruders. Intruders attempt to maximize this throughput by selecting a fixed route through the network, while the interdictors aim to minimize the throughput selecting their arrival rate at each node. We analyze this game and characterize optimal strategies. For special cases, we obtain explicit formulas to evaluate the optimal strategies and use these to compute optimal strategies for general networks. We also consider the network with probabilistic routing of intruders and show that for this case, the value and optimal strategies of the interdictor of the resulting game remain the same.",
author = "Laan, {Corine Maartje} and {van der Mijden}, Tom and Barros, {Ana Isabel} and Richard Boucherie and Herman Monsuur",
year = "2017",
month = "8",
doi = "10.1016/j.ejor.2017.02.035",
language = "English",
volume = "260",
pages = "1069--1080",
journal = "European journal of operational research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

An interdiction game on a queueing network with multiple intruders. / Laan, Corine Maartje; van der Mijden, Tom; Barros, Ana Isabel; Boucherie, Richard; Monsuur, Herman.

In: European journal of operational research, Vol. 260, No. 3, 08.2017, p. 1069-1080.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - An interdiction game on a queueing network with multiple intruders

AU - Laan, Corine Maartje

AU - van der Mijden, Tom

AU - Barros, Ana Isabel

AU - Boucherie, Richard

AU - Monsuur, Herman

PY - 2017/8

Y1 - 2017/8

N2 - Security forces are deployed to protect networks that are threatened by multiple intruders. To select the best deployment strategy, we analyze an interdiction game that considers multiple simultaneous threats. Intruders route through the network as regular customers, while interdictors arrive at specific nodes as negative customers. When an interdictor arrives at a node where an intruder is present, the intruder is removed from the network. Intruders and interdictors compete over the value of this network, which is the throughput of unintercepted intruders. Intruders attempt to maximize this throughput by selecting a fixed route through the network, while the interdictors aim to minimize the throughput selecting their arrival rate at each node. We analyze this game and characterize optimal strategies. For special cases, we obtain explicit formulas to evaluate the optimal strategies and use these to compute optimal strategies for general networks. We also consider the network with probabilistic routing of intruders and show that for this case, the value and optimal strategies of the interdictor of the resulting game remain the same.

AB - Security forces are deployed to protect networks that are threatened by multiple intruders. To select the best deployment strategy, we analyze an interdiction game that considers multiple simultaneous threats. Intruders route through the network as regular customers, while interdictors arrive at specific nodes as negative customers. When an interdictor arrives at a node where an intruder is present, the intruder is removed from the network. Intruders and interdictors compete over the value of this network, which is the throughput of unintercepted intruders. Intruders attempt to maximize this throughput by selecting a fixed route through the network, while the interdictors aim to minimize the throughput selecting their arrival rate at each node. We analyze this game and characterize optimal strategies. For special cases, we obtain explicit formulas to evaluate the optimal strategies and use these to compute optimal strategies for general networks. We also consider the network with probabilistic routing of intruders and show that for this case, the value and optimal strategies of the interdictor of the resulting game remain the same.

U2 - 10.1016/j.ejor.2017.02.035

DO - 10.1016/j.ejor.2017.02.035

M3 - Article

VL - 260

SP - 1069

EP - 1080

JO - European journal of operational research

JF - European journal of operational research

SN - 0377-2217

IS - 3

ER -