Network Interdiction

From NEOS

Jump to: navigation, search

(3A) Two-Person Zero-Sum games for Network Interdiction

-Interdiction in a two-person zero-sum game means that the interdictor is trying to counter any action made by the evader. Before every move the evader knows the probability of getter interdicted on each path they may take. The interdictor is trying to use the same probabilities in order to catch the evader in this giant cat and mouse game. To help give you a sense of what this means, please read the following example of drug smuggling in the Gulf of Mexico

Example: Assume Figure 1 is a network with six nodes, or locations in the Gulf Coast, connected by eight different arcs k. Each arc represents a possible route that could be chosen by an evader, or in this example, a drug smuggler. Each node holds a certain probability of detection pk , which is known by both the evader and the interdictor, in this example, the interdictor is the United States Dug Enforcement agency (DEA). Also in our example every node will have an assigned source of commodity or demand if di < 0. We will assume this example is a two-person, zero-sum game so there will be one evader and one interdictor. The flow on each arc will be denoted by y, with a max and min of the arc flow denoted as zk. There will be an indicator variable xk, which will be one if the interdictor inspects the arc, and 0 otherwise. The standard flow balanced equations are as follows;

\sum_{k{\in}FS(i)} y_k - \sum_{k{\in}RS(i)} y_k = d_i , for all i {\in} M

y_k {\geq} 0 , for all k {\in} A

-Where M is the set of nodes and A is the set of arc.

-The following equations show the in-and-out flows of each node. These are the long hand version of the equations above.

Node 1: y(1,2) + y(1,3) = 0

Node 2: y(2,3) + y(2,4) - y(1,2) = 0

Node 3: y(3,4) + y(3,5) - y(1,3) - y(2,3) = 0

Node 4: y(4,5) + y(4,6) - y(3,4) - y(2,4) = 0

Node 5: y(5,6) - y(3,5) - y(4,5) = 0

Node 6: -y(5,6) - y(4,6) = 0

-An indicator variable xk is used to describe whether or not a given arc k is searched or not. If the arc is searched the variable is 1, and if the arc is not searched the variable is 0, as shown in the following:

x(k) = \begin{cases} 1 & \mbox{searched}\\ 0 & \mbox{otherwise}\\ \end{cases}


-The payoff function for paths p to this two-person, zero-sum game is;

\upsilon(x,l) = \sum_{k{\in}A(p)} p_k x_k, for all probabilities and all paths p

Image:Interdiction_Map.JPG‎

(Figure 1)

Figure 1 depicts a network which contains five possible paths (p) that go from 1-6, made up of arcs (k). Each arc is a single arrow in this figure. Think of each node as a different destination in the Gulf, and the arcs the different paths that the evaders (drug smugglers) might take through the water.

The eight possible paths (l):

Path A: 1-2-4-6

Path B: 1-2-3-4-6

Path C: 1-2-4-5-6

Path D: 1-2-3-5-6

Path E: 1-2-3-4-5-6

Path F: 1-3-4-6

Path G: 1-3-4-5-6

Path H: 1-3-5-6

(3B) Two-Person Zero-Sum games for Network Interdiction (Numerical)

-Now that we understand the basics of the problem, we will now implement numerical data to find the optimal ark flows y(k). To do this we will need to be given the information that the evader and interdictor would be given in this two player game. This information includes destinations in the Gulf Coast, as well as the probability of detection on each connecting ark k

-Locations of nodes (Arbitrary for means of explanation only):

Node 1: Tampico, Mexico

Node 2: Galveston, Texas

Node 3: Paraiso, Mexico

Node 4: Panama City, Florida

Node 5: Havana, Cuba

Node 6: Tampa, Florida

-Probability of detection on a given arc k:

1-2: 22%

1-3: 8%

2-3: 8%

2-4: 7%

3-4: 15%

3-5: 10%

4-5: 20%

4-6: 18%

5-6: 25%

-To solve this network interdiction problem, we will put it into matrix format with a probability matrix P and an incidence matrix B

-The resulting matrices would look like the following:

(Table 1)

Image:P_table.JPG‎

(Table 2)

Image:B-table.JPG‎

-Multiplying the two reselts in PB or:

(Table 3)

Image:PB2.JPG‎

  • The LP is written as:
    • Max min xPBy

subject to

x1 = 1

x ≥ 0

y1 = 1

y ≥ 0

  • If we take the dual with respect to x, we get:
    • υ* = min υ

subject to

PBy - 1υ ≤ 0

1y = 1

y ≥ 0

- 1υ is a column vector of 1s

-Summing the probabilities of detection on path (p) yields path F or 1-3-4-6 as the optimal path for the evador to choose to avoid detection; Shown by table 4

(Table 4)

Image:Prob_2.JPG‎

-Table 4 is the summation of probabilities over each path (p). The lowest value indicates the lowest probability of detection

Retrieved from "http://wiki.mcs.anl.gov/NEOS/index.php/Network_Interdiction"