A defender-attacker model and algorithm for maximizing weighted expected hitting time with application to conservation planning

Abstract

This article studies an interdiction problem in which two agents with opposed interests, a defender and an attacker, interact in a system governed by an absorbing discrete-time Markov chain. The defender protects a subset of transient states, whereas the attacker targets a subset of the unprotected states. By changing some of the transition probabilities related to the attacked states, the attacker seeks to minimize the Weighted Expected Hitting Time (WEHT). The defender seeks to maximize the attacker’s minimum possible objective, mitigating the worst-case WEHT. Many applications can be represented by this problem; this article focuses on conservation planning. We present a defender–attacker model and algorithm for maximizing the minimum WEHT. As WEHT is not generally a convex function of the attacker’s decisions, we examine large-scale integer programming formulations and first-order approximation methods for its solution. We also develop an algorithm for solving the defender’s problem via mixed-integer programming methods augmented by supervalid inequalities. The efficacy of the proposed solution methods is then evaluated using data from a conservation case study, along with an array of randomly generated instances.