Two-Person Zero-Sum Games for Network Interdiction
Loading...
Authors
Washburn, Alan
Wood, Kevin
Subjects
Advisors
Date of Issue
1995
Date
March - April 1995
Publisher
Language
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 that arc that the interdictor is inspecting. The evader must determine a probabilistic "path-selection" strategy which minimizes the probability of detection. The interdictor represents, in a simplified form, U.S. 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.
Type
Article
Description
Operations Research, Volume 43, Issue 2 (Mar. - Apr., 1995), 243-251. The article of record as published may be located at http://dx.doi.org/10.1287/opre.43.2.243.
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.