Data-driven interdiction with asymmetric cost uncertainty: A distributionally robust optimization approach
研究上下级决策者基于各自数据估计对手成本分布时的随机阻断博弈，提出分布鲁棒优化模型，证明渐近一致性并给出混合整数线性规划重构，针对信息不对称提出两种近似方法。
We consider a class of stochastic interdiction games between an upper-level decision-maker (the leader) and a lower-level decision-maker (the follower), where uncertainty lies in the follower's objective function coefficients. Specifically, the follower's profits (or costs) in our model comprise a random vector, whose probability distribution is estimated independently by the leader and the follower, based on their own data. To address the distributional uncertainty, we formulate a distributionally robust interdiction (DRI) model, where both decision-makers solve conventional distributionally robust optimization problems based on the Wasserstein metric. For this model, we prove asymptotic consistency and derive a polynomial-size mixed-integer linear programming (MILP) reformulation. Furthermore, in our bilevel optimization context, the leader may face uncertainty due to its incomplete knowledge of the follower's data. In this regard, we propose two distinct approximations of the true DRI model, where the leader has incomplete or no information about the follower's data. The first approach employs a pessimistic approximation, which turns out to be computationally challenging and requires a specialized reformulation amenable to a Benders-type decomposition algorithm. The second approach leverages a robust optimization approach from the leader's perspective. To address the resulting problem, we propose a scenario-based approximation that admits a potentially large single-level MILP reformulation and satisfies asymptotic robustness guarantees. Finally, for a class of randomly generated instances of the packing interdiction problem, we evaluate numerically how the information asymmetry and the decision-makers' risk preferences affect the models' out-of-sample performance.