On solving large-scale low-rank zero-sum security games of incomplete information
Amnol Monga, Quanyan Zhu · 2016
Zero-sum games are useful to model the strategic interactions between an attacker and a defender over a network. The computation of the equilibrium solutions become challenging when entries of the payoff matrix are either partially or completely unknown. The uncertainties of the game often arise from the error in the observations and the incomplete information on the structure of the game. In this work, we leverage low-rank features of the security games to establish a robust computational framework that enables to solve games of incomplete information and compute their security strategies. We characterize the upper and the lower security values of the games using two robust and convex optimization problems in which the players compute the worst-case strategies subject to their unknown. The robust framework is compared with the benchmark matrix completion approach in which saddle-point equilibrium strategies are computed after the matrix is completed using rank optimization. Our numerical results have shown that the strategy found by using the holistic robust optimization method can outperform the matrix completion method in the prediction of the attacker and defender strategies.