There has been significant interest in studying security games for modeling the interplay of attacks and defenses on various systems involving critical infrastructure, financial system security, political campaigns, and civil safeguarding. However, existing security game models typically either assume additive utility functions, or that the attacker can attack only one target. Such assumptions lead to tractable analysis, but miss key inherent dependencies that exist among different targets in current complex networks. In this paper, we generalize the classical security game models to allow for non-additive utility functions. We also allow attackers to be able to attack multiple targets. We examine such a general security game from a theoretical perspective and provide a unified view. In particular, we show that each security game is equivalent to a combinatorial optimization problem over a set system @math , which consists of defender's pure strategy space. The key technique we use is based on the transformation, projection of a polytope, and the elipsoid method. This work settles several open questions in security game domain and significantly extends the state of-the-art of both the polynomial solvable and NP-hard class of the security game.
The earlier mentioned works studying the complexity of the security game focus on the game with a single attacker resource. However, none of these works provide a systematic understanding of complexity properties or provide an efficient algorithm for the security game when attacker has multiple resources and utility functions are non-additive. @cite_9 , the authors extend the classic security game model to the scenario of multiple attacker resources. They design a @math states transition algorithm to exactly compute the Nash equilibrium in polynomial time. Such an algorithm is complicated and restricted to the case that the defender's resource is homogenous, i.e., the defender can protect any subset of targets with a cardinality constraint. In the practical scenario such as FAMS, the defender's resources may be heterogenous and solving such a scenario is still an open question in the security game domain.
@cite_9
186410217
Algorithms for finding game-theoretic solutions are now used in several real-world security applications. This work has generally assumed a Stackelberg model where the defender commits to a mixed strategy first. In general two-player normal-form games, Stackelberg strategies are easier to compute than Nash equilibria, though it has recently been shown that in many security games, Stackelberg strategies are also Nash strategies for the defender. However, the work on security games so far assumes that the attacker attacks only a single target. In this paper, we generalize to the case where the attacker attacks multiple targets simultaneously. Here, Stackelberg and Nash strategies for the defender can be truly different. We provide a polynomial-time algorithm for finding a Nash equilibrium. The algorithm gradually increases the number of defender resources and maintains an equilibrium throughout this process. Moreover, we prove that Nash equilibria in security games with multiple attackers satisfy the interchange property, which resolves the problem of equilibrium selection in such games. On the other hand, we show that Stackelberg strategies are actually NP-hard to compute in this context. Finally, we provide experimental results.