{'fraction_non_alphanumeric': 0.044527108299550054, 'fraction_numerical': 0.007217000044549383, 'mean_word_length': 4.0055747574980485, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Audit Games with Multiple Defender Resources

Modern organizations (e.g., hospitals, social networks, government agencies) rely heavily on audit to detect and punish insiders who inappropriately access and disclose confidential information. Recent work on audit games models the strategic interaction between an auditor with a single audit resource and auditees as a Stackelberg game, augmenting associated well-studied security games with a configurable punishment parameter. We significantly generalize this audit game model to account for multiple audit resources where each resource is restricted to audit a subset of all potential violations, thus enabling application to practical auditing scenarios. We provide an FPTAS that computes an approximately optimal solution to the resulting non-convex optimization problem. The main technical novelty is in the design and correctness proof of an optimization transformation that enables the construction of this FPTAS. In addition, we experimentally demonstrate that this transformation significantly speeds up computation of solutions for a class of audit games and security games.


Introduction
Modern organizations (e.g., hospitals, banks, social networks, search engines) that hold large volumes of personal information rely heavily on auditing for privacy protection. These audit mechanisms combine automated methods with human input to detect and punish violators. Since human audit resources are limited, and often not sufficient to investigate all potential violations, current state-of-the-art audit tools provide heuristics to guide human effort (Fairwarning 2011). However, numerous reports of privacy breaches caused by malicious insiders bring to question the effectiveness of these audit mechanisms (Ponemon Institute 2011;Ponemon Institute 2012).
Recent work on audit games by Blocki et al. (2013) approaches a piece of this problem using game-theoretic techniques. Their thesis is that effective human audit resource allocation and punishment levels can be efficiently computed by modeling the audit process as a game between an auditor and auditees. At a technical level, their audit game model augments a well-studied Stackelberg security games model (Tambe 2011) with a configurable punishment parameter. The auditor (henceforth called the defender) can audit one of n potential violations (referred to as targets). The defender's optimal strategy is a randomized auditing policy-a distribution over targets such that when the attacker best responds the defender's utility is maximized. The novel ingredient of the audit games model is a punishment level, chosen by the defender, which specifies how severely the adversary will be punished if he is caught. The defender may try to set a high punishment level in order to deter the adversary. However, punishment is not free. The defender incurs a cost for punishing, e.g. punishments such as suspension or firing of violators require maintaining resources for hiring and training of replacements. Blocki et al. (2013) provide an efficient algorithm for computing an optimal strategy for the defender to commit to.
While this work distills the essence of the defender's dilemma in auditing situations, it is too restricted to inform real-world audit strategies. In typical audit settings, the defender has multiple resources using which she can audit a subset of the targets (not just one target). Furthermore, each resource may be restricted in the targets that it can audit. For example, some organizations follow hierarchical audit strategies in which a manager is only required to audit potential violations committed by her direct reports. Similarly, specialized audits are common, for example, employing disjoint audit resources to detect finance-related and privacyrelated violations. Our Contributions. We present a generalized Stackelberg audit game model that accounts for multiple audit resources where each resource is restricted to audit a subset of all potential violations, thus enabling application to the practical auditing scenarios described above. Our main theoretical result is a fully polynomial time approximation scheme (FP-TAS) to compute an approximate solution to the resulting non-convex optimization problem.
To arrive at this FPTAS, we begin with a simple fixed parameter tractable (FPT) algorithm that reduces the nonconvex optimization problem to a linear programming problem by fixing the punishment parameter at a discrete value. Since we perform a linear search over all possible discrete values of the punishment parameter over a fixed range in increasing intervals of size , we get an FPT algorithm once the bit precision is fixed.
Next we present an optimization transformation that reduces the number of variables in the optimization problem at the cost of generating additional constraints. We also provide sufficient conditions that guarantee that the number of constraints is polynomial in size. Significantly, these conditions are satisfied in important practical auditing scenarios, including the hierarchical and specialized audit settings discussed earlier. The design and correctness proof of this optimization transformation constitutes the central novel technical contribution of this paper. Finally, we present an FPTAS to compute the defender's strategy leveraging the output of the optimization transformation when it generates a polynomial number of constraints.
In addition to its role in enabling the design of an FPTAS, a practical motivation for designing the optimization transformation is its promise of speeding up computing game solutions using the FPT algorithm. We experimentally demonstrate that the transformation produces speedups of up to 3× for audit game instances and over 100× for associated security game instances. In general, the speedups are higher as the problem size increases.
As an additional contribution, we consider audit scenarios where the defender can set a different punishment level for each target instead of setting a single, universal punishment level. We provide an FPT algorithm for this problem by designing a novel reduction of this setting to a second order cone program (SOCP).
Related Work. Our work is most closely related to the paper of Blocki et al (2013). We elaborate on the technical connections in the exposition and analysis of our results.
Our work is also closely related to work on security games (Tambe 2011). The basic approach to solving security games, and Stackelberg games more generally (where a leader chooses an optimal strategy, i.e., one that maximizes its utility assuming that the follower best responds) was introduced by Conitzer and Sandholm (2006); it does not scale well when the number of defender strategies is exponentially large, as is the case in most security games. Typical algorithms rely on formulating a mixed integer linear program, and employing heuristics; these algorithms do not provide provable running-time guarantees (see, e.g., Paruchuri et al. (2009);Kiekintveld et al. (2009)). Often the problem is solved just for the coverage probabilities or marginals (probability of defending a target) with the hope that it would be implementable (i.e., decomposable into a valid distribution over allocations). In contrast, Korzhyk et al. (2010) give a polynomial time algorithm for security games where the attacker has multiple resources, each of which can only protect one target at a time (this restriction is known as singleton schedules). Their main tool is the Birkhoff-Von Neumann Theorem, which we also apply.
All our algorithms have theoretical results about their efficiency. Our optimization transformation transforms the problem to one with only coverage probabilities as variables and adds additional constraints for the coverage probabilities that restricts feasible coverage probabilities to be implementable. Thus, in contrast with Korzhyk et al. (2010) our problem has much fewer variables at the cost of additional constraints. Also, the punishment parameter makes our problem non-convex, and so our algorithms must leverage a suite of additional techniques.

The Audit Games Model
An audit game features two players: the defender (D), and the adversary (A). The defender wants to audit n targets t 1 , . . . , t n , but has limited resources which allow for auditing only some of the n targets. Concretely, these resources could include time spent by human auditors, computational resources used for audit (e.g., automated log analysis), hardware (e.g., cameras) placed in strategic locations, among many other examples. The exact nature of these resources will depend on the specific audit problem considered. Rather than focusing on a specific type of audit, we denote resources available to the defender for audit as inspection resources. The defender has k inspection resources {s 1 , . . . , s k } at her disposal, with k < n. Each inspection resource can be used to audit at most one target. Inspection resources are further constrained by the set of targets that they can audit: for instance, a human auditor may not have the expertise or authority to audit certain targets. We define a set of tuples R such that a tuple (j, i) ∈ R indicates that inspection resource s j cannot be used to audit target t i .
A pure action of the defender chooses the allocation of inspection resources to targets. A randomized strategy is given by a probability distribution over pure actions. We use a compact form to represent a randomized strategy as a matrix of probabilities, with p j i the probability of inspection s j auditing target t i subject to the following constraints  Birkhoff-von Neumann (1946) result presented in Korzhyk et al. (2010), which enables the decomposition.) Furthermore, for every distribution over pure actions we can define an "equivalent" strategy using our compact representation: the distributions will be equivalent in the sense that for every target t i the probability p i that that target is inspected is the same.
Similarly to the basic audit games model of Blocki et al. (2013), the defender also chooses a punishment "rate" x ∈ [0, 1] such that if auditing detects an attack (i.e., violation), the attacker is fined an amount x. The adversary attacks one target such that given the defender's strategy the adversary's choice of attack is the best response.
We follow the notations of earlier papers on security games: let the utility of the defender be U a D (t i ) when audited target t i was found to be attacked, and U u D (t i ) when unaudited target t i was found to be attacked. We assume that the attacks on unaudited targets are discovered by an external source. Similarly, define the utility of the attacker as U a A (t i ) when the attacked target t i is audited, and U u A (t i ) when attacked target t i is not audited, excluding any punishment imposed by the defender. Attacks discovered externally are costly for the defender, thus, U a D (t i ) ≥ U u D (t i ). Similarly, attacks not discovered by internal audits are more beneficial to the attacker, thus, U u A (t i ) ≥ U a A (t i ). We can now define the full utility functions. The probabilities p 1 , . . . , p n of each target being audited are given by p i = k j=1 p j i . Then, the utility of the defender when tar- The defender pays a fixed cost ax regardless of the outcome. In the same scenario, the utility of the attacker when target t * is attacked is . The attacker suffers punishment x only when attacking an audited target.
Equilibrium. Under the Stackelberg equilibrium solution, the defender commits to a (randomized) strategy, followed by a best response by the adversary; the defender's strategy should maximize her utility. The mathematical problem involves solving multiple optimization problems, one each for the case when attacking t * is in fact the best response of the adversary. Thus, assuming t * is the best response of the adversary, the * th optimization problem P * in our audit games setting is The first constraint verifies that attacking t * is indeed a best response for the adversary.
The auditor solves the n problems P 1 , . . . , P n (which correspond to the cases where the best response is t 1 , . . . , t n , respectively), and chooses the best among all these solutions to obtain the final strategy to be used for auditing. This is a generalization of the multiple LPs approach of Conitzer and Sandholm (2006).
. Then, ∆ D,i ≥ 0, ∆ i ≥ 0, and the objective can be written as p n ∆ D, * − ax, subject to the quadratic constraint Without loss of generality we will focus on the n'th program P n , that is, we let * be n. Inputs. The inputs to the above problem are specified in K bit precision. Thus, the total length of all inputs is O(nK).

Fixed-Parameter Tractable Algorithms
In this section, we present our FPT algorithm for optimization problem P n , followed by the optimization transformation that improves the FPT algorithm and enables the FPTAS in the next section. Finally, we briefly describe an extension of our algorithmic results to target-specific punishments.
We start with the FPT for P n . Our algorithm is based on the following straightforward observation: if we fix the punishment level x then the P n becomes a linear program that can be solved in polynomial time. We therefore solve the optimization problem P n for discrete values of x (with interval size ) and take the solution that maximizes the defender's utility. This approach provides the following guarantee: Theorem 1. The above approach of solving for discrete values of x is a FPT Θ( )-additive approximation algorithm for the problem P n if either the optimal value of x is greater than a small constant or ∆ n = 0; the bit precision is the fixed parameter.
The proof of Theorem 1 is relegated to the appendix, submitted as supplementary material. We emphasize that fixing the bit precision is reasonable, because inputs to the game model are never known with certainty, and therefore highprecision inputs are not used in practice (see, e.g., Nguyen et al. (2014), Kiekintveld et al. (2013), Blum et al. (2014)).
A naïve approach to improving our FPT algorithm is to conduct a binary search on the punishment rate x. This approach may fail, though, as the solution quality is not singlepeaked in x. We demonstrate this in the appendix using an explicit example. Instead, we describe a transformation of the optimization problem, which will enable a FPTAS for our problem under certain restrictions.

Extracting constraints for p i 's
The transformation eliminates variables p j i 's and instead extracts inequalities (constraints) for the variables p i 's from the constraints below (referred to as grid constraints) Consider any subset of inspection resources L with the resources in L indexed by s 1 , . . . , s |L| (|L| ≤ k). We let M = OnlyAuditedBy(L) ⊂ {t 1 ,. . . , t n } denote the subset of targets that can only be audited by a resource in L (e.g., for every target t i ∈ M and every resource s j / ∈ L the resource s j cannot inspect the target t i ) . For notational convenience we assume that M is indexed by t 1 , . . . , t |M | . Then, in case |L| < |M |, we obtain a constraint p t1 +. . .+p t |M | ≤ |L| because there are only |L| resources that could be used to audit these |M | targets. We call such a constraint c M,L . Consider the set of all such constraints Lemma 1. The optimization problem P * is equivalent to the optimization problem obtained by replacing the grid con- Proof Sketch. We present a sketch of the proof with the details in the appendix. As the optimization objective depends on variables p i 's only, and the quadratic constraints are identical in both problems we just need to show that the regions spanned by the variables p i 's, as specified by the linear constraints, are the same in both problems. As one direction of the inclusion is easy, we show the harder case below.
Let the p i 's belong to the region given by C ∪ {0 ≤ p i ≤ 1}. We first show (in the appendix) that the extreme points of the convex polytope given by C ∪ {0 ≤ p i ≤ 1} sets the variables p 1 , . . . , p n to either 0 or 1.
Next, it is easy to see that for given p i 's and p * i 's, with corresponding feasible p j i 's and p * j i 's, any convex combination p @ i 's of p i 's and p * i 's has a feasible solution p @j i 's which is the convex combination of p j i 's and p * j i 's. Since any point in a convex set can be written as the convex combination of its extreme points (Gallier 2008), it is enough to show the existence of feasible p j i 's for the extreme points in order to prove existence of feasible p j i 's for any point in the convex polytope under consideration.
The extreme points of the given convex polytope has ones in k ≤ k positions and all other zeros (k ≤ k since p 1 + . . . + p n ≤ k). Consider the undirected bipartite graph linking the inspection nodes to the target nodes, with a link indicating that the inspection can audit the linked target. This graph is known from our knowledge of R, and each link in the graph can be labeled by one of the p j i variables. Let S be the set of targets picked by the ones in any extreme points. We claim that there is a perfect matching from S to the the set of inspection resources (which we prove in next paragraph). Given such a perfect matching, assigning p j i = 1 for every edge in the matching yields a feasible solution, which completes the proof.
We prove the claim about perfect matching by contradiction. Assume there is no perfect matching, then there must be a set S ⊆ S , such that |N (S )| < |S | (N is the neighbors function -this result follows from Hall's theorem). As S ⊆ S it must hold that p i = 1 for all i ∈ index(S ) (function index gives the indices of the set of targets). Also, the set of targets S is audited only by inspection resources in N (S ) and, by definition of C, we must have a constraint i∈index(S ) p i ≤ |N (S )| . Using |N (S )| < |S |, we get i∈index(S ) p i < |S | . But, since |index(S )| = |S |, we conclude that all p i for targets in S cannot be one, which is a contradiction.
Observe that obtaining p j i 's from the p i 's involves solving a linear feasibility problem, which can be done efficiently.
Importantly, the definition of C is constructive and provides an algorithm to compute it. However, the algorithm has a worst-case running time exponential in k. Indeed, consider k resources s 1 , . . . , s k and 2k targets t 1 , . . . , t 2k .
. . , s k } we get a new constraint c M,L . Thus, we get k−1 k/2 constraints.

Conditions for Poly. Number of Constraints
Motivated by the above observation, we wish to explore an alternative method for computing C. We will also provide sufficient conditions under which |C| is polynomial.
The intuition behind our alternative algorithm is that instead of iterating over sets of inspection resources, we could iterate over sets of targets. As a first step, we identify equivalent targets and merge them. Intuitively, targets that can be audited by the exact same set of inspections are equivalent.
The algorithm is formally given as Algorithm 1. It builds an intersection graph from the merged targets: every merged set of targets is a node, and two nodes are linked if the two sets of inspection resources corresponding to the nodes intersect. The algorithm iterates through every connected induced sub-graph and builds constraints from the targets associated with the nodes in the sub-graphs and the set of inspection resources associated with them. The next lemma proves the correctness of the Algorithm 1.

Algorithm 1: CONSTRAINT FIND(T, R)
Compute F , the map from T to 2 {s1,...,s k } using R. Merge targets with same F (t) to get set T and a map W , where W (t ) = #merged targets that yielded t Let P V (t ) be the set of prob. variables associated with t , one each from the merged targets that yielded t Form an intersection graph G with nodes t ∈ T and edge set Lemma 2. CONSTRAINT FIND outputs constraints that define the same convex polytope in p 1 , . . . , p n as the constraints output by the naïve algorithm (iterating over all subsets of resources).
The proof appears in the appendix. The algorithm is clearly not polynomial time in general, because it iterates over all connected subgraphs. The next lemma provides sufficient conditions for polynomial running time.
Lemma 3. CONSTRAINT FIND runs in polynomial time if at least one of the following conditions holds: • The intersection graph has O(log n) nodes.
• The intersection graph has constant maximum degree and a constant number of nodes with degree at least 3.
The proof is in the appendix.
Why Are These Conditions Realistic? The conditions specified in Lemma 3 capture a wide range of practical audit scenarios.
First, many similar targets can often be grouped together by type. In a hospital case, for instance, rather than considering each individual health record as a unique target worthy of specific audit strategies, it might make more sense to have identical audit policies for a small set of patient types (e.g., celebrities, regular folks...). Likewise, in the context of tax audits, one could envisage that individuals are pooled according to their types (e.g., high income earners, expatriates, ...). In practice, we expect to see only a few different types. Each type corresponds to a single node in the intersection graph, so that a constant number of types corresponds to a constant number of nodes. That is, both of the lemma conditions are satisfied, even though only one is required.
Second, auditing is often localized. For instance, when considering audits performed by corporate managers, one would expect these managers to primarily inspect the activities of their direct subordinates. This means that the inspection resources (inspection actions of a manager) auditing a node (activities of its subordinates) are disjoint from the inspection resources auditing any other node. Thus, our intersection graph has no edges, and the second lemma condition is satisfied. Slightly more complex situations, where, for instance, employees' activities are audited by two different managers, still satisfy the second condition.

Target-Specific Punishments
We present a brief overview of target-specific punishments with the details in the appendix. We extend our model to target-specific punishments by augmenting the program P n : we use individual punishment levels x 1 , . . . , x n , instead of using the same punishment x for each target. The new optimization problem P X n differs from P n only in (1) objective: max pi,x p n ∆ D,n − j∈{1,...,n} a j x j and (2) quadratic constraints: The naïve way of discretizing each of the variables x 1 , . . . , x n and solving the resulting sub-problems is not polynomial time. Nevertheless, we show that it is possible to design an FPT approximation algorithm by discretizing only p n , and casting the resulting sub-problems as second-order cone problems (SOCP), which can be solved in polynomial time (Boyd and Vandenberghe 2004). We first present the following intuitive result: Lemma 4. At the optimal point for P X n , x n is always 0. Further, discretizing values of p n with interval size and solving resulting sub-problems yields a Θ( ) approximation.
The proof is in the appendix. Next, we show that for fixed values of x n and p n , P X n reduces to an SOCP. We first describe a general SOCP problem (with variable y ∈ R n ) that maximizes a linear objective f T y subject to linear constraints F y = g and m quadratic constraints of the form ∀i ∈ {1, . . . , m}. ||A i y + b i || 2 ≤ c T i y + d i In particular, the constraint k 2 /4 ≤ y i (y j + k ) is the same as ||[k (y i −y j −k )] T || 2 ≤ y i +y j +k, which is an instance of the quadratic constraint above for appropriate A, b, c, d.
Our problem can be cast as an SOCP by rewriting the quadratic constraints as p n (x n + ∆ n ) + δ i,n ≤ p i (x i + ∆ i ) Using our approach (discretizing p n , x n = 0) the LHS of the above inequality is a constant. If the constant is negative we can simply throw out the constraint -it is a tautology since the RHS is always positive. If the constant is positive, we rewrite the constraint as a second-order constraint as described above (e.g., set k = 2 p n (x n + ∆ n ) + δ i,n and set k = ∆ i ). The rest of the constraints are linear. Thus, the problem for each fixed value of p n , x n is an SOCP. Putting everything together, we get the following result. Theorem 2. The method described above is an FPT additive Θ( )-approximate algorithm for solving P X n .

Fully Polynomial Time Approximation
Our goal in this section is to develop an FPTAS for problem P n , under the condition that the set C returned by CONSTRAINT FIND has polynomially many constraints. Our algorithm builds on an earlier algorithm (Blocki et al. 2013) for the restricted auditing scenario with just one defender resource. Since we solve the defender's problem after extracting the constraints C, the variables in our problem are just the p i 's and x. max pi,x p n ∆ D,n − ax , Property of an optimal point. We state the following property of any optimal point p * i 's and x * of the optimization: Lemma 5. If p * n (x * + ∆ n ) + δ j,n ≥ 0 then p * n (x * + ∆ n ) + δ j,n = p * j (x * + ∆ j ) (i.e., quadratic constraint is tight) else when p * n (x * + ∆ n ) + δ j,n < 0 then p j = 0. The proof is in the appendix.
Next, we sort δ i,n 's to get a sorted array δ (i),n in ascending order. Then, we split the optimization problem P n into sub-problems EQ (j) , where in each problem EQ (j) it is assumed that p n , x lies between the hyperbolas p n (x + ∆ n ) + δ (j),n (open boundary) and p n (x + ∆ n ) + δ (j+1),n (closed boundary) in the plane spanned by p n , x. Thus, in EQ (j) , p n (x + ∆ n ) + δ (j),n is non-negative for all (k) > (j) and negative otherwise. Using the property of the optimal point above, for the non-negative case we obtain equalities for the quadratic constraints and for the negative case we claim that for all (k) ≤ (j) we can set p (k) = 0. The optimal value for P n can be found by solving each EQ (j) and taking the best solution from these sub-problems.
The optimization problem for EQ (j) is as follows: As no p i (except p n ) appears in the objective, and due to the equality constraints on particular p i 's, we can replace those p i 's by a function of p n , x. Other p i 's are zero. Next, by a series of simple algebraic manipulations we obtain a twovariable optimization problem: where B is the total number of constraints, which is of the same order as |C|. The details of the algebraic steps are in the appendix.
Solving the sub-problem. Our two final lemmas are not hard to prove. Their proofs appear in the appendix.
Lemma 6. Problem EQ (j) can be solved efficiently for a fixed value x or fixed value of p n .
Lemma 7. The optimal point for EQ j cannot be an interior point of the region defined by the constraints, i.e., at least one of the inequalities is tight for the optimal point.
Algorithm 2: APX SOLVE(l, EQ (j) ) Solve the problem for p n = 0, 1 and x = 0, 1 Collect solutions (p n , x) from the above in M We are now ready to present the FPTAS, given as Algorithm 2. The algorithm first searches potential optimal points on the boundaries (in the first loop) and then searches potential optimal points at the intersection of two boundaries (second loop). The roots are found to an additive approximation factor of 2 −l in time polynomial in the size of the problem representation and l (Schönhage 1982). As shown in Blocki et al. (2013), the case of roots lying outside the feasible region (due to approximation) is taken care of by the function MAKEFEASIBLE. The first loop iterates a maximum of n times, and the second loop iterates a maximum of n 2 times. Thus, we have the following result.
Theorem 3. The optimization problem P n can be solved with an additive approximation factor of Θ(2 −l ) in time polynomial in the input size and l, i.e., our algorithm to solve P n is an FPTAS.

Experimental Results
In this section, we empirically demonstrate the speedup gains from our optimization transformation for both audit games and security games. We obtained speedups of up to 3× for audit game instances and over 100× for associated security game instances. Our experiments were run on a desktop with quad core 3.2 GHz processor and 6GB RAM. Code was written in Matlab using the built-in large scale interior point method implementation of linear programming. We implemented two FPT algorithms-with and without the optimization transformation. For both the algorithms, we used the same problem inputs in which utilities were generated randomly from the range [0, 1], a was fixed to 0.01, x was discretized with interval size of 0.005.
We ran experiments for audit games and security games with varying number of targets and resources. The resources were divided into equal sized groups such that the targets any group of resources could inspect was disjoint from the target set for any other group. Table 1 shows our results with the varying number of targets, resources and size of the group of targets. The results are an average over 5 runs of the optimization with random utilities in each run. Audit games take more time to solve than corresponding security games with a similar number of targets as we run the corresponding LP optimization 200 times (the discrete interval for x is 0.005). Hence we solve for larger security game instances.
Our implementations did not optimize for speed using heuristics because our goal was to only test the speedup gain from our optimization transformation. Thus, we do not scale up to the number of targets that heuristic approaches such as ORIGAMI (Kiekintveld et al. 2009) achieve (1,000,000 targets). ORIGAMI works by iteratively building the optimal attack set, i.e., the set of targets that the adversary finds most attractive at the optimal solution point. However, ORIGAMI considers only coverage probabilities (marginals). Thus, its output may not be implementable with scheduling constraints on resources. In contrast, our approach guarantees that the coverage probabilities output are implementable. Wedding the two approaches to obtain scalable and provably implementable audit and security game solutions remains an interesting direction for future work.
Observe that we removed the 0 ≤ condition in the first set of constraints because that is implied by the next two constraints. Next, note that any constraint (indexed by b) with two variables p n , x can be expressed as p n ≤ f b (x) (closed boundary) for constraint-specific ratio of polynomials f b (x) or by p n < −δ (j),n x+∆n (open boundary). However, we close the open boundary, i.e., p n ≤ −δ (j),n x+∆n , and solve the problem, returning an infeasible solution in case the solution is on the boundary p n = −δ (j),n x+∆n . This is justified by the fact that the curve p n = −δ (j),n x+∆n is included in the other optimization problem EQ (j−1) , and would be output by that sub-problem if it indeed is the global maximizer. Thus, we represent the optimization problem as where B is the total number of constraints described as above.

C Target-Specific Punishments
In this section we extend our FPT result to target-specific punishments. While the formulation of the extended problem is not that different, solving it becomes significantly more challenging.
In more detail, we augment the program P n by using individual punishment levels x 1 , . . . , x n , instead of using the same punishment x for each target. The new optimization problem P X n is max pi,x p n ∆ D,n − j∈{1,...,n} a j x j , Note that the defender's penalty term is now a linear combination of the target-specific punishment level.
The naïve way to approach the above problem is to discretize each of the variables x 1 , . . . , x n and solve the resulting sub-problems, which are linear programs. However, such a discretization of size , even if yielding a Θ( ) additive approximation, will run in time O((1/ ) n ), which is not polynomial for constant .
Nevertheless, we show that it is possible to design an algorithm that runs in time polynomial in and yields a Θ( ) additive approximation, by discretizing only p n , and casting the resulting sub-problems as second-order cone programs (SOCP), which can be solved in polynomial time (Boyd and Vandenberghe 2004). Letting S(n) denote the (polynomial) running time of the SOCP, we obtain a running time of O(S(n)/ ), given fixed bit precision.
We first present the following intuitive result: Restatement of Lemma 4. At the optimal point for P X n , x n is always 0. Further, considering discrete values of p n with interval size and solving the resulting sub-problems exactly yields a Θ( ) approximation.
The proof is in the Missing Proofs section of the appendix. Next, we show that for fixed values of x n and p n the optimization problem P X n reduces to a second-order cone program. We first describe a general SOCP problem: where the optimization variable is y ∈ R n , and all constants are of appropriate dimensions. In particular, we observe that the constraint k 2 /4 ≤ y i (y j + k ) can always be written as a second order inequality ||Ay + b|| 2 ≤ c T y + d by selecting A and b such that Our problem can be cast as a SOCP by rewriting the quadratic constraints as Using our approach (discretizing p n , x n = 0) the LHS of the above inequality is a constant. If the constant is negative we can simply throw out the constraint -it is a tautology since the RHS is always positive. If the constant is positive, we rewrite the constraint as a second-order constraint as described above (e.g., set k = 2 p n (x n + ∆ n ) + δ i,n and set k = ∆ i ). The rest of the constraints are linear, and can be rewritten in equality form by introducing slack variables. Thus, the problem for each fixed value of p n , x n is an SOCP, and can be solved efficiently. Putting everything together, we get the main Theorem 2 of the target-specific punishment section in the paper.

D Missing Proofs
Proof of Theorem 1. The quadratic constraint can be rewritten as Suppose we have an optimal point x o , p o i 's. First, we note that if x o = 1 (resp. x o = 0) then our algorithm will find the optimal solution exactly because x = 1 (resp. x = 0) is one of the discrete values of x considered by our algorithm. In the rest of the proof we assume that 0 < x o < 1. Let > 0 denote the smallest value s.t.
x o + is one of the discrete values of x considered by our algorithm (e.g.
and we consider two cases. Case 1: p o n ≥ τ . In this case we setx = x o + ,p n = p o n −τ andp i = p o i for each i = n. We first show that this is a valid solution. For each i = n we havê Note that the loss in utility for the defender is ∆ D,n τ + a which is upper bounded by That is b for a constant b when either x o is greater than a constant or ∆ n = 0. Observe that due to the fixed bit precision assumption ∆ n = 0 implies ∆ n is greater than a constant. We remark that the solution returned by our algorithm will be at least as good as the solution given byx andp i 's becausex is one of the discrete values of x considered. Thus, the defender's utility in the solution given by our algorithm is θ( )-close to the defenders utility in the optimal solution.
Case 2: p o n < τ . In this case we setp n = 0,x = x o + andp i = p o i for each i = 0. We first show that this is a valid solution. For each i = n we havê Note that the loss in utility for the defender is at most ∆ D,n τ + a which is upper bounded by That is b for a constant b. We again remark that the solution returned by our algorithm will be at least as good as the solution given byx andp i 's becausex is one of the discrete values of x considered. Thus, the defender's utility in the solution given by our algorithm is θ( )-close to the defenders utility in the optimal solution.
Proof of Lemma 1. Since the optimization objective depends on the variables p i 's only, and the quadratic constraints are same in both problems we just need to show that the regions spanned by the variables p i 's, as specified by the linear constraints, are the same in both problems.
First, let p i 's, p j i 's belong to region given by the grid constraints. Then, by the definition of C, for any c M L we know M is audited only by L. Thus, for i ∈ {t 1 , . . . , t |M | } the variables p j i are non-zero only when j ∈ {s 1 , . . . , s |L| }. Therefore, Hence, p i 's satisfies all constraints in C ∪{0 ≤ p i ≤ 1}, and therefore p i 's belong to region given by C ∪ {0 ≤ p i ≤ 1}. Next, let p i 's belong to region given by C ∪{0 ≤ p i ≤ 1}. We first show that the extreme points of the convex polytope given by C ∪ {0 ≤ p i ≤ 1} sets the variables p 1 , . . . , p n to either 0 or 1. We show this by contradiction, relying on the fact that extreme points cannot be written as the convex combination of other points in the convex polytope.
Assume, that there exists some values of p i 's for an extreme point Z such that its k th component p k ∈ (0, 1). An extreme point will satisfy some constraints with equality. For any equality constraint, p k cannot be the only nonintegral value, as the constant on the RHS of any constraint is an integer. Thus, there exists a probability variable different from p k that is non-integral. Let this be the l th component p l ∈ (0, 1). Let ζ be the minimum value that when added to the LHS of the strict inequalities for Z makes atleast one of them an equality. Now, consider the point X derived from Z in which p k 's value is changed to p k + , p l 's value is changed to p l − and all other probability variable values remain unchanged.
Here is a very small value, that is smaller than min(p k , 1 − p k , p l , 1 − p l , ζ). Hence, none of the constraints get violated and X lies in the convex polytope. Also, consider the point X in which the same operations are performed, but, with − , such that X also lies in the convex polytope. Thus, it is easy to see that Z = (X + X )/2. But, that contradicts the assumption that Z is a extreme point.
Next, it is easy to see that for given p i 's and p * i 's, with corresponding feasible p j i 's and p * j i 's, any convex combination p @ i 's of p i 's and p * i 's has a feasible solution p @j i 's which is the convex combination of p j i 's and p * j i 's. Since, any point in a convex set can be written as the convex combination of its extreme points (), it is enough to show the existence of feasible p j i 's for the extreme points in order to prove existence of feasible p j i 's for any point in the convex polytope under consideration.
The extreme points of the given convex polytope has ones in k ≤ k positions and all other zeros. The k ≤ k arises due to the constraint p 1 + . . . + p n ≤ k. Consider the undirected bipartite graph linking the inspections node to the target nodes, with a link indicating that the inspection can audit the linked target. This graph is known from our knowledge of R, and each link in the graph can be labeled by one of the p j i variables. Let S be the set of targets picked by the ones in any extreme points. We claim that there is a perfect matching from S to the the set of inspection resources (which we prove in next paragraph). Given such a perfect matching, assigning p j i = 1 for every edge in the matching yields a feasible solution, which completes the proof.
We prove the claim about perfect matching in the last paragraph. We do so by contradiction. Assume there is no perfect matching, then there must be a set S ⊆ S , such that |N (S )| < |S | (N is neighbors function, this statement holds by the well known Hall's theorem). As S ⊆ S it must hold that p i = 1 for all i ∈ index(S ) (function index gives the indices of the set of targets).. Also, the set of targets S is audited only by inspection resources in N (S ) and, by definition of C we must have a constraint (the function index gives the set of indices of the input set of targets) i∈index(S ) Using, |N (S )| < |S |, we get i∈index(S ) But, since |index(S )| = |S |, we conclude that all p i for targets in S cannot be one, which is a contradiction.
Proof of Lemma 2. Assume constraint c is in the output of the naive algorithm. Restrict the constraint c to be a non-implied constraint, i.e., if c is given by LHS(C) ≤ RHS(c) then it cannot be written as RHS(c i ) for any c 1 , . . . , c n . Note that such a restriction does not change the region defined by the set C. By the description of the naive algorithm, this constraint must correspond to a set of inspection resources, say S, and the set of targets T S inspected only by inspection resources in S, and there exists no subset of T S and S such that the subset of targets is inspected only by the subset of inspection resources. The constraint c is of the form P (T S ) ≤ |S|, where P (T S ) is the sum of the probability variables for targets in T S . Now, for the intersection graph representation, every node x represents targets that are inspected by a given subset x s of inspection resources. For our case, we claim that every t ∈ T S is either equivalent to or linked to another target in T S , otherwise we have the subset {t} ⊂ S inspected only by t s ⊂ T S . Thus, the targets in T S form a connected induced sub-graph. Thus, we conclude that the CONSTRAINT FIND algorithm will consider this set of targets and find the non-implied constraint c.
Next, assume that CONSTRAINT FIND finds a constraint c. As this corresponds to a connected induced subgraph (with targets as nodes), we obtain a set of targets T and a set of inspection resources ∪ t∈T F (t) such that targets in T are audited by ∪ t∈T F (t) only. Thus, by definition of the construction of c, this constraint is same as the constraint c obtained by the naive algorithm when it considers the set ∪ t∈T F (t). That is, c will also be found by the naive algorithm.
Proof of Lemma 3. The proof below lists sufficient conditions under which the number of induced connected subgraphs is polynomial is size. The proofs are constructive also, allowing extracting these sub-graphs in polynomial time.
• Graphs with O(log n) nodes. The maximum number of connected induced subgraphs in a graph with t nodes is 2 t (take any subset of vertexes). Thus, clearly a graph with O(log n) nodes will have polynomially many connected sub-graphs. • Graphs with constant max degree and constant number of nodes with degree ≥ 3. The number of connected induced subgraphs in a tree with max degree d and t vertexes with degree ≥ 3 is bounded from above by 2 (2(d+1)) t+1 n (d+1) t+1 . To prove this result, denote by T (n, d, t) the worst case number of connected induced sub-graphs in a graph with n vertices, and max degree d and t vertices with degree ≥ 3. Remove a vertex X with degree ≥ 3 to get k ≤ d disconnected components. Each connected sub-graph in any component that was linked to X could be combined with any connected sub-graph of any other component linked to X, yielding a new connected sub-graph. Thus, considering every subset of the k components, we get T (n, d, t) ≤ 2 k (T (n − 1, d, t − 1)) k Observing that k < d + 1, and T (n − 1, d, t − 1) ≤ T (n, d, t − 1) we get T (n, d, t) ≤ (2T (n, d, t − 1)) d+1 Thus, we see that T (n, d, t) = 2 (2(d+1)) t+1 (n) (d+1) t+1 satisfies the above equation. As part of the induction, the base case requires reasoning about a graph with max degree either 1 or 2 (t = 0, d = 1 or 2). Thus, we need to show that the connected subgraphs is less than n d+1 , which is n 2 for max-degree 1 and n 3 for max-degree 2. The max-degree 1 case is trivial. For the max-degree 2 case, such graphs can be decomposed efficiently into paths and cycles, and the number of connected sub-graphs on cycles and paths is less that n 2 .
Proof of Lemma 4. First, assume p o i 's and x o i 's are an optimal point of P X n . If x o n > 0 then reducing the value of x o n always yields a feasible point, as the quadratic inequality is still satisfied. Also, clearly reducing x o n increases the objective value. Thus, we must have x o n = 0. Next, reducing the value of p o n by p (≤ ) always yields a feasible point, as the quadratic inequality is still satisfied and so are the linear inequalities. The values of p are chosen so that the new values of p n lie on our discrete grid for p n . Thus, the new feasible point F is p o i 's for i = 1 to n − 1, x o i ' for i = 1 to n − 1 and p n = p o n − p , x n = 0. The objective at this feasible point F is off from the optimal value by a linear combination of p with constant coefficients, which is less than a constant times . Then, the SOCP with the new values of p n yields an objective value at least as high as the feasible point F on the grid. Thus, using our approach, we obtain a solution that differs from the optimum only by Θ( ).