Stability of Interdiction Strategies in Quickest Flow Networks

ABSTRACT Many, if not all, societies have experienced natural disasters, public protests, traffic congestion, and the smuggling of dangerous goods, among other similar events. Such decision‐making and managerial problems can be studied using a game‐theoretic approach on specific networks. This paper studies a type of Stackelberg game known as the Quickest Flow Network Interdiction Problem (QFNIP). This problem considers a predefined volume of source flow, a limited interdiction budget, a network with two distinguished nodes (source and sink), two competing operators, the user, and the interdictor. The user aims to speed the flow from source tosink, while using the available interdiction budget, the interdictor tries to slow down the user's flow as much as possible by removing (interdicting) some network links. A set of removed links constitutes an interdiction strategy. This paper investigates the optimal interdiction strategies and their dependency on the source flow volume. It shows that optimal interdiction strategies depend on the volume of the source flow. This dependency holds up to a sufficiently large threshold of source flow volume, and the optimal strategies remain unchanged when the source flow exceeds that value. An interdiction strategy, independent of the source flow volume, is referred to as stable network interdiction. This paper proposes a practical method to find these stable interdiction strategies, applies it to the Canada Freedom Convoy, and examines the proposed method in both real‐world and randomly generated grid networks.