Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs

1 Introduction

Security is a grand challenge faced by the world. Recently, facing rising threats from ISIS, many major cities have boosted security measures to protect potential attack targets, e.g., subway stations, tourist sites, shopping centers [Park, 2014]. Since strategic attackers can take advantage of patterns of security strategies, it is important to develop randomized security strategies considering both different weights of targets and attacker's surveillance capability.

One challenge lies in designing efficient security resource allocation strategies is that the relative importance of different targets can change over time. Thus the limited security resources need to be dynamically allocated for the best use of them. For example, the entrances of museums are usually crowed in the morning, leading to their high weights in security at that time; while the bar streets and entertainment centers usually require more security measures in the evening. Intuitively, to make the best use of limited security resources, the security agency should assign more resources to the museums in the morning, then transfer some resources to the bar streets in the evening. In this work, we aim at computing randomized dynamic defender strategies to protect targets with time-dependent payoffs.

There has been lots of research on game theory based security resource allocation [Tambe, 2011; Yang et al., 2011; An et al., 2013]. Many systems based on defender-attacker security game models have been successfully deployed [Tambe et al., 2014]. However, most work assumes that the payoffs of targets are static over time [Shieh et al., 2012; An et al., 2011; Gan et al., 2015; Vorobeychik et al., 2014]. Some work considers changing target values, but they only allow the security agency or the adversary to move at pre-defined, discretized time points [Varakantham et al., 2013; Fang et al., 2013; Xu et al., 2014] without analyzing how much loss the discretization can lead to when continuous strategy spaces are considered. While Yin et al. [2014] considered varying target values and that the defender can move resources at any time, their algorithms can only compute optimal pure defender strategies, which is unsuitable in domains where the attacker can easily conduct surveillance and recognize patterns of the defender's pure strategy.

We make five key contributions in this work. First, we propose a new Stackelberg game model, in which the targets' weights are time-dependent and both the defender and the attacker can act at any time, i.e., the defender can transfer resources at any time while the attacker can attack at any time. Thus both agents have continuous strategy spaces. Second, we propose COCO (Computing Optimal Coverage withOut transfer time) to compute the optimal mixed strategy for the defender when she can move security resources among targets without time delay. COCO represents mixed strategies in a compact way and avoids traversing the whole strategy space by exploiting the properties of the optimal defender strategies. Our third contribution is an approach to sample pure strategies based on the compact mixed strategy computed by COCO. The defender can only make a finite number of transfers of resources in a time period in the real world, despite that she can transfer resources at any time point in this period. We sample such 'implementable' pure strategies to realize the compact optimal mixed strategy.

We also consider a more general case in which it takes nonnegligible time to move resources among targets. Our forth contribution is an efficient approximation scheme to compute the near optimal defender mixed strategy. We propose an algorithm ADEN (computing Approximately optimal DEfender strategies in games with Nonzero transfer time) which leads to a defender utility at most ϵ less than the optimal defender utility. Our fifth contribution is detailed experimental analysis on the solution quality and computational efficiency of the proposed algorithms. Experimental results show that both COCO and ADEN make the defender better off than algorithms based on the assumptions of static payoffs or discretized strategy spaces.

2 Model

Assume that there are n targets T = {1, . . . , n} and the defender has m identical security resources (n ≥ m). The defender protects the targets during a time period [0, te] (e.g. the operation hours of a day) everyday. The importance of targets changes over time. We use a continuous function vi(t)(i ∈ T , t ∈ [0, te], vi(t) > 0) to represent the value of a target i at time t and assume vi(t) to be piecewise linear 1 . As in previous work, we model the problem as a Stackelberg game, where the defender commits to a randomized strategy first, and the attacker responds to this strategy.

Strategies. A pure defender strategy S includes the initial assignment of resources at time 0 and the subsequent transfers during [0, te], i.e., S = 〈(i, j, t) : i, j ∈ T , t ∈ [0, te]〉, where (i, j, t) represents that a resource is transferred from target i to target j at time t. (If a target i is protected at time 0, then (i, i, 0) ∈ S). We denote D = 〈dij : i, j ∈ T 〉 where dij represents the time needed to transfer resources from target i to target j. We denote qi(S, t), a 0-1 indicator, to represent whether target i is protected at time t if the defender plays pure strategy S. qi(S, t) is a piecewise constant function over time t ∈ [0, te] with values in {0, 1}. Let S be the defender strategy space. Since the defender can transfer resources at any time during [0, te], S is continuous. A mixed defender strategy can be represented by a distribution x = 〈xS : S ∈ S〉 with xS representing the probability density that pure strategy S is played by the defender. As in previous work, we restrict attacker strategies to pure strategies, denoted as A = (i, ta), representing that the attacker attacks target i at time ta.

Utilities and Equilibrium. We assume the game to be zero-sum. If the attacker plays A = (i, ta) while the defender plays a strategy S with qi(S, ta) = 0, i.e., the attack succeeds, the attacker will gain the value of target i at time ta, vi(ta), and the defender gains -vi(ta). Otherwise, if qi(S, ta) = 1, the attack fails and both players get utility

1 Piecewise linear functions are widely used to approximate complex functions, while the accuracy of approximation can be controlled by setting the number of linear segments.

0. Given a defender's mixed strategy x and an attacker's pure strategy A = (i, ta), the expected attacker utility is

The expected defender utility is Ud(x, A) = -Ua(x, A) due to the zero-sum assumption.

The Stackelberg equilibrium is the same as the maximin equilibrium given the zero-sum assumption: the defender maximizes her minimum utility, or equivalently, minimizes the maximum attacker utility, which indicates that the attacker responds the best.

Compact Representation. It is complicated to directly compute x given its infinite dimensions. We map a mixed defender strategy into a compact form for the ease of computation. Given a mixed strategy x, for each target i ∈ T , we define a coverage function ci(t) which describes the probability of target i being covered by a resource at time t.

ci(t) is a function ranging in [0, 1] over time t ∈ [0, te]. A mixed strategy x corresponds to a coverage vector, c(t) = 〈ci(t) : i ∈ T , t ∈ [0, te]〉. Given x and A = (i, ta), the expected attacker utility can also be represented as Ua(c(t), A) = vi(ta) · (1 - ci(ta)).

3 Negligible Transfer Time

We begin with a simple case in which the transfer time of resources is negligible, i.e., dij = 0. Zero transfer time is a realistic assumption in domains in which targets are close to each other or resources can be transferred quickly (e.g., using helicopters), thus transfer time is negligible compared with the operation time of a pure strategy, i.e., [0, te]. We will relax this assumption in the next section. In this section, we first propose an approach to compute the optimal coverage vector, then propose an approach to sample pure strategies with finite transfers to produce the optimal coverage vector.

3.1 Computing Optimal Coverage Vector

If the transfer time is negligible, we can treat each time point in [0, te] as an independent time point, and just need to compute the optimal coverage vector by computing the 'locally' optimal coverage at each time point. Formally, at a specific time point t0, c(t0) is locally optimal at t0 if it satisfies that

This indicates that the locally optimal coverage minimizes the maximum attacker utility if he attacks at t0. We then explore how to achieve the locally optimal coverage. Let I represent an 'attack set' consisting of targets which lead to the locally optimal attacker utility at t0 if the coverage of targets at t0 is c(t0). Formally,

We have the following Lemma on the properties of a locally optimal coverage.

Lemma 1. A coverage vector c(t) is locally optimal at t0 if and only if it satisfies ∑i∈I ci(t0) = m, hence cj(t0) = 0, ∀j ∈ T \ I. m is the number of resources.

The detailed proofs for lemmas, propositions, and theorems in this paper are available in the online appendix 2 . We now consider computing a coverage vector which is locally optimal at any t∈[0,te]. We first assume that all targets are in the attack set all the time. Such an assumption may enlarge the attack set, and result in infeasible coverage on some targets during some time intervals, i.e., some targets need to be protected with negative probability. We then find these time intervals, revise the attack set and the coverage. We use an example to illustrate the process.

Example 1. Assume that te = 2. There are 3 targets, 1 resource. The value functions of targets are: v1(t) = t, v2(t) = -t + 10, v3(t) = -0.5t + 5. First, assume that all targets are in the attack set all the time. Based on Lemma 1 and the definition of attack set, the coverage functions satisfy that

Thus we can get coverage functions based on value functions vi(t). It is easy to compute that when t ∈ [0, 2], c1(t) < 0, c2(t) > 0, c3(t) > 0. It indicates that target 1 should not be in the attack set during [0, 2]. Thus we can set c1(t) = 0 for t ∈ [0, 2], and remove target 1 from the attack set. Similar to the previous step, we now compute the coverage functions for targets 2 and 3 which stay in the attack set:

The new functions c2(t) ≥ 0, c3(t) ≥ 0, ∀t ∈ [0, 2]. Thus the coverage vector c = 〈ci(t)〉 is now locally optimal ∀t ∈ [0, 2] since it satisfies the condition in Lemma 1 everywhere.

We propose COCO (Computing Optimal Coverage withOut transfer time) in Algorithm 1, which computes the optimal coverage vector for targets in set I during time period [b, e) recursively. We call COCO(I = T , b = 0, e = te) to compute the optimal coverage vector. In COCO, we first assume that the target set I is the attack set during time period [b, e), then compute the corresponding coverage functions of the targets in I (Line 2). E is a vector of all roots of the coverage functions with elements in increasing order, i.e., tk represents the kth smallest root in time period (b, e) (Line 3). If E is empty, Line 5 checks the sign of coverage functions during (b, e). If there does not exist any function with negative value in this time period, the coverage vector is feasible in [b, e) and the algorithm terminates (Line 6). Otherwise assume the attack set includes all targets with positive coverage during (b, e) and repeat the process (Lines 7-9). If E is not empty, during (tk, tk+1), no coverage function has values with opposite signs since (tk, tk+1) is a time period between the adjacent roots of any function. Line 15 uses a set I ′ to

2 http://www.ntu.edu.sg/home/boan/papers/IJCAI15 Dynamic Appendix.pdf

Algorithm 1: COCO(I, b, e)

1 while true do 2 ci(t) ← 1- (n-m) 1 vi (t) ∑j∈I 1 vj (t) , ∀i ∈ I, t ∈ [b, e); 3 E←{tk :ci(tk) = 0, tk ∈ (b, e), ∀i ∈ I}; 4 if E = ∅ then 5 I ′ ← {i : i ∈ I, ci(t) ≥ 0, ∀t ∈ (b, e)} ; 6 if I ′ = I then break; 7 else 8 ci(t) = 0, ∀i ∈ I \ I ′ , ∀t ∈ [b, e) ; 9 COCO(I ′ , b, e); 10 else 11 E ← E ∪ {t0 = b, t|E|+1 = e}; 12 for k ∈ {0, . . . , |E|} do 13 I ′ ← ∅; 14 if ci(t) ≥ 0, ∀i ∈ I, ∀t ∈ (tk, tk+1) then 15 I ′ ← I ′ ∪ {i}; 16 else ci(t) = 0, ∀t ∈ [tk, tk+1); 17 COCO(I ′ , tk, tk+1); 18 return c = {ci(t) : i ∈ I, t ∈ [b, e)};

record targets with positive coverage during (tk, tk+1). Targets in I ′ are considered as in the attack set in time period [tk, tk+1) while other targets are not (Line 16). The process is repeated for each time period [tk, tk+1) (Line 17) to compute the coverage of targets in I ′ until the coverage vector at any time is feasible.

Theorem 2. COCO computes the optimal coverage vector.

3.2 Sampling Pure Strategies

Coverage functions computed by COCO can be continuously changing over time. It is computationally infeasible to treat any t ∈ [0, te] as an independent time point and sample an allocation of resources based on the coverage at t. We now propose an approach to sample pure strategies. Given a coverage vector c(t), we first discretize time period [0, te] as a sequence of time points θ = 〈θk〉 (k is an index) such that ∀t ∈ (θk, θk+1), ∀i ∈ T , ci(t) is differentiable and monotone. Given the piecewise linear assumption of value functions, Line 2 in COCO ensures ci(t) to be piecewise differentiable functions. Hence the discretization is feasible. The procedure of sampling a pure strategy is as follows.

Step 1: Sample an allocation of resources at θk.

• Step 2: Given the allocation at θk, sample the departure targets and destination targets of transfers during (θk, θk+1).
• Step 3: Given the transfers sampled in the previous step, sample the time of each transfer.

Step 4: Go to time point θk+1 and repeat steps 1 - 3.

Next, we describe the implementation of the first three steps. For Step 4, although resources need to be reallocated at θk+1, the number of transfers at this time point is finite given the finite number of resources.

Step 1: Let L = 〈Li : i ∈ T ,Li ∈ {0, 1}, ∑i Li = m〉 represent an allocation of resources with Li indicating whether target i is protected by a resource. Let yL represent the probability of playing allocation L at time θk. Step 1 can be implemented once we get the value of yL. Given c(θk), yL can be computed by approaches used in previous work on security games [Kiekintveld et al., 2009; Letchford and Conitzer, 2013].

Step 2: We first show that a coverage vector can be realized by a specific set of transfers, which is formally shown in Proposition 3. Let Λ = {u : u ∈ T , dcu(t) dt < 0, ∀t ∈ (θk, θk+1)} be a set of targets whose coverage decreases during (θk, θk+1); let V = {v : v ∈ T , dcv(t) dt > 0, ∀v ∈ (θk, θk+1)} be a set of targets whose coverage increases during (θk, θk+1).

Proposition 3. For t ∈ (θk, θk+1), c(t) can be implemented by sampling from pure strategies in which resources are only transferred from targets u ∈ Λ to targets v ∈ V , and each resource is transferred for at most once.

Proof Sketch: Assume that the defender uses a pure strategy S1 with nonzero probability in which a resource is transferred from a target v ∈ V to another target i ∈ T at t0 ∈ (θk, θk+1). Since cv(t) increases continuously in (θk, θk+1), the defender must also use some other pure strategy S2 with nonzero probability in which a resource is transferred from some target j ∈ T to target v at t0. Thus the defender can cancel the transfer made from v in S1 and directly transfer a resource from j to i in strategy S2. If the defender uses a pure strategy S3 in which a resource is transferred from some target i ∈ T to a target u ∈ Λ at t0 ∈ (θk, θk+1), she can get rid of this transfer in a similar way. Given that resources are only transferred from targets u ∈ Λ to targets v ∈ V , a resource will not be transferred from target v ∈ V to other targets during [θk, θk+1]. Thus each resource is transferred for at most once.

We now consider implementing Step 2. Let ΓL = {(u, v) : u ∈ Λ, v ∈ V, Lu = 1, Lv = 0} represent a 'transfer set' of target pairs, i.e., ∀(u, v) ∈ ΓL, a resource is transferred from target u to target v during (θk, θk+1). Step 2 can be done once we get the probability of choosing each ΓL, i.e., p(ΓL). To compute p(ΓL), we first denote p((u, v)|L) as the probability that a resource is transferred from target u to target v during (θk, θk+1) after L is set as the allocation at θk. Once we get the value of p((u, v)|L), p(ΓL) can be computed based on the following class of equations.

To compute p((u, v)|L), we let Z((u, v), t) represent the probability that a resource is transferred from target u to target v before time t. For t ∈ [θk, θk+1], Z((u, v), t) is a function with respect to t. If we can get the expression of Z((u, v), t), p((u, v)|L) can be computed based on the following equations.

Eq. 6 is based on the law of total probability. Eq. 7 indicates that a resource can only be transferred from a target which is protected at θk to a target which is not protected at θk. Our problem now lies in computing the expression of Z((u, v), t).

Computing Z((u, v), t): First, a feasible expression of Z((u, v), t) satisfies the following ∀t ∈ [θk, θk+1].

Eqs. 8 - 9 are based on Proposition 3. Eqs. 10 - 11 are based on the definition of Z((u, v), t). At a time point t ∈ [θk, θk+1], the value of Z((u, v), t) can be computed based on Eqs. 8 - 11. But it is impossible to compute the expression of Z((u, v), t) in this way due to the continuity of time. Note that given Eqs. 8 and 9, the function Z((u, v), t) can be represented as linear combinations of coverage functions (∀t ∈ [θk, θk+1]), i.e.,

Here ziuv (t) are parameters depending on t, or 'parameter functions'. We can get Z((u, v), t) by computing these 'parameter functions'. At a specific time t ∈ [θk, θk+1], we can get the value of the parameter functions based on Eqs. 8 - 11. In addition, we have the following proposition which discusses the properties of the parameter functions.

Proposition 4. There exist parameter functions which lead to a feasible expression of Z((u, v), t) satisfying that each ziuv (t) is piecewise constant during [θk, θk+1].

The proof of Proposition 4 is based on Lemma 5.

Lemma 5. If |Λ| > 2 and |V | > 2, there exists feasible Z((u, v), t) satisfying lim∆t→0 Z((u,v),t+∆t)-Z((u,v),t) ∆t > 0, ∀u, ∀v, ∀t ∈ [θk, θk+1].

Based on Proposition 4 and Lemma 5, we propose Algorithm 2 to compute the parameter functions, hence Z((u, v), t). We first compute the value of the parameter functions at a time point t0, hence we can get an expression of Z((u, v), t) whose parameter functions are constant in [t0, θk+1]. Let R be the set of the roots of functions dZ((u,v),t) dt (Line 4). The expression of Z((u, v), t) is feasible from time t0 to the minimum time point in R (tm, Line 8) since for t > tm, Eq. 11 is violated. The process is repeated for tm until we get the feasible expression of Z((u, v), t) for t ∈ [θ,θk+1].

Theorem 6. Algorithm 2 computes a feasible expression of Z((u, v), t), ∀t ∈ [θk, θk+1] after finite loops.

Algorithm 2: Computing Z((u, v), t)

1 t0 = θk, kuv = 0; 2 while tm < θk+1 do 3 solve ziuv (t0) based on Eqs. 8 - 11 (change the '0' in Eq. 10 to kuv, change the '≥' in Eq. 11 to '>'); 4 R = 〈t : dZ((u,v),t) dt = 0 and t ∈ (t0, θk+1)〉; 5 if R = ∅ then 6 break; 7 else 8 tm = mint R; kuv = Z((u, v), t0); 9 ziuv (t) = ziuv (t0), ∀t ∈ [t0, tm); t0 = tm;

Step 3: Let Z(t|L, (u, v)) be the cumulative distribution function of t, representing the probability that a resource is transferred from target u to target v before time t (t ∈ [θk, θk+1]) after L is set as the allocation at θk and step 2 takes a transfer set ΓL ∋ (u, v). We can implement Step 3 as long as we can get the expression of Z(t|L, (u, v)). Note that the time at which the transfer made from target u to target v occurs is independent of the allocation at θk. Thus we have

Apparently, we can get the expression of Z(t|L, (u, v)) based on the expression of Z((u, v), t).

4 Nonzero Transfer Time

In this section, we address general cases with non-negligible transfer time, i.e., dij ≥ 0 and propose an efficient approximation scheme to compute the optimal defender's mixed strategy. We first obtain a discretized version of the game by properly partitioning the time space, and more importantly, show that the defender's optimal utility is at most ϵ less than the optimal utility in the original continuous version. We then approach the discrete game with a flow formulation. For constructing the discretized game, we first define an (ϵ, δ)-Mesh.

Definition 7. ((ϵ, δ)-Mesh) An (ϵ, δ)-mesh is a uniform discretization of the time space [0, te], denoted as ζ = 〈t0, t1, ..., t|ζ|〉 with t0 = 0, t|ζ| = te, such that δ = tk - tk-1 and vari(tk-1, tk) ≤ ϵ for all k = 1, ..., |ζ|, where vari(tk-1, tk) = maxt∈[tk-1,tk] vi(t) - mint∈[tk-1,tk] vi(t) is the oscillation of vi(t) in interval [tk-1, tk].

Continuity of value functions guarantees the existence of such an (ϵ, δ)-Mesh, which can be easily found 3 . We now convert a general game G into a discretized game Gd. First, we restrict the defender's resource move can only happen at time points tk ∈ ζ and so is the attacker's attack. Thus the strategy space of Gd is a subset of the strategy space of G. Let vi(t) represent the value functions in G, we construct the value functions of Gd using the (ϵ, δ)-Mesh: ∀i ∈ T , let

3 For Lipschitz continuous functions satisfying |vi(t)-vi(t′ )| ≤ K|t - t′ | for all i, we can simply take ϵ = Kδ.

be the value functions of Gd. Note that v′i (t) is a constant in [tk-1, tk] and satisfies |v′i (t)-vi(t)|≤ϵ, ∀t. We also assume that dij are multipliers of δ, i.e., dij = aijδ with aij being some integer. This assumption holds if each dij is given as a rational number and δ is small enough. To show the gap between the optimal defender utility in Gd and the initial game G, we introduce a bridge game Gb, in which the value functions are v′i (t) as in Gd while the defender and the attacker can act at any time as in G. The following lemma shows the relationship between defender utilities in Gd and Gb.

Lemma 8. Let x be a defender's mixed strategy of Gd, then U Gd d (x) = U Gb d (x), where U Gd d (x) and U Gb d (x) are the defender's utility in Gd and Gb respectively if the defender plays x and the attacker responds the best.

This is because the value functions of Gd and Gb are the same. Furthermore, a deeper conclusion holds.

Lemma 9. Assume that transfer time between any target pair dij is multiplier of δ. If x is an equilibrium strategy of Gd, it is an equilibrium strategy of Gb.

Note that this does not apply directly from Lemma 8, since the strategy space of Gd is a subset of the strategy space of Gb. Now we are ready to bound the defender's utility gap between Gd and G, as summarized in the following theorem.

Theorem 10. Let x′ be an equilibrium strategy of Gd and x be an equilibrium strategy of G, we have

where U G d (x′ ) is the defender utility in G if the defender plays x′ and the attacker responds the best, while U G d (x) is the optimal defender utility in G.

In addition, we have U G d (x′ ) = U Gd d (x′ ) based on Eq. 14. Our task now reduces to computing the equilibrium of Gd. Gd is a discretized spatio-temporal game as is shown in Figure 1(a), in which x-axis is the (ϵ, σ)-Mesh and y-axis indicates the targets, i.e., node (k, i) is target i at time tk. An attacker's pure strategy is a node in the graph. If we add a departure node and a destination node to the graph as is shown in Figure 1(b) and require that any edge of the graph has capacity 1, the defender's pure strategy is an m-unit 0-1 integer s - t flow on the graph, i.e., if the defender transfers a resource from target i to target j at time tk, add an edge between node (k, j) and (k +aij , j); if the defender does not transfer the resource on target i at time tk, add an edge between node (k, i) and node (k + 1, i). We have the following theorem about the defender's mixed strategies in Gd.

Theorem 11. A mixed strategy of Gd is an m-unit fractional flow, and vise versa.

Let f(i, j, tk) represent the probability that a resource is transferred from target i to target j at tk. The optimal defender utility can be computed by the following LP which we call ADEN (computing Approximately optimal DEfender strategies in games with Nonzero transfer time).

Note that the probability that a target i is covered by a resource at time tk is equal to the probability that a resource stays at target i during the time period after tk, i.e., ci(tk) = f(i, i, tk). Thus we have the objective and Eq. 16 together to guarantee the optimal defender utility. Eqs. 17 - 19 are for the properties of m-units s - t flow. The coverage vector c = 〈f(i, i, tk) : i ∈ T , tk ∈ ζ〉 computed by ADEN can be directly mapped back to a mixed strategy with a finite support, i.e., pure strategies which transfer resources at tk(∀tk ∈ ζ). Technically, for a resource at any target i and time tk, we can sample its next destination j with probability propositional to f(i, j, tk) (j = i means staying at i). If there is a move, this resource will be in transition from tk to tk+aij . The initial assignment of resources can be sampled based on f(s, j, t0). This LP has size poly( te δ n2 ). When the value functions are all Lipschitz continuous functions satisfying |vi(t) - vi(t′ )| ≤ K|t - t′ | for all i, we take ϵ = Kδ and generate an LP with size poly( Kte ϵ n2 ), which gives an ϵ-approximation to the original problem.

5 Experimental Evaluation

We evaluate the performance of the proposed algorithms in terms of attacker utility. A lower attacker utility indicates a higher defender utility given the zero-sum assumption. We assume te = 100. To illustrate the solution quality of the proposed algorithms, we consider two baseline strategies. The first one is the ORIGAMI algorithm [Kiekintveld et al., 2009] assuming static payoffs. The second one, which we call PDT, is based on the assumption that both the defender and the attacker can act at pre-defined, discretized time points Φ = { n·te 7 : n = 0, 1, · · · , 7} as inXu et al. [Xu et al., 2014]. We also evaluate the scalability of the proposed algorithms.

In each game, we sample piecewise linear value functions with at most two sections, i.e., the number of sections is randomly sampled in {1, 2}. If a value function is determined to have two linear sections, the discontinuity point will be randomly chosen in (0, te), then the values of the function at time 0, te and the discontinuity point will be randomly chosen in (0, 100], thus the value of a value function ranges in (0, 100]. We perform 4 experiment sets to show the performance of the algorithms. In the first experiment set, we restrict transfer time to be zero, and test the solution quality of the algorithms against increasing (1) number of targets; (2) number of resources. We then test the effect of changing ϵ and changing transfer time on the solution quality of ADEN. The third experiment set tests the scalability of the proposed algorithms. We also test the runtime of the sample procedure.

We first evaluate the solution quality of the algorithms. In Figure 2, the y-axis of all subfigures indicate the optimal attacker utility. Figures 2(a) and 2(b) consider zero transfer time. In Figures 2(a), the x-axis indicates the number of targets. In Figure 2(b), the x-axis indicates the number of resources. These two figures show that despite the number of targets or resources, ADEN and COCO significantly perform better than the baseline strategies. COCO achieves lower attacker utilities than ADEN since it can compute the optimal defender strategies. Figures 2(c) and 2(d) further evaluate the solution quality of ADEN. Figure 2(c) evaluates the effect of increasing ϵ on ADEN. As the value of ϵ increases, the optimal attacker utility computed by ADEN increases gently. Since ϵ is an upper bound of the defender's loss, the defender's loss can be far less than ϵ in reality. Solution quality of PDT is not affected by the value of ϵ, but ADEN outperforms PDT even when ϵ = 30. Figure 2(d) evaluates the effect of increasing transfer time on ADEN and PDT (ϵ is fixed at 10). The x-axis indicates different levels of transfer time, i.e., for x = 10, transfer time of resources is randomly generated in [ 10 2 , 10]. Figure 2(d) shows that as transfer time increases, both ADEN and PDT performs worse. While the effect of increasing transfer time is more obvious on ADEN than it is on PDT. ADEN outperforms PDT even when the maximum transfer time reaches 30. If the transfer time is very large, i.e., larger than the operation time of pure strategies, then the defender's optimal strategy is static and ADEN and PDT will perform the same as ORIGAMI.

We then evaluate the scalability of the proposed algorithms. In Figure 3, the y-axis indicates runtime in seconds. In Figure 3(a), the x-axis indicates the number of targets. Runtime of COCO shows obvious increasing trend while that of ADEN does not change much as the number of targets ranges from 6 to 14. In Figure 3(b), the x-axis indicates the number of resources, which does not affect the runtime of COCO or ADEN much as is shown. Figure 3(c) extends the number of targets to 100 and shows the scalability of ADEN against different values of ϵ. Smaller ϵ leads to longer runtime and more obvious increasing trend in runtime. When ϵ = 30, ADEN can solve games with 100 targets in 20 minutes. We did not show the runtime of COCO in Figure 3(c) since it runs out of memory and fails to return a solution when the number of targets n > 15. Figure 3(d) shows the runtime of the sample procedure for sampling pure defender strategies based on the compact optimal mixed strategy computed by COCO.

6 Conclusion

This paper makes four key contributions in computing optimal mixed strategies to protect targets with dynamic payoffs: (1) A Stackelberg game model in which both agents have continuous strategy spaces and the payoffs are dynamic. (2) COCO for computing the optimal mixed defender strategy in a compact form when the defender can move resources from one target to another immediately. (3) A sample procedure for sampling implementable pure strategies based on the compact optimal mixed strategy computed by COCO. (4) ADEN for computing an approximately optimal mixed strategy when transfer time of resources is non-negligible. We also provide extensive experimental analysis that shows the solution quality and scalability of the proposed algorithms.

7 Acknowledgements

This work is supported by NSFC grant No. 61202212 and Singapore MOE AcRF Tier 1 grant MOE RG33/13. This research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its IDM Futures Funding Initiative and administered by the Interactive and Digital Media Programme Office.