摘要：In this work, we investigate a security game between an attacker and a defender. We formulate a zero-sum game in which the payoff matrix has a special structure which results from theadditive propertyof the utility function. The combinatorial nature of security games leads to a large cost matrix. We present structural properties of the optimal attacker strategy. Based on the structural properties, we propose a polynomial-time algorithm to compute the value of the large-scale zero-sum game.
