Two-Person Games for Stochastic Network Interdiction

This paper presents a new formulation for stochastic network interdiction with endogenous uncertainty, in which optimization decisions can influence stochastic processes by altering the corresponding probability space. As an application, we can consider a planning problem in which a decision maker (interdictor), subject to limited resources, installs some detectors at border checkpoints in a transportation network in order to minimize the probability that a smuggler can traverse the residual network undetected or to maximize the smugglers traversing cost. The detecting probabilities are assumed to be known a priori, and installing detector decreases the likelihood of detection.The resulting problem is a two stage stochastic program, in that, at the first stage the interdictor decides which links to install detector for interdicting the smuggler’s moves by detecting him or decreasing his traversing cost. The interdictor’s decision can influence the probabilities of traversing links successfully. In the second stage the smuggler seeks to choose the shortest

Keywords:

interdiction problem , endogenous uncertainty , Stackelberg game , two-stage programming