Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Interdiction Games on Markovian PERT Networks
 
research article

Interdiction Games on Markovian PERT Networks

Gutin, Eli
•
Kuhn, Daniel  
•
Wiesemann, Wolfram
2015
Management Science

In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, and 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 precommitted or adapts to new information revealed over time, respectively. The static model gives rise to a stochastic program, whereas 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, whereas 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.

  • Details
  • Metrics
Type
research article
DOI
10.1287/mnsc.2014.1973
Web of Science ID

WOS:000354137200005

Author(s)
Gutin, Eli
Kuhn, Daniel  
Wiesemann, Wolfram
Date Issued

2015

Publisher

Informs

Published in
Management Science
Volume

61

Issue

5

Start page

999

End page

1017

Subjects

interdiction game

•

PERT network

•

Markov decision process

•

robust optimization

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
RAO  
Available on Infoscience
May 29, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/114186
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés