Two-Person Zero-Sum Games for Network Interdiction

doi:10.1287/opre.43.2.243

Two-Person Zero-Sum Games for Network Interdiction

1995-04-01

0

PRE

AI

DOI：10.1287/opre.43.2.243

原文链接

原文求助

摘要

En 中文

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, 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.

Two-Person Zero-Sum Games for Network Interdiction

摘要

期刊

机构

引用论文