SCIENTIA SINICA Informationis, Volume 47, Issue 4: 492-506(2017) https://doi.org/10.1360/N112016-00088

## Designing game-theoretic security strategies for large public events

Yue YIN1,2,*, Bo AN1,3,
• AcceptedJun 27, 2016
• PublishedFeb 23, 2017
Share
Rating

### Abstract

High-profile, large-scale public events may be attractive targets for terrorist attacks. The security challenge for such events is exacerbated by their dynamic nature: the impact of an attack on different `targets', such as studio entrances, changes over time. In addition, the defender can relocate security resources among potential attack targets at any time, while the attacker may act at any time during the event. This study focuses on developing efficient patrolling algorithms for such dynamic domains, with continuous strategy spaces for both the defender and attacker. We propose SCOUT-A, which makes assumptions regarding relocation costs, exploits payoff representation, and computes optimal solutions efficiently. We furthermore propose SCOUT-C, to compute the exact optimal defender strategy for general cases despite the continuous strategy spaces. The experimental results demonstrate that our algorithms significantly outperform existing strategies.

### Funded by

• Figure 5

(Color online) Minimax assignment

• Table 1   Resources assigned to $i, j, l$ in $S$
 Time period $q_i^t(S)$ $q_j^t(S)$ $q_l^t(S)$ Before $t_1$ $a_i$ $a_j$ $a_l$ $[t_1, t_1 + d_{ij})$ $a_i - 1$ $a_j$ $a_l$ $[t_1 + d_{ij}, t_2)$ $a_i-1$ $a_j +1$ $a_l$ $[t_2, t_2 + d_{jl})$ $a_i - 1$ $a_j$ $a_l$ After $t_2 + d_{jl}$ $a_i - 1$ $a_j$ $a_l + 1$
•

Algorithm 1 SCOUT-A

for all $i \in \mathcal{T}$

$V_i \leftarrow v_i(0), a_i \leftarrow 0$

end for

${\rm left} \leftarrow m$

while ${\rm left} > 0$ do

$i \leftarrow \arg\!\max_{i \in \mathcal{T} }V_i$, $a_i \leftarrow a_i + 1$, ${\rm left} \leftarrow {\rm left} - 1$, $V_i \leftarrow W_i^{a_i}(0)$

end while

$t_m \leftarrow 0$, $k \leftarrow 0$

while $t_m< t_{\rm e}$ do

${\boldsymbol I} \leftarrow \emptyset$

for all $\forall i, j \in \mathcal{T}$

if $\exists t$ such that $\frac{\partial W_i^{a_i - 1}(t)}{\partial t} < \frac{\partial W_j^{a_j}(t)}{\partial t}$ then

$I_{ij} \leftarrow I_{ij}(A, t_m)$

if $I_{ij} < t_{\rm e}$ then

${\boldsymbol I} \leftarrow {\boldsymbol I} \cup I_{ij}$

end if

end if

end for

if ${\boldsymbol I} = \emptyset$ then

break

end if

$I_{ij} \leftarrow \min({\boldsymbol I})$

if $W_i^{a_i - 1}(I_{ij} - \Delta t) \ge W_j^{a_j}(I_{ij} - \Delta t)$ then

$\tau_k \leftarrow I_{ij}, t_m \leftarrow I_{ij}, a_i \leftarrow a_i - 1, a_j \leftarrow a_j + 1, c_{ij}^k \leftarrow 1, k \leftarrow k + 1$

end if

end while

• Table 2   Resources assigned to $i, j, l$ in $S^1$
 Time period $q_i^t(S)$ $q_j^t(S)$ $q_l^t(S)$ Before $t_3$ $a_i$ $a_j$ $a_l$ $[t_3, t_3 + d_{il})$ $a_i-1$ $a_j$ $a_l$ After $t_3 + d_{il}$ $a_i - 1$ $a_j$ $a_l + 1$
•

Algorithm 2 SCOUT-C

$\Psi \leftarrow \emptyset$

for all $\rho \in \{0, \ldots, R_i\}, \rho&apos; \in \{0, \ldots, R_j\}$

$\Psi \leftarrow \Psi \cup \{\theta({\rm Tr})\} \cup \{\theta({\rm Tr}) + d_{ij}\},$ where ${\rm Tr} = (i, j, a_i, a_j, \rho, \rho&apos;)$

end for

run SCOUT-D, using $\Psi$ as the time points set

• Table 3   Transfer time between studios (min, from google map)
 鸟巢 奥林匹克公园 首体 工体 五棵松 鸟巢 – 8 14 17 29 奥林匹克公园 8 – 20 24 33 首体 14 20 – 24 17 工体 17 24 24 – 36 五棵松 29 33 17 36 –
• #### 0

Citations

• Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有