logo

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

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

国家自然科学基金(61202212)

  • 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

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

京ICP备18024590号-1       京公网安备11010102003388号