# optimal_interdiction_of_illegal_network_flow__148ba687.pdf

Optimal Interdiction of Illegal Network Flow

Qingyu Guo1, Bo An2, Yair Zick3, Chunyan Miao2

1Joint NTU-UBC Research Centre of Excellence in Active Living for the Elderly, NTU, Singapore

2School of Computer Science and Engineering, Nanyang Technological University, Singapore

3School of Computer Science, Carnegie-Mellon University, USA

1,2{qguo005,boan,ascymiao}@ntu.edu.sg,3yairzick@cmu.edu

Large scale smuggling of illegal goods is a longstanding problem, with $1.4b and thousands of agents assigned to protect the borders from such activity in the US-Mexico border alone. Illegal smuggling activities are usually blocked via inspection stations or ad-hoc checkpoints/roadblocks. Security resources are insufﬁcient to man all stations at all times; furthermore, smugglers regularly conduct surveillance activities. This paper makes several contributions toward the challenging task of optimally interdicting an illegal network ﬂow: i) A new Stackelberg game model for network ﬂow interdiction; ii) A novel Column and Constraint Generation approach for computing the optimal defender strategy; iii) Complexity analysis of the column generation subproblem; iv) Compact convex nonlinear programs for solving the subproblems; v) Novel greedy and heuristic approaches for subproblems with good approximation guarantee. Experimental evaluation shows that our approach can obtain a robust enough solution outperforming the existing methods and heuristic baselines signiﬁcantly and scale up to realistic-sized problems.

1 Introduction Stopping undesirable behavior on a network is a problem pertaining to many security domains: disruption of enemy supply chains, infectious disease control, and the interception of illegal goods such as drugs or weapons. Physical networks are typically defended via checkpoints: physical roadblocks or inspection points positioned at various points in the network. In all network interdiction scenarios, the objective of those defending the network is to minimize the amount of ﬂow through the network. From a resource optimization perspective, this is an extremely challenging task. There are several factors interrelating here: ﬁrst, defender resources are limited; second, placing a guard at some point on the network does not guarantee that any smuggler passing through will be caught - it merely increases the likelihood of a successful capture; ﬁnally, it is natural to assume that smugglers have prior knowledge of defenders positioning via intelligence gathering. The defender is thus placed at a disadvantage: not only

does she have limited capability to stop an attack, her agents moves are also monitored; thus, smugglers may successfully evade checkpoints if these are constantly positioned in a predictable manner. Indeed, randomized allocation strategies are imperatively needed [GAO, 2009]. Our work addresses the following challenge:

Devise a formal methodology for guarding a large, complex network against undesirable ﬂow, considering action observability and limited resources. Our Contributions: In this paper, we introduce a novel Network Flow Interdiction Game (NFIG) model, where the defender allocates a ﬁxed number of security resources on the network, while the adversary commits to a feasible network ﬂow. To compute the optimal defender strategy, we ﬁrst provide a standard minimax bilevel formulation and reformulate it as a linear program (LP). However, due to the huge number of constraints and variables caused by exponentially large numbers of defender strategies and network paths, the LP is hard to solve. To overcome the computational challenge, we propose a Column and Constraint Generation (CCG) algorithm, with the following key contributions: i) we show that the algorithm converges to the Stackelberg equilibrium with ﬁnite iterations; ii) we show the NP-hardness of the Column Generation subproblem, and provide several novel algorithms to solve it, including an exact compact convex nonlinear program and a greedy algorithm with constantfactor approximation guarantee; iii) we provide an exact compact convex nonlinear program for the Constraint Generation subproblem as well as a fast local search based heuristic algorithm; iv) extensive experimental evaluation shows that our CCG framework can scale up to realistic-sized NFIG instances and signiﬁcantly outperform existing approaches.

Related Work: The network interdiction problem is well studied [Church et al., 2004]. In this model, we are given a weighted, directed or undirected graph, and our goal is minimizing the ﬂow through the graph via deletion of edges/nodes (other goals such as maximizing the shortest path, increasing detection probability and other interdiction methods such as decreasing edge capacity have been studied as well [Altner et al., 2010; Ball et al., 1989; Israeli and Wood, 2002; Malik et al., 1989; Wood, 1993; Guo et al., 2016]. Other works study stochastic network interdiction where the interdiction action is successful with some known probability p [Pan et al., 2001; Pan, 2005]. How-

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

Gulf of Mexico Pacific Ocean

Texas New Mexico Arizona California Oklahoma

Brownsville

San Antonio

Figure 1: Topography and Road Systems in the Southern Border.

ever, none of them consider the randomized resource allocation strategy, i.e., the mixed strategy, due to the impossibility to change the resource allocation frequently, especially for interdiction actions such as destroying arcs. Moreover, randomized resource allocation is known to be necessary to improve the interdiction efﬁciency; for example, in the smuggling domain, checkpoint operation status can actually change daily [GAO, 2009]. However, randomization does lead to a drastic increase in problem complexity: while in the deterministic network interdiction model an adversary s strategy has a compact representation (as a network ﬂow), it is not the case in our setting.

We model NFIG as a Stackelberg security game; security games try and ﬁnd the optimal resource allocation to defend some valuable facility, based on game-theoretic methodologies [Tambe, 2011; Yin et al., 2014]. However, in standard security game models, attacker strategies are typically compactly representable (e.g. a distribution over possible targets) [An et al., 2013; Yin et al., 2015; Gan et al., 2015]. Some recent work proposes network security games [Tsai et al., 2010; Jain et al., 2011; 2013]; here, the defender allocates security resources on a (transportation) network and the attacker chooses a reliable path to escape, and both players have exponentially large strategy spaces; our model differs from these works in several important ways. Most importantly, our goal is minimizing the ﬂow through a network, rather than preventing a single attacker from escaping; thus, the methodology proposed in existing works cannot be directly applied to our setting.

Motivating Domain: Our model is quite general, and can easily apply to various network security domains; to illustrate the underlying issues and motivation for our model choice, we now brieﬂy present the problem in the context of stemming the drug ﬂow through the US-Mexico border patrol. Figure 1 shows the major roads in the southern border area [GAO, 2009]. Drug smuggling in the southern border is dominated by 4 large well-organized and independent cartels: Sinaloa, Juarez, Gulf and Los Zetas, each of them controls the drug trafﬁcking over 1000-mile border and has its own major area of inﬂuence in the United States [Beittel, 2015; Rosenberg, 2015]. These organizations typically use commercial, private and rental vehicles to smuggle illegal goods via land points of entry (sources). The goods travel along

different paths on the road network to different destination cities (sinks) [DOJ, 2010; Rosenberg, 2015]. Trafﬁckers typically choose multiple transport paths, in order to avoid raising obvious suspicion by the inspection stations, and to mitigate losses in case of capture [Steinrauf, 1991].

In 2009, the Border Patrol operated 39 tactical checkpoints with ﬂexible and daily changeable operation status in the southern border, which are generally operated at ﬁxed locations. However, due to the shortage of staff, canines and basic facilities (i.e. security resources), only few of them are actually operational [GAO, 2009]. With this limitation for tactical checkpoints, randomized allocation strategies of limited security resources are essential; smugglers have the ability to observe the operational status of checkpoints, and make their best decision on trafﬁcking activities, such as the amount of drugs to move through different POEs and paths. Indeed, a testimony before Congress by the Arizona Attorney General, revealed the sophisticated surveillance and communication technologies used to monitor security vulnerabilities and adjust plans to increase the chance of success [Kibble, 2009].

2 Preliminaries

Our proposed NFIG models an attacker and a defender who take actions on a capacitated graph G = (V, E), with nodes set V and edges set E, and a capacity vector c, where capacity ce represents the maximum amount of adversary ﬂow passing through edge e without arousing obvious suspicion by inspection facilities (permanent checkpoints, sensors, etc). We assume that the graph has a unique source node (POE) s 2 V and a unique sink node t 2 V (drug distribution city in smuggling scenario). The unique source/sink assumption is no loss of generality: a graph with multiple source nodes and sink nodes can be transformed into a single-source-sink graph by adding two new nodes s and t as the new unique source and sink nodes respectively, connecting s to each source node and t to each sink node with proper capacitated edges. Let P denote the set of all s-t paths in G. For a path p 2 P, we say node v 2 p (edge e 2 p) if p passes through v (e). Let I denote the set of all inspection stations, such as the tactical checkpoints in the border patrol scenario, and an inspection station is operated if the defender assigns a security resource on it, such as staffs, canines, and inspection facilities. Each station i 2 I is characterized by a location, either a node or an edge in the graph (with a bit abuse of notation, we use i interchangeable with its location, such that i 2 V [ E), and a constant parameter i 2 [0, 1] denoting the proportion of adversary ﬂow interdicted at i when operated, i.e., inspection probability. For example, in the border patrol scenario, the ofﬁcers at checkpoint i can conduct regular inspections on passing vehicles and an illegal trafﬁcker will be caught with some probability i depending on the ofﬁcers experience, which can be treated as a constant factor. Let k < |I| be the number of security resources owned by the defender.

Strategies: A defender pure strategy S = h Sii is an allocation of k security resources to k inspection stations, i.e., P

i2I Si = k, where Si 2 {0, 1} and Si = 1 indicates that the inspection station i is operated. The defender pure strategy space is denoted by S. A mixed defender strategy

x = hx Si is a probability distribution over all pure strategies where x S denotes the probability that S is played. Let X denote the defender mixed strategy space.

An attacker strategy is a network ﬂow f with fp representing the amount of adversary ﬂow passing along path p 2 P.1 In order to avoid raising obvious suspicion, a feasible attacker strategy must satisfy the capacity constraint on each edge. Let F denote the set of all feasible attacker strategies, i.e.,

p2P:e2p fp ce 8e 2 E}. (1)

Utility: Since the attacker aims at maximizing his successful drug ﬂow while the defender wants to minimize it, we assume NFIG a zero-sum game. Given a pure defender strategy S and an attacker feasible ﬂow f, the attacker s utility is the sum of successful ﬂows on all paths, i.e., Ua(S, f) = P

p2P Φ(S, p)fp, where

i2I:i2p(1 i)Si (2)

and Φ(S, p) represents the proportion of adversary ﬂow on path p not interdicted by the operated inspection stations given S. The defender utility is Ud(S, f) = Ua(S, f).

Given a defender mixed strategy x and an attacker feasible ﬂow f, the attacker s and defender s expected utilities are: Ua(x, f) = P

S2S x SUa(S, f) and Ud(x, f) = Ua(x, f). Equilibrium: NFIG is a leader-follower game, for which the widely adopted solution concept is the Stackelberg equilibrium (SE). Let y(x) denote the best response ﬂow against defender mixed strategy x. A strategy proﬁle hx , f i forms an SE, if: i) f = y(x ), and ii) Ud(x , f ) Ud(x, y(x)) for all x 2 X. With the zero-sum assumption, the SE can be obtained by the following minimax formulation:

minx2X maxf2F Ua(x, f). (3)

Since X, F are convex sets, and Ua(x, f) is a linear function in x when ﬁxing f and vice versa, according to von Neumann s minimax theorem [Nlkaido, 1954], we have:

minx2X maxf2F Ua(x, f)=maxf2Fminx2X Ua(x, f) (4)

A direct consequence of the minmax theorem, critical for our key solution approach (Section 3.2), is the equivalence of SE and the Nash equilibrium (NE), where x is the best response against f and f is also the best response against x .

3 Solution Approach

In this section, we ﬁrst provide an LP formulation to compute the equilibrium based on the standard minimax formulation. Since this LP has exponentially large number of variables and constraints, we then propose a novel Column and Constraint Generation (CCG) to further improve the scalability.

1Note that the compact representation f = hfei is infeasible in NFIG. Please see Section B of Online Appendix for the explanation available at: http://www.ntu.edu.sg/home/boan/papers/ IJCAI16 Flowinterdiction Appendix.pdf.

3.1 LP Formulation We start from the standard minimax formulation for SE:

S2S,p2P Φ(S, p)x Sfp (5a)

S2S x S = 1 (5b) X

p2P:e2p fp ce 8e 2 E (5c)

x 0, f 0. (5d)

The objective in Eq.(5a) is the attacker s expected utility Ua(x, f). The bilevel minimax program (5) can be reformulated as a linear program by replacing the inner program with its dual, and the resulting linear program (LP) is as follows:

e2E ceue (6a)

S2S x S = 1 (6b) X

S2S x SΦ(S, p)

e2p ue 8p 2 P (6c)

x 0, u 0. (6d)

The dual solution with respect to inequality (6c) provides the equilibrium attacker ﬂow f, deﬁned over all paths in P.

3.2 Column and Constraint Generation The linear program (6) is challenging to solve due to the exponentially large number of variables and constraints (|S|, |P|). To address this challenge, we propose a novel algorithm called Column and Constraint Generation (CCG), and prove the correctness of the CCG algorithm based on the property that the SE of SNIG is the same as the NE (Section 2).

The algorithm CCG is sketched in Algorithm 1. Initially, a small space h S0, P0i is generated with arbitrary candidate defender strategies and s-t paths. Then CCG solves a restricted version of NFIG with LP(S0, P0), where the defender pure strategy space is S0 and the attacker ﬂow is restricted to paths only in P0, i.e., Eqs.(6a) (6d) with h S, Pi replaced by h S0, P0i, and obtains primal and dual solutions (x, u, f). This restricted NFIG can be solved efﬁciently since the game is very small. Obviously, the obtained primal solution x and dual solution f form an SE of the restricted NFIG, but not necessarily the original NFIG. Therefore, two subproblems Col G (Column Generation) and Con G (Constraint Generation) are proposed to generate useful defender pure strategies and s-t paths into h S0, P0i in order to guide the SE of the restricted NFIG to the one of the original NFIG. Respectively, Col G generates a defender strategy S 2 S which is a best response against f, and Con G generates an s-t path p 2 P with maximal reduced cost which measures the degree of violating inequality (6c).

The key of the CCG algorithm is that once Col G generates the pure strategy S already in S0, the current solution x of restricted NFIG is the defender best response against the adversary ﬂow f in the original NFIG (PROPOSITION 1), and similarly, if Con G generates an s-t path p with non-positive reduced cost, the current equilibrium ﬂow f of restricted NFIG is the attacker best response ﬂow against x in the original NFIG (PROPOSITION 7). Therefore, the NE of the original

Algorithm 1: CCG Algorithm for NFIG

1 Initialize S0 by generating arbitrary defender strategies;

2 Initialize P0 by generating arbitrary s-t paths;

4 (x, u, f) LP(S0, P0);

5 S Col G(f);

6 S0 S0 [ {S};

7 p Con G(x, u);

8 P0 P0 [ {p};

9 until convergence;

10 return (x, f).

NFIG is achieved when Col G generates a pure strategy S already in S0 and Con G generates an s-t path p with nonpositive reduced cost. Since the NE is the same as the SE, the current solution pair (x, f) forms the SE of the original NFIG.

Comparison with Double Oracle: The double oracle (DO) algorithm, ﬁrst proposed by Mc Mahan et al. [2003], is a standard method for solving two-player zero-sum games with large scale strategy spaces, and is widely adopted by security game research [Jain et al., 2011; 2013; Vanek et al., 2012; Wang et al., 2016]. In DO, both players commit to mixed strategies. Thus, to apply DO to NFIG, the attacker s strategy is a probability distribution over all feasible ﬂows, rather than a single ﬂow. Besides, although the Core LP of DO can be obtained from minimax formulation with the same manner as LP (6), each constraint is associated with a feasible ﬂow (pure strategy) restricting the attacker s utility no smaller than that ﬂow. Thus, a best-response ﬂow is solved in DO s oracle, which is inefﬁcient due to no compact representation of ﬂows. As comparison, Con G solves an s-t path instead.

The central challenge and novelty of CCG is how to efﬁciently generate the pure defender strategies and s-t paths to add to S0 and P0. Thus, we present the corresponding Col G and Con G algorithms in the following sections.

4 Column Generation (Col G)

This section concerns the Col G subproblem of Algorithm 1, which can be stated as follows: given an attacker feasible ﬂow f deﬁned over P0, generate the defender pure strategy S 2 S blocking the largest amount of ﬂow, i.e., S = arg max S02S Ud(S0, f). PROPOSITION 1 shows that once Col G generates the pure strategy S already in S0, the current equilibrium mixed strategy x of restricted NFIG is the best response against f of the original NFIG.

Proposition 1. If Col G generates the pure strategy S already in S0, the current equilibrium mixed strategy x of restricted NFIG is the best response against f of the original NFIG.

We conduct thorough analysis of Col G s computational complexity, and show that it is NP-hard for general graphs, while polynomial-time solvable for the tree-like networks. For the ease of reading, we put proofs of all propositions and theorems in Section A of Online Appendix1.

Theorem 2. The Col G subproblem is NP-hard.

Algorithm 2: Greedy Algorithm for Column Generation

1 Initialize S0 = ;;

2 while |S0| < k do

3 i = arg maxi/2S0:S0[{i}2S Ud(S0 [ {i}, f);

4 S0 = S0 [ {i };

5 return S0.

Theorem 3. If the network G is tree-like, i.e., G {t} is a tree, then there exists a dynamic programming algorithm able to solve the Col G subproblem in polynomial time.

4.1 Convex Integer Nonlinear Formulation Disregarding the NP-hardness of Col G subproblem, we provide a compact integer program, with nonlinear objective function Ua(S, f), to solve it exactly. The program is proved to be convex (PROPOSITION 4) and hence can be solved to optimality with many commercial solvers, like KNITRO.

i2I:i2p(1 i)Sifp (7a)

i2I Si k (7b)

S 2 {0, 1}|I|. (7c)

Proposition 4. Given an attacker ﬂow f 2 F, the objective function (7a) is convex over decision variable S 2 [0, 1]|I|.

4.2 Greedy Algorithm We also propose a polynomial-time greedy algorithm of computing the approximate best response defender pure strategy, as shown in Algorithm 2 (we slightly abuse notation and let S represent the set of operated inspection stations). Starting from an empty set S = ;, we iteratively assign a security resource on an inspection station i which brings the maximal marginal utility Ud(S [ {i}, f) Ud(S, f), until all k resources are assigned. The approximate pure strategy S0 of Algorithm 2 and the approximate mixed strategy x0 computed by CCG with Col G solved by Algorithm 2 are proved to achieve competitive ratios (THEOREMS 5 & 6).

Theorem 5. The utility of S0 obtained by Algorithm 2 is bounded by Ud(S0, f) Ud(;, f) (1 1

e)(Ud(S , f) Ud(;, f)), where S is the optimal solution for Col G.

Theorem 6. Let (x , f ) be the equilibrium solution of an NFIG, and let (x0, f 0) be the solution computed by CCG algorithm with Col G subproblem solved by greedy Algorithm 2. Then Ud(x0, f 0) Ud(;, f 0) (1 1

e)(Ud(x , f ) Ud(;, f 0)).

5 Constraint Generation (Con G)

Given the optimal primal solution (x, u) of LP(S0, P0), the Con G subproblem generates an s-t path p 2 P that has maximal reduced cost deﬁned as: R(p) = P

S2S0 x SΦ(S, p) P

e2p ue, i.e., p = maxp02P R(p0). Note that R(p) 0 if and only if inequality (6c) associated with p is satisﬁed by (x, u). We show that if Con G generates an s-t path p such that R(p) 0, the current equilibrium ﬂow f of the restricted NFIG is the best response against x of the original NFIG.

Algorithm 3: VNS for Con G

1 Generate a random s t path p;

2 p Local Search(p);

3 while no termination condition is met do

4 p0 randomly pick one from N l(p);

5 p0 Local Search(p0);

6 if R(p0) > R(p) then p p0;

7 if R(p) > 0 then return p

Proposition 7. If the Con G generates an s-t path p with nonpositive maximal reduced cost, the current equilibrium ﬂow f of the restricted NFIG is the attacker best response pure strategy against x of the original NFIG.

5.1 Convex Integer Nonlinear Formulation We ﬁrst propose a compact convex integer program to solve the Con G problem exactly. Let binary variable γ 2 {0, 1}|V |+|E| denote an s-t path p, such that for every node v 2 V and edge e 2 E, γv = 1 if v is on path p and γe = 1 if e is on path p. We say node v 2 e if edge e is adjacent with v. The convex formulation is as follows:

e2E ueγe(8a)

e:s2e γe = 1,

e:t2e γe = 1 (8b) X

e:v2e γe = 2γv 8v 2 V, v 6= s, t (8c)

γe γv, γe γv0 8e 2 E : e = (v, v0) (8d) γs = γt = 1 (8e)

γ 2 {0, 1}|V |+|E|. (8f)

The convexity of the objective (8a) can be easily veriﬁed in the same way of proving PROPOSITION 4. Eqs.(8b) (8e) ensure that γ denotes a feasible s-t path p in the sense that: i) s and t are on p (8e); ii) exactly one edge adjacent with s (t) is on p (8b); iii) if node v, except s and t, is on p, then exactly two edges adjacent with v are on p (8c); and iv) if node v is not on p, then no edge adjacent with v is on p (8c).

Notice that the program (8) without constraint (8d) can also solve the Con G subproblem exactly. The integer programs are usually solved with the popular branch and bound (B&B) framework and the efﬁciency of B&B depends on the quality of the upper bound obtained by solving the linear relaxation of the program (8). Thus, inequality (8d) is proposed to tighten the upper bound by cutting off some fractional solutions with too high objective values, such an example is γ with: i) γe = 1 for e0 = (s, v0), e00 = (v00, t); ii) γv = 0.5 for v0 and v00; iii) γv = 0, γe = 0 for all other nodes and edges.

5.2 Variable Neighborhood Search (VNS) Although the convex program (8) can solve the Con G subproblem exactly, it still cannot scale up to solve large scale networks. Observe, however, in each iteration of CCG algorithm, we actually need not ﬁnd the path with maximal reduced cost; rather, any path with a large enough (positive) reduced cost would sufﬁce. Thus, a fast heuristic search for

Algorithm 4: Local Search (p)

2 p arg maxp02N l(p) R(p0);

3 if R(p ) > R(p) then p p ;

4 else return p;

generating such paths is satisfactory for most iterations, except when the heuristic is unable to ﬁnd a path with positive reduced cost. In this case we can call the convex program (8). To this end, we propose a heuristic search algorithm (Algorithm 3) based on Variable Neighborhood Search (VNS) framework [Hansen and Mladenovi c, 2001].

Two key components of VNS are: i) N l(p), denoting the set of neighbor paths of p within distance l; and ii) Local Search (p) to ﬁnd a local optimum starting from p (Algorithm 4). We say that path p0 is a neighbor path within distance l of p if p0 can be obtained by replacing a v0-v00 sub-path of p with another v0-v00 path of length no larger than l. The Local Search (p) iteratively searches for a neighbor path p with maximal reduced cost (Line 2) and updates current incumbent p if p is a better solution (Line 3), until a local optimum is obtained whose reduced cost is higher than all its neighbor paths.

After initialized with an arbitrary local optimum (Lines 1 2), the VNS randomly picks a neighbor path p0 of p and applies Local Search (p0) to ﬁnd a local optimum (Lines 4 5). Afterwards, the incumbent p is updated. This loop is repeated until a termination condition is met: i) current incumbent p has a positive reduced cost (Line 7); or ii) for cmax consecutive iterations, the incumbent p is not updated.

6 Experimental Evaluation We evaluate the performance of our approach through extensive experiments. We use CPLEX (version 12.6) to solve linear programs and KNITRO (version 9.0.0) to solve nonlinear programs. All computations were performed on a 64-bit PC with 16 GB RAM and a quad-core 3.4 GHz processor. All values are averaged over 40 instances unless otherwise speciﬁed. All random planar graphs are generated by the Waxman geographical model (WG) suitable for modeling highway networks [Waxman, 1988]. In the WG model, |N| nodes (cities) are placed in a rectangular domain uniformly, and each pair of nodes at Euclidean distance d is jointed by an edge with probability p = e λd, where λ is a constant adjusted to achieve the desirable average degree D. The two nodes with maximal Euclidean distance are set as the source and sink nodes of graph G. By default, the instances are parameterized as follows: the number of inspection stations |I| = b (|V | + |E|)c and the number of resources k = bβ(|V | + |E|)c, where and β are tunable parameters. All inspection stations are randomly placed on the graph. The edge capacity ce is randomly chosen in [0, 10], and inspection probability i [0.4, 0.6]. The l and cmax are set as 4 and |V | respectively in VNS.

We compare the scalability of three versions of our algorithms: i) CCG: Algorithm 1 with Col G and Con G solved by programs (7) and (8); ii) CCG*: Algorithm 1, where Col G and Con G are ﬁrst solved by greedy methods (Algorithms 2 and 3), and then call the programs (7) and (8) when greedy

0 50 100 150 200 250 300 350 400

10 20 30 40 50 60

Runtime(seconds)

Number of Nodes

0 100 200 300 400 500 600 700 800

10 20 30 40 50 60

Runtime(seconds)

Number of Nodes

10 20 30 40 50 60

Runtime(seconds)

Number of Nodes

0.2 0.25 0.3 0.35

Defender Utility

CCG* DMU DMT DMW

(d) Varying (β = 0.15)

0.05 0.1 0.15 0.2

Defender Utility

CCG* DMU DMT DMW

(e) Varying β ( = 0.3)

10 20 30 40 50 60

Defender Utility

Number of Nodes

CCG* DMU DMT DMW

-7 -6 -5 -4 -3 -2 -1

10 20 30 40 50 60

Defender Utility

Number of Nodes

CCG* DMU DMT DMW

(g) D=2.86.

10 20 30 40 50 60

Defender Utility

Number of Nodes

CCG* DMU DMT DMW

10 20 30 40 50 60

Defender Utility

Number of Nodes

CCG* DMU DMT DMW

(i) Robustness (20%)

CCG* DMU DMT DMW

Defender Utility

San Diego Laredo (j) Border Patrol Sectors

Figure 2: Runtime: 2(a) 2(c), Defender Utility: 2(f) 2(h), Vary and β: 2(d) 2(e), Robustness: 2(i), Real Application: 2(j).

methods return a pure strategy S already in S0 or path p with R(p) 0; iii) LP: the linear program (6), with the benchmark double oracle (DO) where two oracles solve the best response pure strategies (S, f) for both players [Jain et al., 2011].

To evaluate the solution quality of our approach, we implement three heuristic strategies as baselines. The quality of a solution x is measured by Ud(x, y(x)). The baseline mixed strategies are: i) DMU with marginal coverage probability of each inspection station equal to k |I|; ii) DMT where marginal coverage probability of each inspection station is normalized inspection probability; iii) DMW where marginal coverage probability of each inspection station is normalized inspection weight. The inspection weight wi of station i is deﬁned as the maximum amount of ﬂow that i can interdict, i.e., the production of i and the maximum amount of ﬂow passing through that edge or node; Given the marginal coverage probabilities, the defender mixed strategies are generated by the Combo Sampling algorithm [Tsai et al., 2010].

Scalability Analysis. We compare the scalability of our algorithms on WG graphs with varying degrees: D = 2.86 which is the mean degree of road network [Gastner and Newman, 2006], and D 2 {2.7, 3.0}. = 0.3 and β = 0.15. The results are depicted in Figures 2(a) 2(c), where DO cannot scale up to 50 nodes for D = 2.7 and D = 2.86 and 40 nodes for D = 3.0 with runtime cap of 1800 seconds, while LP cannot scale up to 30 nodes with memory cap of 8GB. The results show that although our approaches (CCG,CCG*) involve nonlinear programs (7) and (8), they still outperform LP and DO signiﬁcantly due to the compact representation. Besides, CCG* also outperforms CCG a lot which shows that the greedy methods (Algorithms 2 and 3) can obtain good enough solutions. Especially CCG* can scale up to realisticsized networks with 60 nodes and over 40 inspection stations and 20 resources, while the number of tactical checkpoints operated in the Southern border is 39 in 2009 [GAO, 2009].

Solution Quality Analysis. We also compare the solution qualities of our algorithms with three baseline strategies on WG graphs with varying degrees ( = 0.3 and β = 0.15), demonstrated by Figures 2(f) 2(h). It is clear that CCG* outperforms these baselines signiﬁcantly. Besides, the baseline DMW works best among the three baselines since the inspection weights well measure the capability of inspection

stations. Note that the numbers of inspection stations and resources are proportional with the network size, and hence there exists no monotone relationship between utility and network size.

Varying Values of and β. Figures 2(d) 2(e) show the solution qualities of CCG* and three baselines on WG graphs (|V | = 40, D = 2.86) with varying values of and β, from which we can see: i) with ﬁxed β, increasing improves the defender utility for more available inspection stations; ii) with ﬁxed , increasing β also improves the defender utility for more available resources. Moreover, CCG* outperforms these baselines signiﬁcantly for all tested values of and β.

Robustness. In reality, the attacker might not have perfect observation on the defender strategy. Thus, we compare the solution qualities of CCG* and baselines on WG graphs (|V | = 40, D = 2.86, = 0.3 and β = 0.15) with the attacker s estimation x0 of the defender strategy x randomly generated by: x0 = x/| x| where x S x S [1 δ, 1+δ]. The solution quality of x is measured by Ud(x, f 0) with f 0 being the attacker best response against x0. The result is depicted in Figure 2(i) with δ = 20%, and the result shows that our approach CCG* is robust enough and outperforms baselines signiﬁcantly under a high level of observation uncertainty.

Application on Southern Border Network. We also conduct experiments on two sectors in Southern Border Patrol: Laredo and San Diego sectors. Please see Section C of Online Appendix1 for details of these sectors. The results are depicted in Figure 2(j), showing that our approach signiﬁcantly outperforms the baseline methods for the realistic networks.

7 Conclusion

This paper studies the problem of optimally interdicting an illegal network ﬂow. We introduce a novel Stackelberg game model called NFIG, and propose a Column and Constraint Generation (CCG) algorithm to solve it. The computational complexity of its Col G subproblem is analyzed. Several novel algorithms are provided to solve the two subproblems including convex optimization, 1 1

e approximation method and a heuristic search algorithm. Experimental evaluation shows that CCG scales up to realistic-sized networks and signiﬁcantly outperforms existing methods and heuristics.

Acknowledgements This research is supported by NRF2015NCR-NCR003-004, the National Research Foundation, Prime Minister s Ofﬁce, Singapore under its IDM Futures Funding Initiative. The authors would like to thank the anonymous reviewers for their helpful comments.

References [Altner et al., 2010] Douglas S Altner, Ozlem Ergun, and Nelson A

Uhan. The maximum ﬂow network interdiction problem: Valid inequalities, integrality gaps, and approximability. Operations Research Letters, 38(1):33 38, 2010. [An et al., 2013] Bo An, Matthew Brown, Yevgeniy Vorobeychik,

and Milind Tambe. Security games with surveillance cost and optimal timing of attack execution. In AAMAS, pages 223 230, 2013. [Ball et al., 1989] Michael O Ball, Bruce L Golden, and Rakesh V

Vohra. Finding the most vital arcs in a network. Operations Research Letters, 8(2):73 76, 1989. [Beittel, 2015] June S. Beittel. Mexico: Organzied Crime and Drug Trafﬁcking Organizations. Congressional Research Service, 2015. [Church et al., 2004] R.L. Church, M.P. Scaparra, and R.S. Middle-

ton. Identifying critical infrastructure: The median and covering facility interdiction problems. Annals of the Association of American Geographers, 94(3):491 502, 2004. [DOJ, 2010] DOJ. National Drug Threat Assessment 2010. U.S.

Department of Justice National Drug Intelligence Center, 2010. [Gan et al., 2015] Jiarui Gan, Bo An, and Yevgeniy Vorobeychik.

Security games with protection externalities. In AAAI, pages 914 920, 2015. [GAO, 2009] GAO. BORDER PATROL: Checkpoints Contribute to

Border Patrols Mission, but More Consistent Data Collection and Performance Measurement Could Improve Effectiveness. U.S. Government Accountability Ofﬁce, 2009. [Gastner and Newman, 2006] Michael T Gastner and Mark EJ

Newman. The spatial structure of networks. The European Physical Journal B-Condensed Matter and Complex Systems, 49(2):247 252, 2006. [Guo et al., 2016] Qingyu Guo, Bo An, Yevgeniy Vorobeychik,

Long Tran-Thanh, Jiarui Gan, and Chunyan Miao. Coalitional security games. In AAMAS, 2016. [Hansen and Mladenovi c, 2001] Pierre Hansen and Nenad Mlade-

novi c. Variable neighborhood search: Principles and applications. European journal of operational research, 130(3):449 467, 2001. [Israeli and Wood, 2002] Eitan Israeli and R Kevin Wood. Shortest-

path network interdiction. Networks, 40(2):97 111, 2002. [Jain et al., 2011] Manish Jain, Dmytro Korzhyk, Ondrej Vanek,

Vincent Conitzer, Michal Pechoucek, and Milind Tambe. A double oracle algorithm for zero-sum security games on graphs. In AAMAS, pages 327 334, 2011. [Jain et al., 2013] Manish Jain, Vincent Conitzer, and Milind Tambe. Security scheduling for real-world networks. In AAMAS, pages 215 222, 2013. [Kibble, 2009] Kumar C. Kibble. Law enforcement responses to

mexican drug cartels. US Department of Homeland Security, 2009.

[Malik et al., 1989] Kavindra Malik, AK Mittal, and Santosh K

Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4):223 227, 1989. [Mc Mahan et al., 2003] H. Brendan Mc Mahan, Geoffrey J. Gor-

don, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In ICML, pages 536 543, 2003. [Nlkaido, 1954] Hukukane Nlkaido. On von neumann s minimax

theorem. Paciﬁc J. Math, 4:65 72, 1954. [Pan et al., 2001] F Pan, W Charlton, and DP Morton. Stochastic network interdiction of nuclear material smuggling. Network Interdiction and Stochastic Integer Programming, pages 1 19, 2001. [Pan, 2005] F. Pan. Stochastic network interdiction: models and

methods. Ph D thesis, University of Texas, Austin, 2005. [Rosenberg, 2015] Chuck Rosenberg. 2015-National Drug Threat

Assessment Summary. U.S. Department of Justice Drug Enforcement Administration, 2015. [Steinrauf, 1991] Robert L Steinrauf. Network interdiction models.

Technical report, DTIC Document, 1991. [Tambe, 2011] Milind Tambe. Security and Game Theory: Algo-

rithms, Deployed Systems, Lessons Learned. Cambridge University Press, 2011. [Tsai et al., 2010] Jason Tsai, Zhengyu Yin, Jun-young Kwak,

David Kempe, Christopher Kiekintveld, and Milind Tambe. Urban security: Game-theoretic resource allocation in networked domains. In AAAI, pages 881 886, 2010. [Vanek et al., 2012] Ondrej Vanek, Zhengyu Yin, Manish Jain,

Branislav Bosansk y, Milind Tambe, and Michal Pechoucek. Game-theoretic resource allocation for malicious packet detection in computer networks. In AAMAS, pages 905 912, 2012. [Wang et al., 2016] Zhen Wang, Yue Yin, and Bo An. Computing

optimal monitoring strategy for detecting terrorist plots. In AAAI, 2016. [Waxman, 1988] Bernard M Waxman. Routing of multipoint con-

nections. Selected Areas in Communications, IEEE Journal on, 6(9):1617 1622, 1988. [Wood, 1993] R Kevin Wood. Deterministic network interdiction.

Mathematical and Computer Modelling, 17(2):1 18, 1993. [Yin et al., 2014] Yue Yin, Bo An, and Manish Jain. Gametheoretic resource allocation for protecting large public events. In AAAI, pages 826 834, 2014. [Yin et al., 2015] Yue Yin, Haifeng Xu, Jiarui Gan, Bo An, and Al-

bert Xin Jiang. Computing optimal mixed strategies for security games with dynamic payoffs. In IJCAI, pages 681 688, 2015.