Network interdiction models are used to model a how a “defender” should best react to the presence of an “attacker” on a network. In contrast to other network interdiction models, shortest-path network interdiction considers an attacker who is attempting to maximize their probability of reaching a given sink node from a given source node. The attacker has a probability of traversing each arc safely. The defender is able to “interdict” a subset of these arcs (within the confines of a budget) by placing sensors on them, thereby reducing the attacker’s probability of safely traversing that arc.

This network interdiction model can be seen as a bilevel game. As the defender, we attempt to *minimize* the attacker’s *maximum*-reliability path through the network. Many of the models are obtained by beginning with this min-max formulation and consolidating it into something more workable.

Here’s a picture to visualize what is happening. As defenders, we choose first the arcs on which to place sensors. Afterwards, the attacker will note our decision and take the “best” (maximum-reliability) path through the network.

On the picture, the red dashes represent sensors. The blue path represents the attacker’s maximum-reliability path through the network.

Let’s build a model! We’ll need to define a few things first.

- : our directed network
- : arcs on which we can place sensor
- : interdiction budget
- : cost of placing a sensor on arc
- : probability of attacker traversing arc undetected
- : probability of attacker traversing arc undetected
*when a sensor is present* - : value of maximum-reliability path from to with no sensors installed
- : the attacker’s starting point
- : the attacker’s goal

For our data to make sense, we must have .

Great! We’ll now add a few variables.

- : probability of attacker making it from node to node undetected
- : whether or not we place a sensor on arc

If is defined as above, we surely want . It only makes sense that if the attacker is present at the ending goal, they will make it to their goal with probability .

Furthermore, we want $\pi_i$ to take on specific values based on our values of . Specifically, if we *do* interdict arc , we want to enforce . If we *do not* interdict arc , we want to enforce . Our objective will be to minimize . This will ensure that is calculated to the attacker’s best path from to .

Now let’s examine the model.

Remember when we wanted to enforce certain conditions on depending on our choices of for ? Let’s see if those hold!

Let . By the second constraint, we have , as desired. We also want to ensure the third constraint is *dominated* by this constraint; that is, it has no bearing on the model. Because we have . This proves the third constraint is dominated by the second.

Now, let . By the third constraint, we have , which is again what we want. We will also ensure the second constraint is dominated by this constraint. Because and , we have . Thus, the second constraint is indeed dominated by the third.

In a few weeks, we’ll be taking a closer look at the *stochastic* case of the maximum-reliability network problem, in which the attacker’s starting and ending points are unknown.

Anyways, back to watching The Bachelor finale. I’m totally only watching because my wife is. #TeamLauren

Cormican, Kelly J., David P. Morton, and R. Kevin Wood. “Stochastic network interdiction.” *Operations Research* 46.2 (1998): 184-197.

This is a nice introduction to interdiction. Can you say something about the players in the game and the underlying assumptions about how they operate?

LikeLike

We make a ton of assumptions about the knowledge of information. As defenders, we know with certainty the probabilities associated with each arc. We also assume that the attacker will know which arcs we interdict, and that the attacker will respond to our choices optimally. The former of these is plausible, though the latter is highly unlikely.

The beauty of the above formulation is that it considers the worst-case scenario. When we as defenders assume the interdictor knows our choices, we place a firm bound on the attacker’s maximum-reliability path. It’s more likely that the attacker will operate suboptimally and will be even less likely to traverse the network safely. We win either way!

LikeLiked by 1 person