Two-Person Zero-Sum Network-Interdiction Game with Multiple Inspector Types

摘要

This thesis extends the game-theoretic network-interdiction model of Washburn & 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 zerosum 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.