A Scalable Double-Oracle Algorithm for Multi-Domain Deception Game
Ahmed Bilal Asghar, Ahmed H. Anwar Hemida, Charles Kamhoua, Jon M. Kleinberg · 2024
This paper considers a multi-layer game representing a cyber-physical system where a defender must protect a set of resources from an adversary. The defender employs deceptive actions in both the cyber and physical domains. The two domains are interconnected, and the players’ payoffs depend on their actions across both domains. We investigate the complexity of this multi-domain game and use a double oracle approach to solve it, presenting integer linear programs for the player oracles. Due to the high dimensionality of the defender’s combined action space, the game becomes intractable even for medium-sized networks. Therefore, we propose a heuristic defender oracle to solve large-scale problems efficiently. Our simulations validate that the proposed method can efficiently solve large-scale problems. Numerical results demonstrate that by using the heuristic oracle, the defender’s payoff is, on average, within 16% of the optimal solution for random problem instances.