A Game Theoretic Model for the Optimal Location of Integrated Air Defense System Missile Batteries

作者：Han, Chan Y.^*; Lunday, Brian J.; Robbins, Matthew J.

来源：INFORMS Journal on Computing, 2016, 28(3): 405-416.

DOI：10.1287/ijoc.2016.0690

• sequential game
• trilevel programming
• combinatorial optimization
• game tree search
• heuristic

We examine the optimal location of Integrated Air Defense System (IADS) missile batteries to protect a country's assets, formulated as a Defender-Attacker-Defender three-stage sequential, perfect information, zero-sum game between two opponents. We formulate a trilevel nonlinear integer program for this Defender-Attacker-Defender model and seek a subgame perfect Nash equilibrium (i.e., a set of attacker and defender strategies from which neither player has an incentive to deviate). Such a trilevel formulation is not solvable via conventional optimization software, and an exhaustive enumeration of the game tree based on the discrete set of strategies is only tractable for small instances. We develop and test a customized heuristic over a set of small instances having deliberate parametric variations in a designed experiment, comparing its performance to an exhaustive enumeration algorithm. Testing results indicate the enumeration approach to be severely limited for realistically sized instances, so we demonstrate the heuristic on a larger instance from the literature for which it maintains computational efficiency.

• 出版日期2016
• 单位中国人民解放军空军电子技术研究所