On Greedy and Strategic Evaders in Sequential Interdiction Settings with Incomplete Information.

We consider a class of sequential interdiction settings where the interdictor has incomplete initial information about the network while the evader has complete knowledge of the network, including its structure and arc costs. In each time period, the interdictor can block at most k arcs known to him for the duration of the period. By observing the evader's actions, the interdictor learns about the network structure and costs and thus, can adjust his actions in subsequent time periods. It is known from the literature that if the evader is greedy (i.e., she uses the shortest available path in every time period), then under some assumptions on the the feedback generated from the evader's actions, the greedy interdiction policies that block k-most vital arcs in each time period are efficient and have a finite regret. In this paper, we consider the evader's perspective and explore strategic evasion policies under the assumption that the interdictor is greedy. In particular, we show that the evader's problem is NP-hard even for two time periods. Then we derive constructive properties of optimal evasion policies for two time periods when the interdictor has no initial information about the network structure. Based on these theoretical observations, we design a heuristic algorithm for a strategic evader in a general setting with an arbitrary time horizon and any initial information available to the interdictor initially. Finally, our computational experiments demonstrate that the proposed heuristic consistently outperforms the greedy evasion policy on several classes of synthetic network instances.