2-PERSON ZERO-SUM GAMES FOR NETWORK INTERDICTION

A single evader attempts to traverse a path between two nodes in a net work while a single interdictor attempts to detect the evader by setti ng up an inspection point along one of the network arcs. For each are there is a known probability of detection if the evader traverses the are that the interdictor is inspecting. The evader must determine a pr obabilistic ''path-selection'' strategy which minimizes the probabilit y of detection while the interdictor must determine a probabilistic '' arc-inspection'' strategy which maximizes the probability of detection . The interdictor represents, in a simplified form, U.S. and allied fo rces attempting to interdict drugs and precursor chemicals as they are moved through river, road, and air routes in Latin America and the Ca ribbean. We show that the basic scenario is a two-person zero-sum game that might require the enumeration of an exponential number of paths, but then show that optimal strategies can be found using network how techniques of polynomial complexity. To enhance realism, we also solve problems with unknown origins and destinations, multiple interdictors or evaders, and other generalizations.