{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T06:00:39Z","timestamp":1673157639326},"reference-count":38,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Decision Analysis"],"abstract":"We study sequential shortest path interdiction, where in each period an interdictor with incomplete knowledge of the arc costs blocks at most [Formula: see text] 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\u2019s 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\u2019s 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.<\/jats:p>","DOI":"10.1287\/deca.2021.0426","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T13:24:25Z","timestamp":1629379465000},"source":"Crossref","is-referenced-by-count":0,"title":["Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback"],"prefix":"10.1287","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-4651-810X","authenticated-orcid":false,"given":"Jing","family":"Yang","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-8292-8838","authenticated-orcid":false,"given":"Juan S.","family":"Borrero","sequence":"additional","affiliation":[{"name":"School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-2888-8630","authenticated-orcid":false,"given":"Oleg A.","family":"Prokopyev","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-8123-5009","authenticated-orcid":false,"given":"Denis","family":"Saur\u00e9","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, Faculty of Physics and Mathematics, University of Chile, 8320000 Santiago, Chile"}]}],"member":"109","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"key":"B1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R","year":"1993"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022645805569"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90003-5"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44969-8_5"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1002\/net.20236"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0396-4"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2020.1041"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/deca.2015.0325"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2018.1773"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s13675-018-0103-0"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.4284\/sej.2009.76.2.328"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90020-7"},{"key":"B14","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"Erd\u0151s P","year":"1959","journal-title":"Publ. Math. Debrecen."},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584329"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpubeco.2008.04.006"},{"key":"B17","unstructured":"Gift PD (2010) Planning for an adaptive evader with application to drug interdiction operations. PhD thesis, Naval Postgraduate School, Monterey, CA."},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/deca.1100.0194"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1002\/net.10039"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-013-1372-x"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1812459116"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90065-5"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1080\/07408170500488956"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jspi.2006.02.015"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1002\/net.20458"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1002\/net.21712"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-34675-5"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2712906"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7997-1_61"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2016.0699"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.11.008"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-014-1722-3"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(97)00085-3"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1080\/00036840701720721"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-017-2694-x"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.05.003"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.07.028"}],"container-title":["Decision Analysis"],"original-title":[],"language":"en","deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T16:51:01Z","timestamp":1673110261000},"score":1,"resource":{"primary":{"URL":"http:\/\/pubsonline.informs.org\/doi\/10.1287\/deca.2021.0426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,19]]},"references-count":38,"alternative-id":["10.1287\/deca.2021.0426"],"URL":"https:\/\/doi.org\/10.1287\/deca.2021.0426","relation":{},"ISSN":["1545-8490","1545-8504"],"issn-type":[{"value":"1545-8490","type":"print"},{"value":"1545-8504","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,19]]}}}