Heterogeneous Air Defense Battery Location: A Game Theoretic Approach

In the air defense context of a missile-and-interceptor engagement, a challenge for the defender is that surface to air interceptor missile batteries often must be located to protect high-value targets dispersed over a vast area, subject to an attacker observing the disposition of batteries prior to developing and implementing an attack plan. To model this scenario, we formulate a two-player, three-stage, perfect information, sequential move, zero-sum game. The resulting trilevel math programming formulation cannot be solved via direct optimization and it is not suitable to solve via full enumeration for realistically-sized instances. We instead utilize the game tree search technique Double Oracle, within which we embed alternative heuristics to solve an important subproblem for the attacker. Whereas full enumeration required up to 8.6 hours to solve the largest instance considered, our superlative implementation of Double Oracle terminates in a maximum of 3.39 seconds over the set of instances and properly identifies the optimal SPNE strategies in 75% of our test instances. Regarding those instances for which Double Oracle failed, we note that the relative deviation is less than 2.5% from optimal, on average, yielding promise as a solution method to solve realistically-sized instances.