Optimization Online


Interdiction Games on Markovian PERT Networks

Eli Gutin (eli.gutin08***at***imperial.ac.uk)
Daniel Kuhn (dkuhn***at***imperial.ac.uk)
Wolfram Wiesemann (ww***at***imperial.ac.uk)

Abstract: In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, while an interdictor endeavors to maximize the project duration by delaying some of the project tasks. We formulate static and dynamic versions of the interdictor's decision problem where the interdiction plan is either pre-committed or adapts to new information revealed over time, respectively. The static model gives rise to a stochastic program, while the dynamic model is formalized as a multiple optimal stopping problem in continuous time and with decision-dependent information. Under a memoryless probabilistic model for the task durations, we prove that the static model reduces to a mixed-integer linear program, while the dynamic model reduces to a finite Markov decision process in discrete time that can be solved via efficient value iteration. We then generalize the dynamic model to account for uncertainty in the outcomes of the interdiction actions. We also discuss a crashing game where the proliferator can use limited resources to expedite tasks so as to counterbalance the interdictor's efforts. The resulting problem can be formulated as a robust Markov decision process.

Keywords: Interdiction game, PERT network, Markov decision process, Robust optimization

Category 1: Stochastic Programming

Citation: Technical Report, Department of Computing, Imperial College London, April 2013

Download: [PDF]

Entry Submitted: 04/15/2013
Entry Accepted: 04/15/2013
Entry Last Modified: 03/31/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society