Two-person games for stochastic network interdiction : models, methods, and complexities
| dc.contributor.advisor | Morton, David P. | en |
| dc.creator | Nehme, Michael Victor | en |
| dc.date.accessioned | 2010-05-27T14:20:28Z | en |
| dc.date.available | 2010-05-27T14:20:28Z | en |
| dc.date.issued | 2009-12 | en |
| dc.description | text | en |
| dc.description.abstract | We describe a stochastic network interdiction problem in which an interdictor, subject to limited resources, installs radiation detectors at border checkpoints in a transportation network in order to minimize the probability that a smuggler of nuclear material can traverse the residual network undetected. The problems are stochastic because the smuggler's origin-destination pair, the mass and type of material being smuggled, and the level of shielding are known only through a probability distribution when the detectors are installed. We consider three variants of the problem. The first is a Stackelberg game which assumes that the smuggler chooses a maximum-reliability path through the network with full knowledge of detector locations. The second is a Cournot game in which the interdictor and the smuggler act simultaneously. The third is a "hybrid" game in which only a subset of detector locations is revealed to the smuggler. In the Stackelberg setting, the problem is NP-complete even if the interdictor can only install detectors at border checkpoints of a single country. However, we can compute wait-and-see bounds in polynomial time if the interdictor can only install detectors at border checkpoints of the origin and destination countries. We describe mixed-integer programming formulations and customized branch-and-bound algorithms which exploit this fact, and provide computational results which show that these specialized approaches are substantially faster than more straightforward integer-programming implementations. We also present some special properties of the single-country case and a complexity landscape for this family of problems. The Cournot variant of the problem is potentially challenging as the interdictor must place a probability distribution over an exponentially-sized set of feasible detector deployments. We use the equivalence of optimization and separation to show that the problem is polynomially solvable in the single-country case if the detectors have unit installation costs. We present a row-generation algorithm and a version of the weighted majority algorithm to solve such instances. We use an exact-penalty result to formulate a model in which some detectors are visible to the smuggler and others are not. This may be appropriate to model "decoy" detectors and detector upgrades. | en |
| dc.description.department | Mechanical Engineering | en |
| dc.format.medium | electronic | en |
| dc.identifier.uri | http://hdl.handle.net/2152/7512 | en |
| dc.language.iso | eng | en |
| dc.rights | Copyright is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works. | en |
| dc.subject | Stochastic network interdiction problem | en |
| dc.subject | Stackelberg game | en |
| dc.subject | Cournot game | en |
| dc.subject | Smugglers | en |
| dc.subject | Smuggling | en |
| dc.subject | Radiation detectors | en |
| dc.subject | Border checkpoints | en |
| dc.subject | Two-person games | en |
| dc.subject | Mathematical models | en |
| dc.title | Two-person games for stochastic network interdiction : models, methods, and complexities | en |
| thesis.degree.department | Mechanical Engineering | en |
| thesis.degree.discipline | Operations Research and Industrial Engineering | en |
| thesis.degree.grantor | The University of Texas at Austin | en |
| thesis.degree.level | Doctoral | en |
| thesis.degree.name | Doctor of Philosophy | en |