2-PERSON ZERO-SUM GAMES FOR NETWORK INTERDICTION
成果类型：
Article
署名作者：
WASHBURN, A; WOOD, K
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.2.243
发表日期：
1995
页码：
243-251
关键词：
摘要：
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 are there is a known probability of detection if the evader traverses the are 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, 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 how techniques of polynomial complexity. To enhance realism, we also solve problems with unknown origins and destinations, multiple interdictors or evaders, and other generalizations.