Premium
Stochastic network interdiction with incomplete preference
Author(s) -
Pay Babak Saleck,
Merrick Jason R. W.,
Song Yongjia
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21831
Subject(s) - interdiction , pairwise comparison , stackelberg competition , mathematical optimization , computer science , ambiguity , path (computing) , shortest path problem , function (biology) , mathematics , artificial intelligence , mathematical economics , theoretical computer science , graph , evolutionary biology , engineering , biology , programming language , aerospace engineering
We study a class of stochastic network interdiction problems where the defender has incomplete (ambiguous) preferences. Specifically, we focus on the shortest path network interdiction modeled as a Stackelberg game, where the defender (leader) makes an interdiction decision first, and then the attacker (follower) selects a shortest path after the observation of random arc costs and interdiction effects in the network. We assume that the defender's risk preferences over exogenously given probabilities can be summarized by the expected utility theory. Although the exact form of the utility function is ambiguous to the defender, we assume that a set of pairwise gamble comparisons made by the defender is available, which can be used to restrict the shape of the utility function. We present two approaches to tackle this problem. The first approach conducts utility estimation and optimization separately, by first finding the best fit for a piecewise linear concave utility function according to the available data, and then optimizing the expected utility. The second approach integrates utility estimation and optimization, by modeling the utility ambiguity under a robust optimization framework following Armbruster and Delage [B. Armbruster and E. Delage, Manag. Sci., 61 (2015), 111‐128] and Hu and Mehrotra [J. Hu and S. Mehrotra, IIE Trans., 47 (2015), 358‐372]. We conduct extensive computational experiments to evaluate the performances of these approaches.