Journal
DECISION ANALYSIS
Volume 13, Issue 1, Pages 68-98Publisher
INFORMS
DOI: 10.1287/deca.2015.0325
Keywords
network interdiction; shortest path; k-most vital arcs; learning; incomplete information
Categories
Funding
- National Science Foundation [CMMI-1233441]
- Air Force Research Laboratory Mathematical Modeling and Optimization Institute
- Air Force Office of Scientific Research
- Air Force Summer Faculty Fellowship
- Chilean Millennium Institute of Complex Engineering Systems [ICM: P05-004-F FIN. ICM-FIC]
- Business Intelligence Research Center (CEINE) at the University of Chile
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1233441] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available