Scalable solutions of Markov games for smart-grid infrastructure protection

The anticipated proliferation of cyber components for collecting information and controlling operations of smart grids increases their vulnerability to a variety of cyber attacks. For instance, a large-scale simultaneous attack on smart meters to destabilize the grid could be feasible via cyber means, which is not viable via physical attacks alone. The interactions between the providers and attackers of the smart grid and their optimal strategies can be modeled as a Markov game. However, the computational complexity of such a game grows exponentially with the size of the infrastructure, making it impractical for smart grids of reasonable sizes. In this paper, we show that when the players' current interest is a subset of the states only and they are willing to accept small inaccuracies in the game solutions, many Markov game states can be pruned. We present a pruning algorithm in which a threshold parameter is used to control qualitatively the tradeoff between computation time and solution accuracy. The algorithm is iterative with decoupled state values in each iteration, and we parallelize the state estimations to reduce the overall computation time. We illustrate with examples that the pruning algorithm reduces the computation time greatly without losing much precision in the game solutions, and that parallelization further reduces the computation time.