Designing the Game to Play: Optimizing Payoff Structure in Security Games

1 Introduction

Research efforts in security games have led to success in various domains, ranging from protecting critical infrastructure [Letchford and Conitzer, 2013; Wang et al., 2016] and catching fare invaders in metro systems [Yin et al., 2012], to combating poaching [Fang et al., 2016] and preventing cyber intrusions [Durkota et al., 2015; Basilico et al., 2016]. In these games, a defender protects a set of targets from an attacker by allocating defensive resources. One key element that characterizes the strategies of the players is the payoff structure. Existing work in this area typically treats the payoff structure of the players as given parameters, sometimes with uncertainties known a priori given the nature of the domain. However, under various circumstances, the defender is able to change the attacker's payoff, thus rendering the existing models inadequate in expressiveness. For example, in wildlife poaching, the law enforcement agency may charge a variable fine if the poacher is caught at different locations, e.g., in the core area vs. in the non-core area. In cybersecurity, the network administrator may change the actual or appeared value of any network node for a potential attacker. In these cases, the defender's decision making is two-staged: she chooses the payoff structure, as well as the strategy of allocating defensive resources. With a properly chosen payoff structure, the defender may save the effort by achieving much better utility with the same or even less amount of resources.

∗Z. R. Shi and Z. Tang contributed equally to this work.

As existing work in security games does not provide adequate tools to deal with this problem (see Section 2 for more details), we aim to fill this gap as follows. We study how to design the attacker's payoff structure in security games given budget constraints in weighted Lp -norm (p = 0, 1, ∞). That is, the distance between the original payoff structure and the modified payoff structure is bounded, using distance metrics such as Manhattan distance (i.e., L1 -norm) with varying weights for reward and penalty of different targets. The intuition behind this setting is that the defender can change the payoffs to make a target that is preferable to the defender more attractive to the attacker and disincentivize the attacker from attacking targets that can lead to a significant loss to the defender. More change incurs a higher cost to the defender and the defender has a fixed budget for making the changes. Our findings can be summarized as follows:

L1 -norm case: When the budget constraint is in weighted L1 -norm form, i.e. additive cost, our contribution is threefold. (i) We exploit several key properties of the optimal manipulation and propose a mixed integer linear program (MILP)- based algorithm with approximation guarantee. (ii) We propose a novel branch-and-bound approach with improved efficiency achieved by effective pruning for the general case. (iii) Finally, we show that a polynomial time approximation scheme (PTAS) exists for a special but practical case where the budget is very limited and the manipulation cost is uniform across targets. The PTAS is built upon the key observation that there is an optimal solution where no more than two targets' payoffs are changed in this restricted case.

L0 and L∞-norm cases: We propose a O(n3 ) and a O(n2 log n) algorithm for problems under budget constraints in L0 -norm form and weighted L∞-norm form, respectively, where n is the total number of targets. For L0 -norm form budget, i.e. limited number of targets to manipulate, our algorithm converts the problem into O(n2 ) subproblems and reduces each subproblem to a problem of finding a subset of items with the maximum average weight. The latter can be solved in O(n) time. For L∞-norm form budget, i.e. limited range of manipulation on each target, we reduce the problem to traditional Stackelberg Security Games with fixed payoff structure, which again admits an efficient algorithm.

Numerical evaluation: We provide extensive experimental evaluation for the proposed algorithms. For problems with L1 -norm form budget constraint, we show that the branchand-bound approach with an additive approximation guarantee can solve up to hundreds of targets in a few minutes. This is faster than other baseline algorithms we compare to. Somewhat surprisingly, naively solving n non-convex subproblems using interior point method achieves good performance in practice despite that there is no theoretical guarantee of solution quality. We also evaluate the proposed O(n3 ) algorithm for the L0 -norm form case and show its superior performance over two greedy algorithms and a MILP based algorithm.

2 Preliminaries and RelatedWork

The security game that we consider in this paper features a set of n targets, T = {1, 2, . . . , n}. The defender has r units of defensive resources, each can protect one target. The attacker can choose to attack one target after observing the defender's strategy. If the defender covers target i when it is attacked, the defender gets a reward Rd i ≥ 0 and the attacker gets a penalty P a i ≤ 0. Otherwise, the defender gets a penalty P d i ≤ 0 and the attacker gets a reward Ra i ≥ 0. When the defender commits to a mixed strategy c, that is, covering target i with probability ci, the defender's and attacker's expected utilities when target i is attacked are U d i = ciRd i + (1 - ci)P d i and U a i = ciP a i + (1 - ci)Ra i , respectively.

We adopt the commonly used solution concept of Strong Stackelberg Equilibrium (SSE) [Kiekintveld et al., 2009]. At an SSE, the defender chooses an optimal strategy that leads to the highest expected utility for her when the attacker chooses a best response (assumed to be a pure strategy w.l.o.g), breaking ties in favor of the defender. Given a coverage c, the attack set Γ ⊆ T contains all the targets which have a weakly higher attacker's expected utility than any other target, i.e.,

[Kiekintveld et al., 2009] show that there exists an SSE where the defender only covers the targets in the attack set.

Given the game parameters, the optimal defender strategy in such a game can be computed using multiple linear programs (LPs) [Conitzer and Sandholm, 2006] or an efficient O(n2 ) algorithm called ORIGAMI [Kiekintveld et al., 2009] based on enumerating the possible attack sets. We leverage insights from both works to devise our algorithms.

Although many algorithms have been developed for security games under various settings, in most of the existing literature, the payoff structure is treated as fixed and cannot be changed by the defender, either in the full information case [Korzhyk et al., 2010; Paruchuri et al., 2008; Laszka et al., 2017], or in the presence of payoff uncertainties [Kiekintveld et al., 2013; 2011; Yin and Tambe, 2012; Letchford et al., 2009; Blum et al., 2014]. As mentioned earlier, in many real-world scenarios the defender has control over the attacker's payoffs. The approaches above ignore this aspect and thus leave room for further optimization.

Indeed, despite its significance, jointly optimizing the payoff structure and the resource allocation is yet underexplored. A notable exception, and a most directly related work to ours, is the audit game model [Blocki et al., 2013; 2015]. The defender can choose target-specific "punishment rates", in order to maximize her expected utility offset by the cost of setting the punishment rate. Compared with their model, ours is more general in that we allow not only manipulation of attacker's penalty, but also attacker's reward.

This realistic extension makes their core techniques inapplicable. Also, we treat the manipulation cost as a constraint instead of a regularization term in the objective function, for in some real-world settings, payoffs can be manipulated only once, yet the defender may face multiple attacks afterwards. This makes it hard to determine the regularization coefficient. Another closely related work [Schlenker et al., 2018] focuses on the use of honeypot [Kiekintveld et al., 2015; Durkota et al., 2015; Píbil et al., 2012]. It studies the problem of deceiving a cyber attacker by manipulating the attacker's (believed) payoff. However, it assumes the defender can only change the payoff structure, ignoring the allocation of defensive resources after the manipulation. [Horák et al., 2017] study the manipulation of attacker's belief in a repeated game. They assume actively engaging attacker and defender, which is not the case in our problem.

If we conceptually decouple the payoff manipulation from resource allocation, the defender faces a two-stage decision. She first chooses the structure of the game, and then plays the game. Thus, our problem may be viewed as a mechanism design problem, albeit not in a conventional setting. Most work in mechanism design considers private information games [Fujishima et al., 1999; Myerson, 1989], while in our work, and in most security game literature, the payoff information is public. Some design the incentive mechanism using a Stackelberg game [Kang and Wu, 2015], with applications to network routing [Sharma and Williamson, 2007], mobile phone sensing [Yang et al., 2012], and ecology surveillance [Xue et al., 2016]. However, these works solve the Stackelberg game to design the mechanism, rather than designing the structure of the Stackelberg game.

3 Optimizing Payoff with Budget Constraint in Weighted L1 -norm Form

In this section, we focus on computing the optimal way of manipulating attacker's payoffs and allocating defensive resources. Payoff manipulation is subject to a budget constraint in weighted L1 -norm form, i.e., the defender can change the attacker's reward and penalty, at a cost that grows linearly in the amount of change. The cost rate, referred to as weights, may be different across targets. This is an abstraction of several domains. For example, a network administrator may change the actual or appeared value of any network node although such change often incurs time and hardware costs.

Let Ra , P a , ¯Ra , ¯ P a denote the attacker's reward and penalty vectors before and after the manipulation. Similar to the initial payoff structure, we require that ¯Ra ≥ 0 ≥ ¯ P a and denote Dj = Ra j -P a j . Let ϵ = ¯Ra -Ra and δ = ¯ P a -P a be the amount of change in attacker's reward and penalty and µ, θ the weights on ϵ, δ resp.. The weighted L1 budget constraint is then ∑j (µj|ϵj| + θj|δj|) ≤ B where B is the budget. The defender's strategy is characterized by (c, ϵ, δ). Given this strategy, in the manipulated game the attacker attacks some target t, which belongs to the attack set Γ. We first show some properties of the optimal solution.

Property 1. There is an optimal solution (c, ϵ, δ) with corresponding attack target t and attack set Γ which satisfies the following conditions:

Proof sketch. Condition 1: If any ϵj, δj ̸= 0 with j /∈ Γ, we may either set ϵj, δj = 0 or push j into the attack set. There is no need to protect a target that is not in the attack set. Condition 2: Flipping the sign of ϵ and δ leads to no better solution. Condition 3: For each target i, we can shift the change on Ra i to P a i and vice versa while one is more budget efficient than the other depending on coverage. We can show that these manipulations can be done simultaneously. 1

Similar to the multiple LPs formulation in [Conitzer and Sandholm, 2006], we consider n subproblems Pi, each assuming some target i ∈ T is the attack target, and the best solution among all n subproblems is the optimal defender strategy. Condition 2 in Property 1 shows it is possible to infer the sign of ϵ and δ given the attack target. So in the sequel, we abuse the notation by treating ϵ, δ as the absolute value of the amount of change, and assume w.l.o.g. that in Pi, ¯Ra i = Ra i +ϵi, ¯ P a i = P a i +δi and ∀j ̸= i, ¯Ra j = Ra j -ϵj, ¯ P a j = P a j - δj. Thus, a straightforward formulation for Pi is

≥ U a

j = cj(P a

j - δj) + (1 - cj)(Ra

j - ϵj), ∀j ̸= i

The above formulation is non-convex due to the quadratic terms in Constraint 3 which leads to an indefinite Hessian matrix, and thus no existing solvers can guarantee global optimality for the above formulation.

3.1 AMILP-based Solution with Approximation Guarantee

To find a defender strategy with solution quality guarantee, we solve the atomic version of the subproblems with MILPs. We show an approximation guarantee which improves as the fineness of discretization grows. We further propose a branch-and-bound-like framework for pruning subproblems to improve runtime efficiency.

In the atomic version of the payoff manipulation problem, we assume the defender can only make atomic changes, with the minimum amount of change given as ρ0. We refer to the atomic version of Pi as APi. APi can be formulated as the MILP in Equations 9-19. We simplify the objective function as ci since Di ≥ 0. All constraints involving sub/super-script j, k without a summation apply to all proper range of summation indices. We use binary representation for ¯Ra i /ρ0 and ¯ P a i /ρ0 in constraints 10-14. The binary representation results in bilinear terms like yk j cj . We introduce variables αk j , βk j and constraints 18-19 to linearize them.

1 Due to limited space, the full proofs are included in the full version of the paper: https://arxiv.org/abs/1805.01987

s.t. Constraint 4-8

The optimal defender strategy for the atomic payoff manipulation problem can be found by checking the solution to all the subproblems and compare the corresponding U d i . We can also combine all the subproblems by constructing a single MILP, with additional variables indicating which subproblem is optimal. The details can be found in the full version.

A natural idea to approximate the global optima of the original L1 -constrained payoff manipulation problem is, for each attack target i, approximate Pi with APi using small enough ρ0. Theorem 1 below shows such an approximation bound.

Theorem 1. The solution of the atomic problem is an additive maxi 2ρ0(Rd i -P d i ) Ra i -approximation to the original problem.

Proof sketch. The floor and ceiling notations are about the "integral grid" defined by ρ0. Suppose (c∗ , ϵ∗ , δ∗ ) is an optimal solution to Pi. Let ϵ′ = ⌊ϵ∗ ⌋, δ′ = ⌊δ∗ ⌋, and c′ = c∗ except c′i = c∗i - 2ρ0/(Di + ϵ′i - δ′i ). We can show such feasible solutions yield the desired approximation bound.

We note that the idea of discretizing the manipulation space is similar to [Blocki et al., 2013; 2015]. Yet allowing changes in both reward and penalty and the difference in objective function make our formulation different and the reduction to SOCP used in [Blocki et al., 2015] inapplicable.

We can further improve the practical runtime of the MILPs by pruning and prioritizing subproblems as shown in Alg. 1. We first compute a global lower bound by checking a sequence of greedy manipulations. Inspired by Condition 2 and 3 in Property 1, we greedily spend all the budget on one target to increase its reward or penalty, leaving all other targets' payoff parameters unchanged (Lines 2 - 8).

Upper bounds in Pi can be computed with budget reuse: we independently spend the full amount of budget B on each target to increase Ra i and P a i and decrease Ra j and P a j , j ̸= i, as much as possible. For the ease of notation, in Alg. 1 we

Algorithm 1 Branch-and-bound

Input: Payoffs σ = {Rd , P d ,Ra , P a }, budget B 1: Initialize LB ← ∅, globalLB ← -∞,N ← ∅ containing set of indices of pruned subproblems. Set ρ0 to be a desired accuracy. 2: for SubproblemPi do 3: Greedy Modifications (GM): 4: GM1 ← ¯Ra i = Ra i +B 5: GM2 ← ¯ P a i = min{P a i +B, 0}, ¯Ra i = max{Ra i ,Ra i +B +P a i } 6: LBi ←maxj∈{1,2} ORIGAMI-BS(GMj) 7: end for 8: globalLB ←maxi∈[n] LBi 9: Sort Pi in decreasing LBi. 10: for sorted Pi do 11: Overuse Modifications (OM): ∀j ̸= i, ¯Ra j = max{0,Ra j - B}, ¯ P a j = min{P a j , P a j -B +Ra j } 12: OM1 ← ¯Ra i = Ra i +B. 13: OM2 ← ¯ P a i = min{P a i +B, 0}, ¯Ra i = max{Ra i ,Ra i +B +P a i } 14: UBi ←minj∈{1,2} ORIGAMI-BS(OMj) 15: if UBi ≤ globalLB then 16: Prune Pi 17: else 18: run MILP of Pi with additional constraint ci ≤ globalLB-P d i Rd i -P d i 19: end if 20: end for 21: Output: Best solution among globalLB and all Pi's.

assume manipulations have uniform cost. The weighted case can be easily extended.

The subproblem Pi is pruned if its upper bound is lower than the global lower bound. To make the pruning more efficient, we solve subproblems in descending order of their corresponding lower bounds, hoping for an increase in the global lower bound. For subproblems that cannot be pruned, we set ρ0 to the desired accuracy and solve the MILP to approximate the subproblem optima. We also add to the MILP the linear constraint on ci derived from the global lower bound.

To get the bounds, we call an improved version of the ORIGAMI algorithm in [Kiekintveld et al., 2009] by doing a binary search on the size of the attack set Γ, and solve the linear system. It is denoted as ORIGAMI-BS in Alg. 1. Recall r is the defender's total resource. Let M be the attacker's expected utility for attack set and ¯Ek = 1 ¯Ra i - ¯ P a i .

We iteratively cut the search space by half based on cj and M. The complexity improves from O(n2 ) to O(n logn). A complete description can be found in the full version.

We end this subsection by remarking that atomic payoff manipulation arises in many real-world applications. For example, it is infeasible for the wildlife ranger to charge the poacher a fine of $100/3. In those cases, our proposed MILP formulation could be directly applied.

3.2 PTAS for Limited Budget and UniformCosts

We show that for a special but practical class of problems, there exist a PTAS. In many applications, the defender has only a limited budget B ≤ minj∈T{∣∣P a j ∣∣ , Ra j }. Additionally, the weights on ϵ and δ are the same. W.l.o.g., we assume

Algorithm 2 PTAS for a special case in L1

Input: Payoffs {Rd , P d ,Ra , P a }, budget B, tolerance η. 1: InitializeM ←-∞ 2: for all ordered pairs of targets (i, j) do 3: for s = 0, 1, . . . , ⌊B/η⌋ do 4: M ←max{M, ORIGAMI-BS(Rd , P d ,Ra +sei-(B-s)ej,Rd )} 5: M ←max{M, ORIGAMI-BS(Rd , P d ,Ra +sei,Rd -(B-s)ej)} 6: M ←max{M, ORIGAMI-BS(Rd , P d ,Ra ,Rd +sei-(B-s)ej)} 7: M ←max{M, ORIGAMI-BS(Rd , P d ,Ra -(B-s)ej,Rd +sei)} 8: end for 9: end for 10: Output: M

µj = θj = 1. We first show a structural theorem below and then discuss its algorithmic implication.

Theorem 2. When budget B ≤ minj∈T{∣∣P a j ∣∣ , Ra j } and µj = θj = 1, ∀j ∈ T , there exists an optimal solution which manipulates the attack target and at most one other target.

Proof sketch. Since B is limited, either Ra t or P a t is unchanged according to Condition 3 of Property 1. Assume all manipulations happen on attacker's reward. If some three targets get manipulated, we can simultaneously increase ϵt for attack target t and decrease ϵj for j ̸= t such that j's utility increases to be the same as target t, until some ϵj becomes 0. After such change, the defender's utility does not decrease, and the number of targets manipulated decreases. Other cases also hold due to symmetry.

The theorem above is tight, i.e. we show in the full version an instance where two targets are manipulated. When B ≤ minj∈T {∣∣P a j ∣∣ , Ra j } and µj = θj = 1, ∀j ∈ T , Theorem 2 naturally suggests a PTAS - we can use linear search for manipulations on all pairs of targets as shown in Alg. 2, where ei is a unit vector with a single one at position i. Theorem 3 shows the approximation guarantee, with a proof similar to Theorem 1, which is included in the full version.

Theorem 3. Alg. 2 returns an additive maxi∈[n] 2η(Rd i -P d i ) Ra i approximate solution.

4 Optimizing Payoff with Budget Constraint in Other Forms

In this section, we explore budget constraints in other forms and show polynomial time algorithms correspondingly.

4.1 Weighted L∞-normForm

When the budget constraint is in weighted L∞-norm form, the defender can make changes to Ra and P a for every target to the extent specified by Br i and Bp i respectively. Equivalently, the defender can choose Ra and P a from a given range. A real-world setting for this problem is when a higher level of authority specifies a range of penalty for activities incurring pollution and allow the local agencies to determine the concrete level of penalty for different activities.

We observe that Condition 2 of Property 1 still holds in this setting. Therefore, such problem can be solved by simply solving n subproblems. In the ith subproblemwhich assumes i is the attack target, we may set reward and penalty of i to be the upper bound in the given range and choose the lower bound for other targets. With our improved ORIGAMI-BS algorithm, this problem can be solved in O(n2 log n) time.

Theorem 4. With budget constraint in weighted L∞-norm, solving for defender's optimal strategy reduces to solving for defender's optimal coverage in fixed-payoff security games.

4.2 L0 -normForm

When the budget constraint is in L0 -norm form, the defender needs to choose which targets to make changes, while the amount of change can be unconstrained. Notice that allowing the defender to arbitrarily modify the attacker's reward Ra is not practical and will lead to a trivial solution: the defender will place all coverage on one attack target t = argmaxi Rd i and set Ra t = ∞. Thus, we only allow the defender to change P a to ¯ P a and write ¯Ra = Ra . This corresponds to the domains where the defender can make some of the targets special. For example, in wildlife protection, legislators can designate some areas as "core zones", where no human activity is allowed and much more severe punishment can be carried out. But the defender cannot set all the areas to be core zones.

We assume the defender has a budget which allows her to change the penalty of B targets. Similar to the L∞ case, we first observe that the defender will choose an extreme penalty value once he decides to change the penalty of a target.

Property 2. There exists an optimal solution where either ¯ P a j = -∞ for B targets or ¯ P a j = -∞ for (B - 1) targets and ¯ P a t = 0 for 1 target. If ¯ P a j = -∞, then cj = 0.

Proof. When t is the attack target, the defender would like to maximize ¯ P a t and minimize ¯ P a j for all j ̸= t. If ¯ P a j = -∞ and cj > 0, target j will not be attacked as U a j = -∞. In such case, target j is effectively removed from the game.

The defender's problem becomes non-trivial when the budget B < T , and we now provide a O(n3 ) algorithm (Alg. 3) for solving this problem. We note that several intuitive greedy algorithms do not work, even in more restrictive game settings. A detailed comparison of our algorithm, several greedy algorithms, and a baseline MILP is provided in Section 5.

First, we sort the targets in decreasing attacker's reward Ra k . Let Ek = 1 Ra k-P a k and ¯Ek = 1 ¯Ra k- ¯ P a k for all k ∈ T . When i is the attack target, by Property 2, we have ¯Ei ∈ {1/Ra i ,Ei} and ¯Ej ∈ {0, Ej}. Let Γl = {1, 2, . . . , l} for l = 1, 2, . . . , n. We notice that one of the Γl's, denoted as Γl∗, encapsulates the attack set in the optimal solution to our problem. That is, in the optimal solution, each target in the attack set is in Γl∗; those targets not in the attack set either are outside Γl∗, or, if they are in Γl∗, have ¯ P a = -∞. A proof can be found in the full version. This allows us to formally define a subproblem Ql,i: assume (i) the optimal attack set is encapsulated by Γl, (ii) the attack target is i ∈ Γl, and (iii) no target is covered with certainty, what is the defender's optimal strategy (c, ¯E)? A subproblem may be infeasible. First, we show that Ql,i can be solved in O(n) time. From Equation 21, for Ql,i, we have

Let s = min{B, l - 2} if ¯Ei = Ei and s = min{B - 1, l - 2} if ¯Ei = 1 Ri . Then Ql,i reduces to finding s out of the (l - 1) ¯Ek's to set to 0, and set the rest ¯Ek = Ek, so as

Input: Payoffs {Rd , P d ,Ra , P a }, budget B 1: Initialize U d (1..n, 1..n) ←-∞. 2: for attack set Γl do 3: for attack target i ∈ Γl do 4: {V alue, Γdrop l , Γkeep l } ← Random(〈v,w〉, s) 5: Set ¯Ej ← 0 for j ∈ Γdrop l , ¯Ej ←Ej for j ∈ Γkeep l . 6: If solution is valid, i.e. M ≥ Ra l+1 and cj ∈ [0, 1], then update U d (l, i) 7: Repeat inner iteration with s ← min{B - 1, l - 2} and ¯Ei ← 1/Ra i . 8: end for 9: end for 10: for target k with largest s P a k do 11: for attack target i do 12: Update U d (l, i) if r big enough for ck = 1 13: end for 14: end for 15: Output: max(U d )

to maximize the above quotient. As a result, Ql,i is closely connected to the problem of choosing subsets with maximum weighted average, which can be solved efficiently.

Proposition 1. [Eppstein and Hirschberg, 1997] Given a set S where |S| = n, real numbers {vk : k ∈ S}, positive weights {wk : k ∈ S}, and an integer r. Among all subsets of S of order n-r, a subset T ⊂ S which maximizes A(T ) = ∑k∈T vk ∑k∈T wk can be found in O(n) time.

Lemma 1. The subproblemQl,i can be solved in O(n) time.

Proof. Consider Equation 22. We equate vk = (Ri - Rk)Ek + m l-s-1 and wk = Ek + 1 l-s-1 ¯Ei. Let v = {vk : k ∈ Γl\{i}}, w = {wk : k ∈ Γl\{i}}. By Property 2, we may assume s targets will be removed. Finding a subset T ⊂ Γl\{i}, |T | = l-s-1, to maximize A(T) is equivalent to our problem to maximize the quotient in Equation 22.

After we find the optimal choices for the s targets, we need to verify on Line 6 of Alg. 3 that the attack set is valid. Since ck = 0 for k /∈ Γl, we need M ≥ Ra l+1 , where M is the attacker's expected utility as defined in Equation 20. We also need valid coverage probabilities cj 's. These could have been violated by setting some ¯ Pi's to -∞.

We are now ready to show the main result of this section.

Theorem 5. There is a O(n3 ) algorithm for finding the optimal defender strategy with budget constraint in L0 -norm.

Proof sketch. Consider Alg. 3. Since Ra is fixed, Γl's cover all the attack sets that need to be checked. There are O(n2 ) subproblems Ql,i. For each Ql,i, we run a randomized algorithm for the maximum weighted average problem with expected running time O(n) (Line 4). A deterministic O(n) algorithm exists in [Eppstein and Hirschberg, 1997]. The subproblems Ql,i miss the solutions where some target j is covered with certainty. In this case, Γn is the only possible attack set, and the solution is found on Lines 10-14. A solution is feasible if by removing targets we can keep the sum of coverage probabilities below the defender's resources.

5 Experimental Results

5.1 Simulation Results for L1 Budget Problem

We compare our branch-and-bound (BnB) algorithm (Alg. 1) with three baseline algorithms - NonConv, multiple MILP,

• (a) Runtime, small instances
• (c) Runtime, large instances

(b) Gap, small instances

• (d) Gap, large instances

Figure 1: Runtime and solution quality for L1 case with standard deviation of the mean shown as vertical line

and single MILP. NonConv refers to solving n non-convex optimization problems as shown in Equations 2-8 using IPOPT [Wächter and Biegler, 2006] solver with default parameter setting, which converges to local optima with no global optimality guarantee. Multiple MILPs, as specified by Equations 9-19, and the single MILP formulation, in the full version, are equivalent and have an approximation guarantee specified in Thm. 1. The original payoff structures are randomly generated integers between 1 and 2n with penalties obtained by negation (recall n is the number of targets). Budget and weights of the manipulations are randomly generated integers between 1 and 4n.

We set ρ0 = mini∈T Ra i 4(Rd i -P d i ) which gives an additive 12 -approximate solution. Gurobi is used for solving MILPs, which is terminated when either time limit (15 min) or optimality gap (1%) is achieved. For each problem size, we run 60 experiments on a PC with Intel Core i7 processor. The solution quality of a particular algorithm is measured by the multiplicative gap between that algorithm and BnB, i.e. ZA-ZBnB ZBnB where ZA is best solution value by algorithmA. Thus a positive (negative) gap indicates better (worse) solution value than BnB. We report mean and standard deviation of the mean of runtime and solution quality in Fig. 1. Small instances refer to problem sizes from 5 to 25. Large instances refer to problem sizes from 50 to 250.

For problems of small size (Fig. 1a and 1b), BnB finds better solutions in nearly the same time as NonConv, faster than the other two. Since budget size can easily be indivisible by ρ0 which is the atomic change we can make, greedy manipulation cannot be achieved by MILPs when such indivisibility happens. On the other hand, BnB first computes a global lower bound using such greedy manipulations, thus creating a gap between BnB and the other two MILP-based algorithms. Indeed the multiplicative gap between the greedy solution and the optimal solution is reported as 0.39% with a variance of 0.14%. For problems of large size (Fig. 1c and 1d), we only compare BnB and NonConv as the other two algorithms timed out in solving MILP. BnB runs faster than NonConv. It returns better solutions for three problem sizes and nearly the same solution for the other two cases. The MILP-based solution including BnB also has a larger standard deviation in runtime than NonConv.

5.2 Simulation Results for L0 Budget Problem

We compare the performance of our O(n3 ) algorithm with a baseline MILP and two greedy algorithms. Greedy1 removes a target that can lead to most solution quality increase at a time. Greedy2 starts from the target with highest |P d | and determines whether to remove it by checking the solution quality before and after removal. Details of these algorithms can be found in the full version.

Initial payoffs are generated in the same way as in the previous subsection. In Fig. 2a, we assume the defender has r = 1 resource and budget B = n/2, the worst case for the O(n3 ) algorithm. The runtime of MILP starts to explode with more than 100 targets, while the O(n3 ) algorithm solves the problem rather efficiently. We also note that MILP exhibits high variance in runtime. The variances of other algorithms, including the O(n3 ) algorithm, are relatively trivial and thus not plotted. We then test the algorithms with multiple defender resources, as shown in Fig. 2b. With n targets, we assume the defender has r = n/10 units of resources and a budget B = n/2. Most MILP instances reach the time limit of 5 minutes when n ≥ 100. Yet the O(n3 ) algorithm's runtime is almost the same as the single resource case.

Our O(n3 ) algorithm and MILP are guaranteed to provide the optimal solution. In contrast, the greedy algorithms exhibit fast runtime but provide no solution guarantee. We measure the solution quality in Fig. 2c and 2d using U d greedy-p U d opt-p where p = minj P d j . Greedy1, which runs slightly slower than Greedy2, achieves higher solution quality but both greedy algorithms can lead to a significant loss. In fact, extreme examples exist, as shown in the full version.

Acknowledgments

The research is initiated with the support of the CAIS summer scholar program.