Security Games with Information Leakage: Modeling and Computation

1 Introduction

Stackelberg security games played between a defender (leader) and an attacker (follower) have been widely studied in the past few years [Korzhyk et al., 2010; Letchford and Vorobeychik, 2011b; 2011a; Tambe, 2011; Basilico et al., 2012]. Most models, in particular, including all the deployed security systems in [Tambe, 2011], assume that the attacker is not able to observe (even partially) the defender's instantiated pure strategy (i.e., which targets are being protected), thus he makes decisions based only on his knowledge of the defender's mixed strategy. This fails to capture the attacker's real-time surveillance, by which he may partially observe the deployed pure strategy. For example, the attacker may observe the protection status of a certain target while approaching for an attack; or in some security domains information regarding the protection status of certain targets may leak to the attacker due to real-time surveillance or even an insider threat; further, well-prepared attackers may approach certain adversarially chosen target to collect information before committing an attack.

Unfortunately, this problem- an issue we refer to as information leakage - has not received much attention in Stackelberg security games. In the literature of patrolling games, attackers' real-time surveillance is indeed considered [Agmon et al., 2008b; 2008a; Basilico et al., 2009a; 2009b; Bošanský et al., 2011; Vorobeychik et al., 2014]. However, all these papers study settings of patrols carried out over space and time, i.e., the defender follows a schedule of visits to multiple targets over time. In addition, they assume that it takes time for the attacker to execute an attack, during which the defender can interrupt the attacker by visiting the attacked target. Therefore, even if the attacker can fully observe the current position of the defender (in essence, status of all targets), he may not have enough time to complete an attack on a target before being interrupted by the defender. The main challenge there is to create patrolling schedules with the smallest possible time between any two target visits. In contrast, we consider information leakage in standard security game models, where the attack is instantaneous and cannot be interrupted by the defender's resource re-allocation. Furthermore, as may be more realistic in our settings, we assume that information is leaked from a limited number of targets. As a result, our setting necessitates novel models and techniques. We also provide efficient algorithms with complexity analysis.

This paper considers the design of optimal defender strategy in the presence of partial information leakage. Considering that real-time surveillance is costly in practice, we explicitly assume that information leaks from only one target, though our model and algorithms can be generalized. We start from the basic security game model where the defender allocates k resources to protect n targets without any scheduling constraint. Such models have applications in real security systems like ARMOR for LAX airport and GUARDS for airports in general [Tambe, 2011]. We first show via a concrete example in Section 2 how ignoring information leakage can lead to significant utility loss. This motivates our design of optimal defending strategy given the possibility of information leakage. We start with a linear program formulation. However, perhaps surprisingly, we show that it is difficult to solve the LP even for this basic case, whereas the optimal mixed strategy without leakage can be computed easily. In particular, we show that the defender oracle, a key subproblem used in the column generation technique employed for most security games, is NP-hard. This shows the intrinsic difficulty of handling information leakage. We then approach the problem from three directions: efficient algorithms for special cases, approximation algorithms and heuristic algorithms for sampling that improves upon the status quo. Our experiments support our hypothesis that ignoring information leakage result in significant loss of utility for the defender, and demonstrates the value of our algorithms.

Note: due to space limit all the proofs in this paper are either described with sketches or omitted. Formal proofs can be found in the full version.

2 Model of Information Leakage

Consider a standard zero-sum Stackelberg security game with a defender and an attacker. The defender allocates k security resources to protect n targets, which are denoted by the set [n] = {1, 2, ..., n}. In this paper we consider the case where the security resources do not have scheduling constraints. That is, the defender's pure strategy is to protect any subset of [n] of size at most k. For any i ∈ [n], let ri be the reward [ci be the cost] of the defender when the attacked target i is protected [unprotected]. We consider zerosum games, therefore the attacker's utility is the negation of the defender's utility. Let s denote a pure strategy and S be the set of all pure strategies. With some abuse of notation, we sometimes regard s as a subset of [n] denoting the protected targets; and sometimes view it as an n-dimensional 0-1 vector with k 1's specifying the protected targets. The intended interpretation should be clear from context. The support of a mixed strategy is defined to be the set of pure strategies with non-zero probabilities. Without information leakage, the problem of computing the defender's optimal mixed strategy can be compactly formulated as linear program (1) with each variable xi as the marginal probability of covering target i. The resulting marginal vector ⃗x is a convex combination of the indicator vectors of pure strategies, and a mixed strategy achieving marginal ⃗x with small support can be efficiently sampled [Tsai et al., 2010].

Building on this basic security game, our model goes one step further and considers the possibility that the protection status of one target leaks to the attacker. Here, by "protection status" we mean whether this target is protected or not in an instantiation of the mixed strategy. We consider two related models of information leakage:

1. PRobabilistic Information Ieakage (PRIL): with probability pi(≥ 0) a single target i leaks information; and

with probability p0 = 1- ∑ni=1 pi no targets leak information. So we have ⃗ p = (p0, p1, ..., pn) ∈ ∆n+1 where ∆n+1 is the (n + 1)-dimensional simplex. In practice, ⃗ p is usually given by domain experts and may be determined by the nature or property of targets.

1. ADversarial Information Leakage (ADIL): with probability 1 - p0, one adversarially chosen target leaks information. This model captures the case where the attacker will strategically choose a target for surveillance and with certain probability he succeeds in observing the protection status of the surveyed target.

Given either model - PRIL with any ⃗ p ∈ ∆n+1 or ADIL - we are interested in computing the optimal defender patrolling strategy. The first question to ask is: why does the issue of information leakage matter and how does it affect the computation of the optimal defender strategy? To answer this question we employ a concrete example.

Consider a zero-sum security game with 4 targets and 2 resources. The profiles of reward ri [cost ci] is ⃗r = (1, 1, 2, 2) [⃗c = (-2,-2,-1,-1)], where the coordinates are indexed by target ids. If there is no information leakage, it is easy to see that the optimal marginal coverage is ⃗x = ( 2 3 , 23 , 1 3 , 1 3 ). The attacker will attack an arbitrary target, resulting in a defender utility of 0. Now, let us consider a simple case of information leakage. Assume the attacker observes whether target 1 is protected or not in any instantiation of the mixed strategy, i.e., p1 = 1. As we will argue, how the marginal probability ⃗x is implemented would matter now. One way to implement ⃗x is to protect target {1, 2} with probability 23 and protect {3, 4} with probability 13 . However, this implementation is "fragile" in the presence of the above information leakage. In particular, if the attacker observes that target 1 is protected (which occurs with probability 2 3 ), he infers that the defender is protecting target {1, 2} and will attack 3 or 4, resulting in a defender utility of -1; if target 1 is not protected, the attacker will just attack, resulting in a defender utility of -2. Therefore, the defender gets expected utility - 4 3 .

Now consider another way to implement the same marginal ⃗x by the following mixed strategy:

If the attacker observes that target 1 is protected (which occurs with probability 23 ), then he infers that target 2 is protected with probability 10 27 10 27 + 4 27 + 4 27 = 5 9 , and target 3, 4 are both protected with probability 29 . Some calculation shows that the attacker will have the same utility 13 on target 2, 3, 4 and thus will choose an arbitrary one to attack, resulting in a defender utility of - 13 . On the other hand, if target 1 is observed to be unprotected, the defender gets utility -2. In expectation, the defender gets utility 23 ×(- 13 )+ 13 ×(-2) = - 89 .

As seen above, though implementing the same marginals, the latter mixed strategy achieves better defender utility than the former one in the presence of information leakage. However, is it optimal? It turns out that the following mixed strategy achieves an even better defender utility of - 13 , which can be proved to be optimal: protect {1, 2} with probability 59 , {1, 3} with probability 29 and {1, 4} with probability 2 9 .

This example shows that compact representation by marginal coverage probabilities is not sufficient for computing the optimal defending strategy assuming information leakage. This naturally raises new computational challenges: how can we formulate the defender's optimization problem and compute the optimal solution? Is there still a compact formulation or is it necessary to enumerate all the exponentially many pure strategies? What is the computational complexity of this problem? We answer these questions in the next section.

3 Computing Optimal Defender Strategy

We will focus on the derivation of the PRIL model. The formulation for the ADIL model is provided at the end of this section since it admits a similar derivation. Fixing the defender's mixed strategy, let ti (¬ti) denote the event that target i is protected (unprotected). For the PRIL model, the defender's utility equals

where u = minj [rj Pr(tj) + cj Pr(¬tj)] is the defender's utility when there is no information leakage; and

is the defender's utility multiplied by probability Pr(ti) when target i leaks out its protection status as ti (i.e., protected); vi = minj [rj Pr(tj , ¬ti) + cj Pr(¬tj , ¬ti)] is the defender utility multiplied by Pr(¬ti) when i leaks out status ¬ti.

Define variables xij = Pr(ti, tj) (setting xii = Pr(ti)). Using the fact that Pr(ti, ¬tj) = xii - xij and Pr(¬ti, ¬tj) = 1 - xii - xjj + xij, the following linear program computes the defender's optimal patrolling strategy:

where u, ui, vi, xij, θs are variables; s denotes a pure strategy and the sum condition "s : i, j ∈ s" means summing over all the pure strategies that protect both targets i and j (or i if i = j); θs denotes the probability of choosing strategy s.

Unfortunately, LP (2) suffers from an exponential explosion of variables, specifically, θs. From the sake of computational efficiency, one natural idea is to find a compact representation of the defender's mixed strategy. As suggested by LP (2), the variables xij, indicating the probability that targets i, j are both protected, are sufficient to describe the defender's objective and the attacker's incentive constraints.

Let us call variables xij the pair-wise marginals and think of them as a matrix X ∈ Rn×n , i.e., the i'th row and j'th column of X is xij (not to be confused with the marginals ⃗x). We say X is feasible if there exists a mixed strategy, i.e., a distribution over pure strategies, that achieves the pair-wise marginals X. Clearly, not all X ∈ Rn×n are feasible. Let P(n, k) ∈ Rn×n be the set of all feasible X. The following lemma shows a structural property of P(n, k).

Lemma 1. P(n, k) is a polytope and any X ∈ P(n, k) is a symmetric positive semi-definite (PSD) matrix.

Therefore, we would be able to compute the optimal strategy efficiently in polynomial time if the constraints determining the polytope P(n, k) were only polynomially many - recall that this is the approach we took with LP (1) in the case of no information leakage. However, perhaps surprisingly, the problem turns out to be much harder in the presence of leakage.

Lemma 2. Optimizing over P(n, k) is NP-hard.

We prove Lemma 2 by reduction from the k-densest subgraph problem. This suggests that there is no hope of finding polynomially many linear constraints which determine P(n, k), assuming P ̸= NP. In fact, P(n, k) is closely related to a fundamental geometric object, known as the correlation polytope, which has applications in quantum mechanics, statistics, machine learning and combinatorial problems. We refer the reader to [Pitowsky, 1991] for more information.

Another approach for computing the optimal defender strategy is to use the technique of column generation, which is a master/slave decomposition of an optimization problem. The essential part of this approach is the slave problem, which is also called the "defender best response oracle" or "defender oracle" for short [Jain et al., 2010]. We defer the description of the defender oracle to Section 3.1, while only mention that Lemma 2 also implies the follows.

Lemma 3. The defender oracle is NP-hard.

By now, we have shown the evidence of the difficulty of solving LP (2) using either marginals or the technique of column generation. For the ADIL model, a similar argument yields that the following LP formulation computes the optimal defender strategy. It is easy to check that it shares the same marginals and defender oracle as the PRIL model.

where variable w is the defender's expected utility when an adversarially chosen target is observed by the attacker.

3.1 Leakage from Small Support of Targets

Despite the hardness results for the general case, we show that the defender oracle admits a polynomial time algorithm if information only leaks from a small subset of targets; we call this set the leakage support. By re-ordering the targets, we may assume without loss of generality that only the first m targets, denoted by set [m], could possibly leak information in both the PRIL and ADIL model. For PRIL model, this means pi = 0 for any i > m and for ADIL model, this means the attacker only chooses a target in [m] for surveillance.

Why does this make the problem tractable? Intuitively the reason is as follows: when information leaks from a small set of targets, we only need to consider the correlations between these leaking targets and others, which is a much smaller set of variables than in LP (2) or (3). Restricted to a leakage support of size m, the defender oracle is the following problem. Let A be a symmetric matrix of the following block form

where m′ = n-m; Amm′ ∈ Rm×m′ for any integers m,m′ is a sub-matrix and, crucially, Am′m′ is a diagonal matrix. Given A of form (4), find a pure strategy s such that sT As is maximized. That is, the defender oracle identifies the size-k principle submatrix with maximum entry sum for any A of form (4). Note that m = n in general case.

Before detailing the algorithm, we first describe some notation. Let A[i, :] be the i'th row of matrix A and diag(A) be the vector consisting of the diagonal entries of A. For any subset C1,C2 of [n], let AC1,C2 be the submatrix of A consisting of rows in C1 and columns in C2, and sum(AC1,C2 ) = ∑i∈C1,j∈C2 Aij be the entry sum of AC1,C2 . The following lemma shows that Algorithm 1 solves the defender oracle. Our main insight is that for a pure strategy s to be optimal, once the set C = s ∩ [m] is decided, its complement ¯ C = s \ C can be explicitly identified, therefore we can simply brute-force search to find the best C ⊆ [m]. Lemma 4 provides the algorithm guarantee, which then yields the polynomial solvability for the case of small m (Theorem 1).

Lemma 4. Let m be the size of the leakage support. Algorithm 1 solves the defender oracle and runs in poly(n, k, 2m) time. In particular, the defender oracle admits a poly(n, k) time algorithm if m is a constant.

Algorithm 1 Defender Oracle

Input: matrix A of form (4).

Output: a pure strategy s.

• 1: for all C ⊆ [m] constrained by |C| ≤ k do
• 2: ⃗v = 2 ∑i∈C A[i, :] +diag(A);
• 3: Choose the largest k-|C| values from{vm+1, ..., vn}, and denote the set of their indices as ¯ C;
• 4: Set valC = sum(AC,C) + sum(v ¯ C );
• 5: end for
• 6: return the pure strategy s = C∪ ¯ C with maximum valC .

Theorem1. (Polynomial Solvability) There is an efficient poly(n, k) time algorithm which computes the optimal defender strategy, if m is a constant.

3.2 An Approximation Algorithm

We now consider approximation algorithms. Recall that information leakage is due to the correlation between targets, thus one natural way to minimize leakage is to allocate each resource independently with certain distributions. Naturally, the normalized marginal ⃗x∗/k becomes a choice, where ⃗x∗ is the solution to LP (1). To avoid the waste of using multiple resources to protect the same target, we sample without replacement. Formally, the independent sampling without replacement algorithm proceeds as follows: 1. compute the optimal solution ⃗x∗ of LP (1); 2. independently sample k elements from [n] without replacement using distribution ⃗x∗/k.

Zero-sum games exhibit negative utilities, therefore an approximation ratio in terms of utility is not meaningful. To analyze the performance of this algorithm we shift all the payoffs by a constant, -mini ci, and get an equivalent constantsum game with all non-negative payoffs. Theorem 2 shows that this algorithm is "almost" a (1 - 1e ) - approximation to the optimal solution in the PRIL model, assuming information leaks out from any target i with equal probability pi = 1-p0 n . We note that proving a general approximation ratio for any ⃗ p ∈ ∆n+1 turns out to be very challenging, intuitively because the optimal strategy adjusts according to different ⃗ p while the sampling algorithm does not depend on ⃗ p. However, experiments empirically show that the ratio does not vary much for different ⃗ p on average (see Section 5).

Theorem 2. Assume each target leaks information with equal probability pi = 1-p0 n . Let ¯ ci ≥ 0 be the shifted cost and UindepSample be the defender utility achieved by independent sampling without replacement. Then we have:

4 Sampling Algorithms

From Carathéodory's theorem we know that, given any marginal coverage ⃗x, there are many different mixed strategies achieving the same marginal ⃗x (e.g., see examples in Section 2). Another way to handle information leakage is to generate the optimal marginal coverage ⃗x∗ , computed by LP (1), with low correlation between targets. Such a "good" mixed strategy, e.g., the mixed strategy with maximum entropy, is usually supported on a pure strategy set of exponential size. In this section, we propose two sampling algorithms, which efficiently generate a mixed strategy with exponentially large support and are guaranteed to achieve any given marginal ⃗x.

4.1 Max-Entropy Sampling

Perhaps the most natural choice to achieve low correlation is the distribution with maximum entropy restricted to achieving the marginal ⃗x. This distribution can be formulated as the solution of Convex Program (CP) (5).

However, naive approaches for solving CP (5) require exponential time since there are O(2n ) variables. Interestingly, it turns out that this can be resolved.

Theorem 3. There is an efficient algorithm which runs in poly(n, k) time and outputs a pure strategy s with probability θ∗ s for any pure strategy s ∈ S, where ⃗ θ∗ is the optimal solution to Convex Program (5) (within machine precision 1 ).

The proof of Theorem 3 relies on Lemmas 5 and 6. Lemma 5 presents a compact representation of ⃗ θ∗ based on the KKT conditions of CP (5) and its dual - the unconstrained Convex Program (6):

where variables ⃗ β ∈ Rn and e-βs = Πi∈se-βi .

Lemma 5. Let ⃗ β∗ ∈ Rn be the optimal solution to CP (6) and set αi = e-β∗ i for any i ∈ [n], then the optimal solution of CP (5) satisfies

where αs = Πi∈sαi for any pure strategy s ∈ S. Furthermore, ⃗ β∗ can be computed in poly(n, k) time.

We note that the characterization of θ∗ s in Lemma 5 is not new (e.g., see [Singh and Vishnoi, 2013]), and we state it for completeness. Our contribution lies at proving that CP (6) can be computed efficiently in poly(n, k) time in our security game settings despite the summation ∑s e-βs of O(2k ) terms. In particular, f(⃗ β) is a convex function of n variables. If the function value and gradient can be computed in polynomial time, then so is the optimal solution ⃗β∗ . The key idea to evaluate f(⃗ β) is to use Dynamic Programming (DP) to evaluate the sum ∑s e-βs inside the expression of f (⃗ β) and then do the other calculations explicitly. 2 Notice that the set of all pure strategies consists of all the subsets of [n] of cardinality k. Let αi = e-βi and αs = Πi∈sαi. We then build the following DP table T (i, j) = ∑s:s⊆[j],|s|=i αs, which sums over all the subsets of [j] of cardinality i. Our goal is to compute T(k, n) = ∑s e-βs . We first initialize T(1, j) = ∑ji=1 αi and T(j, j) = Πji=1αi for any j. Then using the following update rule, we can build the DP table and compute T (k, n) in poly(k, n) time.

Our next lemma considers how to efficiently sample a pure strategy s from an exponentially large support with probability θ∗ s represented by Equation (7).

Lemma 6. Given any input ⃗α ∈ [0,∞)n , Algorithm 2 runs in poly(k, n) time and correctly samples a pure strategy s with probability θs = αs ∑s αs , where αs = Πi∈sαi.

We notice that approximately uniform sampling from combinatorial structures has been studied in theoretical computer science [Jerrum et al., 1986]. Algorithm 2 uses a variant of the algorithm in [Jerrum et al., 1986], and extends their results to the weighted (by θ∗ s ) and exact case.

1 Computers cannot solve general convex programs exactly due to possible irrational solutions. Therefore, our algorithm is optimal within machine precision, and we simply call it "solved".

2∇f (⃗ β) can be computed in a similar fashion.

Algorithm 2 Max-Entropy Sampling

Input: : ⃗α ∈ [0,∞)n , k.

Output: : a pure strategy s with |s| = k.

• 1: Initialize: s = ∅;
• 2: Compute the DP table T(i, j) = ∑s:s⊆[j],|s|=i αs for any i, j satisfying i ≤ k, j ≤ n and i ≤ j;
• 3: Set i = k, j = n;
• 4: while i>0 do
• 5: Independently add j to s with probability

• 6: if j added to s then
• 7: i = i - 1;
• 8: end if
• 9: j = j -1;
• 10: end while
• 11: return s.

4.2 UniformComb Sampling

[Tsai et al., 2010] presented the Comb Sampling algorithm, which randomly samples a pure strategy and achieves a given marginal in expectation. The algorithm can be elegantly described as follows (also see Figure 1): thinking of k resources as k buckets with height 1 each, we then put each target, the height of which equals precisely its marginal probability, one by one into the buckets. If one bucket gets full when filling in a certain target, we move the "rest" of that target to a new empty bucket. Continue this until all the targets are filled in, at which time we know that k buckets are also full. The algorithm then takes a horizontal line with a uniformly randomly chosen height from the interval [0, 1], and the k targets intersecting the horizontal line constitute the sampled pure strategy. As easily observed, Comb Sampling achieves the marginal coverage in expectation [Tsai et al., 2010].

However, is Comb Sampling robust against information leakage? We first observe that Comb Sampling generates a mixed strategy with support size at most n + 1, which precisely matches the upper

bound of Carathéodory's theorem.

Proposition 1. Comb Sampling generates amixed strategy which mixes over at most n + 1 pure strategies.

Proposition 1 suggests that the mixed strategy sampled by Comb Sampling might be very easy to explore. Therefore we propose a variant of the Comb Sampling algorithm. Our key observation is that Comb Sampling achieves the marginal coverage regardless of the order of the targets. That is, the marginal is still obtained if we randomly shuffle the order of the targets each time before sampling, and then fill in them one by one. Therefore, we propose the following Uniform Comb Sampling (UniCS) algorithm:

1. Order the n targets uniformly at random;
2. fill the targets into the buckets based on the random order, and then apply Comb Sampling.

Since the order is chosen randomly each time, the mixed strategy implemented by UniCS mixes over exponentially many pure strategies, and achieves the marginal.

Proposition 2. Uniform Comb Sampling (UniCS) achieves the marginal coverage probability.

5 Experiments

Traditional algorithms for computing Strong Stackelberg Equilibrium (SSE) only optimize the coverage probability at each target, without considering their correlations. In this section, we experimentally study how traditional algorithms and our new algorithms perform in presence of probabilistic or adversarial information leakage. In particular, we compare the following five algorithms.

• Traditional: optimal marginal + comb sampling, the traditional way to solve security games with no scheduling constraints [Kiekintveld et al., 2009; Tsai et al., 2010];
• OPT: the optimal algorithm for PRIL or ADIL model (Section 3.1) using column generation with the defender oracle in Algorithm 1;
• indepSample: independent sampling without replacement (Section 3.2);
• MaxEntro: max entropy sampling (Algorithm 2);
• UniCS: uniform comb sampling (Section 4.2).

All algorithms are tested on the following two sets of data:

Los Angeles International Airport (LAX) Checkpoint Data from [Pita et al., 2008]. This problem was modeled as a Bayesian Stackelberg game with multiple adversary types in [Pita et al., 2008]. To be consistent with our model, we instead only consider the game against one particular type of adversary - the terrorist-type adversary, which is the main concern of the airport. The defender's rewards and costs are obtained from [Pita et al., 2008] and the game is assumed to be zero-sum in our experiments.

Simulated Game Payoffs. A systematic examination is conducted with simulated payoffs. All generated games have 20 targets and 10 resources. The reward ri (cost ci) of each target i is chosen uniformly at random from the interval [0, 10] ([-10, 0]).

In terms of running time, all the algorithms run efficiently as expected (terminate within seconds using MATLAB) except the optimal algorithm OPT, which takes about 3 minutes per simulated game on average. Therefore we mainly compare defender utilities. All the comparisons are listed in Figure 2 (for LAX data) and Figure 3 (for simulated data). The line "Basis" is the utility with no leakage and is listed as a basis for utility comparisons. Y-axis is the defender's utility - the higher, the better. We examine the effect of the total probability of leakage (i.e., the x-axis 1 - p0) on the defender's utility and consider 1 - p0 = 0, 0.1, ..., 1. For probabilistic information leakage, we randomly generate the probabilities that each target leaks information with the constraint ∑ni=1 pi = 1-p0. For the case of leakage from small support (for simulated payoffs only), we randomly choose a support of size 5. All the utilities are averaged over 50 random games except the ADIL model for LAX data. For the simulated payoffs, we also consider a special case of uniform leakage probability of each target (see Theorem 2). The following observations follow from the figures.

Observation 1. The gap between the line "Basis" and "OPT" shows that information leakage from even one target does cause dramatic utility decrease to the defender. Moreover, adversarial leakage causes more utility loss than probabilistic leakage; leakage from a restricted small support of targets causes less utility decrease than from full support.

Observation 2. The gap between the line "OPT" and "Traditional" demonstrates the necessity of handling information leakage. In particular, the relative loss u(OPT) -u(Basis) is approximately half of the relative loss u(Traditional) - u(Basis) in Figure 3 (and 65% in Figure 2). Furthermore, if leakage is from a small support (left-up panel in Figure 3), OPT is close to Basis.

Observation 3. MaxEntro and UniCS have almost the same performance (overlapping in all these figures). Both algorithms are almost optimal when the leakage support is the full set [n] (they almost overlap with OPT in the right-up and left-down panels in Figure 3).

Observation 4. An interesting observation is that IndepSample outperforms Traditional at 1 - p0 = 0.3 or 0.4 in all of these figures, which is around 1e ≈ 0.37. Furthermore, the gap between IndepSample and OPT does not change much at different 1 - p0.

Observation 5. From a practical view, if the leakage is from a small support, OPT is preferred as it admits efficient algorithms (Section 3.1); if the leakage is from a large support, MaxEntropy and UniCS are preferred as they can be computed efficiently and are close to optimality. From a theoretical perspective, we note that the intriguing performance of IndepSample, MaxEntropy and UniCS raises questions for future work.

6 Conclusions and Discussions

In this paper, we considered partial information leakage in Stackelberg security games. We focused on the one-target leakage case, but do emphasize that our models, hardness results and algorithms can be easily generalized. Our results raise several new research questions, e.g., is it possible to derive a theoretical approximation guarantee for MaxEntro and UniCS, and can we develop efficient algorithms to handle information leakage in other security game settings? More generally, it is an interesting problem to study analogous issues of information leakage in other settings beyond security, e.g., auctions or general games.

Acknowledgement: This research was supported by MURI grant W911NF-11-1-0332, US-Naval Research grant Z14-12072 and NSF grant CCF- 1350900.