Two-person zero-sum network-interdiction game with multiple inspector types

Abstract

Wood (1995) to handle multiple types of interdiction assets (e.g., aircraft, ground-based inspection teams), referred to here as "inspectors." A single evader attempts to traverse a path between two vertices in a directed network while an interdictor, controlling inspectors of different types, attempts to detect the evader by assigning inspectors to edges in the network. Each edge has a known probability of detection if the evader traverses the edge when an inspector of a given type is present. The problem for the interdictor is to find a mixed inspector-to-edge assignment strategy that maximizes the average probability of detecting the evader, i.e., the "interdiction probability." The problem for the evader is to find a mixed "path-selection strategy" that minimizes the interdiction probability. The problem is formulated as a two-person zero-sum game with a surrogate objective that evaluates expected number of detections. That model is solved with a "direct solution procedure" and a "marginal-probability solution procedure." On numerous test problems, both procedures correctly compute expected number of detections, but the latter more often finds a solution that simultaneously optimizes interdiction probability. The latter procedure is also much faster and is therefore preferred.