Dynamic network interdiction games with imperfect information and deception

Network interdiction problems consist of zero-sum games between an attacker and an intelligent network defender, where the attacker seeks to degrade network operations while the defender adapts its operations to counteract the effects of the attacker. This problem has received significant attention in recent years due to its relevance to military problems and network security. In this paper, we study a class of dynamic network interdiction games where the attacker has imperfect knowledge of the network topology, and where the attacker can learn about the topology by monitoring network operations. The network observes the attacker´s actions, and can choose to avoid using the observed parts of the network in order to disguise information from the attacker. We pose this problem as a multistage game with nested imperfect information structure, and study the extensive form of this game. This form has special structure that we exploit to develop a novel decomposition algorithm for obtaining recursive solutions to this game. We characterize the payoff function of subgames starting at attacker´s information sets as piecewise linear concave functions of the attacker´s information state, the beliefs those information sets. We then develop a recursive algorithm based on extensions of partially observed Markov Decision Process algorithms to obtain complete solutions to these multistage games with nested information. The resulting recursive algorithm allows dynamic programming-like solution of dynamic games with partially nested information structure, where signaling between players is possible. We illustrate the algorithm with a simple example.