  We consider a class of sequential network interdiction problem 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 decision epoch, the interdictor can block (for the duration of
the epoch) at most $k$ arcs known to him/her. By observing the evader's
actions, the interdictor learns about the network structure and costs and thus,
can adjust his/her actions in subsequent decision epochs. It is known from the
literature that if the evader is greedy (i.e., the shortest available path is
used in each decision epoch), then under some assumptions the greedy
interdiction policies that block $k$-most vital arcs in each epoch are
efficient and have a finite regret. In this paper, we consider the evader's
perspective and explore deterministic "strategic" evasion policies under the
assumption that the interdictor is greedy. We first study the theoretical
computational complexity of the evader's problem. Then we derive basic
constructive properties of optimal evasion policies for two decision epochs
when the interdictor has no initial information about the network structure.
These properties are then exploited for the design of a heuristic algorithm for
a strategic evader in a general setting with an arbitrary time horizon and any
initial information available to the interdictor. Our computational experiments
demonstrate that the proposed heuristic outperforms the greedy evasion policy
on several classes of synthetic network instances under either perfect or noisy
information feedback. Finally, some interesting insights from our theoretical
and computational results conclude the paper.
