Security Game with Non-additive Utilities and Multiple Attacker Resources
This work addresses the problem of modeling security interactions in complex systems like critical infrastructure for researchers and practitioners, though it is incremental as it builds on classical models.
The paper tackles the limitations of existing security game models by generalizing them to allow non-additive utility functions and multiple attacker targets, addressing inherent dependencies in complex networks. It shows that each security game is equivalent to a combinatorial optimization problem, settling open questions and extending the state-of-the-art in polynomial solvable and NP-hard classes.
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 $\varepsilon$, 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.