Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback

Jing Yang (), Juan S. Borrero (), Oleg A. Prokopyev () and Denis Sauré ()
Additional contact information
Jing Yang: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Juan S. Borrero: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078
Oleg A. Prokopyev: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Denis Sauré: Department of Industrial Engineering, Faculty of Physics and Mathematics, University of Chile, 8320000 Santiago, Chile

Decision Analysis, 2021, vol. 18, issue 3, 218-244

Abstract: We study sequential shortest path interdiction, where in each period an interdictor with incomplete knowledge of the arc costs blocks at most k arcs, and an evader with complete knowledge about the costs traverses a shortest path between two fixed nodes in the interdicted network. In each period, the interdictor, who aims at maximizing the evader’s cumulative cost over a finite time horizon, and whose initial knowledge is limited to valid lower and upper bounds on the costs, observes only the total cost of the path traversed by the evader, but not the path itself. This limited information feedback is then used by the interdictor to refine knowledge of the network’s costs, which should lead to better decisions. Different interdiction decisions lead to different responses by the evader and thus to different feedback. Focusing on minimizing the number of periods it takes a policy to recover a full information interdiction decision (that taken by an interdictor with complete knowledge about costs), we show that a class of greedy interdiction policies requires, in the worst case, an exponential number of periods to converge. Nonetheless, we show that under less stringent modes of feedback, convergence in polynomial time is possible. In particular, we consider different versions of imperfect randomized feedback that allow establishing polynomial expected convergence bounds. Finally, we also discuss a generalization of our approach for the case of a strategic evader, who does not necessarily follow a shortest path in each period.

Keywords: network interdiction; shortest path; learning; incomplete information; limited feedback (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/deca.2021.0426 (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:18:y:2021:i:3:p:218-244

Access Statistics for this article

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