# nonadditive_security_games__a6d0aa67.pdf

Non-Additive Security Games

Sinong Wang, Fang Liu Department of ECE, The Ohio State University Columbus, OH 43210, USA {wang.7691, liu.3977}@osu.edu

Ness Shroff Departments of ECE and CSE, The Ohio State University Columbus, OH 43210, USA shroff.11@osu.edu

Security agencies have found security games to be useful models to understand how to better protect their assets. The key practical elements in this work are: (i) the attacker can simultaneously attack multiple targets, and (ii) different targets exhibit different types of dependencies based on the assets being protected (e.g., protection of critical infrastructure, network security, etc.). However, little is known about the computational complexity of these problems, especially when there exist dependencies among the targets. Moreover, previous security game models do not in general scale well. In this paper, we investigate a general security game where the utility function is defined on a collection of subsets of all targets, and provide a novel theoretical framework to show how to compactly represent such a game, efficiently compute the optimal (minimax) strategies, and characterize the complexity of this problem. We apply our theoretical framework to the network security game. We characterize settings under which we find a polynomial time algorithm for computing optimal strategies. In other settings we prove the problem is NP-hard and provide an approximation algorithm.

Introduction The nature of resource allocation in practical security games often results in exponentially many pure strategies for the defender, such that the defender s optimal mixed strategy is hard to solve. In the past few years, several works have tried to resolve this issue from both theoretical and practical perspectives (Kiekintveld et al. 2009; Korzhyk, Conitzer, and Parr 2010; Jain et al. 2011; Letchford and Conitzer 2013; Xu et al. 2014; Xu 2016). A common restriction in these works is to either assume that the attacker only attacks one target, or that different targets are independent. The latter implies that the payoff of a group of targets is the sum of the payoffs of each one (Korzhyk, Conitzer, and Parr 2011). In practice, there exists various dependencies among the targets such that attacking one target will influence the others. Traditional models that ignore the inherent synergistic effects among the targets could lead to catastrophic consequences (Buldyrev et al. 2010). Motivated by this phenomenon, some recent works have investigated the security game with dependent targets (Shakarian, Lei, and Lindelauf 2014; Vorobeychik and Letchford 2015).

Copyright c 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

However, these works are limited to specific dependencies and provide neither a systematic understanding of complexity properties, nor an efficient algorithm. For example, Shakarian et al. (2014) assumes that the attacker and defender can choose a subset of nodes in a power grid and their utilities are dependent on the set of disconnected loads. They show that the defender best response problem (DBR) can be solved in polynomial time if the attacker attacks at most one target, while NP-hard in other cases. However, their complexity results cannot be easily reduced to the complexity of determining the defender s mixed strategies. In this paper, we introduce a new security game, which we call the Non-additivity Security Game (NASG). It is a nonzero-sum game including two players - the defender and attacker, and n targets, denoted by [n] = {1, 2, . . . , n}. We model various dependencies among the targets by defining the strategy of each player as a subset of [n] and adopt a general set function as the utilities. Specifically, the attacker obtains benefits for successfully attacked targets and pays a cost for its strategy. Also, the defender will lose benefits for those targets and also pays a cost. A critical feature of the NASG is that the benefit and cost for several targets is not the summation of each target s utility, instead, it is dependent on the specific combination of targets.. At a high level, the main challenge of NASG is that both the size of the strategy space and the number of utility functions are Θ(2n). We are interested whether the following well understood questions in the case of additive utility functions can be addressed under the non-additivity assumption.

How to compactly represent the NASG and how to efficiently compute the mixed strategies of NASG?

What is the complexity of computing the mixed strategies of NASG?

To answer these questions, we make the following contributions: (1) We provide the conditions for compactly representing the NASG and prove that there exists poly(n) number of variables in the compact model if the number of non-additive utility functions is poly(n). The main technique is isomorphism and projection of a polytope. (2) We design an algorithmic framework to efficiently compute the mixed strategies for NASGs by reducing the original problem to an oracle problem. The main technique is to design a polynomial-time vertex mapping algorithm from the low-

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

dimensional polytope to a simplex; (3) We prove that the above oracle problem and the computation of mixed strategies of NASG can be reduced to each other in polynomialtime under a reasonable restriction. Furthermore, we show that such an oracle problem is a problem of maximizing a pseudo-boolean function; (4) Finally, we apply our theoretical framework to the network security game. We provide polynomial-time algorithms for some kinds of networks and security measures, while for the general case, we show the NP-hardness and propose an approximation algorithm. All the proofs in this paper are left to the supplemental material due to space constraints.

Problem Description and Preliminary We begin by defining the NASG as a two-player normalform non-zero-sum game. Players and targets: The NASG contains two players (a defender and an attacker), and n targets, indexed by set [n] {1, 2, . . . , n}. Strategies and utility functions: A pure strategy for each player is a subset of [n]. In the general case, we consider the complete pure strategy space of attacker and defender, defined as the power set 2[n] {V |V [n]}, denoted by A and D, respectively. So there are N 2n pure strategies for both players. Let set function Ca( ) : A R and Cd( ) : D R be the attacker s and defender s cost function, respectively, and the set function B( ) : A R be the benefit function. Remark 1. Traditional models do not consider a cost function, instead, they assume that there exists a resource constraint such that certain strategies, i.e., subsets of [n], are restricted. In our paper, we explicitly consider the cost function but do not have such resource constraints1. In cybersecurity applications, security resources are available for a cost and can be used to replace resource constraints, as illustrated in (Vorobeychik and Letchford 2015). Tie-breaking Rule: When the attacker and defender choose strategy A A and D D, targets in the set A\D are successfully attacked by the attacker. Moreover, both players pay the cost for their strategy, and the attacker s and defender s payoff is given by [B(A\D) Ca(A)] and [ B(A\D) Cd(D)], respectively. Normal-form representation: Suppose that the order of the attacker s pure strategy is given by index function σ( ) : A {1, 2, , N}, then define the index function μ( ) for the defender s pure strategy: μ(U) = σ(U c) for any U D. This definition of the index function is to guarantee the symmetry of benefit matrix, which simplifies most theoretical results. Note that this assumption can be generalized, but makes the notation cumbersome. Then we can define the utility matrices including the cost matrices of attacker and defender: CA, CD RN N,

CA σ(A),μ(D) = Ca(A), CD σ(A),μ(D) = Cd(D), A, D 2[n],

and the benefit matrix M RN N, Mσ(A),μ(D) = B(A\D), A, D 2[n].

1Later, in this paper, we will consider the limited resource.

Let Ma and Md be the attacker s and defender s payoff matrices. It s clear that Ma = M CA and Md = M CD. The mixed strategy p, q ΔN is a distribution over the set of pure strategies A, D, where pσ(A), qμ(D) is the probability that the attacker chooses strategy A and the defender chooses strategy D. ΔN represents a N-dimensional simplex. Then the expected payoffs for the attacker and defender is given by following bilinear form, when they play the mixed strategy p ΔN and q ΔN, by

Ua(p, q) = p T Maq and Ud(p, q) = p T Mdq.

Solution Concepts: In this paper, we assume that both players move simultaneously and the standard solution concept is the Nash Equilibrium (NE). Our goal is to compute the defender s minimax mixed strategies and we call it the min max problem. The following three definitions are used heavily in our theoretical development. Definition 1. The common utility function is defined as the following transform of the benefit function B( ), cost function Ca( ) and Cd( ) for all U 2[n],

V U ( 1)|U\V |B(V ),

V U ( 1)|U\V |Ca(V ),

V :U V ( 1)|V \U|Cd(V ).

Intuitively, if we regard the benefit function as a measure defined on a given algebra of set [n], then using the inclusion-exclusion principle to expand each term in the summand, the common utility is equivalent to measuring the utility of the intersection of the targets, which seems like measuring the synergy effect of targets. Definition 2. The support set of NASG is

S = {U A|Bc(U) or Cc a(U) or Cc d(U c) = 0}, (1)

and support index set σ(S) = {σ(U)|U S}.

Definition 3. The projection operator πS : RN R|S| is

πS((x1, x2, . . . , x N)) = (. . . , xi, . . .)i σ(S), (2)

and projection of polytope: ΠS(ΔN) {πS(x)|x ΔN}.

Strategically Zero-sum Form Although the NASG contains non-zero-sum payoff, we prove the following proposition, which shows that it belongs to the strategically zero-sum game (Moulin and Vial 1978). Proposition 1. The set of Nash equilibriums of NASG is equivalent to the set of Nash equilibriums of zero-sum game with payoff matrix M CA + CD. Clearly, the Stackelberg equilibrium set is equivalent to the NE set of the NASG. This proposition allows us to solve the NASG via the equivalent zero-sum game, which can be tackled by a linear programming approach. In the sequel, we use M = M CA + CD to denote the payoff matrix.

Compact NASG

Defender Oracle Problem

Theorem 4 Algorithm 1

Compact D-NASG

Defender Oracle Problem

Maximizing a pseudo-boolean function Theorem 7

Restrict and A

Figure 1: The summary of the main results. The double arrow denotes the polynomial time reduction. The single arrow denotes the compact representation

Remark 2. The traditional zero-sum security game (Xu 2016) assumes that the defender gets a reward ri if target i is covered, or incurs a cost ci if uncovered. We can set specific values for our utility functions to recover their setting.

The main results of this paper are summarized in Fig. 1.

The Compact Representation of NASG

Based on the equivalent zero-sum game M and von Neumann s minimax theorem, computing the NE of NASG can be formulated as the following min max problem,

min q ΔN max p ΔN p T M q. (3)

This optimization model has 2n+1 variables, which implies that NASG is in general hard to solve. The goal of this section is to find a condition on the NASG that can be compactly represented with only poly(n) variables. To convey our idea more easily, we begin with following intuitive example.

Motivating Example

We first use gauss elimination of the matrix M to transform it into the row canonical form, which is to left and right multiply M by elementary matrices E and F,

min q ΔN max p ΔN p T M q = min q ΔN max p ΔN p T E 1EM FF 1q

= min q ΔN max p ΔN p T E 1 M r 0 0 0

where r is the rank of payoff matrix M , and M r is the non-zero block of its row canonical form. If we define the affine projection f(p) = p T E 1 T , g(q) = F 1q, and let Δa N = {f(p)|p ΔN}, Δd N = {g(q)|q ΔN}, we can obtain the following optimization problem,

min q Δd N max p Δa N p T M r 0 0 0

Since the polyhedra Δa N and ΔN are isomorphic, their vertices exhibit one-one correspondence. Similar argument for the polyhedra Δd N and ΔN. Thus the optimization problem (3) and (4) are equivalent. Further, considering the fact

that only the first r elements in vector p and q have the non-zero coefficients in (4), we can further simplify (4) as

min q Πr(Δd N) max p Πr(Δa N) p T M rq , (5)

where the operator Πr( ) is to project the N dimensional polytope into its first r coordinates.

Remark 3. The observation is that the number of variables in the model (5) depends on the rank of the payoff matrix. For example, if the rank of M is poly(n), we can compactly represent NASG with only poly(n) variables.

The Formal Description of Compact NASG Although the above conceptual derivation provides a possible path to compactly represent the NASG, there exists a significant technical challenge: the elementary matrices E, F and their inverse matrices have exponential size, hence, the key question is whether we can find both elementary matrices efficiently? To tackle this problem, we first show that the payoff matrix M can be decomposed as the product of three matrices. The following technical lemma is critical in our decomposition.

Lemma 1. For all U 2[n], the utility function satisfies

V U Bc(V ),

V U Cc a(V ),

V :U V Cc d(V ).

Note that similar results hold for the cost functions and their common utility. Then we can decompose the payoff matrix M in terms of common utilities. An illustrative example can be seen in the supplemental material.

Theorem 1. The payoff matrix M = M CA + CD can be decomposed as

M = Q(D L + V)QT , (6)

where D is the diagonal matrix with Dσ(A),σ(A) = Bc(A). V and L are two sparse matrices with non-zero elements: Vμ([n]),σ(A) = Cc d(A), Lμ(D),σ({ }) = Cc a(Dc). The Q is binary matrix with Qσ(A),μ(D) =

Based on this result, we can let elementary matrices E = Q 1, F = (QT ) 1, affine transformation f(p) = QT p and g(q) = QT q to yield two isomorphic polytopes: Δa N and Δd N with ΔN. The whole procedure is listed in Fig. 2, and the following theorem answers part of our first question.

Theorem 2. If |S| = poly(n), the rank of the payoff matrix M is poly(n), moreover, the NASG can be compactly represented by poly(n) number of variables and (p , q ) is a NE of NASG if and only if (πS(f(p )), πS(g(q ))) is the optimal solution of (8).

Since we do not utilize the row canonical form of M , instead, we extract the non-zero columns and rows of D

The Framework of Compact Representation Isomorphic polytope: solving the NASG is equivalent to solving the following optimization problem,

min q Δd N max p Δa N p T (D L + V)q (7)

Projection of polytope: projects the polytope Δa N and Δd N into coordinates with indices in σ(S), and further simplify (7) as the following compact represented model,

Compact NASG min q ΠS(Δd N) max p ΠS(Δa N) p T MSq (8)

where matrix MS is a sub-matrix of D L + V, which is obtained by extracting those rows and columns whose index belonging to σ(S).

Figure 2: The isomorphism and projection of a polytope

L + V to form the low-dimensional matrix MS, the Theorem 2 provides only a sufficient condition for our compact representation. Indeed, we can make it both sufficient and necessary by further conducting elementary elimination to transform the matrix D L + V into an approximate diagonal matrix D. However, this process will significantly complicate our affine transformation f and g, and make it impossible to map the optimal solution of compact model (8) to the original mixed strategy. Implication of compact NASG: From the perspective of attacker s utility function, our compact representation (8) simplifies Ua(p, q) as (similar result holds for Ud(p, q)),

U S p σ(U)[q σ(U)Bc(U) Cc a(U)]. (9)

Based on the definition of affine transformations f, g and matrix Q, each variable p σ(U) =

V :U V pσ(V ) is the marginal probability that the attacker attacks all the targets in set U, while q σ(U) =

V Uc qμ(V ) is the marginal probability that the defender does not defend any target in set U. Therefore, we can regard Bc(U), Cc a(U) (not B(U) and Ca(U)!) as the benefit and cost function for a virtual target U , and the formula (9) calculates the expected utility in such a new game. Theorem 8 provides a sufficient condition of which kind of non-additive security game can be compactly represented. We then discuss several important applications of this result. One application is based on the following corollary. Corollary 1. If all the utility functions are additive, i.e., B(U) =

i U B({i}) (similarly for cost function), the common utility satisifies Bc(U) = 0, |U| > 1. Further, the cardinality of support set |S| = n. Remark 4. The previous works (Kiekintveld et al. 2009; Korzhyk, Conitzer, and Parr 2011; Korzhyk et al. 2011) assuming that the utility functions are additive have provided a compact represented game, in which the defender s mixed strategy is represented by a n dimensional marginal probability vector. Corollary 1 recovers and justifies this result.

Another application is, in the network security domain, if we adopt some classic parameters as the security measure such as node s betweenness centrality (the number of shortest paths from all vertices to all others that pass through that node), the cardinality of support set |S| =poly(n). In the sequel, the terminology NASG refers to those NASGs that only have poly(n) variables in their compact model. Based on our compact representation, a natural question that arises is, can we efficiently solve such a compact model and implement the optimal solution by the defender s mixed strategy? We will answer this question in the next section.

Oracle-based Algorithmic Framework The main result of this section is given in the following theorem.

Theorem 3. There is a poly(n) time algorithm to solve the min max problem if there is a poly(n) time algorithm to compute the defender oracle problem, which is defined as, for any vector w R|S|, compute

x = arg max x ΠS(Δd N) w T x. (10)

It is not surprising that the compact NASG can be reduced to the defender oracle problem (DOP), and the reduction follows from an application of equivalence between separation and optimization (Gr otschel, Lov asz, and Schrijver 1981). What is interesting, however, is the reduction from the min max problem to the compact NASG. Namely, how to map the optimal solution of compact NASG to a defender s mixed strategy in poly(n) time. We show that this can be done by exploiting the geometric structure of polytope Δd N.

Reducing Compact NASG to Oracle Problem For simplicity, we use Ha and Hd to denote the polytope ΠS(Δa N) and ΠS(Δd N), and Ia and Id to denote their vertices, respectively. The compactly represented NASG (8) can be formulated as the linear programing (LP) problem.

Compact-LP min u (11)

s.t. v T MSq u v Ia, q Hd. (12)

The compact LP has poly(n) number of variables and possibly exponentially many constraints. One can therefore apply the ellipsoid method to solve such an LP, given a poly(n) time separation oracle. Further, the separation oracle can be reduced to the following two parts: given any (q , u), (1) membership problem: decide whether q Hd. If not, generate a hyperplane separating (q , u) and Hd; (2) inequality constraint problem: decide whether all the inequality constraints hold. If not, find one violated constraint. We have the following result for these problems.

Lemma 2. The membership problem and inequality constraint problem of compact LP (11) can be reduced to the defender oracle problem (10) in poly(n) time.

Algorithm 1 Vertex Mapping from Vertex to Pure Strategy

Input: Vertex v U Id Output: Defender s pure strategy U of original NASG T = ; for each i [n] do if v U σ({i}) = 0 then T = T {i}; end for U = T c;

Reducing NASG to Compact NASG

A classical result in combinatorial optimization is that if the separation problem of polytope P Rn can be solved in poly(n) time, we can decompose any point x P into the convex combination of at most (n + 1) vertices of P (Gr otschel, Lov asz, and Schrijver 1981). Note that this is precisely the DOP required for the above reduction. Applying this result to the optimal solution x of compact LP (11), we can get a convex decomposition x = |S|+1 i=1 λivi, where vi Id. If we can map the vertices vi back to the vertices (pure strategy) of original NASG, denoted by h(vi), the mixed strategies of the defender can be expressed as

i=1 λih(vi). (13)

Thus, the key lies in how to compute h(vi) in poly(n) time. To tackle this problem, first, considering an arbitrary pure strategy U 2[n], the corresponding vertex is a unit vector e U RN with only one non-zero element e U μ(U) = 1. Based on the affine transformation g(q) = QT q, the corresponding vertex of isomorphic polytope Δd N is

g(e U) = QT e U = QT μ(U), (14)

where Qμ(U) is the μ(U)th row of matrix Q. Then the corresponding point v U of the projected polytope Hd is

v U = πS(QT μ(U)), (15)

which is a sub-vector of QT μ(U). The problem is that the vertex in the high-dimensional polytope may not project to a vertex of its low-dimensional image. However, the following lemma will provide a positive result.

Lemma 3. S 2[n] s.t. [n] S, the vertices of the polytope Hd are the rows of a sub-matrix of Q, which is formed by extracting the column whose index belongs to σ(S).

No matter which coordinate we project the polytope Δd N into, the number of vertices is still N, and they form a submatrix of Q. Therefore, we can exploit the property of matrix Q to construct a vertex mapping algorithm and the correctness of Algorithm 1 is justified by following theorem.

Theorem 4. Vertex mapping algorithm runs in O(n) time and maps each vertex of Hd to a unique pure strategy.

Solving NASG is a Combinatorial Problem In this section, we will answer our second question, i.e., what is the complexity of the NASG, in a restrictive class: the attacker attacks at most c targets, the defender can protect at most k targets, where c is a constant and k is arbitrary; the defender s cost functions Cd( ) are additive. Then, the attacker s and defender s pure strategy spaces are given by A = {A 2[n]||A| c}, D = {D 2[n]||D| k}.

Definition 4. A D-NASG is given by the tuple (A, D, B, Ca, Cd), where the set of benefit function B = {B(A)|A A}, set of attacker s and defender s cost function Ca = {Ca(A)|A A}, Cd = {Cd(i)|i [n]}.

The first assumption is motivated by the fact that both players have limited resources (Kiekintveld et al. 2009) and they cannot cover any targets. In the realistic scenario, the attacker cannot simultaneously attack a large amount of targets such that c is a constant. The second assumption is reasonable because in the security game, the synergistic effect always occurs after the attack and defense, and will not influence the defense cost. For example, in the cybersecurity game, the defender is to deploy the anti-virus software in each communication node, in which case the cost (licensing cost) of deploying multiple nodes is equal to the summation of each one. Let Na = |A| and Nd = |D|, our main result is the following theorem.

Theorem 5. There is a poly(n) time algorithm to compute the defender s mixed strategy in D-NASG, if and only if there is a poly(n) time algorithm to compute the defender oracle problem: for any w RNa,

x = arg max x H d w T x, (16)

where the definition of H d is given in (18).

Reduction between D-NASG and Oracle Problem The reduction from D-NASG to DOP still follows our isomorphism and projection framework, and the main technical step is a partial decomposition of the payoff matrix. However, the reverse direction follows from a different path. First, let the payoff matrix of D-NASG be denoted by Mb R|A| |D|, which is a sub-matrix of M .

Theorem 6. The payoff matrix Mb RNa Nd can be decomposed as Mb = IMAJT , (17)

where the matrix I RNa Na and J RNd Na are binary matrices, and the matrix MA RNa Na contains one nonzero diagonal, non-zero row and non-zero column.

The detailed definition of each elements in matrix I, J and MA can be seen in the supplemental material. Similarly, we have the affine transformation: f (p) = IT p, g (q) = JT q; transformed polytope: Δa Na, Δd Nd; projected polytope:

H a = ΠS(Δa Na), H d = ΠS(Δd Nd). (18)

Note that in this case, the polytope Δd Nd is not isomorphic with ΔNd, but the correctness of our compact representation

follows a similar proof of Theorem 2. Further, the compactly represented linear programming is expressed as

Compact-D-LP min u (19)

s.t. v T MAq u v I a, q H d, (20)

where I a is the set of vertices of polytope H a.

Lemma 4. The separation problem for H d and the compact optimization problem (19) reduce to each other in poly(n) time.

Considering the equivalence between separation (H d) and optimization (DOP), we arrive at the reduction between the DOP (16) and the compact model (19). The main technique in the reduction between D-NASG and the compact optimization (19) is: (i) for any arbitrary instance MA of compact optimization problem, we can construct the set of utility functions: B, Ca in O(2cn) = O(n) time based on Lemma 1; (ii) vertex mapping algorithm from pure strategy to H d.

Lemma 5. The min max problem of D-NASG and compact optimization (19) reduces to each other in poly(n) time.

Lemma 4 and Lemma 5 together yield our desired result.

What is the Defender Oracle Problem

Through a series of reductions, we find that the NASG is essentially a defender oracle problem defined on a lowdimensional polytope H d, but the complicated form of polytope H d still prevents us from uncovering how the nonadditive utility function change the internal combinatorial structure of the security game. Fortunately, based on the investigation of the geometric structure of the H d, we will prove that the DOP is indeed a problem of maximizing a pseudo-boolean function.

Theorem 7. The defender oracle problem is equivalent to, for any vector w R|S|, maximize a pseudo-boolean function under a cardinality constraint,

i=1 xi n k,x {0,1}n

The complexity of (21) is dependent on the support set S. For example, in the simplest case, S = [n], we can efficiently solve such a problem by summing all the positive elements of vector w, which corresponds to the traditional additive security game. Instead, if S = {U 2[n]||U| 2}, then the oracle problem is a binary quadratic programming problem, which is known to be NP-hard. If k = n, the above problem will degenerate to an unconstrained optimization. This result builds a connection between the NASG and optimizating a pseudo-boolean function, which enables us to design an efficient DOP solver or understand the complexity of NASG via analyzing the structure of the support set S and using the results of combinatorial algorithm design.

Application to the Network Security Domain In this section, we will apply our theoretical framework to an important domain, in which the security game occurs in a network. The following definition is motivated by the works (Gueye, Marbukh, and Walrand 2012; Shakarian, Lei, and Lindelauf 2014). Definition 5. A network security game is given by the tuple (G, T, Fa, c), where G = (V, E) with node set V , edge set E, T is the network value function, Fa is the failure operator, c is the maximum number of nodes attacker can choose and defender can protect any targets (k = n). The network value function T : G R is a security measure assessing the utility of a network, and failure operator Fa : 2G 2G is to generate a new network via a specific failure mode after removing some nodes. For example, Shakarian et al. (2014) adopt the number of connected load nodes as T, and edge cascading failure model as Fa. The main result of our work is summarized as in TABLE 1.

Table 1: Solvability Status

CASES SOLVABILITY APPENDIX Additive benefit function poly(n) Trivial The separable support set S with poly(n) Theorem 6, maxi |Ui| = Θ(log(n)) Corollary 1 Constant c, negative common utilities poly(n) Theorem 7, except for singleton set Corollary 2 Constant c 2 NP-hard and efficient approximation Last Section

The first polynomial solvable class is trivial, because the size of support set is O(n) when all the utility functions are additive. Regarding the second polynomial solvable class, we have the following result Corollary 2. (Second solvable class) If the support set S satisfies separability such that

i=1 Si such that Ai Aj = , Ai Si, Aj Sj,

and set [n] is divided into m pairwise disjoint subsets by

U Si U, 1 i m,

and maxi |Ui| = Θ(log(n)), then we can solve the defender oracle problem in poly(n) time. The basic idea of the second solvable class is to show that when S is separable with size of largest component equal to Θ(log(n)), the DOP is separable and can be solved in poly(n) time via an enumerating algorithm. Corollary 3. (Third solvable class) If c is constant, all the common utilities Bc(U) are negative except the singleton set, for which Cc d(U) are negative, and we can solve the defender oracle problem in poly(n) time. In the third solvable class, we will show that DOP under such a condition is a submodular minimization problem, which can be solved in poly(n) time. These special cases are interesting because they correspond to the following applications.

Algorithm 2 Separable Approximation

Calculate benefit B(U) = T(G) T(Fa(G\U)), U A; for each U A do Calculate Bc(U) =

W U( 1)|U\W |B(W); if |Bc(U)| ϵc then Bc(U) = 0; end for Create support set S and let (S1, . . . , Sm) disjoint (S);

The second class can be applied in a sparse network. For example, if the size of largest connected component of G is Θ(log(n)), S will satisfy the condition of second solvable class (Corollary 1 in supplemental material).

The third class can be applied to a dense network where the most nodes are adjacent. For example, if c = 2, attacking any two nodes will lead to the superposition of the failure effect, resulting in negative common utilities.

Another application of the third class: in cybersecurity, the sensor network often exhibits a tree topology. The game is such that the attacker attempts to invade some nodes to destroy the connectedness of the network and the IT manager is required to deploy anti-virus software in some nodes. We show that this game satisfies the condition of the third class. (Corollary 4 in supplemental material)

For the general network (not sparse, not dense or not a tree), the problem is clearly NP-hard, but we still need to answer two questions: (1) can we still compactly represent the game if c is large, i.e., |S| = poly(n)? (2) can we efficiently solve such a game? To tackle these problems, we propose a novel separable approximation framework (Algorithm 2), which can guarantee the approximation error of the original problem, instead of the DOP. One crucial observation is that the common utility in the realistic network is well concentrated around zero. In Fig. 3, we examine the distributions of the benefit function and its common utility function in the following two kinds of network: Erd os-Renyi network G(n, p) and scalefree network G(n, α), where n is the number of nodes, p is the probability that any two nodes are connected, α is the parameter of degree distribution of the scale-free network. Suppose that the network G consists of m connected components: V1, V2, . . . , Vm and we adopt the following two kinds of network value functions,

T1(G) = max 1 i m |Vi|, T2(G) =

The different form of network value functions have different assessment of the network. The detailed comparison can be found in (Gueye, Marbukh, and Walrand 2012). As can be seen in Fig. 3, in both Erd os-Renyi and scale-free networks, although the distribution of the benefit function is random, the distribution of the common utility function is well concentrated around zero and 90% of them are less than 0.05. In particular, when the number of nodes increases, this phe-

nomenon is amplified such that almost 99% of the common utility functions are less than 0.05.

0.0 0.2 0.4 0.6 0.8 1.0 0.0

Normalized Value

Benefit, T2 Common utility, T2 Benefit, T1 Common utility, T1

Erdos Renyi (n=10,p=0.2)

0.0 0.2 0.4 0.6 0.8 1.0 0.0

Erdos Renyi (n=10,p=0.6)

Normalized Value

Benefit, T2 Common utility, T2 Benefit, T1 Common utility, T1

0.0 0.2 0.4 0.6 0.8 1.0 0.0

Erdos Renyi (n=30,p=0.2)

Normalized Value

Benefit, T2 Common utility, T2 Benefit, T1 Common utility, T1

0.0 0.2 0.4 0.6 0.8 1.0 0.0

Erdos Renyi (n=30,p=0.6)

Normalized Value

Benefit, T2 Common utility, T2 Benefit, T1 Common utility, T1

Figure 3: The distributions of common utility function and benefit function. All their value are absolute value and normalized in [0, 1].

Based on the above observation, we can let most of the common utility functions equal to 0 according to a given threshold ϵc. Formally, let Bc( ) denote the new common utility function generated by Algorithm 2, then the corresponding approximate benefit function satisfies

| B(U) B(U)| =

Bc(W) Bc(W) 2|U|ϵc.

Since |U| c, the maximum error between the original benefit functions and new generated benefit functions is less than 2cϵc. A classic result of game theory is that, if the maximum difference between the elements of two payoff matrices is bounded by ϵ, the difference of the optimal game values yielded by these two payoff matrices are bounded by 2ϵ (Lipton, Markakis, and Mehta 2003). Therefore, the approximation error of our game value is bounded by 2c+1ϵc. Remark that the disjoint operator in Algorithm 2 separates the support set S into m parts that satisfies the conditions of separability of support set S. As shown at the top of Fig. 4, for the Erd os Renyi, scalefree and Italian communication network, the size of support set will be reduced 90% by an extremely small approximation error 0.05. Moreover, this process also leads to a separable structure of S, and the resulting complexity of solving the NASG is poly(n)O(2maxi |Ui|). For example, in the bottom of Fig. 4, the complexity term maxi |Ui| can be greatly reduced to the order of Θ(log(n)) with an approximation error of 1%, regardless of the size and density of the network, and how many targets the attacker can choose. The more comprehensive numerical results can be found in

0.0 0.2 0.4 0.6 0.8 1.0

c=2, ER, p=0.2 c=2, ER, p=0.3 c=2, SF, α=2 c=2, SF, α=3 c=3, ER, p=0.2 c=3, ER, p=0.3 c=3, SF, α=2 c=3, SF, α=3

The complexity term

Approximation error ε n=40

0.0 0.2 0.4 0.6 0.8 1.0 1

39-nodes Italia Communication Network

The size of support set

Approximation error ε

c=2,T1 c=2,T2 c=4, T1 c=4, T2

0.0 0.2 0.4 0.6

39-nodes Italia Communication Network

The complexity term

Approximation error ε

c=2, T1 c=2, T2 c=4, T1 c=4, T2

0.0 0.2 0.4 0.6 0.8 1.0 1

The size of support set

Approximation error ε

ER,p=0.2 ER,p=0.3 Scale-free, α=2 Scale-free, α=3

Figure 4: Top: the size of support set |S| versus approximation error ϵ; Bottom: the complexity term maxi |Ui| versus approximation error ϵ. Remark that the ϵ represents the approximation error of the game value. Note that SF denotes the scale-free network.

the supplementary material. In summary, our approximation framework can reduce the complexity term maxi |Ui| to order Θ(log(n)) by only 10% approximation error in most networks including Erd os-Renyi, scale-free network and a 39 nodes Italian communication network. Therefore, using our theoretical framework, we can approximately and compactly represent a realistic network security game and solve it in poly(n) time with high accuracy.

Conclusion In this paper, we examined the security game under nonadditive utility functions and a structured strategy space, i.e., uniform matroid. We showed that the size of the compact representation is dependent on the number of non-additive strategies, and NASG is essentially the problem of maximizing a pseudo-boolean function. Compared with previous results, this work greatly extends the polynomial solvable class, provides an understanding of the complexity properties, and partly answers the question proposed by Xu (2016) in zero-sum, uniform matroid scenario. For future directions, we plan to investigate (i) the relationship between the Oracle problem and the NASG when the defender has a nonstructured strategy space; (ii) how to efficiently compute the defender s mixed strategy when attacker and defender have different benefit functions.

Acknowledgement This work was supported in part by a grant from the Army Research Office AROW911NF-15-1-0277, and an Army Research Office MURI W911NF-12-1-0385.

References Buldyrev, S. V.; Parshani, R.; Paul, G.; Stanley, H. E.; and Havlin, S. 2010. Catastrophic cascade of failures in interdependent networks. Nature 464(7291):1025 1028.

Gr otschel, M.; Lov asz, L.; and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169 197. Gueye, A.; Marbukh, V.; and Walrand, J. C. 2012. Towards a metric for communication network vulnerability to attacks: A game theoretic approach. In Game Theory for Networks. Springer. 259 274. Jain, M.; Korzhyk, D.; Vanˇek, O.; Conitzer, V.; Pˇechouˇcek, M.; and Tambe, M. 2011. A double oracle algorithm for zero-sum security games on graphs. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 1 (AAMAS), 327 334. International Foundation for Autonomous Agents and Multiagent Systems. Kiekintveld, C.; Jain, M.; Tsai, J.; Pita, J.; Ord o nez, F.; and Tambe, M. 2009. Computing optimal randomized resource allocations for massive security games. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 689 696. International Foundation for Autonomous Agents and Multiagent Systems. Korzhyk, D.; Yin, Z.; Kiekintveld, C.; Conitzer, V.; and Tambe, M. 2011. Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness. J. Artif. Intell. Res.(JAIR) 41:297 327. Korzhyk, D.; Conitzer, V.; and Parr, R. 2010. Complexity of computing optimal stackelberg strategies in security resource allocation games. In AAAI. Korzhyk, D.; Conitzer, V.; and Parr, R. 2011. Security games with multiple attacker resources. In IJCAI Proceedings International Joint Conference on Artificial Intelligence, volume 22, 273. Citeseer. Letchford, J., and Conitzer, V. 2013. Solving security games on graphs via marginal probabilities. In AAAI. Lipton, R. J.; Markakis, E.; and Mehta, A. 2003. Playing large games using simple strategies. In Proceedings of the 4th ACM conference on Electronic commerce (EC), 36 41. ACM. Moulin, H., and Vial, J.-P. 1978. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7(3-4):201 221. Shakarian, P.; Lei, H.; and Lindelauf, R. 2014. Power grid defense against malicious cascading failure. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, 813 820. International Foundation for Autonomous Agents and Multiagent Systems. Vorobeychik, Y., and Letchford, J. 2015. Securing interdependent assets. Autonomous Agents and Multi-Agent Systems 29(2):305 333. Xu, H.; Fang, F.; Jiang, A. X.; Conitzer, V.; Dughmi, S.; and Tambe, M. 2014. Solving zero-sum security games in discretized spatio-temporal domains. In AAAI, 1500 1506. Citeseer. Xu, H. 2016. The mysteries of security games: Equilibrium computation becomes combinatorial algorithm design. ar Xiv preprint ar Xiv:1603.02377.