Balance Between Scalability and Optimality in Network Security Games


Kai Wang. 2020. “Balance Between Scalability and Optimality in Network Security Games.” In Doctoral Consortium at International Conference on Autonomous Agents and Multi-agent Systems (AAMAS).


Network security games (NSGs) are widely used in security related domain to model the interaction between the attacker and the defender. However, due to the complex graph structure of the entire network, finding a Nash equilibrium even when the attacker is fully rational is not well-studied yet. There is no efficient algorithms known with valid guarantees. We identify two major issues of NSGs: i) non-linearity ii) correlation between edges. NSGs with non-linear objective function are usually hard to optimize, while correlated edges might create exponentially many strategies and impact the scalability. In this paper, we analyze the distortion of linear and non-linear formulations of NSGs with fully rational attacker. We provide theoretical bounds on these different formulations, which can quantify the approximation ratio between linear and non-linear assumption. This result can help us understand how much loss will the linearization incur in exchange for the scalability.
Last updated on 07/26/2021