Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-plane Approach

1 Introduction

Recent deployments of attacker-defender Stackelberg security games (SSGs), such as for the US Federal Air Marshals Service (FAMS) or the US Coast Guard [Tambe, 2011] have led to significant research in integrating richer models of human (adversary) decision-making into SSGs [Pita et al., 2010; Yang et al., 2011]. These bounded rationality models [McKelvey and Palfrey, 1995; Camerer, 2011] step beyond assumptions of perfect adversary rationality in many SSG applications. In fact, a recent SSG application, the US Coast Guard's PROTECT system for randomized patrolling, uses one such adversary model: the quantal response (QR) model [McKelvey and Palfrey, 1995; Shieh et al., 2012].

This paper focuses on scaling up SSG algorithms integrated with any of a family of discrete choice models [Train, 2003], an important class of bounded rationality models of adversary decision making, of which QR is an important representative. Unfortunately, algorithms for handling such bounded rationality models in SSGs fail when faced with massive scale. These algorithms [Yang et al., 2012], require explicit enumeration of defender strategies, which is not feasible in massive-scale SSGs such as with the FAMS or the US Coast Guard in bigger ports. Previous work has provided branch-and-price (BnP) [Barnhart et al., 1994] as a key technique to avoid explicit enumeration of defender strategies in SSGs [Jain et al., 2010]; however, how well BnP would handle bounded rationality models is an unknown.

Fernando Ord ´o ˜nez

University of Chile Santiago, Chile fordon@dii.uchile.cl

To address this shortcoming in previous work, our first contribution investigates the effectiveness of BnP in SSG algorithms handling bounded rationality. As we illustrate via a BnP algorithm called COCOMO, the non-convexity of the objective function given bounded rationality adversary models creates enormous hurdles in scale-up.

The second and main contribution of this paper is then a new algorithm called BLADE, which for the first time illustrates an efficient realization of the cutting-plane approach in SSGs [Kelley, 1960; Boyd and Vandenberghe, 2008]. The cutting-planes approach iteratively refines the solution space via cuts. Our key hypothesis is that with these cuts, BLADE can successfully exploit the structure of the solution space of defender strategies - generated due to the bounded rationality adversary models in SSGs - whereas BnP approaches are blind to this structure. BLADE is based on three novel ideas. First, we present a separation oracle that can effectively prune the search space via deep cuts. More importantly we show that to handle massive scale SSGs, not only must this separation oracle itself use a secondary oracle but that this twolevel hierarchy of oracles is efficient. Second, we provide a novel heuristic to further speed-up BLADE by exploiting the SSG objective function to improve its cuts. Third, BLADE provides a technique for quality-efficiency tradeoff. As we experimentally demonstrate, BLADE is significantly more efficient than COCOMO.

2 Background and Notation

We consider an SSG [Conitzer and Sandholm, 2006; Yin et al., 2010] where a defender has a total of M resources to protect a set of targets T = {1, . . . , |T |} from an attacker. Given a target i, the defender receives reward Rd i if the adversary attacks a target that is covered by the defender; otherwise, the defender receives penalty P d i . Correspondingly, the attacker receives penalty P a i in the former case and reward Ra i in the latter. SSGs may be non-zero-sum, but Rd i > P d i and Ra i > P a i for all i.

We denote the j th defender pure strategy as Aj , which is an assignment of all the security resources. Aj is represented as a column vector Aj = 〈Aij〉T , where Aij indicates whether target i is covered by Aj. For example, in an SSG with 4 targets and 2 resources, Aj = 〈1, 0, 0, 1〉T represents the pure strategy of assigning one resource to target 1 and another to target 4. Let A = {Aj} be the set of feasible assignments of resources, i.e., the set of defender pure strategies. The defender's mixed-strategy can then be represented as a vector a = 〈aj〉, where aj ∈ [0, 1] is the probability of choosing Aj . A more compact representation of the defender's mixedstrategy is x = 〈xi〉, where xi = ∑Aj∈A ajAij is the marginal probability that a security resource will be assigned to target i [Kiekintveld et al., 2009]. Given xi, the expected utility of the defender if target i is attacked is U d i (xi) = xiRd i +(1-xi)P d i and the adversary's is U a i (xi) = xiP a i + (1 - xi)Ra i .

Our formulation exploits this compact marginal representation, but must then convert this representation to a mixed strategy over the actual defender pure strategies (i.e., 〈aj〉). Such conversion in the presence of resource assignment constraints is NP-hard [Korzhyk et al., 2010]; yet such constraints abound in security problems. For example, when air marshals are scheduled to protect two flights out of 100, not all (100 2 ) schedules are feasible. There are spatio-temporal constraints: the air marshal's two flights have to be connected, e.g., an air marshal cannot fly from Los Angeles to New York and then from Chicago to Seattle. Furthermore, there might be user-specified constraints [An et al., 2010]: FAMS might want to cover 50% of the flights to Chicago. Thus, the defender's optimization problem can be written as follows:

We denote the objective function in P1 as F(x). In F(x), U d i (xi) is the defender's expected utility if the adversary chooses target i; and qi(x) is the probability that the adversary chooses target i. qi(x) depends on the model used, e.g., assuming a QR model of the adversary, qi(x) is a logit function of x. This leads to a nonlinear fractional optimization problem [Yang et al., 2011], which in general is NP-hard [Vavasis, 1995]. Furthermore, Xf represents the feasible region of the marginal coverage vector, which is defined by the intersection of Xf1 which encompasses the spatio-temporal constraints, and Xf2 which encompasses the user-specified linear constraints on the marginals. Therefore, Xf = Xf1 ∩ Xf2.

3 Generalized PASAQ

Before discussing scale-up, we generalize the existing algorithms to solve SSGs integrated with bounded rationality models, as they are specialized to the QR model. More specifically, we generalize PASAQ, the fastest current algorithm to compute optimal defender strategy against a QR adversary model [Yang et al., 2012]. In PASAQ, the objective function of P1 is

QR is a representative of a more general form of the discrete choice model [Train, 2003; Goeree et al., 2005] for adversary response as shown in Equation (3). In SSGs, typically fi(xi) ≥ 0, ∀xi ∈ [0, 1] is a monotonically decreasing function of xi, indicating that as the defender's marginal coverage on target i increases, the probability that the adversary chooses this target decreases, e.g., in QR, fi(xi) = eλU a i (xi) is an exponentially decreasing function of xi.

G-PASAQ generalizes PASAQ to solve P1 with the general form of qi(x) in Equation (3). As with PASAQ, G-PASAQ solves this non-linear fractional optimization problem using binary search. At each step of the binary search it solves a non-convex optimization problem whose objective is a sum of nonlinear functions of marginal variables xi. Approximating each of these single-variable nonlinear functions as a piecewise-linear function with K segments, the non-convex problem is approximated by the MILP shown in Equation (4) - (9); this MILP solved in each iteration of the binary search.

The objective function in Equation (4) is a piecewise linear approximation of ∑i∈T (r - P d i )fi(xi) - ∑i∈T αixifi(xi) where αi = Rd i - P d i is a constant, γik is the slope of fi(xi) in the kth segments and μik is the corresponding slope of xifi(xi). The range of each xi is divided into K segments, and xi is replaced by the variables {xik, k = 1 . . . k} such that xi = ∑Kk=1 xik. {zik, k = 1..K} in Equation (6)-(8) are integer variables that decide the particular segment that xi lies in. For example, assuming K = 5, there are 5 possible sets of values for {zik} that satisfy the constraints in Equation (6)-(8). If we set {zi,1..3 = 1; zi,4 = 0}, then xi is in the fourth segment, i.e., xi ∈ [0.6, 0.8]. Equation (9) defines the feasible regions for x. More details are in [Yang et al., 2012].

4 COCOMO- A Branch-and-Price Algorithm

G-PASAQ assumes that the set of defender pure (A) can be explicitly enumerated.

strategies In massive SSGs, A cannot be enumerated; COCOMO (COlumn generation for COmplex adversary MOdels) attempts in such cases to use the branch-and-price approach to scale-

up G-PASAQ. COCOMO exploits the fact that the integer variables in G-PASAQ represent the particular piecewise linear segments each marginal xi belongs to and defines a branching tree shown in Figure 1. Initially at the root node, all the integer variables are relaxed to be continuous, indicating that none of the xi are set to any fixed ranges. The ith level in the tree is associated with marginal xi. If each marginal is divided into K segments, each node has K children. For example, in Figure 1, the two nodes at level 1 are associated with the two possible ranges of marginal x1: the left node sets x1 ∈ [0, 0.5], realized by setting z11 = 0; the right node sets x1 ∈ [0.5, 1], realized by setting z11 = 1. As we move deeper, more integer variable values are set. The tree has a depth of |T | and K|T | nodes in total.

COCOMO starts from the root node in the branching queue and iterates until the queue is empty. In each iteration, the top node in the branching queue is first branched into a set of children. For each child node, the upper bound (UB') and the lower bound (LB') are estimated. If the two bounds are not close enough, the node is added to the branching queue. COCOMO keeps a record of the best lower bound solution ( ˜ LB) found so far, and uses that to prune all the unvisited nodes in the branching queue. In the end, the defender strategy associated with this best lower bound is returned as the solution.

Upper Bound Estimation: To generate tighter upper bounds, we run G-PASAQ at each node of COCOMO, where the values of some variables zik are set to either 0 or 1 (see Figure 1). We obtain the upper bound by relaxing the rest of the integer variables to be continuous, resulting in an LP called UpperBound-LP. UpperBound-LP cannot escape the large number of variables aj and Aj; hence we apply the standard column generation technique: we start by solving UpperBound-LP with a subset of columns, i.e., defender strategies Aj, and iteratively add more columns with negative reduced cost. Let's first rewrite Equation (9) based on the definition of Xf from Equation (1) and (2).

The reduced cost of column Aj is ωT Aj - ρ, where ω and ρ are the duals of Equation (10) and (11) respectively. Given the optimal duals of the current iteration of UpperBound-LP, a separate Slave process provides a new column with the minimum reduced cost; the process iterates until convergence.

Slave: Given the spatio-temporal constraints, the Slave can often be formulated as a minimum-cost integer flow problem on a polynomial-sized network, e.g., [Jain et al., 2010] provide such a Slave formulation with application to the FAMS domain.

Lower Bound Estimation: A subset of the columns will be generated while solving the UpperBound-LP. The lower bound of the same node is computed by running GPASAQ with this subset of columns.

5 BLADE- ACutting-Plane Algorithm

Despite our effort for efficiency in COCOMO, the need to run column generation at each of the K|T | nodes ultimately leads to its inefficiency. BLADE (Boosted piecewise Linear Approximation of DEfender strategy with arbitrary constraints) uses the cutting-plane approach to scale-up G-PASAQ, and avoids running column generation at each node. Algorithm 1 presents BLADE. The Master is a modified version of P1 with a relaxed defender strategy space, defined by the set of boundaries ˜Hx ≤ ˜h. In Line (2), ( ˜H, ˜h) is initialized with the user-specified constraints, (B, b). The solution found by the Master, i.e., ˜x, provides an upper bound (UB) of the solution for P1. In each iteration, the Separation Oracle checks whether or not ˜x ∈ Xf . If so, the optimal solution of P1 has been found; otherwise, a new cutting plane Hlx ≤ hl is returned to further restrict the search space in the Master. The Separation Oracle also returns a feasible solution xf 'closest' to the infeasible solution ˜x, which provides a lower bound (LB = F (xf )) of the solution for P1. In Line (9), we improve our lower bound estimation to further speed up the algorithm. The algorithm terminates when UB and LB are close enough, i.e., UB - LB ≤ ϵ.

Algorithm 1: BLADE

1 Input: {Rd i , P d i ,Ra i , P a i }, (B, b), ϵ; 2 ( ˜H, ˜h) ← (B, b), feasible ← false; 3 UB←M, LB←-M; 4 while UB - LB > ϵ do 5 (UB, ˜x) ← Master( ˜H, ˜h); 6 (feasible, Hl, hl, xf )← SeparationOracle(˜x); 7 ˜H ← ˜H ∪ Hl , ˜h ← ˜h ∪ hl ; 8 if feasible ̸= true then 9 (LB, xl) ← LowerBoundEstimator( ˜H, ˜h) ; 10 return xl;

5.1 Master

We first reformulate P1 by representing its feasible region using the set of bouandries instead of the extreme points:

H is a N-by-|T | matrix, where N is the number of linear boundaries of the convex hull. Each row, Hlx ≤ hl, represents a linear boundary of Xf1. In the presence of userspecified constraints, Bx ≤ b is added to the boundary set of Xf , as defined in Equation (2). However, we cannot directly solve P1.1 because H and h are not initially given.

In BLADE, the Master solves P1.1 using G-PASAQ with a subset of the boundaries of Xf . More specifically, Equation (9) is rewritten as Equation (12) and (13):

( ˜H, ˜h) in Equation (13) represents the subset of the boundaries for Xf . The solution of Master, denoted as ˜x, then provides an upper bound on the solution of P1.1: F(˜x) ≥ F(x∗ ), where x∗ denote the optimal solution of P1.1. As the algorithm keeps refining the feasible region by adding new boundaries to the Master, this upper bound gets tighter.

Given ˜x as the relaxed solution from the Master, we check whether it belongs to Xf . If so, we have found the optimal solution of P1.1. Otherwise, we further restrict the feasible region in the Master via a cut to separate the current infeasible solution and the original feasible region.

5.2 Separation Oracle

One standard approach for checking feasibility and generating cutting planes is to apply Farkas' Lemma, as in [Papadimitriou and Roughgarden, 2008]. However, the resulting cutting planes are not guaranteed to be deep cuts that touch the feasible region and therefore eliminate as much of the infeasible region as possible. Instead, we use a norm-minimization approach for the Separation Oracle in BLADE, which efficiently checks the feasibility of ˜x, and generates a deep cut to separate Xf from an infeasible ˜x. Additionally, our approach finds a feasible point that is closest to ˜x, allowing us to compute a lower bound on the optimal objective.

Check Feasibility: The Separation Oracle checks the feasibility of ˜x by minimizing its distance to the feasible region. If the minimum distance is 0, ˜x is within the feasible region. We choose 1-norm to measure the distance between ˜x and any feasible point, as 1-norm leads to a Linear Program (LP), which allows the use of column generation to deal with large defender strategy space. We first show the Min-1-Norm LP in Equation (14)-(18),

In the above LP, a marginal coverage is represented by the set of defender pure strategies: Aa. Constraint (17) and (18) enforces that Aa satisfies both the spatio-temporal constraints and the user-specified constraints. The 1-norm distance between the given marginal ˜x and Aa is represented by vector z. This is obtained by combining Constraints (15) and (16): -z ≤ |Aa - ˜x| ≤ z. The objective function minimizes the 1-norm of z, therefore the 1-norm distance between ˜x and any given feasible marginal is minimized.

Lemma 1. Given a marginal ˜x, let (z∗ , a∗ ) be the optimal solution of the corresponding Min-1-Norm LP. ˜x is feasible if and only if ∑i∈T z∗ i = 0. Furthermore, Aa∗ provides the feasible marginal with the minimum 1-norm distance to ˜x.

Generate Cut: If ˜x is infeasible, we need to further restrict the relaxed region in the Master. Theoretically, any hyperplane that separates ˜x from the feasible region could be used. In practice, a deep cut is preferred. Let w, v, g and u be the dual variables of Constraints (15), (16), (17) and (18) respectively; and let y = w - v.

Lemma 2. Given an infeasible marginal ˜x, let (y∗ , g∗ , u∗ ) be the dual values at the optimal solution of the corresponding Min-1-Norm LP. The hyperplane (y∗ )T x-(g∗ )T b+u∗ = 0

separates ˜x and Xf :

Proof. The dual of the Min-1-Norm LP is:

Equation (19) can be proved using LP duality. Since ˜x is infeasible, the minimum of the corresponding Min-1-Norm LP is strictly positive. Therefore, the maximum of the dual LP is also strictly positive.

We now prove the contrapositive of Equation (20):

Given any x′ , there is a corresponding LP with the same formulation as that in Equation (21)-(23). Let (y′ , u′ , g′ ) be the optimal solution of this LP. Note that, (y∗ , u∗ , g∗ ) is a feasible solution of this LP. Therefore,

This indicates that the minimum 1-norm distance between x and Xf is strictly positive. Hence, x is infeasible.

Lemma 3. Equation (20) is a deep cut that touches the feasible convex hull Xf .

Proof. For simplicity, we consider the cases without userspecified constraints. The cut in Equation (20) then becomes (y∗ )T x + u∗ ≤ 0. Let aj be the dual of the j th constraint in Equation (22) and a∗ = 〈a∗j 〉 be the dual at the optimal solution of LP in Equation (21)-(23). According to the LP duality, Aa∗ is the optimal solution of the Min-1-Norm LP. Therefore, Aa∗ is the feasible marginal with the minimum 1-Norm distance to ˜x. Furthermore, ∀a∗j > 0, the corresponding constraint in Equation (22) is active, i.e. (y∗ )T Aj + u∗ = 0. Hence, the extreme point Aj is on the cutting-plane.

Therefore, by solving either the Min-1-Norm LP or its dual LP, the Separation Oracle can not only check the feasibility of a given marginal, but also generate a deep cut. We choose to solve the dual LP in Equation (21)-(23), since it gives the constraint directly as shown in Equation (20). However, since in our case the set of the defender's pure strategies is too large to be enumerated, the constraints of the LP cannot be enumerated.We solve the LP using a constraint generation approach, outlined in Algorithm2. Specifically, we solve the LP in Equation (21)-(23) with a subset of constraints first, and use a Secondary Oracle to check whether the relaxed solution violates any of the other constraints.

Secondary Oracle: The secondary oracle is executed at Line (6) in Algorithm 2. If any constraint in Equation (22) is violated, the oracle returns the one that is most violated, i.e., Al with the most negative value of the LHS of Equation (22); otherwise, we have found the optimal solution of the LP. The secondary oracle is similar to the Slave in COCOMO.

Algorithm 2: Separation Oracle

1 Input: {Rd i , P d i ,Ra i , P a i }, (B, b), ˜x, A(0) ; 2 A←A(0) , Al ←A1; 3 while Al ̸= ∅ do 4 A←A∪Al; 5 (y∗ , u∗ , g∗ ) ← Solve-Separation-Oracle-LP(A); 6 Al ←SecondaryOracle(y∗ , u∗ , g∗ ); 7 return (y∗ , u∗ , g∗ );

5.3 WBLADE

The convergence of BLADE depends on how fast the cuts generated by the Separation Oracle approximate the feasible set around the optimal solution of P1.1. We propose WBLADE, which modifies the Separation Oracle by changing the norm used to determine the distance to Xf for one that takes the objective function into account, to bias the cut generated toward the optimal solution. Formally, given the solution ˜x from the Master, instead of searching for the feasible point with the 1norm distance, which is uniform in all dimensions, we modify the objective function of the Min-1-Norm LP in Equation (14) as:

where ∇iF(˜x) is the gradient of objective function F(x) at point ˜x with respect to xi; ξ is a pre-defined constant to ensure that ∇iF (˜x) + ξ > 0, ∀i so the objective remains a norm. We refer to this modified LP as Min-Weighted-Norm LP.

Lemma 4. A marginal ˜x is feasible if and only if the minimum of the corresponding Min-Weighted-Norm LP is 0.

Proof. We already showed that zi ≥ 0 represents the absolute difference between ˜x and the feasible point Aa on the ith dimension. Combining with ∇iF(˜x) + ξ > 0, ∀i, we have ∑i (∇iF(˜x) + ξ)zi ≥ 0. According to Lemma 1, ˜x is feasible if and only if the minimum of ∑i zi is 0. Hence, if there exists (z∗ , a∗ ) such that ∑i z∗ i = 0, we have ∑i (∇iF (˜x) + ξ)z∗ i = 0; and vice versa.

To provide some intuition into why tighter bounds can be obtained by solving Min-Weighted-Norm LP, we consider the case when ∇iF(˜x) > 0 and ˜x ≥ Aa. First we note that these are typical situations in security games, where having more defense resources tends to benefit the defender. This is the case even if the attacker is boundedly rational, as in the quantal response model. Therefore for most values of ˜x the gradient ∇iF(˜x) will be positive. As a result, a solution ˜x of the relaxed problem solved by the master will tend to use more resources than what is feasible, i.e., ˜x ≥ Aa. These properties are confirmed in our numerical experiments.

Then, if we have ∇iF(˜x) > 0 and ˜x ≥ Aa, the Min-Weighted-Norm LP is equivalent to minimizing ∇F (˜x) · (˜x - Aa) and hence also to maximizing

Equation (25) is the first-order Taylor approximation of F (x), maximizing which should provide a good lower bound if ˜x is close to the feasible region.

Regarding the cuts generated, since ∇F(˜x) > 0 we can take ξ = 0. In this case the Min-Weighted-Norm LP is looking for the projection point in Xf on the highest level-set perpendicular to ∇F(˜x). The cut generated, therefore, will be this highest level-set perpendicular to ∇F(˜x). Since the gradient points in the direction of maximum increase of its function, for sufficiently smooth functions and sufficiently close projection point, points with higher function values than the projection point would be eliminated by this cut. Figure 2(b) demonstrates an example: the shaded polyhedron represents the feasible region Xf . Given the infeasible point x′ and its gradient ∇F(x′ ), the solid line perpendicular to ∇F(x′ ) approximates the level-set of F(x). Therefore, the half-space on the direction of ∇F(x′ ) of that line would tend to have points with higher value of F (x) than the other half-space. This suggests that such a cut would prune more infeasible points with high objectives, leading to a tighter upper bound. Confirming this intuition, Figure 2(a) shows that over 30 random samples the upper-bound decreases faster in WBLADE: x-axis marks iterations in time, y-axis plots the upper bound.

5.4 Quality and Runtime Trade-off

The feasible point returned by the Separation Oracle provides a lower bound on P1.1. A better lower bound can be achieved by solving a restricted version of P1.1 (Line 9 in Algorithm 1). This can be done by replacing Xf1 with the convex hull formed by the subset of defender pure strategies generated in solving the Separation Oracle. These upper and lower bounds allow us to trade off between solution quality and runtime by controlling the threshold ϵ: as soon as UB - LB ≤ ϵ the algorithm returns the feasible solution associated with LB, which is guaranteed to be within ϵ of the optimal objective.

6 Experimental results

In this section, we compare COCOMO and BLADE assuming two different bounded rationality models. We take FAMS as our example domain. For each setup, we tried 30 game instances. In each game, payoffs Rd i and Ra i are random integers from 1 to 10, while P d i and P a i are random integers from -10 to -1; the feasible schedules for each unit of resources are generated by randomly selecting 2 targets for each schedule (we assume that each air marshal can cover 2 flights on a single trip, similar to [Jain et al., 2010]). In all experiments, the deployment-to-saturation (d:s) ratio is set to 0.5, which is shown to be computationally harder than any other d:s ratio [Jain et al., 2012]. Furthermore, we set the number of piecewise linear segments to be 15 for each fi(xi), given that 10

segments provide a sufficiently good approximation [Yang et al., 2012]. The results were obtained using CPLEX v12.2 on a standard 2.8GHz machine with 4GB main memory.

The BEST BLADE Given the two versions of BLADE, one with the non-weighted Separation Oracle and another with the weighted Separation Oracle, we investigate whether it would be more effective to combine them such that two cuts are generated in each iteration.

While this combined version CBLADE could generate more cuts per iteration reducing the total number of iterations, the runtime of each iteration might be longer. Our first set of experiment investigates the efficiency of the three BLADE algorithms. Figure 3 shows the average runtime of these three algorithms

with different number of targets. WBLADE achieves the shortest runtime, as shown in Figure 3. Furthermore, although on average CBLADE takes less iterations to converge, it generates more cuts than both BLADE and WBLADE. For example, with 60 targets, CBLADE takes 17 iterations on average to converge, while WBLADE and BLADE take 23 and 29 iterations respectively. However, the total cuts generated by CBLADE is 34 (2 cuts per iteration) which is more than WBLADE and BLADE. Given this result, we will use WBLADE as the representative of the BLADE family in the rest of the experiments.

Quantal Response Model Figure 4(a), 4(b) and 4(c) present the average runtime of COCOMO and WBLADE assuming a QR model of the adversary with λ parameter set to 0.76, as in [Yang et al., 2011]. In the experiment, we set

50 minutes as the runtime limit. The dashed line in the figures indicates that at that point at least some game instances were not completed within this time limit; and the absence of any markers afterward implies the trend continues. COCOMO cannot scale to 80 targets, as shown in Figure 4(a). In Figure 4(b), we vary the amount of user-specified constraints (i.e. percentage of the number of targets) while fixing the number of targets to be 60. The constraints were randomly generated inequalities of the marginal coverage vector 〈x〉. Increasing the amount of user-specified constraints doesn't impact the runtime of WBLADE, but significantly slows down COCOMO. We then vary the threshold from 0.4 to 0.01 as shown in Figure 4(c). COCOMO is only able to converge when the threshold is larger than 0.05;in comparison, the runtime of WBLADE slowly increases as the threshold decreases. Thus, WBLADE obtain much better solution quality within significantly shorter amount of time than COCOMO.

We further investigate the tradeoff between solution quality and runtime of WBLADE and show the result in Figure 4(d). We gradually increase the solution quality by decreasing the threshold under different number of targets, illustrating runtime-quality tradeoff.

A More Complex Bounded Rationality Model We now set fi(xi) = 1 1+e-λixi , a more complex model than QR.We investigate the impact of model complexity on the runtime of COCOMO and WBLADE. Figure 5(a) and 5(b) display the runtime comparison of COCOMO and WBLADE. As shown in Figure 5(a), while COCOMO could not finish running within 50 minutes in any of the settings, the runtime of WBLADE was less than 7 seconds for 20 targets. In Figure 5(b), we show that the runtime of BLADE gradually increases as the threshold decreases. In comparison, COCOMO is only able to finish running when the threshold is sufficiently large (≥ 0.4) leading to poor solution quality. Thus, as the bounded rationality model becomes more complex, BLADE's advantage over COCOMO is further magnified.

7 Summary

SSGs and their applications have emerged as a thriving area of research, but scalability, particularly in the presence of complex adversary models remains an open challenge. BLADE is today the only algorithm that can handle large-scale SSGs given bounded-rationality adversary models, and for the first time provides an efficient realization of the cutting-plane approach within SSGs.

Acknowledgments. This research was supported by Army Research Office under Grant W911NF-10-1-0185 and MURI

Grant W911NF-11-1-0332. F. Ord´o˜nez would also like to acknowledge the support of Conicyt, through Grant ACT87.