Sequential Shortest Path Interdiction with Incomplete Information

Juan S. Borrero (), Oleg A. Prokopyev () and Denis Sauré ()
Additional contact information
Juan S. Borrero: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Oleg A. Prokopyev: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Denis Sauré: Department of Industrial Engineering, Universidad de Chile

Decision Analysis, 2016, vol. 13, issue 1, 68-98

Abstract: We study sequential interdiction when the interdictor has incomplete initial information about the network and the evader has complete knowledge of the network, including its structure and arc costs. In each time period, the interdictor blocks at most k arcs from the network observed up to that period, after which the evader travels along a shortest path between two (fixed) nodes in the interdicted network. By observing the evader’s actions, the interdictor learns about the network structure and arc costs and adjusts its actions to maximize the cumulative cost incurred by the evader. A salient feature of our work is that the feedback in each period is deterministic and adversarial. In addition to studying the regret minimization problem, we also discuss time stability of a policy, which is the number of time periods until the interdictor’s actions match those of an oracle interdictor with prior knowledge of the network. We propose a class of simple interdiction policies that have a finite regret and detect when the instantaneous regret reaches zero in real time. More importantly, we establish that this class of policies belongs to the set of efficient policies.

Keywords: network interdiction; shortest path; k-most vital arcs; learning; incomplete information (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/deca.2015.0325 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ordeca:v:13:y:2016:i:1:p:68-98

Access Statistics for this article

More articles in Decision Analysis from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().