Stochastic network interdiction with incomplete preference. Issue 1 (3rd July 2018)

• Record Type: Journal Article
• Authors: Pay, Babak Saleck; Merrick, Jason R. W.; Song, Yongjia
• Is Part Of: Networks. Volume 73:Issue 1(2019)
• Page Start: 3
• Page End: 22
• Publication Date: 2018-07-03
• Subjects: expected utility -- incomplete preferences -- mixed integer programming -- network interdiction -- robust optimization -- stochastic programming; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21831
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: 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.