Comparing Strategic Secrecy and Stackelberg Commitment in Security Games

1 Introduction

Strong Stackelberg Equilibrium (SSE) has for some time been used to allocate limited security resources to protect targets in many security scenarios including public infrastructures [Kiekintveld et al., 2009; Shieh et al., 2012; Yin et al., 2014; Gan et al., 2015; Zhao et al., 2016] and wildlife [Fang et al., 2016]. In the SSE solution concept, the defender discloses the (possibly randomized) commitment to protect the targets. This commitment is then observed by the attacker who adopts the best response. While in theory it is always favorable for the defender to disclose the commitment, in practice this concept overestimates the surveillance of the attacker [An et al., 2013; Pita et al., 2010] and neglects the fact that certain part of information could have been hidden to the attacker due to imperfect observation [Catchnews, 2016; Gul, 2011]. One example is that the attacker may have been uncertain about the number of the resources of the defender, since the defender can actually use unmarked resources (e.g., plainclothes police) to protect the targets. As a consequence, it is no longer clear that disclosing the full commitment is always beneficial for the defender compared to strategically revealing only part of information (termed strategic secrecy from now on) - in fact we present an example later in the paper where it is worse for the defender to disclose full commitment compared to strategic secrecy.

We address this discrepancy between the theory and practice and propose a novel class of security games that extends the existing security models in two main aspects: (1) the attacker has an uncertain information about the number of resources of the defender, (2) the defender is allowed to strategically disclose the number of resources.

We model these aspects as Disguised-resource Security Game (DSG) and analyze the strategic secrecy where the defender strategically deceives the attacker by disguising some of her resources. The number of the revealed resources is modeled as a signal which can only be sent by the defender with enough resources. We compare the expected utility of strategic secrecy with the value of public commitment and formally show that they have different advantages depending on the payoff structure. To be able to evaluate the difference between strategic secrecy and commitment in practice we introduce a collection of novel algorithms to solve for the solution concept based on Perfect Bayesian Equilibrium (PBE) [Spence, 1973; Zhuang and Bier, 2011]: (1) we introduce a basic Mixed-Integer Linear Programming (MILP) with an exponential number of variables and constraints, (2) an MILP of directly applying compact representation, and (3) a novel approach based on support set enumeration, and (4) an approximation algorithm based on support set enumeration to produce an ϵ-PBE. Finally, we conduct extensive experimental evaluation to show that our algorithms can scale to realistic problems and to examine the fundamental trade-offs between secrecy and public commitment for realistic problems. We conclude that the boundary of such trade-offs is close to zero-sum games which confirms the practical use of plainclothes police due to the approximate zero-sum nature of many security scenarios (e.g., [Banks and Anderson, 2006; Durkota et al., 2015; Haskell et al., 2014; Major, 2002]).

2 RelatedWork

Previous work on secrecy and deception in security games has failed to address the key dilemma of strategic secrecy

૛ resources

<ૠૡ ǡ ૠૡ ǡ ૚૝>

െ૚Ǥ ૞ െ૚Ǥ ૞

ࢊǣ

െ૟

Figure 1: Example (left: strategic secrecy, right: commitment).

and commitment for various reasons. Brown et al. [2005] study secrecy in the context of ballistic missile deployment, but assume that the attacker is not aware that the defender can hide resources, so there is no rational possibility for belief update. Other researchers explore signaling games to model a "feint" in homeland security [Hendricks and McAfee, 2006; Oliveros, 2005]. In these games the defender's resource allocation causes a noisy signal following an uncontrolled signaling technology, in contrast with our model where the defender controls the signals sent. One key feature of the strategic secrecy in our model is that the revealed security resources (signal) are valid information for the attacker, which differs from the cheap talk game [Farrell and Rabin, 1996] where messages are costless and unverifiable.

Recently, there are some literatures studying the information disclosure to persuade the attacker to take the desired action [Rabinovich et al., 2015; Xu et al., 2015] with a strong assumption that the attacker can fully access the defender's correlated random allocation and signaling scheme by unlimited surveillance, which is unrealistic in the strategic secrecy scenarios. The most closely related model was proposed by Zhuang and Bier [2011], where deception is regarded as a signal to mislead the attacker's belief about the defender type, while the true defense is treated as a hidden action. Their model assumes that the defender deterministically sends the signal, while we allow the randomized signaling strategy, which is possible and more general in resource allocation domain. Furthermore, they only provide general results for high-level special cases without providing efficient algorithms for realistic problems.

3 Motivating Example

Suppose a small police station (the defender) has three districts to protect, A, B and C. The police station has either one or two patrol units, depending on the day. We call these cases the weak and strong types, and assume that they are equally likely for the example. An attacker will choose one of the three districts to target, represented by a mixed attacking strategy a = 〈aA, aB, aC〉 where at denotes the probability of attacking district t ∈ {A,B,C}. The police strategy can be compactly represented by a coverage vector c = 〈cA, cB, cC〉 such that ct is the probability that district t is covered by a patrol unit. There are four payoffs associated with each district, 〈Rd t , P a t , P d t ,Ra t 〉: if a resource is allocated to attacked district t, then defender receives a reward Rd t and the attacker receives a penalty P a t ; otherwise the payoffs are P d t and Ra t respectively. The game is shown in Figure 1, where A and B are homogeneous districts with the same payoffs and RaA = -P dA = 12, and RaC = -P dC = 2, while Rd t = P a t = 0 for t ∈ {A,B,C}. Consider that the strong type (with 2 resources) can disguise one resource, or choose to commit herself by revealing both resources.

If the defender chooses to reveal the type, the scenario can be captured by the strong Stackelberg equilibrium (SSE), widely adopted in the security game literature, where the attacker can observe the defender strategy with extensive surveillance. We will present the formal equilibrium concept in the next section. For now, it is easy to see that in the equilibrium (shown in the game tree on the right in Figure 1), the weak type will play the coverage vector 〈0.5, 0.5, 0〉 equalizing the attacker's expected payoff between A and B, resulting in an expected utility of -6. The strong type will play 〈 7 8 , 78 , 14 〉 and receive -1.5.

It is worthwhile to note that the assumption of the attacker knowing the defender strategy is critical to the advantage of commitment. However, as we discussed in Section 1, the extensive surveillance assumption is actually unrealistic and thus cannot capture the problem here. Even though, the defender can still do better with strategic secrecy, taking into account the limited observation of the attacker. If the defender is allowed to strategically disguise a resource, we have a different game, shown in the game tree on the left in Figure 1. Suppose that the strong type hides one resource with 100% probability. When the attacker observes only 1 patrol unit, he cannot know the type he is facing. Thus, the attacker will update his belief on the defender type and it turns out that he is playing against both types with equal probability according to Bayes' rule. Now the weak type still plays coverage 〈0.5, 0.5, 0〉, while the strong type plays 〈1, 1, 0〉 and attacker receives an expected payoff of 3 for attacking A or B and plays a mixed strategy 〈0.5, 0.5, 0〉. We can verify that the equilibrium is formed where no player has incentive to deviate. As we will formally present in the next section, such equilibrium is the Perfect Bayesian equilibrium (PBE) in extensive-form games. In the equilibrium, the weak type still receives -6, while the strong type gets 0, better than -1.5 with commitment. One thing to notice here is that the attacker does not know the probability of the strong type disguising one resource, and the reason of updating the posterior belief according to Bayes' rule is that as long as both players agree on the equilibrium, the attacker can infer such probability and update the belief, which is the key spirit of Nash equilibrium.

4 Disguised-Resource Security Games (DSG)

A DSG extends the structure of a Stackelberg security game [Kiekintveld et al., 2009], but adds a way to model the defender holding private information about the number of resources. The game is played by a defender and an attacker. The defender protects a set of targets T and the attacker chooses a target t ∈ T to attack. There are multiple defender types and each one has a different number of available resources to protect the targets. We note that this abuses the terminology "type" a bit, since we will assume that all types have the same utility function, but effectively have a different strategy spaces. We use θ ∈ Θ to represent the number of resources available to each defender type (e.g., police teams, patrol boats). The prior probability distribution over types p : Θ → [0, 1] is known to both players.

In DSG, the defender is allowed to publicly reveal only a subset of her available resources and the number of revealed resources is denoted as a signal. 1 W.l.o.g., we assume that the signal is in the set Θ. The remaining resources are disguised, as in the case of a plainclothes police officer or unmarked vehicle. Importantly, in our model the defender cannot send invalid signals that claim a greater number of resources than are actually available, so a defender of type θ can only send a signal s ≤ θ. The payoffs follow the same definition in Section 3. Consistently with existing work on security games Rd t > P d t andRa t > P a t . The DSG is an extensive-form game which proceeds as illustrated by the motivating example: Nature randomly chooses one type for the defender and let it be the strong type θ = 2. The strong type draws a signal according to the mixed signaling strategy which turns out to be s = 1. The attacker cannot distinguish the two decision nodes corresponding to both types sending the same signal s = 1, and the set of these decision nodes is called an information set denoted by I(s).

Strategies: Let c = 〈ct〉 and a = 〈at〉 denote the defender's coverage strategy and attacker's mixed attacking strategy as defined in Section 3. Let o = 〈os〉 denote the mixed signaling strategy such that os represents the probability of sending signal s. Let ∆θc = {c ∈ [0, 1]|T| : ‖c‖1 = θ} denote the set of coverage strategies available for defender type θ and ∆c = ⋃θ∈Θ ∆θc be the set of all coverage strategies. Similarly, we denote by ∆θo = {o ∈ [0, 1]|Θ| : ‖o‖1 = 1, os = 0 ∀s > θ} the set of mixed signaling strategies available for defender type θ and ∆o = ⋃θ∈Θ ∆θo . Let ∆a = {a ∈ [0, 1]|T| : ‖a‖1 = 1} represent the set of all mixed attacking strategies. Let πd = 〈πc, πo〉 denote the defender policy where πc : Θ×Θ→∆c is the coverage policy such that πc(θ, s) ∈ ∆θc denotes the coverage strategy adopted by defender type θ conditioned on sending signal s and πc(t|θ, s) is the corresponding marginal coverage on target t, and πo : Θ → ∆o is the signaling policy with πo(θ) ∈ ∆θo representing the mixed signaling strategy for defender type θ and πo(s|θ) being the corresponding probability of sending signal s. In particular, we use πc(θ) = 〈πc(θ, s)〉 to denote the coverage policy for defender type θ. Let πa : Θ → ∆a denote the attacker policy such that πa(s) ∈ ∆a is the mixed attacking strategy adopted by the attacker observing signal s, where the corresponding probability of attacking target t is denoted by πa(t|s).

Posterior Belief: Let ∆Θ = {〈δθ〉 : ‖δ‖1 = 1} be the set of all possible probability distributions over Θ. We denote by µ : Θ → ∆Θ the attacker's posterior belief on the defender type conditioned on the received signal. In particular, µ(θ|s) denotes the posterior probability of defender type being θ at information set I(s). Apparently, µ(θ|s) = 0 for θ < s. If I(s) is on the equilibrium path, i.e., s is sent with positive probability (∑θ:θ≥s pθπo(s|θ) > 0), the belief is determined by the Bayes' rule, such that:

1 The intuition of such definition is that the attacker is more likely to observe the number of revealed resources due to the limited observation.

Otherwise, if I(s) is off the equilibrium path, such as I(s = 2) in the motivating example where no type sends such signal, we adopt the optimistic conjecture [Rubinstein, 1985]. That is to say, when the defender acts off the equilibrium strategy, the attacker believes the defender of her weakest type, against which the attacker would gain the most. Intuitively the attacker always prefers to play against a defender type with fewer resources, which is confirmed by Theorem 1. Thus, at information set I(s) which is off equilibrium path, we have: µ(s|s) = 1 and µ(θ|s) = 0 for all θ > s. Throughout the paper, we assume that posterior belief µ follows Bayes' rule and the optimistic conjecture for information sets on and off equilibrium path respectively.

Utilities: Given the defender coverage strategy c ∈ ∆c and the mixed attacking strategy a ∈ ∆a, the expected payoffs of both players are defined as follows:

Given the defender's policy πd = 〈πc, πo〉 and attacker's policy πa, the expected utility of the attacker conditioned on receiving signal s, and the expected utility of the defender type θ are defined as follows:

Theorem 1. For two defender types θ and θ′ such that θ > θ′ , suppose 〈c, a〉 is a Nash equilibrium between the attacker and defender type θ, then there always exists an NE profile 〈c′ , a′ 〉 between the attacker and defender type θ′ such that Pa(c′ , a′ ) ≥ Pa(c, a).

Proof. W.l.o.g, assume ct < 1 for each t ∈ T. According to the defender's best response criteria, ct > 0 only for t in the support set of a. We iteratively construct a coverage vector c′ and a set of targets T ′ as follows: i) initially, c′ = c, and T ′ = {t ∈ T : at > 0}; ii) for each target t ∈ T ′ , we decrease c′t a bit by a small amount value δt which is proportional to 1/(Ra t -P a t ) such that (Ra t -P a t )δt = (Ra t′ - P a t′)δt′ for any t, t′ ∈ T ′ ; and iii) if for some target t ∈ T ′ , c′t ≤ 0, we remove t from T ′ and set c′t to 0; iv) the procedure terminates as long as ∑t∈T c′t = θ′ . At this point, we obtain a coverage strategy c′ for the defender type θ′ covering T ′ such that targets in T ′ are all best response targets for the attacker. Let a′ be the mixed attacking strategy such that a′t = λ/(Rd t -P d t ) for t ∈ T ′ and a′t = 0 otherwise, where λ = 1/∑t∈T ′ 1 Rd t -P d t . It can be easily verified that strategy profile 〈c′ , a′ 〉 forms an NE, and Pa(c′ , a′ ) > Pa(c, a).

Equilibrium Concepts: Analogous to the equilibrium of extensive-form game with first-mover hidden actions [Zhuang and Bier, 2011], the solution concept adopted for DSG is based on PBE, which is the profile 〈π∗ d , π∗ a 〉 where:

Due to the strict requirement in PBE that both players will not play a suboptimal response strategy, the computation of PBE is extremely challenging. Thus, we also consider the ϵ-PBE, an approximation of PBE that allows players to have a small incentive to play strategies other than the one played in the equilibrium. Formally, an ϵ-PBE is a strategy profile 〈π∗ d , π∗ a 〉 where: i) Ud(π∗ c (θ), π∗ o (θ), π∗ a ) ≥ Ud(πc(θ), πo(θ), π∗ a ) - ϵ, ∀θ ∈ Θ, 〈πc(θ), πo(θ)〉 and ii) Ua(π∗ c , π∗ o , π∗ a (s)) ≥ Ua(π∗ c , π∗ o , πa(s)) - ϵ, ∀s ∈ Θ, πa(s).

The SSE [Leitmann, 1978] between the defender and attacker is a pair of strategies 〈c, f(c)〉 where: i) Pd(c, f(c)) ≥ Pd(c′ , f(c′ )), ∀c′ , ii) Pa(c, f(c)) ≥ Pa(c, a), ∀a; and iii) the attacker breaks ties in favor of defender: Pd(c, f(c)) ≥ Pd(c, a) for all optimal attacking strategies a.

Given these formal definitions, we can verify that the game trees in Figure 1 correspond with PBE and SSE respectively, and the defender utility is higher in PBE. However, disguising resources is not always beneficial. Consider the same game in the motivating example. Suppose the payoffs are changed by setting RdC = 8 and the game is no longer zero-sum. The PBE remains unchanged, as well as the SSE for the weak type. In SSE for the strong type, coverage 〈 78 , 78 , 14 〉 is still played. However, the attacker will attack C which brings the strong type an expected utility of 0.5, higher than 0 in PBE. We can see that the benefit of PBE is sensitive to the correlation between defender and attacker payoffs and the strategic secrecy is preferred when the game is "close" to zero-sum. Our next section affirms such conjecture with theoretical analysis.

5 PBE versus SSE

For zero-sum DSGs where the players' payoffs are perfectly correlated, we prove that any PBE gives the defender utility at least as high as SSE (Theorem 2). The intuition for Theorem 2 is that for zero-sumDSGs, the defender cannot benefit from public commitment and SSE reduces to NE, while in PBE the attacker cannot distinguish the defender type, so he may not play the best response to each individual type, and the defender can take the advantage.

Theorem 2. For a zero-sum DSG, given any PBE 〈π∗ d , π∗ a 〉 and SSE 〈cθ , aθ 〉 formed by defender type θ and the attacker, we have: Ud(π∗ c (θ), π∗ o (θ), π∗ a ) ≥ Pd(cθ , aθ ), ∀θ.

Proof. SSE is equivalent with NE in zero-sum games. Given that aθ is the best response against cθ and vice versa, and π∗ c (θ, s) is the best response against π∗ a (s), we have:

Thus:

On the other hand, we analyze a PBE in the special case where all types have a similar number of resources, and show that this PBE has defender utility less than or equal to SSE (Theorem 3). The idea is that when all types have a similar number of resources, it is likely that there exists a set of targets T ′ = {t1, .., tk}, such that for each type θ, the NE coverage strategy has support set T ′ . In this case, we can show the existence of a PBE where each defender type is playing that NE coverage strategy regardless of signals, and the corresponding defender's expected utility is equal to her expected utility in NE, which is no higher than that in SSE. Since Theorem 3 has no restriction on the correlation between defender and attacker payoffs, with less correlation the defender benefits more from commitment and the defender utility in SSE can be much higher than that in the PBE in Theorem 3.

Theorem 3. Let the targets be listed by Ra t with descending order: T = {t1, .., t|T|}. If there exists k such that: ∑kl=1 Ra tl -Ra tk Ra tl -P a tl ≤ θ ≤ ∑kl=1 Ra tl -Ra tk+1 Ra tl -P a tl holds for any type θ, then there exists a PBE 〈π∗ d , π∗ a 〉 such that Ud(π∗ c (θ), π∗ o (θ), π∗ a ) ≤ Pd(cθ , aθ ) for any type, where 〈cθ , aθ 〉 is an SSE between type θ and the attacker.

Proof. Suppose such a k exists. For any type θ, define uθ as follows:

and we have:

according to the inequality in the theorem. Consider the strategy profile 〈π∗ d , π∗ a 〉 where:

We have: Pa(π∗ c (θ, s), t) = uθ for t ∈ {t1, .., tk}. In other words, π∗ a (s) is best response against each individual coverage vector π∗ c (θ, s) for all θ, s ∈ Θ : θ ≥ s. According to the definition of SSE, we have:

6 Computing PBE Solutions

We now introduce computation methods for computing PBE. We first try an MILP based on mixed defender strategy representation which is a variant of the sequence-formMILP for extensive-form games. This approach is not scalable due to

the exponential number of pure strategies, even with implementation of constraint-generation approach. To reduce the strategy space we directly apply the compact representation (coverage), and propose another MILP with a polynomial number of variables and constraints. However, the defender's best response criteria turn out to be nontrivial. Although they can be linearly represented based on the complementary slackness conditions [Bertsimas and Tsitsiklis, 1997], the auxiliary binary variables and logistic constraints make the MILP not scalable. We omit the formulations and experiments of these (failed) approaches for the ease of reading.

To produce a scalable solution, we further investigate the special structure of PBE. We start with PBEs where the attacker policy is unbiased (Definition 1 given later), which makes the defender's best response criteria much easier to represent. We then propose a concise and scalable formulation to compute such PBEs based on support set enumeration. In case no such PBE exists, the formulation is modified to compute the ϵ-PBE instead. The experimental evaluation shows that in almost all cases, our approach can compute a PBE, and a high-quality approximate ϵ-PBE in the remaining cases. We now give a definition of an unbiased attacker strategy, followed by the support set enumeration approach.

Definition 1. A mixed attacking strategy a with support set T ′ is called unbiased if at = λT ′/(Rd t -P d t ) for all t ∈ T ′ and at = 0 otherwise, where λT ′ = 1/ ∑t∈T ′ 1 Rd t -P d t . The attacker's policy πa is unbiased if the mixed attack strategy πa(s) is unbiased for each s ∈ Θ.

There exists one and only one mixed attacking strategy with support set T ′ , which is unbiased, for any T ′ ⊆ T. Therefore, we denote such strategy with support set T ′ as aT ′ . The unbiased attacking strategy is not trivial. In fact, it follows the spirit of NE to make the defender strategy the best response. In particular, the defender's expected payoff against aT ′ is:

For defender of type θ, c is the best response against aT ′ if and only if: ∑t∈T ′ ct = min{θ, |T ′ |}, and the corresponding defender's optimal expected payoff is denoted as:

Support Set Enumeration: Let T denote the set of all subsets of T. The intuition of support set enumeration is as follows. Suppose there exists a PBE profile where the attacker strategy is unbiased. To compute such a PBE, a na¨ıve way is to consider all possible unbiased attacker policies, which is of size |T ||Θ| as there are |Θ| information sets. For each unbiased attacker's policy πa, let T ′s ∈ T be the support set of πa(s). We can easily verify whether there exists a PBE where the attacker's policy is πa with linear constraints, since the defender's best response can be easily ensured by:

However, the size of T is exponential (2|T| ), which makes it impossible to generate all possible unbiased attacker policies. Fortunately, we do not necessarily need to generate all of them due to a nice property of the PBE 〈πd, πa〉 such that there are only limited subsets of T able to serve as the support set of πa(s) no matter if πa(s) is unbiased or not (Lemma 1 & Theorem 4). Thus, we only consider a small subset T ′ ⊂ T , and the property of PBE ensures that T ′ is enough to search for a PBE with unbiased attacker strategy. (We will discuss how to generate T ′ later.) As such, instead of brute force search, an MILP with no objective function is provided:

In (3), S is the decision variable corresponding with πo such that Sθs = πo(s|θ); ˜ C is the decision variable defined as follows: ˜ Cθst = πo(s|θ)πc(t|θ, s) if I(s) is on the equilibrium path, otherwise ˜ Csst = πc(t|s, s) and ˜ Cθst = 0 for any θ > s; Binary variable χs = 1 if and only if I(s) is on the equilibrium path; δ in (3f) is a small enough constant as the threshold of probability of sending s, while M is a large enough constant; xst is the slack variable which takes zero when target t is in the support set of πa(s); Variable vd θ denotes Ud(πo(θ), πc(θ), πa); yθs is the slack variable which takes zero when s is in the support set of πo(θ); Binary variable φsT ′ = 1 iff T ′ is the support set of πa(s). (3i) and (3j) correspond to the attacker's best response criteria, including the optimistic conjecture, such that at information set I(s), the expected utility of attacking a target in the support set of πa(s) is the highest among all targets. (3k) ensures that πc(θ, s) is the best response coverage against πa(s) as required by (2). In particular, given the support set of πa(s) being T ′ , we have πc(t|θ, s) = 0 for t /∈ T ′ . 2 Finally, (3l)-(3m) ensure that the defender is playing the best response signaling strategy such that πo(s|θ) > 0 only if Pd(πc(θ, s), πa(s)) ≥ Pd(πc(θ, s′ ), πa(s′ )) for any s′ ≤ θ.

The MILP (3) returns a PBE if and only if there exists one with unbiased attacker's policy πa whose support sets are in T ′ . If no such PBE exists, we slightly modify MILP (3) to compute the ϵ-PBE instead, with the MILP (4), which is the same as MILP (3) except: i) the expected utility of attacking target t in support set of πa(s) is no lower than the best response minus ϵ; and ii) πo(s|θ) > 0 only if Pd(πc(θ, s), πa(s)) ≥ Pd(πc(θ, s′ ), πa(s′ )) - ϵ for any s′ ≤ θ. The feasible solution of MILP (4) is ensured to be an ϵ-PBE. Notice that ϵ in MILP (4) is a constant number instead of a variable since otherwise the formulation becomes non-convex. Thus, to get the best approximation, the binary search on ϵ is conducted.

Generating Support Sets: List the targets by Ra t in descending order: T = {t1, .., t|T|}. Our next Lemma shows that the support set T ′ of πa(s) in PBE must contain the first |T ′ | targets in T. 2 The intuition is that the defender will always cover the targets in T ′ with the highest priority, otherwise the attacker's best response is violated.

Lemma 1. In PBE, the support set of the mixed attack strategy πa(s) at any I(s) has the form: T ′ = {t1, .., t|T ′ |}.

Proof. It is sufficient to prove that if t ∈ T ′ , then any target with higher reward is also in the support set. We prove by contradiction. Suppose there exists a target t′ with Ra t′ > Ra t which is not in the support set T ′ . One reasonable assumption adopted here (and throughout the paper) is that in PBE, there exists no defender type which fully covers every target in the support set of the mixed attacking strategy. Thus, we have:

since otherwise the defender type θ can always decrease coverage πc(t′ |θ, s) and increase coverage πc(t|θ, s) to improve the expected utility, which contradicts to the best response criteria. Let Ua(πd, s, t) denote the attacker's expected utility of attacking target t at information set I(s):

According to Eqs.(5) & (6), we have:

Contradict to that t is attacker's best response target.

2 We assume that in PBE, there exists no defender type which fully covers every target in the support set of mixed attacking strategy which is reasonable for realistic payoffs.

Although Lemma 1 already restricts the number of support sets to |T |, we can further eliminate some of them with Theorem 4. The intuition of Theorem 4 is that a defender with more resources can cover more targets while keeping them all the best response targets for the attacker, and k and K are the minimal and maximal numbers of such targets respectively. Therefore, the size of support set of πa(s) against defender of unknown type is within interval [k,K]. Notice that when θmin ≈ θmax, we have: |T ′ | = |K -k +1| ≪ |T|.

Theorem 4. Let k and K be the smallest and the largest values respectively of i such that there exists a type θ satisfying ∑it=1 Ra t -Ra ti Ra t -P a t ≤ θ ≤ ∑it=1 Ra t -Ra ti+1 Ra t -P a t . In PBE, the support set T ′ of πa(s) at any I(s) satisfies: k ≤ |T ′ | ≤ K.

Proof. Obviously, k corresponds to the smallest i such that:

while K corresponds to the largest i such that:

Similar to the proof of Theorem 3, there exists a coverage vector c for type θmin which only covers {t1, .., tk} and makes all of {t1, .., tk} the best response targets for the attacker; Also, there exists a coverage vector c′ for type θmax which only covers {t1, .., tK} and makes all of {t1, .., tK} the best response targets for the attacker.

We prove by contradiction with the above consequences. Suppose there exists a support set T ′ of πa(s) such that |T ′ | < k, according to Lemma 1, we have: T ′ = {t1, .., t|T ′ |}. Let tl be an arbitrary target in T ′ . Since {t1, .., tl, .., tk} are all best response targets for the attacker against c of θmin:

In PBE, since πc(θ, s) is the best response against πa(s) with support T ′ , where tk /∈ T ′ , we have:

given the assumption that in PBE, there exists no defender type which fully covers the targets in the support set of the mixed attacking strategy.

According to Eq.(6), in PBE, the attacker's expected utilities of attacking tl and tk are:

Since tl ∈ T ′ and tk /∈ T ′ , Ua(πd, s, tl) ≥ Ua(πd, s, tk). According to Eq.(7) and ∑θ∈Θ:θ≥s µ(θ|s) = 1, we have:

Sum it up over l ∈ {1, .., |T ′ |}, we get:

which contradicts to the following fact:

Thus, |T ′ | ≥ k.

Now assume |T ′ | > K. Notice that {t1, .., tK} are the set of best response targets against coverage c′ of type θmax. Let l be an arbitrary index in {1, ..,K}. We have:

since c′t|T′| = 0. In PBE, both targets tl and t|T ′ | are in the support set of πa(s). According to Eq.(8), we have:

Since ∑θ∈Θ:θ≥s µ(θ|s) = 1, we get:

Sum up over all 1 ∈ {1, .., K}, we have:

However, it contradicts the following fact when s = θmin:

7 Experimental Evaluation

We performed experiments to evaluate our algorithms, and to gather empirical data on how PBE compares generally to SSE. We use CPLEX for all optimizations on a 64-bit PC with 16 GB RAM and a quad-core 3.4 GHz processor. All values are averaged over 1000 instances expect for the runtime averaged over 100 instances. The game instances are generated as follows unless otherwise specified: each type θ is randomly drawn from {⌊0.1|T |⌋, ⌊0.1|T |⌋ + 1, .., ⌊0.4|T |⌋}. The probability distribution over Θ is randomly generated. The attacker's payoffs Ra t andP a t are randomly drawn from the intervals [1, 10] and [-10,-1] respectively. The defender's payoffs are generated as follows: Rd t = ω(-P a t ) + (1 - ω) ˜ Rd and P d t = ω(-Ra t ) + (1 -ω) ˜ P d , where ˜ Rd and ˜ P d are randomly drawn from same intervals as Ra t and P a t respectively. The parameter ω controls correlation between the defender and attacker payoffs, such that when ω = 1, the game is zero-sum, and there is no correlation when ω = 0. The 95% confidence intervals are drawn in all figures which show that all the results are statistically significant.

Scalability & Solution Quality: We test the runtime of our approach on DSG instances with varying numbers of types |Θ| ∈ {2, 4, 6, 8} and ω ∈ {0, 1}. The results are shown in Figs 2(a)-2(b), which shows that our approach can scale to realistic-sized instances with over 100 targets within minutes for for all categories of games. We also test the solution quality of our approach on randomly generated games with |T| ∈ {40, 60, 80, 100} and |Θ| ∈ {4, 6}. Pr(PBE) denotes the proportion of instances where a PBE is computed. ϵmax is the maximum value of ϵ among returned ϵ-PBEs. |T ′ | represents the average number of generated support sets per instance. The results for ω = 0 and 1 are given in Tables 2(c) and 2(d) respectively, from which we can see that the PBE is computed for over 99% of all tested instances. Even when the PBE is not returned, ϵmax is significantly small compared with payoffs, showing that our approach can compute solutions with very good quality. We also note that |T ′ | is much smaller than the number of targets, which empirically supports Theorem 4 to reduce the candidate support sets.

PBE vs. SSE & NE: We now compare the defender utility of PBE with SSE and NE. We test on random game instances with 20 targets, 8 types Θ = {θ1 = 1, .., θ8 = 8}, and varying value of ω ∈ {0.8, 0.85, 0.9, 0.95, 1.0}. In reality, different types may be of different importance for the defender. For example, a conservative defender may care more about the utility in the worst case with minimal resources. As such, we list the differences between defender utilities of each individual type in PBE and SSE in Figure 2(e). We also depict the expected defender utilities of PBE, SSE and NE in Figure 2(f). We observe that: i) with increasing ω, the defender benefits more in PBE compared to SSE, and the benefit of strategic secrecy is not limited to zero-sum games, which supports our formal analysis; ii) for the expected utility, the boundary of tradeoffs between strategic secrecy and commitment is within [0.9, 0.95], close to zero-sum games; iii) PBE significantly outperforms NE regardless of the value of ω, supporting the motivation of strategic information revelation; and iv) the benefit of PBE shows a quadratic relationship with the defender types. An intuitive explanation would be that the attacker is playing the best response against the defender of unknown type which can be treated as an "average" type ¯ θ. Therefore, the type θ closer to ¯ θ benefits less from secrecy. Zero-sum games capture the nature of security issues where the attacker's success indicates the failure of the defender, and the zero-sum approximation is widely adopted in game theoretic analysis in various security domains [Chen, 2007; Durkota et al., 2015; Haskell et al., 2014; Jain et al., 2011; Major, 2002; Nguyen et al., 2009a; 2009b; Wang et al., 2016; Yin and An, 2016; Guo et al., 2016; Yin et al., 2016]. On the other hand, it is also emphasized that the zero-sum model is at best an approximation [Banks and Anderson, 2006]. One interpretation is that although both players are likely to agree on the importance of targets, the costs of conducting an attack or defending a target may be ignored by the opponent. Our results show that the boundary of PBE outperforming SSE is close to zero-sum (w ≈ 0.93) which, to an extent, explain the coexistence of strategic secrecy and commitment in practice.

Robustness: We analyse the robustness of PBE solution against two major uncertainties on random zero-sum game instances with 30 targets and 6 types. First, the defender and the attacker may have different valuations of targets. Let ˜R∗ t and ˜ P ∗ t (∗ represents a or d) denote the payoffs estimated by the attacker. We denote by δ the degree of uncertainty such that ˜R∗ t ∼ R∗ t · [1-δ, 1+δ], ˜ P a t = -˜Rd t and ˜ P d t = -˜Ra t . Let ˜πa and πd be policies for attacker and defender correspondingly computed with their own estimations. We compare Ud(πd, ˜πa) with Ud(π∗ d , ˜πa) where π∗ d is the best response against ˜πa w.r.t. defender's estimation of payoffs. Second, we consider the attacker's bounded rationality, such that with a small probability δ, the attacker randomly chooses one target to attack. The metric for robustness analysis remains the same. The results are depicted in Figures 2(g) & 2(h), which show that the PBE solution is robust enough even with a high degree of uncertainty (20%), which makes it a practical alternative for the defender and also shows that our analysis and explanation of strategic secrecy based on PBE is reasonable.

8 Conclusions

1 1 We study a longstanding dilemma in security games: given the theoretical advantages of commitment, why is it that realworld security forces often use secrecy? By introducing the possibility that the defender has valuable private information, we show that there is a fundamental tradeoff between secrecy and commitment. We provide a generalization of security games to capture this, a novel scalable algorithm for computing PBE solutions for these games, and empirical results that demonstrate the effectiveness of our algorithms as well as providing a deeper understanding of the competing advantages of secrecy and commitment. Our theoretical and empirical results show that the boundary of such tradeoffs between secrecy and commitment is close to zero-sum, which is the case for most security domains. We conclude that both secrecy and commitment have a vital role in security policy.

Acknowledgements

This research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its IDM Futures Funding Initiative, NRF2015 NCR-NCR003-004, the National Science Foundation (NSF) under Grant No. IIS1253950, and the Czech Science Foundation (grant no. 1523235S).