Sequential Shortest Path Interdiction with Incomplete Information
Sequential Shortest Path Interdiction with Incomplete Information
复制标题
不完全信息的顺序最短路径拦截
DOI：
10.1287/deca.2015.0325
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Denis Sauré
中科院分区：
文献类型：
--
作者：
J. S. Borrero;O. Prokopyev;Denis Sauré
我们研究了序贯阻断时，阻断者有不完整的初始信息的网络和逃避者有完整的知识的网络，包括其结构和弧成本。在每个时间段内，拦截器从直到该时间段观察到的网络中阻挡最多k个弧，之后逃避者沿被拦截网络中的两个（固定）节点之间的最短路径沿着行进。通过观察逃避者的行为，拦截者了解网络结构和弧成本，并调整其行动，以最大限度地提高逃避者所招致的累积成本。我们的工作的一个显着特点是，在每个周期的反馈是确定性和对抗性的。除了研究遗憾最小化问题，我们还讨论了时间稳定性的政策，这是时间周期的数量，直到拦截器的行动匹配的预言拦截器与网络的先验知识。我们提出了一类简单的阻断政策，有一个有限的遗憾和检测时，瞬时遗憾达到零，在真实的时间。更重要的是，我们建立了这类政策属于有效的政策集。
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.