An Ambiguity Aversion Framework of Security Games under Ambiguities

1 Introduction

Nowadays, protecting people and critical assets against potential attacks has become a critical problem for public security around the world [Tambe, 2011]. It is impossible to provide surveillance on all the targets of security. Thus, it is an increasing concern about how to allocate security resources. Essentially, addressing this concern requires a strategy of allocating security sources (e.g., security team or defender) based on the understanding of how terrorists (the attacker) usually plan and act according to their knowledge of security capabilities. In the literature, most of the existing work deals with this problem in Stackelberg's game framework (a specific kind of game in game theory) [Pita et al., 2009; Tambe, 2011]. That is, a defender commits to a strategy first and an attacker makes his decision based on the defender's commitment. The typical solution concept in these games is Strong Stackelberg Equilibrium (SSE), which concentrates on determining the defender's optimal mixed strategy based on two assumptions: (i) the attacker knows this strategy and responds optimally; and (ii) both players have point-valued payoffs for each pure strategy profile (a complete list of pure strategies, one for each player in the game).

However, in real life, a human attacker usually acts on partial information of a defender's strategies and the attacker's rationality is bounded [Tambe, 2011; Yang et al., 2012]. Moreover, Korzhyk et al. [2011] suggests that the Nash Equilibrium (NE) strategy should be applied instead of SSE when a defender is unclear about an attacker's knowledge of surveillance. Furthermore, the assumption of point-valued payoffs is also unrealistic because the payoff of each pure strategy profile, which is based on experts analysis, historical data, and airport managers' judgements, is often ambiguous because of time pressure, lack of data, random events, reliability of information sources, and so on. In particular, the payoff of a pure strategy profile often has to face two types of ambiguity: (i) the value of a payoff is ambiguous: (a) absent, (b) interval-valued, and (c) of multiple possibilities; (ii) the strategy profile that relates to a given payoff is ambiguous.

Let us consider a scenario in an airport area, which covers the following five targets: Shopping Area (SA), Prayer Room (PR), Special Location (SL), VIP Lounges (VL), and Hotel (H). Now an airport manager tries to assign a security team to cover one of these five targets, and an attacker will choose one to assault. So, there are two consequences for the interaction: the security team succeeds in protecting a target or the attacker succeeds in assaulting a target. And the payoffs of an interaction for the defender might be ambiguous. (i) The value of payoff is ambiguous: (a) absent: because the special location in an airport is unique, it is hard to estimate the value, such as the Butterfly Garden in Singapore Changi Airport; (b) interval-valued: the payoff of protecting a shopping area mainly depends on the amounts of customers, which is indeterministic in a period; and (c) ambiguity lottery: for instance, the prayer room, after knowing that the assessment expert is a religionist, the airport manager would not completely trust the expert's suggestion, e.g., a reliability of 80%. Thus, the manager is uncertain about the payoff of Prayer Room with 20%. (ii) The pure strategy profile that relates to a given payoff is ambiguous: suppose the more people a location may have, the higher the payoff. Since the hotel usually is close to the VIP lounge, it may be easier to estimate roughly a combined total number of people in both places, but it is difficult to estimate a total number of people in each place. So, sometimes the manager does not know the payoff of these two targets separately. Given these two types of ambiguity, our task in this paper is to determine the defender's optimal strategy.

More specifically, based on Dempster-Shafer (D-S) theory

[Shafer, 1976], we first use the ambiguity aversion principle of minimax regret [Ma et al., 2013] to obtain the preference degree of a given player for the subsets of pure strategy profiles. Then, we consider the distance of each subset of profiles' preference degree to the worst preference degree to set the relative payoffs of this player. Thus, according to whether some payoffs are absent, we introduce two methods to calculate mass values, which indicate the possibilities of a subset of pure strategy profiles containing the best outcome for the given player. Moreover, we deploy the idea behind the ambiguity aversion principle of minimax regret to obtain the player's belief degree of a belief interval for each pure strategy profile. Finally, from the belief degrees of each player, we can derive the defender's optimal strategy directly.

This paper advances the state of the art on the topic of security resources allocation in the following aspects. (i) We identify two types of ambiguity in security resources allocation: ambiguous payoffs and ambiguous strategy profile. (ii) We propose an ambiguity aversion framework to determine the optimal strategy for a defender in security games under ambiguities. (iii) Our framework can consider the correctness of point-value security game models under ambiguities. (iv) We show the relationship between the payoffs boundary and the risk attitude of a player in security games under ambiguities. And (v) we present two methods to reduce complete ignorance in security games under ambiguities.

The rest of this paper is organized as follows. Section 2 recaps D-S theory and relevant definitions. Section 3 formally defines security games under ambiguities. Section 4 develops an ambiguity aversion framework to handle security games under ambiguities. Sections 5 discusses some properties of our framework. Section 6 handles the influence of complete ignorance. Section 7 discusses the related work. Finally, Section 8 concludes the paper with future work.

2 Preliminaries

This section recaps a decision method based on D-S theory [Shafer, 1976], which extends the probability theory as follow.

Definition 1. Let Θ be a set of exhaustive and mutually exclusive elements, called a frame of discernment (or simply a frame). Function m : 2Θ → [0, 1] is a mass function if m(∅) =0 and ∑A⊆Θ m(A)=1. With respect to m, belief function (Bel) and plausibility function (Pl) are defined as follows:

The following is a normalized version of the generalized Hartley measure for nonspecificity [Dubois and Prade, 1985].

Definition 2. Let m be a mass function over a frame of discernment Θ and |A| be the cardinality of set A. Then the ambiguity degree of m, denoted as δ : m →[0, 1], is given by:

Hence, we can define an ambiguity decision problem, which is a 4-tuple (C, S, U, M ) as follow:

• C = {c1, . . . , cn} is the set of all choices, such as all possible actions;
• S = {s1, . . . , sm} is the set of consequences caused by these choices;
• F = {fc | c ∈ C, ∀s ∈ S, fc(s) ∈ ℜ}, i.e., the utility of consequence s ∈ S that is caused by selecting choice c ∈ C is fc(s) ∈ ℜ (a real number set);
• M = {mc | c ∈ C}, i.e., the decision maker's uncertainty about the utility that choice c could cause (due to multiple possible consequences) is represented by mass function mc over the frame of discernment Θ = {h1, . . . , hn}, where hi ∈ ℜ and for any fc(s), fc(s) ∈ Θ.

Thus, the point-valued expected utility function [Von Neumann and Morgenstern, 1944] can be extended to an expected utility interval [Strat, 1990]:

Definition 3. For choice c1 specified by mass function mc1 over Θ = {h1, ..., hn}, its expected utility interval is EU I (c1) = [E(c1), E(c1)], where

The following is a decision rule for expected utility intervals, i.e., the ambiguity aversion principle of minimax regret, which is presented in [Ma et al., 2013]:

Definition 4. Let m be a mass function over Θ = {h1, ..., hn}, EUI (x) = [E(x), E(x)] be the expected utility interval of choice x ∈ C, and δ(x) be the ambiguity degree of mx. Then the ambiguity-aversion maximum regret of choice ci against choice cj , denoted as ℜcj ci ∈ ℜ, is given by:

where ε(cj) = E(cj ) -δ(cj )(E(cj ) -E(cj)). And the strict preference ordering ≻ over these two choices ci and cj is defined as follow:

This ordering states that choice ci is strictly preferred than cj, if the ambiguity-aversion maximum regret of ci is smaller than that of cj. Also, it is easy to prove that E(c) ≤ ε(c) ≤ E(c), and ε(c) means that for the reason of ambiguity aversion, the decision maker will reduce his upper expected utility (but still not lower than E(c)) for a given choice based on the ambiguity degree δ of mc.

Moreover, we can prove easily that with the binary relation ∼ (i.e., x ∼ y if x ̸≻ y and y ̸≻ x), we can compare any two choices properly. Finally, in game theory, the problem of selecting the optimal strategy for a given player with respect to the strategies selected by other players can be considered as a decision problem for selecting the best choice under the condition that the strategies (choices) of other players are given. So, when the payoff functions in game theory are represented by mass functions, we can find the optimal strategy by Definitions 3 and 4.

3 Security Games under Ambiguities

This section defines security games under ambiguities. 1

Based on the airport scenario in Section 1, we can construct a payoff matrix of a security game as shown in Table 1, in which the defender is the row player and the attacker is the column player. Moreover, their payoffs are listed in the cells as "a; b", where a for the defender's payoff and b for the attacker's. Consider the second row in Table 1. When the pure strategy profile is (PR, SA), 2 which means the defender fails to protect SA, the payoff of the defender is negative (e.g., [-7,-3]) and that of the attacker is positive (e.g., 5). Since the evaluation of the shopping area is inaccurate for the defender, an interval value is used for his payoffs (e.g., [-7,-3]). Similarly, when the profile is (PR, PR), the defender succeeded in protecting the prayer room. As the evaluation of the prayer room is based on an expert's suggestion, m(c) = 0.8 means the reliability for the expert's evaluation c is 80% and m(d) = 0.2 means the expert's suggestion is unreliable for the defender with 20%. Moreover, when the profile is (PR, SL), null means that the defender is completely unknown for the value he might lose if he fails to protect the special location. Finally, the defender cannot distinguish the payoffs of (PR, VL) and (PR, H), but just knows that the payoff of these two compound strategy profiles is -8. Formally, we have:

Definition 5. A security game under ambiguities, denoted as G, is a 6-tuple of (N,A, Ψ, Θ, M, U ), where:

• N = {1, 2} is the set of players, where 1 stands for the defender and 2 stands for the attacker.
• A = {Ai | i = 1, 2}, where Ai is the finite set of all pure strategies of player i. 3
• Ψ = {(ak, bl) | ak ∈ A1 ∧bl ∈ A2} is the set of all pure strategy profiles.
• Θ={Θi | Θi=Θ+i ∪Θ-i , i = 1, 2}, where Θ+i is a finite positive number set and Θ-i is a finite negative number set.
• M = {mi,X | i = 1, 2, X ⊆ Ψ}, where mi,X is the mass function over a frame of discernment Θ+i or Θ-i .
• U = {ui(X) | i = 1, 2, X ⊆ Ψ}, where ui(X) is the payoff function ui : 2Ψ →M.

Moreover, for any X ⊆ Ψ ∧ |X| > 1, if ∃ui(Y )Y⊂X ∧ mi,Y (B) > 0 ∧B ⊂ Θ+i or B ⊂ Θ-i , then mi,X(Θ-i ) = 1.

1 In this paper, we only consider simple security games that face one type of attacker in order to discover more intrinsic characteristics of security games under ambiguities.

2 The defender's strategy is PR (covering the Prayer Room) and the attacker's strategy is SA (attacking the Shopping Area).

3 Assigning a security team covering a specific place can be regards as a pure strategy in the security game.

Table 1: Airport security game

Here a={-8, -7}, b={-9, . . . , 0}, c={5, 6}, d={0, . . . , 9}.

The same as traditional game theory, for each player his mixed strategy set is denoted as Δi, in which a probability is assigned to each of his pure strategy. By this definition, we can distinguish two types of ambiguity in security games. (i) The value of a payoff is ambiguous: (a) absent: for ui(X), we have |X| = 1 ∧ ∀ui(Y )X⊆Y , mi,Y (Θ+i )=1 or mi,Y (Θ-i )= 1; (b) interval value: for ui(X), we have mi,X(B)=1, where B = {hi, . . . , hj} ∧ B ⊂ Θ; and (c) ambiguity lottery: for ui(X), ∃B ⊂ Θi such that mi,X(B) > 0 ∧ |B| > 1. And (ii) the pure strategy profile that relates to a given payoff is ambiguous: for ui(X), we have |X| > 1 ∧ mi,X(Θ-i ) ̸= 1. Moreover, the value of payoff is not ambiguous if the payoff is: (i) a point value: for ui(X), we have m({B})=1, where B⊆Θi∧|B| =1; or (ii) risk: for ui(X), if m(B) > 0, then B ⊆Θi∧|B| = 1. Finally, the profile that relates to a given payoff is not ambiguous if for ui(X), we have |X|=1.

Clearly, for any ui(X), X ⊆ Ψ and |X| = 1, if we have hi ∈ Θi and m({hi}) = 1, then the payoff of each pure strategy profile is a point value, which means that the security game under ambiguities is reduced to a traditional security game. Moreover, the definition assumes that there are imprecise probabilities [Shafer, 1976] for the payoffs of the subsets of profiles. This is consistent with our intuition that the possible payoff values in a given security game are often finite and discrete. For example, if the payoffs are actually money, then the number of payoffs is finite and their differences will not be less than 0.01. Hence, in order to consider the payoffs of compound profiles, the payoff function is defined on the set of all pure strategy profiles subsets. Finally, the last sentence in Definition 5 means the possible subsets of strategy profiles that do not appear in the payoff matrix of a game (e.g., Table 1) have no influence on the outcome of this game.

Finally, we take the second row in Table 1 about the airport scenario in Section 1 as an example to discuss some insights of these two types of ambiguity. (i) The value of a payoff is ambiguous. (a) An absent payoff means there are no appropriate values to represent a situation, i.e., he only knows the result of the pure strategy profile is successful or not. Thus, we can distinguish two types of absent payoff: positive absent payoff (m({Θ+i }) = 1) and negative absent payoff (m({Θ-i }) = 1). In Table 1, when the profile is (PR, SL), it satisfies this situation and m1,{(PR,SL)} ({Θ-i }) = 1. (b) For interval-valued payoffs, the complete ignorance of player i for the interval-valued payoff [xs, xt] of the payoff function ui(X) can be represented by mi,X({xs, . . . , xt}) = 1.

It means that player i only knows that the payoff that he can gain could be any value in-between xs and xt, but cannot be sure which value it is. Then, by Equations (4) and (5), we can obtain the corresponding expected payoff interval as follow:

That is, the expected payoff interval is the same as the interval-valued payoff itself. Thus, in Table 1, when the pure strategy profile is (PR, SA), it satisfies this situation and m1,{(PR,SA)} ({-7, . . . ,-3}) = 1. (c) Ambiguity lottery means that multiple discrete situations are possible with (a generalization of) the probability of each situation being known. In Table 1, when the profile is (PR, PR), it satisfies this situation. And (ii) the pure strategy profile that relates to a given payoff is ambiguous: it means some strategies of players are closely related and so the combined value is applied in this situation. In Table 1, profiles (PR, VL) and (PR, H) satisfy this situation and m1,{(PR,VL),(PR,H)} ({-8}) = 1. Thus, we can represent the payoff matrix in Table 1 by mass functions as shown in Table 2 without changing its meaning.

4 Ambiguity Aversion Framework

This section discusses how to handle a security game under ambiguities. To handle such a game, we first transform all the five types of payoff values (i.e., absent, interval-valued, ambiguity lottery, point-valued, and risk) into point values for all subsets of pure strategy profiles. Then, we handle the payoffs of compound strategy profiles by finding the point value for each pure strategy profile. Finally, the defender's optimal strategy can be obtained by well established methods (e.g., [Pita et al., 2009; Tambe, 2011; Yang et al., 2012]).

The basic assumptions of our framework are as follow:

• A1: Each player i will consider the relative expected payoff of the subsets of profiles.
• A2: Each player will maximize his expected payoffs relative to his subjective priorities.
• A3: The worst expected outcome of negative absent payoff is worse than any other types of payoffs.

Intuitively, A1 means that if a player believes he will not obtain the expected payoff that is lower than the worst payoff in the game, he only needs to consider how well the given strategy performs compared with the worst one. A2 is a rational player assumption. A3 means that for the reason of caution, the players think that there exists a chance that the negative absent payoff turns out to be the worst outcome in the game.

As a consequence of these assumptions, we can deploy the ambiguity aversion method, as shown in Figure 1, to obtain the point value for all pure strategy profiles as follow.

(i) Calculate the expected payoff intervals and ambiguity degree of Xr for a given player i.

As we can represent all types of payoffs by mass functions in security games under ambiguities, we can calculate the expected payoff intervals for the defender by Equations (4) and (5), and the ambiguity degree by Equation (3) directly.

(ii) Obtain preference degree νi(Xr) for player i.

Definition 6. Let EUIi(Xr) = [Ei (Xr),Ei(Xr)] be an interval-valued expected payoff of profile subset Xr for player i, and δi(Xr) be the ambiguity degree of mi,Xr , then the preference degree of Xr is given by:

2

Actually, since the preference degree of νi(Xr) is a kind of pointed value expected utility, it is reasonable to assume that νi(Xr) ∈ [Ei (Xr),Ei(Xr)]. Thus, with this assumption, it is easy to prove that Definition 6 is a unique one that satisfies the properties in Definition 4. Moreover, Ma et al. [2013] proved that the preference ordering induced by this definition is equivalent to that in Definition 4.

In the security game as shown in Table 1, suppose Θ1 = {-9, -8, . . . , 0, 1, . . . , 9}. According to Definition 5, we can express all types of ambiguities in Table 1 by mass functions. Thus, by Equation (9), the defender's preference degrees can be obtained as shown in Table 3. 4

4 Here we consider the payoff value of the defender first. Later

(iii) Determine player i's relative payoff di(Xr) between the given preference degree and the worst one in a game.

First, the worst preference degree can be defined as follow:

Definition 7. For a security game under ambiguities, a preference degree is the worst preference degree, denoted as ν w i (Xk) (w means the worst one), of player i if and only if

Thus, we can formally define the relative payoff as follow:

Definition 8. Let ν w i (Xk) be the worst preference degree of player i, then the relative payoff, denoted as di(Xr), for the subset of pure strategy profiles Xr is:

Clearly, we have di(Xr) ≥ 0. The motivation of this step is to transform all the payoff values into positive numbers in order to obtain the mass values in the next step. For the airport security game in Table 1, by Equation (10), we can obtain the defender's point-valued relative payoffs as shown in Table 4.

(iv) Derive the mass function from di(Xr) for player i.

Since a belief interval can be used to express the belief degree and uncertainty of each pure strategy profile for a given player, we need a method to assign a mass value to each subset of pure strategy profiles. In fact, the mass value based on di(Xr) represents the possibility that a subset of pure strategy profiles contains the most favorable outcome that player i would like to have. Thus, we present the following two theorems (which are the variants of the comparison rules in [Ma et al., 2012], and so we omit their similar proofs here for the sake of space):

Theorem 1. For a given security game with absent payoffs, let Xr ⊂ Ψ be one of n elements such that di(Xr) ̸= 0 with relative payoff aj, then the mass function over Ψ of profiles subset Xr for player i is:

Moreover, the uncertainty for the whole game for player i is

on we will discuss the attacker's .

Theorem 2. For a given security game without any absent payoff, let Xr ⊂ Ψ be one of n elements such that di(Xr) ̸= 0 with relative payoff aj, then the mass function over Ψ of profiles subset Xr for player i is:

Intuitively, in a game without absent payoffs, there is some evidence for all the payoff evaluations. So, the value of the worst preference degree is based on some evidence. However, for an absent payoff where a player has absolutely no idea about the value, it means that the result of the worst preference degree is completely obtained by the subjective judgement about the boundary of the payoff values. So, the player has some kind of uncertainty about the result of the absent payoff (whether it turns out to be worse than the lower bound of the values). Hence, the player has to express his uncertainty in this situation to depict his preference of the strategies. So, we deploy Theorems 1 and 2 to derive the mass function.

For the airport security game in Table 1, by Theorems 1 and 2, we can obtain the mass function for the defender in Table 5 from the relative payoffs as shown in Table 4.

(v) Obtain the belief interval by Definition 1 for player i.

For the airport security game in Table 1, we can obtain the belief interval for the defender as shown in Table 6 by Definition 1 from the mass function shown in Table 5.

(vi) Obtain the point-valued belief degree based on the belief interval for player i.

Definition 9. Let mi(Xr) be the mass value of the profiles subset Xr for player i and mi(Ψ) be the mass value of Ψ, which both induce belief function Beli(y) and plausibility function Pli(y) over Ψ. Let δi(y) be the ambiguity degree of the belief interval (y = {(aj, a-j)} ⊂ Xt), then its pointvalued belief degree is given by

where

(vii) Construct the point-valued belief degree of player i's adversaries by repeating steps (i) to (vi).

For the airport security game in Table 1, repeat steps (i) to (vi) for the attacker. Then by Definition 9 and the belief interval for the defender shown in Table 6, we can obtain the traditional security game as shown in Table 7. 5

(viii) Use some well established methods in security games to determine the optimal mixed strategy of the defender.

For the airport security game in Table 1, by Table 7 and the idea in [Korzhyk et al., 2011], we can obtain the optimal mixed strategy of the defender is ( 5 13 /SA, 4 13 /PR, 4 13 /SL).

5 Properties

This section reveals two properties of our framework. One is about the correctness of point-value game models under ambiguities and the other is about the risk attitude of the defender.

As we pointed out in Section 1, most existing researches of security games assume that all players have point-valued payoffs for each pure strategy profile. However, in real-life security allocation problems, since the experts or data analysts have to estimate a complex security system that involves a large number of uncontrollable and unpredictable factors, it is very reasonable to assume that there exist some deviations for the point-valued estimations of payoffs. So, the manager will ask the question: under which condition, the defender's optimal strategy obtained from the point-valued payoffs is the same if the estimation has a range of deviation? Since the defender's optimal strategy is determined by the set of SSE or NE, we can answer this question by the following theorem:

Theorem 3. Let asl be the payoffs of each pure strategy profile sl in a traditional security game G = (N, A, Ψ, Θ, M, U ) for player i, [bsl , csl ] (bsl ·csl > 0∧asl ∈ [bsl , csl ]) be the interval payoffs of each profile in G′ = (N, A, Ψ, Θ′ , M ′ , U ′ ), if for any two payoffs ask , asr in G, we have ask - bsk = asr - bsr , csk - bsk = csr -bsr , and |Θ′+|=|Θ′-|, then these two games G and G′ have the same set of SSE (and NE).

Proof. As we use the belief degree in Definition 9 to determine the optimal strategy for the defender in our framework, according to [Weibull, 1996] and the concept of SSE [Korzhyk et al., 2011], we only need to prove that asl and the belief degree, ηi(sl), of [bsl , csl ] satisfy an equation ηi(sl) = kasl + l, where k > 0 ∧ k, l ∈ ℜ (ℜ is a set of real numbers). It can be easily proved in our framework. So, games G and G′ have the same set of NE and SSE.

5 Due to page limit, we do not present each step of the attacker's payoffs value in this paper.

Now, we turn to the second property about the player's risk attitude. Actually, the preference degree in Definition 6 can be presented by νi(Xr) = αEi (Xr)+(1 -α)Ei(Xr), where α = (1+δi(Xr )) 2 . Similarly to Hurwicz's criterion [Jaffray and Jeleva, 2007], this definition ascribes a value, which is a weighted sum of its worst and best expected payoffs of the subset of pure strategy profiles Xr. Thus, α can be interpreted as a degree of pessimism. That is, a risk seeking (optimism) player will assign a lower value to α than a risk averse (pessimism) player for the same expected payoffs intervals. So, a risk seeking player will obtain a higher preference degree than a risk averse player for the same expected payoff intervals. Hence, by Definition 2, we find that the ambiguity degree is determined by mass function m and frame Θ. Furthermore, as the mass function will not change for a given set of pure strategy profiles and the boundary of Θ is based on the manger's subjective judgement, we can show that a player's risk attitude can be influenced by the boundary of Θ:

Theorem 4. Let m be a mass function on frame Θi = {h1, . . . , hn}, νi(X) be the preference degree that obtained from m, m′ be a mass function on Θ′i = {k1, . . . , km}. If Θ′i ⊃Θi and m′ (X)= m(X), X⊂Θi then ν ′ i (X) >νi(X).

Proof. Because m′ (X) = m(X), X⊂Θi, and Θ′i ⊃ Θi, by Definition 2, we have δ′i (Xr) < δi(Xr). Hence, by m′ (X) = m(X) and Equations (4) and (5), we have EUIi = EU I ′ i . Thus, by Equation (9), we have ν ′ i (X) > νi(X).

Intuitively, Theorem 4 means that for an expected payoff interval, the more risk seeking the defender is, the wider the range he will consider for the possible payoffs values of the whole game. For example, when considering value of the real estates, the manager may not worry too much about an error within a range of one thousand dollars for the price of a house, since one thousand is a very small value for a house. The defender will then be more risk seeking to determine the point value estimation for a house. However, when considering the daily revenue of shops, the manager might be more cautious to consider an error within the range of one thousand. So, this theoremmeans that the manager should not over-estimate the possible payoff values in a security game under ambiguities if he wants to be cautious when estimating the value of each pure strategy profile. Simply, the players' risk attitude will influence the point-valued belief degree and eventually the solution of a security game under ambiguities.

6 Reduce Influence of Complete Ignorance

In a security game, it is very important to reduce the effect of complete ignorance for the strategy profile selection. For example, in an airport, if the defender is unsure about the value of the security targets and chooses a wrong strategy for patrolling, then the attacker will take advantage and make a successful assault, which is unacceptable for public security. Moreover, in our framework, the complete ignorance for the strategy profile selection of player i is determined by mi(Ψ), where Ψ is the set of all pure strategy profiles. We now provide two methods to reduce the complete ignorance in a security game as shown in the following theorem:

Theorem 5. In security game G = (N, A, Ψ, Θ, M, U ), let di(Xr) be the relative payoffs of game G, mi(Ψ) be the uncertainty of the whole game (complete ignorance) that defined in Theorem 1. Then:

• (i) For game G′ = (N,A, Ψ, Θ, M ′ , U ′ ), if d′i (Xr) > di(Xr), and ∀di(Xs) = 0, d′i (Xs) = di(Xs), then m′i (Ψ) < mi(Ψ).
• (ii) For gameG′′ = (N, A∪B, Ψ∪Φ, Θ, M ∪M ′′ , U ∪U ′′ ), if G = (N,A, Ψ, Θ, M, U ), di(Xr) ∈ [t, 2t], where t > ∑ di(Xr) 2n , then m′′ i (Ψ∪Φ) < mi(Ψ).

Proof. We can prove (i) and (ii) together. By Theorem 1 and ∀di(Xs)=0, d′i (Xs) = di(Xs), we have

where aj is the value of the relative payoff di(Xr) such that aj > 0, a′j is the value of the relative payoff d′i (Xr) such that a′j > 0, and n is the number of element aj or a′j . Clearly, by d′i (Xr) >di(Xr), we have a′j > aj . Thus, item (i) holds.

Moreover, in G′′ , when the number of relative payoffs in Δ is 1, we have:

So, in this case, item (ii) holds. When the number of relative payoffs in Δ is k - 1, item (ii) also holds. Then, when the number of relative payoffs in Δ is k (assume the sum of k - 1 relative payoffs in Φ is b, the newly added one's relative payoff is c), we have ∑nj=1 aj + b + c < 2t(n + k - 1) + 2t because the relative payoffs in Φ belongs to [t, 2t]. Then:

So, when the number of relative payoffs in Δ is k, item (ii) holds as well. Therefore, item (ii) holds no matter how many relative payoff values in Φ.

Actually, Theorem 5 tells us that there are two methods for reducing the effects of complete ignorance for strategy selection in a security game under ambiguities: (i) to increase the importance degrees of some security targets (apparently, we cannot increase that of an absent payoff one); and (ii) to consider more security targets before selecting a strategy when the importance degrees of all security targets are not too high. These are consistent with our intuition. In fact, if the values of some security targets are high enough, then the defender will not hesitate to assign a random patrolling to cover those targets. On the other hand, if all security targets are not so important, the defender can consider more targets or make the absent payoff target more specific. For example, when the payoff of a shopping area is unknown, the defender can consider carefully that the payoff of which shop is unknown and how to evaluate other shops. In this way, he can reduce the effect of complete ignorance for his optimal strategy selection.

7 RelatedWork

Recently, there have been lots of interest in studying the games under ambiguity. Eichberger and Kelsey [2011] show that ambiguity preferences will cause players to pursue strategies with high payoffs of equilibrium and ambiguity-aversion can make the strategies with low payoffs of equilibrium less attractive. Similarly, Giuseppe and Maria [2012] investigate the difference among equilibria with respect to various attitudes toward ambiguity, and show that different types of contingent ambiguity will affect equilibrium behavior. And Bade [2011] proposes a game-theoretic framework that studies the effect of ambiguity aversion on equilibrium outcomes based on the relaxation of randomized strategies. However, none of these models provides a method to handle the two types of ambiguity, which our model did.

The problem of modeling uncertainty has become a key challenge in the realm of security. Kiekintveld et al. [2010] introduce an infinite Bayesian Stackelberg game method to model uncertain distribution of payoffs. Yang et al. [2012] consider the bounded rationality of human adversaries and use prospect theory [Kahneman and Tversky, 1979] and quantal response equilibrium to obtain the defender's optimal strategy. Korzhyk et al. [2011] consider the uncertainty of the attacker's surveillance capability and suggest that the defender should select the NE strategy in this situation. However, none of them has considered the ambiguities in security games. Instead, our paper has fully considered this issue.

8 Conclusions and FutureWork

This paper proposed an ambiguity aversion framework for security games under ambiguities. Moreover, we reveal two properties of our framework about the correctness of pointvalue security game models under ambiguities and player's risk attitude in our ambiguous games. In addition, we propose two methods to reduce the effects of complete ignorance in security games under ambiguities. There are many possible extensions to our work. Perhaps the most interesting one is the psychological experimental study of our ambiguity aversion framework. Another tempting avenue for evaluating our framework is to show that under ambiguity, selecting the defender's optimal strategy by our framework is better than a random point-valued game matrix. Hence, we can also consider the effect of regret and ambiguity aversion for constructing the equilibrium and selecting the defender's optimal strategy. Finally, We will consider the event reasoning framework developed in the CSIT project [Ma et al., 2009; 2010; Miller et al., 2010] as a testbed to fully evaluate the usefulness of our model.

Acknowledgments

We would like to thank anonymous reviewers for insightful comments which helped us significantly to improve this paper. This work has been supported by the EPSRC projects EP/G034303/1; EP/H049606/1 (the CSIT project); Bairen plan of Sun Yat-sen University; National Natural Science Foundation of China (No. 61173019); major projects of the Ministry of Education, China (No. 10JZD0006).