论文标题
在分布不确定性下的多阶段最短路径问题上
On the multi-stage shortest path problem under distributional uncertainty
论文作者
论文摘要
在本文中，我们考虑了用户和攻击者之间的歧义性多阶段网络游戏。假定ARC成本是随机变量，可以满足某些ARC的某些子集的规定的一阶时刻限制，并且对于某些特定的ARC而言。用户旨在通过在网络中的两个固定节点之间穿越累积的预期损失，而攻击者的目标是通过从可允许分布的家族中选择ARC成本的分布来最大化用户的预期损失。与大多数相关研究相反，用户和攻击者都可以在用户路径的特定节点上动态调整他们的决策。通过观察用户的决策，攻击者可能会揭示与当前用户位置发出的弧相关的一些其他分发信息。结果表明，由此产生的多阶段分布在鲁棒的最短路径问题（DRSPP）接受了线性混合组合编程重新印度（MIP）。特别是，我们通过引入不同形式的非预期性约束来区分无环和一般图。最后，我们进行了一项数值研究，在其中探索了几类合成网络实例的自适应决策质量和所提出的MIP重新印度的计算障碍。
In this paper we consider an ambiguity-averse multi-stage network game between a user and an attacker. The arc costs are assumed to be random variables that satisfy prescribed first-order moment constraints for some subsets of arcs and individual probability constraints for some particular arcs. The user aims at minimizing its cumulative expected loss by traversing between two fixed nodes in the network, while the attacker's objective is to maximize the user's expected loss by selecting a distribution of arc costs from the family of admissible distributions. In contrast to most of the related studies, both the user and the attacker can dynamically adjust their decisions at particular nodes of the user's path. By observing the user's decisions, the attacker may reveal some additional distributional information associated with the arcs emanated from the current user's position. It is shown that the resulting multi-stage distributionally robust shortest path problem (DRSPP) admits a linear mixed-integer programming reformulation (MIP). In particular, we distinguish between acyclic and general graphs by introducing different forms of non-anticipativity constraints. Finally, we perform a numerical study, where the quality of adaptive decisions and computational tractability of the proposed MIP reformulation are explored with respect to several classes of synthetic network~instances.
