Some Polynomial-time Algorithms for Solving Zero-Sum and Nonzero-Sum Security Game Problems

Given the importance of security, optimal force allocation is a topic of interest to researchers. Over the past two decades, a new branch of game theory called the security game, has been successfully used as a method to calculate the optimal defense policy for security issues. In these games, in addition to the limitations of security resources, the logical reaction of the attacker to any defender's strategy, is considered. Formerly, some optimization problems have been proposed to optimize the force allocation using the game theory, and some algorithms have been proposed that do not work for all types of security games and in all situations. In this paper, an algorithm with polynomial execution time is proposed to calculate the optimal coverage of the targets. The basis of this algorithm is expanding a set of targets called the attack set, which is included in the set of the attacker's best responses; and finally, limiting this set to a target with the maximum defender's payoff. Next, a zero-sum security game is introduced, in which by choosing any defender's strategy, the sum of defender's and attacker's payoffs are zero. It is proved that to calculate the optimal strategy in this game, it is enough to calculate the largest attack set. Accordingly, a polynomial-time algorithm is also proposed for this type of the game.