We study a security game over a network played between a @math and @math @math . Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of @math nodes to scan and clean.Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of "The price of defense" (MFCS'06). We are interested in Nash equilibria (NE) of this game, as well as in characterizing @math - @math networks which allow for the best @math @math @math , termed Price of Defense; this is the ratio of @math over the expected number of attackers that the defender catches in a NE. We provide characterizations of the NEs of this game and defense-optimal networks. This allows us to show that the NEs of the game coincide independently from the coordination or not of the attackers. In addition, we give an algorithm for computing NEs. Our algorithm requires exponential time in the worst case, but it is polynomial-time for @math constantly close to 1 or @math . For the special case of tree-networks, we refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal NE. On the other hand, we prove that it is NP-hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any @math .
We provide an overview of two recent applications of security games. We describe new features and challenges introduced in the new applications. Security games involving the allocation of multiple security resources to defend multiple targets generally have an exponential number of pure strategies for the defender. One method that has been successful in addressing this computational issue is to instead directly compute the marginal probabilities with which the individual resources are assigned (first pursued by (2009)). However, in sufficiently general settings, there exist games where these marginal solutions are not implementable, that is, they do not correspond to any mixed strategy of the defender. In this paper, we examine security games where the defender tries to monitor the vertices of a graph, and we show how the type of graph, the type of schedules, and the type of defender resources affect the applicability of this approach. In some settings, we show the approach is applicable and give a polynomial-time algorithm for computing an optimal defender strategy; in other settings, we give counterexample games that demonstrate that the approach does not work, and prove NP-hardness results for computing an optimal defender strategy. We study the problem of optimal resource allocation for packet selection and inspection to detect potential threats in large computer networks with multiple computers of differing importance. An attacker tries to harm these targets by sending malicious packets from multiple entry points of the network; the defender thus needs to optimally allocate her resources to maximize the probability of malicious packet detection under network latency constraints. We formulate the problem as a graph-based security game with multiple resources of heterogeneous capabilities and propose a mathematical program for finding optimal solutions. We also propose Grande, a novel polynomial time algorithm that uses an approximated utility function to circumvent the limited scalability caused by the attacker's large strategy space and the non-linearity of the aforementioned mathematical program. Grande computes solutions with bounded error and scales up to problems of realistic sizes. The security game is a basic model for resource allocation in adversarial environments. Here there are two players, a defender and an attacker. The defender wants to allocate her limited resources to defend critical targets and the attacker seeks his most favorable target to attack. In the past decade, there has been a surge of research interest in analyzing and solving security games that are motivated by applications from various domains. Remarkably, these models and their game-theoretic solutions have led to real-world deployments in use by major security agencies like the LAX airport, the US Coast Guard and Federal Air Marshal Service, as well as non-governmental organizations. Among all these research and applications, equilibrium computation serves as a foundation. This paper examines security games from a theoretical perspective and provides a unified view of various security game models. In particular, each security game can be characterized by a set system E which consists of the defender's pure strategies; The defender's best response problem can be viewed as a combinatorial optimization problem over E. Our framework captures most of the basic security game models in the literature, including all the deployed systems; The set system E arising from various domains encodes standard combinatorial problems like bipartite matching, maximum coverage, min-cost flow, packing problems, etc. Our main result shows that equilibrium computation in security games is essentially a combinatorial problem. In particular, we prove that, for any set system @math , the following problems can be reduced to each other in polynomial time: (0) combinatorial optimization over E; (1) computing the minimax equilibrium for zero-sum security games over E; (2) computing the strong Stackelberg equilibrium for security games over E; (3) computing the best or worst (for the defender) Nash equilibrium for security games over E. Therefore, the hardness [polynomial solvability] of any of these problems implies the hardness [polynomial solvability] of all the others. Here, by "games over E" we mean the class of security games with arbitrary payoff structures, but a fixed set E of defender pure strategies. This shows that the complexity of a security game is essentially determined by the set system E. We view drawing these connections as an important conceptual contribution of this paper. Network based security games, where a defender strategically places security measures on the edges of a graph to protect against an adversary, who chooses a path through a graph is an important research problem with potential for real-world impact. For example, police forces face the problem of placing checkpoints on roads to inspect vehicular traffic in their day-to-day operations, a security measure the Mumbai police have performed since the terrorist attacks in 2008. Algorithms for solving such network-based security problems have been proposed in the literature, but none of them scale up to solving problems of the size of real-world networks. In this paper, we present Snares, a novel algorithm that computes optimal solutions for both the defender and the attacker in such network security problems. Based on a double-oracle framework, Snares makes novel use of two approaches: warm starts and greedy responses. It makes the following contributions: (1) It defines and uses mincut-fanout, a novel method for efficient warm-starting of the computation; (2) It exploits the sub-modularity property of the defender optimization in a greedy heuristic, which is used to generate "better-responses"; Snares also uses a better-response computation for the attacker. Furthermore, we evaluate the performance of Snares in real-world networks illustrating a significant advance: whereas state-of-the-art algorithms could handle just the southern tip of Mumbai, Snares can compute optimal strategy for the entire urban road network of Mumbai.