Asymmetric Stochastic Shortest-Path Interdiction Favoring the Evader

We discuss a two-stage shortest-path interdiction problem between an interdictor and an evader, in which the cost for an evader to use each arc is given by the arc’s base cost plus an additional cost if the arc is attacked by the interdictor. The interdictor acts first to attack a subset of arcs, and then the evader traverses the network using a shortest path. In the problem we study, the interdictor does not know the exact value of each base cost, but instead only knows the (nonnegative uniform) distributions of each arc’s base cost. The evader observes both the subset of arcs attacked by the interdictor and the true base cost values before traversing the network, and is thus at an advantage. The interdictor seeks to maximize evader’s shortest-path costs, but the choice of objective is a key consideration. We examine ideas underscoring how the interdictor could maximize the expected objective that an evader will incur, and then more generally explore the maximization of the evader’s conditional value-at-risk, given some specified risk parameter