Two-person zero-sum games for network interdiction

Two-person zero-sum games for network interdiction

0.00 Avg rating0 Votes
Article ID: iaor19982358
Country: United States
Volume: 43
Issue: 2
Start Page Number: 243
End Page Number: 251
Publication Date: Mar 1995
Journal: Operations Research
Authors: ,
Keywords: military & defence, networks, law & law enforcement
Abstract:

A single evader attempts to traverse a path between two nodes in a network while a single interdictor attempts to detect the evader by setting up an inspection point along one of the network arcs. For each arc there is a known probability of detection if the evader traverses the arc that the interdictor is inspecting. The evader must determine a probabilistic ‘path-selection’ strategy which minimizes the probability 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, US and allied forces attempting to interdict drugs and precursor chemicals as they are moved through river, road, and air routes in Latin America and the Caribbean. 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 flow techniques of polynomial complexity. To enhance realism, we also solve problems with unknown origins and destinations, multiple interdictors or evaders, and other generalizations.

Reviews

Required fields are marked *. Your email address will not be published.