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

More info
  • ReceivedApr 8, 2016
  • AcceptedJun 27, 2016
  • PublishedFeb 23, 2017


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


    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