Equilibrium Analysis of Multi-Defender Security Games

1 Introduction

With terrorism and cyber threats ever on people's minds, developing and refining our understanding of both security threats and responses to these is both an important research area, and of great practical value. Game theory has come to play an important role in the security domain, with considerable modeling and algorithmic advances, as well as actual deployment of security systems in practice that are based on such models and algorithms, including LAX Airport [Jain et al., 2008; Pita et al., 2009], US Coast Guard [Shieh et al., 2012], and the Federal Air Marshals Service [Jain et al., 2010a; 2010b; Kiekintveld et al., 2009], among others.

A popular game theoretic model of security that has received much attention both in the research and in practice is as a Stackelberg game between a single defender and a single attacker, in which the defender commits to a randomized strategy, while the attacker, upon learning this strategy, chooses an optimal target or a subset of targets to attack [Conitzer and Sandholm, 2006]. In most of the associated literature, it is assumed that a single defender is responsible for all the targets that need protection, and that she has control over all of the security resources. However, there are many domains in which there are multiple defender agencies who are in charge of different subsets of all targets. While sometimes such agencies can be aligned to follow the same set of goals, in general different defender entities exhibit at least some disparities in goals. In particular, a defender is typically responsible (financially, politically, or legally) for targets in their direct charge, rather than other targets that may have social importance. This is certainly the case for the private sector, where different corporations secure their own resources without necessarily much concern for those of others, but is also common for the public sector, with different government agencies held accountable for their own assets, and not for those of others. In such non-cooperative security scenarios, the typical single-defender Stackelberg game model is clearly inadequate. Instead, we must consider the consequences of strategic interactions among multiple defenders, each charged with protecting their assets from common adversaries. An important consideration in such games is the negative externalities that security decisions impose on others: specifically, when a defender chooses a high level of security investment, budget-constrained attackers are more likely to choose others to attack. The resulting dynamics is likely to lead to over-investment in security, a phenomenon observed in several related efforts [Bachrach et al., 2013].

We consider a problem with multiple defenders protecting a collection of homogeneous targets. Each defender chooses a probability distribution over protection levels for all targets in their charge. A single attacker then best responds to the defenders' action by attacking the target with the lowest probability to be protected, breaking ties uniformly at random. Our analysis is focused on three models of such multidefender games, with defenders acting non-cooperatively in all of these. We show that a Nash equilibrium among defenders in this two-stage game model need not always exist, even when the defenders utilize randomized strategies (i.e., probability distributions over target protection levels); this is distinct from a model in which the attacker moves simultaneously with the defenders, where a mixed strategy equilibrium is guaranteed to exist. When an equilibrium does exist, we show that the defenders protect all of their targets with probability 1 in all three models, whereas the socially optimal protection levels are generally significantly lower. When no equilibrium exists, we characterize the best approximate Nash equilibrium (that is, one in which defenders have the least gain from deviation), showing that over-investment is substantial in this case as well. Our price of anarchy (PoA) analysis, which relies on the unique equilibrium when it exists, and the approximate equilibrium otherwise, demonstrates a surprising finding: whereas PoA is unbounded in the simpler models, increasing linearly with the number of defenders, the more general model shows this to be an atypical special case achieved when several parameters are exactly zero. More generally, PoA tends to a constant as the number of defenders increases.

RelatedWork Althoughmost work in Stackelbergmodels of security concerns computing a Stackelberg equilibrium in a single-defender single-attacker scenario, there are several exceptions. [Jiang et al., 2013] consider (mis)-coordination in cases where there are multiple defenders who are responsible for different sets of targets and share the common utility function over all targets. In this work, the defenders are fundamentally cooperative (sharing identical goals), however, making it distinct from our contribution. [Bachrach et al., 2013] examined non-cooperative security games among many defenders, in a two-stage model, but imposed strong assumptions on the model structure, and only considered onedimensional continuous "security investment" strategies for the defender (departing significantly from the typical structure of Stackelberg security games, in which defensive strategies are discrete protection choices). [Smith et al., 2014] extend the standard computational Stackelberg game framework to analyze games with multiple defenders, but offer no theoretical analysis. [Chan et al., 2012] propose interdependent defense (IDD) games, to study aspects of the interdependence of risk and security in a natural extension of interdependent security (IDS) games previous proposed by Heal and Kunreuther [Heal and Kunreuther, 2002] to consider attackers as explicit players in the game. In IDD games, unlike our setting, defenders and the attacker move simultaneously. To our knowledge, no previous work considers a theoretical analysis of multi-defender games with defenders protecting multiple targets, making previous literature on the subject qualitatively distinct from the typical practical considerations of single-defender settings, where resource allocation among multiple targets is a fundamental concern.

2 ModelingMulti-Defender Security Games

Our modeling effort proceeds in three steps, each generalizing the previous. As we see below, each generalization step reveals new and surprising insights about the multi-defender security setting, allowing us to appreciate the fundamental incentive forces.

2.1 The Baseline Model

We start with a model which most reflects the related literature: in particular, this model involves n defenders and a single attacker, with each defender engaged in protecting a single target. Each target has the same value to the defender v > 0. We suppose that the defender has two discrete choices: to protect the target, or not. In addition, the defender can randomly choose among these; our focus is on these coverage probabilities (i.e., the probability of protecting, or covering, the target), which we denote by si for a given defender i. The attacker is strategic and could observe the defenders' strategies to choose a target so as to maximize the damage. We assume that attacker is indifferent among the targets, and attacks the target with the lowest coverage probability, breaking ties uniformly at random. In a given scenario, for all defenders, the attacker's strategy is a vector of probabilities P =< p1, p2, ..., pn >, where pi is the probability of attacking a target i, with ∑ni=1 pi = 1.

We assume that if the attacker chooses to attack a target corresponding to defender i and defender i chooses to protect the target, then the utility of the defender i is 0, and if the attacker attacks the target but it is not protected, then the utility of the defender is -v. If a defender chooses to cover a target, it will incur a cost c > 0. Additionally, we assume that the defender gets a utility of zero whenever another defender's target is attacked. We can thus define the expected utility of a defender i as

where uai is the utility of i if it is attacked, and uui is the utility of i if it is not attacked. By the assumptions above,

2.2 The Multi-Target Model

Our key conceptual departure from related work is in allowing each defender to protect multiple targets, aligning it better with practical security domains. Specifically, suppose that there are n defenders, each protecting k ≥ 1 targets. Then the strategy of defender i will be a vector < si1, si2, ...sik >. The strategy profile of the attacker can then be described as a matrix of probabilities,

in which ∑ni=1 ∑kj=1 pij = 1 and pij ≥ 0 for each i and j. The expected utility of a defender i in this model is

where uaij is the utility of target j to defender i if it is attacked, and uuij is the utility of target j to i if it is not attacked. Using the notation introduced earlier, we have

2.3 The General Model

Finally, we analyze the most general version of the model considered. We assume that if the attacker chooses to attack a target i and the defender i chooses to protect the target, then the utility of the defender i is Uc, and if the attacker attacks the target but it is not protected, then the utility of the defender is Uu. It is reasonable to assume that Uc ≥ Uu. If the target of defender i is not attacked, then we assume that the utility of defender i is T ≥ Uc. Other assumptions are same as those in the multi-target model. In the general model, therefore,

2.4 Solution Concepts

We consider a class of solutions to multi-defender security games where the defenders' simultaneously commit to a probability distribution s over their pure strategies (corresponding to protection decisions for each target), and the attacker subsequently chooses an optimal target to attack, breaking ties uniformly at random. Since the attacker's behavior is straightforward (given s), we will focus on the simultaneous-move game among the defenders, and Nash equilibria thereof (giving rise to subgame perfect equilibria of the two-stage game of interest). As we demonstrate below, Nash equilibria are not guaranteed to exist, in which case we focus on ϵ-equilibria, in which no player gains more than ϵ by deviating; in particular, we will consider ϵ-equilibria with the smallest attainable ϵ. In fact, we could see Nash equilibrium as a special case of ϵ-equilibrium in which ϵ = 0.

To measure how the efficiency of the game degrades due to selfish behavior of its defenders, we consider Utilitarian Social Welfare and (ϵ)-Price of Anarchy in our paper. Utilitarian Social Welfare means the sum of all defenders' payoffs. For the smallest attainable ϵ, we define ϵ-Price of Anarchy (ϵ-PoA) as follows:

where SWO means the optimal (utilitarian) social welfare we can get from the game, SWE means the worst-case (utilitarian) social welfare in ϵ-equilibrium. An underlying assumption of this definition is that the value of SWO and SWE are both positive. If they are both negative, then ϵ-PoA will be the reciprocal of above equation. We should also note that the ordinary Price of Anarchy can be seen as a special case of ϵ-Price of Anarchy in which ϵ = 0.

3 The Baseline Model

Our first result presents necessary and sufficient conditions for the existence of a Nash equilibrium in the baseline model, and characterizes it when it does exist. We omit the proofs of Baseline Model (this section) and Multi-target Model (next section) due to space constraints, and they can be found in extended version of the paper on the website.

Theorem1. In the Baselinemodel, Nash equilibriumexists if and only if v ≥ c. In this equilibrium all targets are protected with probability 1.

Thus, if a Nash equilibrium does exist, it is unique, with all defenders always protecting their target. But what if the equilibrium does not exist? Next, we characterize the (unique) ϵ-equilibrium with the minimal ϵ that arises in such a case. We will use this approximate equilibrium strategy profile as a prediction of the defenders' strategies.

Theorem 2. In the Baseline model, if v < c, the optimal ϵ-equilibrium is for all defenders to cover their target with probability vc . The corresponding ϵ is v(c-v) cn .

Armed with a complete characterization of predictions of strategic behavior among the defenders, we can now consider how this behavior related to socially optimal protection decisions. Since the solutions are unique, there is no distinction between the notions of price of anarchy and price of stability; we term the ratio of socially optimal welfare to welfare in equilibrium as the price of anarchy for convenience.

First, we characterize the socially optimal outcome.

Theorem 3. In the Baseline model, the optimal social welfare SWO is

From this result, it is already clear that defenders systematically over-invest in security, except when values of the targets are quite high. This stems from the fact that the attacker creates a negative externality of protection: if a defender protects his target with higher probability than others, the attacker will have an incentive to attack another defender. In such a case, we can expect a "dynamic" adjustment process with defenders increasing their security investment well beyond what is socially optimal. To see just how much the defenders lose in the process, we now characterize the price of anarchy of our game.

If v ≥ c, it is one and only one Nash equilibrium when all defenders have the coverage probability 1 for their targets. And the corresponding social welfare is

Because it is the only Nash equilibrium, we could get the Price of Anarchy as follows:

Figure 1 shows the relationship among Price of Anarchy, number of defenders, and ratio of cost c and value v. From the figure we could find that when number of defenders and ratio of c and v are small enough (e.g. n ≤ 5 and cv = 0.2), the price of anarchy is close to 1. Otherwise, the price of anarchy is unbounded, growing linearly with n.

If v < c, there is no Nash equilibrium. However, we could get the optimal ϵ-equilibrium when all defenders have the same coverage probability vc for their targets. The corresponding Social Welfare is

Similarly, we could get the v(c-v) cn -Price of Anarchy as follows,

which is, again, linear in n.

4 The Multi-Target Model

Armed with observations from the model with a single target for each defender, we now extend the model to a case not as yet considered in the literature in a theoretical light: each defender protects a set of k targets. This gives rise to a combinatorial set of possible decisions for each defender, so that even computing a best response is not necessarily easy. Remarkably, we are able to characterize equilibria and approximate equilibria in this setting as well.

Our first result is almost a mirror-image of the corresponding result in the baseline model: when a Nash equilibrium exists, all defenders protect all of their targets with probability 1.

Theorem4. In theMulti-Target model, Nash equilibrium exists if and only if v ≥ kc. In this equilibrium all targets are protected with probability 1.

Next, we consider scenarios when v < kc, in which there is no Nash equilibrium. Our next result characterizes optimal (lowest-ϵ) approximate equilibria.

Theorem5. In theMulti-Target model, if v < kc, then in the optimal ϵ-equilibrium all targets are protected with probability v kc . The corresponding ϵ is v(kc-v) cnk .

Thus, as n increases, the optimal approximate equilibrium approaches a Nash equilibrium. Figure 2 illustrates the relationship between ϵ and the number of targets each defender protects when v = 10 and c = 1. In this figure, ϵ = 0 when k ≤ 10, which means that an exact Nash equilibrium exists; ϵ increases with k when k > 10, but at a decreasing rate, converging to vn when k →∞.

Finally, we characterize socially optimal welfare, and, subsequently, put everything together in describing the price of anarchy.

Theorem 6. In the Multi-Target model, the optimal social welfare SWO is

Thus, just as in the baseline case, the defenders will generally over-invest in security.

If v ≥ kc, there is a unique Nash equilibrium with all targets protected with probability 1. The corresponding social welfare is

Because it is the only Nash equilibrium, the Price of Anarchy is

If v < kc, there is no Nash equilibrium. However, we could get the optimal approximate equilibrium when all defenders have the same coverage probability v kc for their targets. The corresponding Social Welfare is

And the v(kc-v) cnk -Price of Anarchy is

Clearly, in either case, and just as in the baseline model, the price of anarchy is unbounded, growing linearly with n.

We now consider how PoA changes as a function of k, i.e. the number of targets each defender has. When k ≤ v cn , a Nash equilibrium exists and the PoA is 1; when v cn < k ≤ vc , PoA increases linearly in k with the slope nc v . However, when k > vc , a Nash equilibrium does not exist and the approximate PoA is n + 1 - v kc , which increases very slowly with k, and is bounded by n + 1 when k → ∞. Figure 3 illustrates the relationship between (approximate) Price of Anarchy and k for n = 2. When k is very small, PoA = 1. For intermediate k, PoA increases linearly, and when k is sufficiently large, Nash equilibrium no longer exists, and ϵ-PoA increases quite slowly, converging to 3 when k → ∞.

5 The General Model

Both the baseline and the multi-target models made rather strong assumptions about the structure of the utility functions of the players. In the general model, we relax these assumptions, allowing for arbitrary utilities for the players when the target is attacked or not, and when it is protected or not (when attacked). Quite surprisingly, our findings here are qualitatively different: the special case of the baseline and multitarget models turns out to be an exception, rather than the rule when more general models are considered.

Just as before, we start by characterizing Nash and approximate Nash equilibria.

Theorem7. In the General model, Nash equilibrium exists if and only if Uc -Uu ≥ kc- (n-1)(T-Uc) n . In this equilibrium all targets are protected with probability 1.

Proof. We firstly claim that Nash equilibrium can appear only if coverage probability of all of targets tij are identical. Otherwise, there will be a target tik which has the possibility of 0 to be attacked, and defender i has incentive to decrease sik. To find Nash equilibrium, we need only consider scenarios in which all targets have the same coverage probability.

When all targets have the same possibility s to be protected. Then for each defender, her expected utility is

If s < 1, then some defender i could slightly increase s to s + δ (δ is a very small positive real number) for all of her targets to make sure them not be attacked and get the value u′ = kT - k(s + δ)c,

As Uc ≥ Uu, T ≥ Uc, and δ can be very small, u′ - u > 0 when s < 1. We could know that the defender has incentive to improve s when s < 1. So the Nash equilibrium can appear only if sij = 1 for all defenders' targets sij . When all targets have the same possibility s = 1 to be covered, for each defender, her expected utility is

We claim that, if a defender i has incentive to deviate, the "optimal" deviation could appear only if defender i has the same protection probability s′ for all her targets. Otherwise, for some target tik which has the probability 0 to be attacked, she could always decrease s′ to get higher utility. If probabilities of targets protected by defender i are all s′ (0 ≤ s′ < 1), then her expected utility is u′ = (Uc - Uu - c)s′ + Uu + (k - 1)(T - s′ c), and

1. If Uc-Uu ≥ kc, then u′ -u ≤ 0, we could know that it is a Nash equilibrium when all targets have the probability 1 to be protected.
2. If Uc-Uu < kc, the maximal value of u′ -u corresponds to s′ = 0,

If kc - (n-1)(T-Uc) n ≤ Uc -Uu < kc, u′ -u ≤ 0, it is a Nash equilibrium; otherwise, it is not.

To sum up, Nash equilibrium exists if and only if Uc -Uu ≥ kc - (n-1)(T-Uc) n , and the equilibrium corresponds to all targets having probability 1 of being protected.

Next, we characterize the optimal approximate equilibrium when no Nash equilibrium exists.

Theorem 8. In the General model, in the optimal ϵequilibrium all targets are protected with probability T-Uu kc . The corresponding ϵ is (T-Uu)(kc-Uc+Uu) cnk .

Proof sketch. When all targets have the same probability s of being protected, the expected utility of each defender is

Assume 0 ≤ s < 1. If some defender i slightly increases s to s + δij for target tij, then she would obtain utility u′ = ∑kj=1 T - (s + δij )c,

Then we consider scenarios in which a defender i could get higher utility by decreasing protection probability. We claim that the "optimal" deviation could appear only if defender i has the same protection probability s′ for all of her targets. Otherwise, for some target tik which has the probability 0 to be attacked, she could always decrease coverage probability of tik to get higher utility.

Then we need only consider cases in which a defender deviates by decreasing probabilities of all her targets to s - δ. And her utility will be u′′ = (Uc - Uu - kc)(s - δ) + Uu + (k - 1)T , As Uc - Uu < kc, when δ = s (the maximal value of δ), we could get maximal value of u′′ - u,

By comparing the value of equation (1) and equation (2), we could get different value of ϵ for for ϵ-equilibrium as shown below:

When s = T-Uu kc , we could get the minimal ϵ = (T-Uu)(kc-Uc+Uu) cnk .

We claim that the (T-Uu)(kc-Uc+Uu) cnk -equilibrium can appear only if all targets have the same coverage probability s. We prove this by contradiction. Suppose that targets have different coverage probabilities. This gives rise to two cases: 1) Each defender uses an identical coverage probability for each target she owns (these may differ between defenders); 2) There exists a defender, who has a different probability to protect her own targets.

In case 1), there exist β defenders (1 ≤ β < n) who have the same minimal probability s′ to protect all of their targets. The expected utility for each defender among these β defenders is:

When T-Uu kc < s′ ≤ 1, some defender i among these β defenders could decrease probability of all her targets to 0 to get value u1 = Uu + (k - 1)T ,

When 0 ≤ s′ ≤ T-Uu kc , some defender i among these β defenders could slightly increase probabilities of all her targets to s′ + δ3 to get the utility u2 = kT - k(s′ + δ3)c

The above inequality holds because δ3 can be arbitrarily small. Thus, no profile in case 1) can be a (T-Uu)(kc-Uc+Uu) cnk -equilibrium.

In case 2), for defenders who have different coverage probability for their own targets, they could always increase payoff by decreasing some of their targets' probability to get a corresponding profile in case 1). Then we could know that any profile in case 2) cannot be a (T-Uu)(kc-Uc+Uu) cnk - equilibrium.

As the final step towards characterizing the Price of Anarchy, we derive optimal social welfare in this model.

Theorem9. In the General model, the optimal social welfare SWO is

Proof sketch. We firstly claim that we could get optimal social welfare only if all targets have the same probability s to be protected their. Otherwise, some target tij has the probability of 0 to be attacked. Then we could decrease sij to get a better social welfare. Consequently, we need only to consider an optimal identical coverage probability s to obtain optimal social welfare, which can be done in a relatively straightforward way.

If Uc - Uu ≥ kc - (n-1)(T-Uc) n , the Nash equilibrium is unique, with all targets protected with probability 1. The corresponding social welfare in equilibrium is

So far we have not yet added any constrains to value of T, Uc, and Uu (except that T ≥ Uc ≥ Uu). In order to make Price of Anarchy well-defined, we need to add constraints that values of T, Uc, and Uu are all non-positive (just as in the previous two models) or all non-negative. To be consistent with previous models, we add constraints that Uc, Uu and T are all non-positive (little changes if all are non-negative).

In the case of a unique Nash equilibrium, the price of anarchy is

If Uc - Uu < kc - (n-1)(T-Uc) n , there is no Nash equilibrium. However, we could get the optimal approximate Nash equilibrium when all defenders use the same coverage probability T-Uu kc for all targets. The corresponding Social Welfare is

We now analyze the relationship between (ϵ-)PoA and the values of n and k. Here are the key differences from MultiTarget Model. First we consider (ϵ-)PoA as the function of n. If T = 0, then we could find that the result is same as that in Multi-Target Model and (ϵ-)PoA linearly increases in n, which is unbounded. However, if T ̸= 0, PoA and ϵ-PoA are increasing in n, and as n → ∞, approach 1- cT and 1+ Uu-T kT , respectively. In other words, PoA (exact and approximate) is bounded by a constant, for a constant k!

Consider now approximate price of anarchy as a function of k. If T = 0, it is bounded by n + 1. However, if T ̸= 0, when kc - (n-1)(T-Uc) n ≤ Uc -Uu, it is an increasing function of k. When kc - (n-1)(T-Uc) n > Uc -Uu, it may at first increase or decrease in k, depending on the the values of the model parameters. However, when k is large enough, price of anarchy will invariably be decreasing in k, and as k →∞, ϵ-PoA→ 1. Figure 4 provides an example of the relationship between ϵ-PoA and k. Observe that all the curves begin to decrease when k > 10; they all approach 1 as k →∞. Thus, price of anarchy in the general model is only unbounded in the special case when T = 0, whereas when T ̸= 0, price of anarchy is always bounded by a constant. This observation is particularly surprising and significant considering the fact that the baseline and simplified multi-target models are quite natural, and seemingly innocuous, restrictions of the general case.

6 Conclusion

We examined a non-cooperative multi-defender security game in which defenders may protect multiple targets, offering complete characterization of Nash and approximate equilibria, socially optimal solutions, and price of anarchy. Our results show that defenders generally over-protect the targets in this model, but different modeling assumptions give rise to qualitatively different outcomes: a simpler model gives rise to an unbounded price of anarchy, whereas a more general model sees PoA converge to a constant when the number of defenders increases.

There are a number of directions for further work. Firstly, in our work we assume that strategy spaces of defenders are symmetric, and the impact of asymmetry is far from clear. Secondly, defenders in our model always have incentive to over-invest for their targets. Some public policies such as taxation and penalties may be helpful to improve the overall efficiency. Finally, it would be important to consider how interdependence among targets affects the levels of security investment and the price of anarchy.

Acknowledgments

This work was partially supported by the Air Force Research Laboratory under award FA8785-14-2-0180, National Science Foundation under award CNS-1238959, and Sandia National Laboratories.