Robust Solutions for Multi-Defender Stackelberg Security Games

1 Introduction

Stackelberg Security Games (SSGs) have attracted much attention in the multi-agent community [Paruchuri et al., 2008b; Tambe, 2011; Nguyen et al., 2013; An and Tambe, 2017]. They were applied to a variety of security problems, including the allocation of security resources at the Los Angeles International Airport [Pita et al., 2008], and protecting biodiversity in conservation areas [Basak et al., 2016] (see [Sinha et al., 2018] for an overview). The original SSG model postulates a single defender facing a single attacker. In many applications, however, different targets may be valuable - to varying extents - to multiple disparate parties, each of which is interested in defending its targets of interest. Accordingly, the model of Multi-defender Stackelberg Security Games (MSSGs), wherein multiple defenders (leaders)

∗This research has been partly supported by the Israel Science Foundation under grant 1958/20 and the EU Project TAILOR under grant 992215.

protect a set of targets against a strategic attacker (follower) who is their common enemy, has recently gained increasing attention. Solution concepts for this game were developed over time, starting from ζ-Nash Equilibrium (NE) [Gan et al., 2018], coordination mechanism [Gan et al., 2020], coalition formation [Mutzari et al., 2021] and correlated equilibrium (CE) via negotiation [Castiglioni et al., 2021].

However, for reasons we will detail shortly, to date, the solutions offered for MSSGs are highly sensitive, wherein small perturbations in the attacker's utility, or slight uncertainties thereof, can dramatically alter the defenders' resulting payoffs and alter the equilibrium.

Tie-Breaking and Discontinuity. The key, and somewhat subtle, reason for the high sensitivity of the previous solutions has to do with the issue of tie-breaking. Typically, in SSGs, at equilibrium, the attacker has several equally attractive targets. Indeed, otherwise the defender(s) could shift resources from the overly protected targets to increase the protection of the attacker's chosen target. So, as ties are ubiquitous, the attacker's tie-breaking behaviour plays a crucial role in the analysis. Different works have considered different tiebreaking policies. In the case of a single defender, it is commonly assumed that the attacker breaks ties in favor of the defender, the reason being that the defender can essentially enforce his choice by shifting an arbitrarily small amount of resources away from his desirable target, absorbing only an arbitrarily small utility loss.

In the case of multiple heterogeneous defenders, however, optimistic tie-breaking is not well-defined (and not justified), as the best target for each defender may be different. Hence, [Gan et al., 2018] use pessimistic tie-breaking, wherein each defender acts as if (among its choices) the attacker will attack the target that is worst for the defender. So, different defenders act as if the attacker, deterministically, attacks a different target. This tie-breaking rule, however, is not only overly pessimistic and unrealistic (as the attacker cannot simultaneously attack multiple targets), but also results in a sharp non-continuity in the defenders' payoffs. This is because the pessimistic tie-breaking occurs only at the point of exactly identical utilities (of the attacker) for the disparate targets. If the attacker's utility is slightly perturbed (or if there is even a slight uncertainty with regards to the attacker's true utilities), then the pessimistic tie-breaking is no longer relevant and the defenders' payoff may change dramatically. This discontinuity in payoff, in turn, shapes the structure of the solution concepts, which also tend to exhibit a discontinuity at the exact equilibrium point. Indeed, this sensitivity, and discontinuity, is the core reason why, in the existing MSSG models, exactNE need not exist (see [Mutzari et al., 2022] for an example).

In practice, however, such sharp discontinuity is often hard to justify. Indeed, while it is standard in game theory to assume that players' utilities are common knowledge, it is unrealistic to assume that these utilities are known accurately to any level of precision. Evidently, the defenders must somehow infer the attacker's utilities using some combination of data and reasoning, but this data (and reasoning) may be incomplete, imprecise, or noisy. Additionally, the attacker itself may have bounded computational resources, or be subject to other forms of noise, and thus not operate exactly as dictated by infinite precision calculations. Finally, the attacker's strategy is also determined by its knowledge/belief of the defender's coverage strategies, which the attacker needs to somehow infer from possibly incomplete and noisy data.

Robustness in MSSGs. Accordingly, as detailed in the related work, in the single defender setting, a whole line of research is devoted to addressing uncertainties (see [Nguyen et al., 2014]). Most of these papers tackle uncertainty by applying robust optimization techniques ([Pita et al., 2009; Jiang et al., 2013; Qian et al., 2015; Nguyen et al., 2014]). Some works consider a Bayesian approach [Kiekintveld et al., 2011; Yin and Tambe, 2012; Yang et al., 2012; Amin et al., 2016]. We believe, however, that this avenue is ill-suited for the multi-defender setting, with its tie-breaking subtlety. Robust optimization takes a worst-case approach: if some parameters are only known to lay within some set, then one assumes - pessimistically - that these parameters obtain values that minimize the objective function. In the multidefender setting, however, there is no one worst case; the worst-case for one defender may well be good for another. So, worst-case robustness is not well defined in this setting. We note that one could possibly propose a multi-player worst case analysis wherein each defender acts as if the parameters are worst for itself. But, coupled with pessimistic tiebreaking, this would result in an unreasonably, doubly pessimistic and unrealistic perspective, wherein different defenders postulate attackers with different parameters, attacking different targets; as if they inhabit parallel universes. The multi-defender setting therefore calls for a different approach.

Our Contribution. In this paper, we offer a robust model for the analysis of MSSGs. First, we formally define the notion of a robust solution, which formalizes the notion that the game solutions (e.g. Nash equilibrium, core) remain valid even after small perturbations or uncertainties in the game's parameters. We then introduce a formal model wherein small perturbations in the attacker's utility result in only small changes in the attacker's expected behavior, and hence also in that of the defenders. Essentially, we model the attacker's behavior as being probabilistic, with a continuous distribution concentrated around the behavior dictated by the presumed (and possibly inaccurate) utility. Importantly, we do not suppose any specific form for this distribution, only that it is concentrated as stated. Thus, this one model captures and unifies many possible scenarios and sources of noise and uncertainty.

Once we have formally defined the notions of robustness and the robust MSSG model, we show that the robust model indeed offers robust solutions. For the non-cooperative setting, we provide an efficient algorithm for constructing a robust approximate NE. For the cooperative setting, we consider the core of the game, for different variants of the core (α, γ). For the α version, we prove that the robust approximate core is always non-empty, and give an efficient algorithm for finding solutions therein. Importantly, since the utility of the defenders is no longer determined by their pessimistic beliefs, the resulting core solutions allow greater utility for the defenders than in previous models. Finally, we show that the γ-core may be empty.

We note that an additional benefit of the model, besides robustness, is that it renders moot the entire issue of tiebreaking - optimistic or pessimistic. With a continuous probability distribution, there is zero probability for ties.

Full version. Due to space limitations, this version of the paper focuses on introducing the key concepts and proof ideas. Complete proofs can be found at [Mutzari et al., 2022].

Selected Related Work. Robust analysis of the singledefender case has attracted considerable attention. Many of these employ robust optimization techniques to address uncertainties, while others model uncertainties using Bayesian models. Robust optimization is employed by: [Kiekintveld et al., 2013] in a setting where the attacker's utilities are known to lay in some interval, but the exact value is not known; and by [Pita et al., 2009] is a settings wherein the attacker may exhibit bounded rationality; by [Jiang et al., 2013] in a setting wherein the attacker's type is only known to be monotone. [Qian et al., 2015] consider a worst-case approach for studying risk-averse attackers, for which the level of riskadverseness is unknown. Finally, [Nguyen et al., 2014] offer a unified framework and methods for simultaneously addressing multiple types of uncertainties in single defender SSGs using robust optimization. As detailed in the introduction, we argue that the worst-case approach of robust optimization is ill-suited for the multi-defender setting, wherein there is no one worst-case for all defenders.

Other works, still in the single defender setting, employ a Bayesian approach to address uncertainties (as we do for the multi-defender setting). A general analysis of a single defender Bayesian SSG was introduced in [Paruchuri et al., 2008a]. [Kiekintveld et al., 2011] study Bayesian SSGs with a continuous payoff distribution for the attacker. They demonstrate scenarios where there are too many possible attacker types to consider, and known solutions for a finite number of attacker types don't scale well. [Yin and Tambe, 2012] provide a unified Bayesian approach to handling both discrete and continuous uncertainty in attacker types. [Yang et al., 2012] model human adversaries with bounded rationality as quantal response adversaries, which with some probability do not choose the best response. They specifically assume that the attacker's strategy is determined by a scaled soft-max function of the expected utilities of the attacker on each target, and utilize the specific structure of the soft-max function to obtain a solution for the setting (see also [Amin et al., 2016], who consider general SGs).

Our work differs from all of the above in that it considers the multi-defender case. The Bayesian modeling we introduce is also different. On the one hand, unlike the unrestricted, general Bayesian models (e.g. [Paruchuri et al., 2008a; Kiekintveld et al., 2011; Yin and Tambe, 2012], [Paruchuri et al., 2008a; Yin and Tambe, 2012]), we assume a concentrated distribution (Definition 3.2). This, we believe, adequately models most frequent sources of uncertainty, including noisy and imprecise information, bounded computation power, and most incarnations of bounded rationality. On the other hand, we do not suppose any specific form for this concentrated distribution (e.g. soft-max), as such an assumption would fail to model many real-world uncertainties.

2 Defining Robustness

The main objective of this work is to develop a robust MSSG framework. We now formally define the notion of robustness. We deliberately do so in the most general terms, not confining the definition to the specific game, or solution concepts that we consider. We later show how the model we offer indeed exhibits robustness as defined here.

Solution Concepts. Consider the Nash equilibrium solution concept. Technically, given a game G, there is a set NE(G) of strategy profiles for which the NE property holds. Similarly, the core of G is a set of coalition structures core(G), for which the core properties hold. Thus, in the most general sense, a solution concept is a function X from the set of games (of some class) to some space S, which maps each game G (of the class) to the corresponding structures for which the specific property of the solution concept holds.

Nearness. Conceptually, robustness of a solution x states that x remains a solution even under "small" perturbations in game parameters. This requires a notion of distance amongst games. Given a distance function d(·, ·) over game pairs, say that games G, ˆG are η-near if d(G, ˆG) ≤ η (later, d will be instantiated based on the MSSG's specific parameters).

Definition 2.1 (Robust Solution). Let X be a solution concept, G a game, and x ∈ X(G). We say that x is an η-robust X of G, if x ∈ X( ˆ G) for any ˆG that is η-near to G.

Thus, for example, a strategy profile x is said to be an ηrobust ϵ-NE of G if it is an ϵ-NE of any ˆG that is η-near to G (G itself included).

3 The Robust MSSGModel

The Standard model. In an MSSG, there is a set N = {1, . . . , n} of defenders, a set T = {t1, . . . , tm} of targets that the defenders wish to protect, and an attacker, who seeks to attack the targets. Each defender i ∈ N has ki ∈ N security resources, each of which can be allocated to protect a target. The attacker chooses one target to attack. The attack is successful if the target is unprotected by any security resource. A successful (res. unsuccessful) attack at t yields utility ra (t) (res. pa (t)) to the attacker and pdi (t) (res. rd i (t)) to defender i, for all i (rd i (t) > pdi (t), ra (t) > pa (t)).

An MSSG is thus a 5-tuple G = (N, T , K, R, P), where K = (k1, . . . , kn) are the numbers of security resources of the defenders, R = (ra (t1), . . . , ra (tm), rd 1 (t1), . . . , rdn (tm)), is the sequence of rewards, and similarly P - the sequence of penalties.

The defenders' allocation of security resources to the targets may be randomized. Specifically, each defender i chooses a coverage vector xi ∈ Cki (where Ck = {x ∈ [0, 1]m| ∑ xt ≤ k}). Here, xi,t is the probability that target t is protected by one of defender i's security resources. 1 We denote by X = (xi)i∈N .

If the defenders are uncoordinated, the probability that target t ∈ T is protected is

The overall coverage vector c = (ct)t∈T is assumed to be known to the attacker, which chooses its action after the defenders have committed to their distribution. Thus, the attacker and defenders' utilities upon an attack at t are:

In the classic (non-robust) model, all players are assumed to be rational. As such, the attacker's best response is to attack a target in the set BR(c) := argmaxt∈T U a (c, t), which maximizes its expected utility. However, as discussed in the introduction, BR(c) typically consists of multiple targets, which brings about the issues of tie-breaking and discontinuity.

The Robust Model. The non-robustness of the standard MSSG model arises from the assumption of exact deterministic behavior of the attacker, whereby it always plays the exact optimal play, even if the difference between the optimal play and the next in line is minuscule. Therefore, small changes in the attacker's utility function may lead to abrupt changes in the attacker's strategy, in turn causing abrupt changes in the defender's utilities. Accordingly, to obtain a robust model, we model the attacker's behavior as being probabilistic, with a continuous distribution concentrated around the deterministic behavior dictated by the presumed (possibly inaccurate) utility. Importantly, we seek a general model which can capture the multitude of possible reasons for the mentioned perturbations. The formal details follow.

Given a coverage vector c, and the resultant attacker's utility vector u = u(c) = (U a (c, t))t∈T (over the different targets), the attacker's actual behavior is assumed to be determined by a probability distribution ω(u) ∈ [0, 1]m, specifying the probability that the attacker will actually attack each target. The function ω is termed the Attacker's Behavior Function, and is assumed to have the following properties:

Definition 3.1 (Attacker's Behaviour Function (ABF)). A continuously differentiable function ω : Rm + → Rm + is an attacker's behaviour function if the following axioms hold:

1. ω(u) is a probability distribution.

1 Provably, any such coverage vector can be implemented by a distribution over deterministic allocation strategies, each employing at most k resources.

1. ω is monotone increasing at each coordinate.
2. For each ∅ ̸= S ⊆ T and t ∈ S : ωt(u) ∑t′∈S ωt′ (u) is independent of any ut′ , t′ ̸∈ S.

Axiom 3 states that, given that the attack is within the set S, the conditional probability of an attack on any specific target t ∈ S is only determined by the inter-relationships between the utilities of targets within S.

Thus, given a coverage vector c, inducing attacker utilities u(c), and ABF ω, defender i's expected utility is given by:

The following definition provides that the attacker's behavior is centered around the optimal deterministic one.

Definition 3.2 ((δ, ϵ)-ABF). Let G be an (M)SSG, and δ, ϵ > 0. An ABF ω is a (δ, ϵ)-ABF if:

Thus, with a (δ, ϵ)-ABF, any target offering a utility δ less than the optimal one will be attacked with probability < ϵ.

We believe this (δ, ϵ)-ABF formulation captures, under one unifying definition, the many possible sources for noise and uncertainty in the attacker's utility, as discussed in the introduction. With these definitions, a robust MSSG is a pair G = ⟨G, ω⟩, where G is a MSSG and ω is a (δ, ϵ)-ABF. 2

4 Solution Concepts

For completeness, we review the MSSG solution concepts, as defined in previous works. Throughout, we consider the approximate versions.

ζ-Nash Equilibrium. Given the players' utility functions, the definitions of approximate NE is standard:

Definition 4.1 (ζ-Nash Equilibrium). A strategy profile X = (xi)i∈N is an ζ-NE if for any defender i ∈ N and any strategy x′i of i:

Coalitions. When the defenders are uncoordinated, independent choices may result in inefficient resource use. Therefore, [Mutzari et al., 2021] consider a model for coalition formation in MSSG, which we adopt. Any subset P ⊆ N of defenders may form a coalition, in which case they act as a single defender with kP = ∑i∈P ki resources. The coalition consisting of all of the defenders is called the grand coalition.

Coalitions partition the set of defenders: N = {P1, . . . , Pℓ}. Each coalition Pi chooses a coverage vector xj ∈ CkPj }. Denoting X = (x1, . . . , xℓ), the probability that target t is protected is:

2 We note that inevitably the proper values for δ, ϵ are dependent on G. The reason is that δ must be small compared to the attacker's utilities, thus must be scaled in accordance, and ϵ must depend on the number of targets as it has to be small relative to 1/m.

Given a strategy profile X and a target t, the defenders' utilities are defined in the same way as in (3). A coalition structure is any such pair CS = ⟨P,X⟩.

Since CS includes a coverage vector X that (by (6)) induces the overall coverage vector cov(X), for notational simplicity, the players' utilities can be viewed as a function of the coalition structure, which we simply denote U d i (CS).

Deviations. Given a coalition structure CS, a subset of defenders may choose to deviate and form a new coalition. In such a case, one must define the strategy played by all defenders. Following [Moulin and Peleg, 1982; Chalkiadakis et al., 2011; Shapley, 1973], the assumption is that in order to protect the status quo, the remaining defenders take revenge against the deviators. The revenge is ζ-successful if it results in at least one deviator gaining no more than ζ from the deviation. It is assumed that this revenge strategy is chosen after the deviators choose their strategy. A deviation is ζapproximate successful if it admits no ζ-successful revenge.

Definition 4.2 (ζ-approximate core). A coalition structure CS is in the ζ-approximate α-core if it admits no ζapproximate successful deviation.

So, in the ζ-approximate core, a deviation cannot add more than ζ to the utility of at least one of the deviation's members.

5 The Robustness Theorem

We now provide the central robustness theorem, which essentially states that in the robust MSSG model, any approximateNE or approximate-core automatically translates to their respective robust counterparts. We note that, technically, the theorem essentially follows directly from the continuity of ω, but the result is exactly what is necessary.

First, recall that the definition of a robust solution (Definition 2.1) requires a distance function between games. In MSSG, for G = (N, T ,K,R,P), ˆG = (N, T ,K, ˆR, ˆ P), and G = (G, ω), ˆ G = ( ˆG, ˆω), we define:

The following lemma bounds the change in utility arising from small changes in the game parameters.

Lemma 5.1. Let G be a robust MSSG and η > 0. Then there exists a constant b such that, for any coverage vector c, any defender i ∈ N and any game ˆ G η-near to G: | ˆU d i (c)-U d i (c)| ≤ 0.5bη (where ˆU d i (c), U d i (c) are the utilities of defender i in games ˆ G, G respectively).

The proof essentially follows from the continuity of the ABF (see full version, [Mutzari et al., 2022], for details).

Theorem 5.2. Let G be a MSSG. With b of Lemma 5.1, for any η:

1. any ζ-NE of G is also an η-robust (ζ + bη)-NE of G.
2. any ζ core of G is also an η-robust (ζ + bη)-core of G (for all three variants of the core α, β, γ).

Proof. We prove (1). The proof of (2) is analogous. Let X be a ζ-NE of G, and ˆ G η-near to G. Then, for any possible x′i

Algorithm 1 ALLOC

• Input: value c, ˜ c ∈ [0, 1], G = (N , T , K, P, R) Output: a strategy profile X = (xi,t) 1: ct ← 0, for all t 2: for i ∈ N do 3: for t ∈ T by reverse ⪯˜ ci precedence order do 4: xi,t ←min{1- 1-c 1-ct , ki} 5: ki ← ki - xi,t 6: ct ← 1 - (1 - ct)(1 - xi,t); 7: end for 8: end for

of player i

where we use Lemma 5.1 for (7) and (9), and (8) follows by the definition of ζ-NE.

Accordingly, in order to find robust solutions in our model it suffices to find regular solutions in the model, and robustness then follows automatically. The remainder of the paper is thus dedicated to finding such solutions.

6 Nash Equilibrium in Robust MSSGs

We now show how to compute an approximate NE in robust MSSGs. For simplicity, we restrict the discussion to nonsaturated games. A robust MSSG G is α-saturated if there exists a coverage c ∈ CkN and t ∈ T s.t. ct ≥ 1 - α and ωt(c) ≥ ϵ. In a saturated game, there are sufficient resources to induce an attack that is almost surely caught. The results can be extended to saturated games using a similar approach to the one used by [Gan et al., 2018].

Theorem 6.1. There exists a polynomial algorithm, such that for any G there exist A, B, C, ϵ0, δ0 s.t. for any (δ, ϵ)-ABF ω with ϵ < ϵ0, δ < δ0, on input (G, ω) the algorithm outputs a strategy profile X that is a ζ-NE, for ζ = Bδ +Cϵ (provided (G, ω) is not Aδ-saturated).

The exact constants, together with a detailed proof, appear in the full version, [Mutzari et al., 2022]. The proof builds upon the techniques of [Gan et al., 2018], but requires significant adaptations for our setting. For simplicity, here, we consider the case where all targets carry identical penalties and identical rewards for the attacker (but not the defenders). This case allows us to explain the core elements of the construction and the proof, while avoiding the technicalities. Note that in the explanation we do not seek to obtain the best constants. Better bounds are offered in the complete proof.

For the case we are considering, we can further normalize the attacker's utilities so that pa (t) = 0 and ra (t) = 1 for all t. With this assumption, U a (c, t) = 1 - ct, for all c, t.

The core procedure underlying the algorithm is ALLOC (Algorithm 1). ALLOC gets as input a parameter c, and aims to have ct = c, for all targets. To this end, the defenders - one by one in order - iterate through the targets, allocating resources until either (i) the c level is reached, or (ii) their resources are fully depleted. This allocation is performed in Line 4, where xi,t = 1 - 1-c 1-ct brings the coverage to exactly c, and xi,t = ki depletes the defender's resources. Importantly, each defender considers the targets in reverse preference order of its expected utility from the target, assuming some identical coverage level ˜ c (with ˜ c possibly different from c) . Specifically, for targets t, t′ , we denote t ⪯˜ ci t′ if U d i (˜ c, t) ≤ U d i (˜ c, t′ ). In ALLOC, defenders iterate through the targets from the least to the highest in the ⪯˜ ci order.

Clearly, the actual coverage level obtained by ALLOC is determined by c: if c is too small then ALLOC may complete without depleting the defenders' resources, and if c is too big then some targets my have ct < c. However, there exists a ¯ c for which the algorithm completes with ct = ¯ c for all targets (assuming the game is non-saturated). This ¯ c can be approximated to within any level of accuracy by binary search, with multiple runs of ALLOC. Set β = (1 - ¯ c)/2.

Set ˇ c = ¯ c +mδ/β. For δ sufficiently small, ˇ c < 1 - β. Consider the outcome of running ALLOC with c = ˇ c and ˜ c = ¯ c. Let ˆX be the resultant allocation, and for each t, let ˆ ct be the resultant coverage of target t. Since ˇ c > ¯ c, there will necessarily be targets t for which ˆ ct < ¯ c, but for δ sufficiently small there will be only one such target. Denote this target t∗ . For all other t's, ˆ ct = ˇ c.

We now argue that ˆX is a ζ-NE for ζ = Bδ+Cϵ, for some constants B, C dependant only on G.

In the following, we focus on the attacker's behavior occurring with probability ≥ ϵ. For ease of exposition, we say that an event is likely if it happens with probability ≥ ϵ.

If all defenders play by ˆX then an attack is only likely at t∗ . This is since ˆ ct - ˆ ct∗ ≥ δ, and hence ˆut∗ - ˆut ≥ δ, for all t, and ω is a (δ, ϵ)-ABF. Consider a deviation of defender i, and let c′ be the coverage vector resulted from this deviation. We now explain why c′ cannot "substantially" increase the utility of i. Let: L be the targets - aside from t∗ to which i allocated resources, L+ = L ∪ {t∗ }, and H = T \ L+. We consider what c′ can do to attacks on H, L and t∗ .

Attacks on H. We argue that under c′ the attacker is unlikely to attack any target of H. The reason is that since i did not allocate resources to H, the only way that it can induce an attack on H is by increasing the coverage of all targets in L+ to ˇ c + δ. But, since ct∗ < ¯ c = ˇ c -mδ/β, bringing t∗ 's coverage to ˇ c + δ can only be accomplished by taking coverage from the members of L. In doing so, at least one will result with coverage less than ˇ c - δ (the value of ˇ c was so chosen).

Attacks on L. A deviation can induce attacks on L. However, it cannot provide i substantially more than it originally obtained, where substantially means adding more than δB utility. The reason is that since t∗ is not ˇ c covered, it must be that t∗ was considered by i after all elements of L - or else i would either bring t∗ 's coverage to ˇ c or fully deplete its resources. So, t ⪯¯ ci t∗ , for all t ∈ L. This means that - at coverage level ¯ c - attacks on targets of L offer i no more utility than attacks on t∗ . So, if ¯ c where the coverage, then inducing an attack on L would offer no gain to i. In practice, the elements of c′ and ˆc are not exactly ¯ c, but they are O(δ) away. So, since U d i (c, t) is linear in c, the differences in utility can also be only O(δ). So attacks on L cannot offer substantially more utility than what t∗ initially offered.

Attack on t∗ . A deviation can also possibly increase the coverage of t∗ , thus offering more utility if and when attacked. However, one can only add O(δ) coverage (while keeping an attack on t∗ likely), so that this addition cannot add more than O(δ) utility.

Putting It All Together. We obtain that with probability 1 - ϵ the added utility due to the deviation is at most δB, for some constant B. With probability ϵ the increase can be larger, but clearly bounded by C = maxj,t rd j (t). So, the utility increase is bounded by ζ = δB + ϵC. This completes the construction of ζ-NE. By Theorem 5.2, this strategy is also an η-robust (ζ + bη)-NE, for any η > 0.

7 The Robust Core

In this section we outline the algorithm to construct a robust ζ-approximate α-core, and correctness proof. The full details appear in the paper's full version [Mutzari et al., 2022].

Resistance to Subset Deviations. With minor adaptations, the ALLOC procedure can be applied to the cooperative setting (wherein probabilities are additive rather than multiplicative). Also, the procedure can easily be configured to accept a target utility level u as input (rather than target coverage c) - see full version [Mutzari et al., 2022]. As before, repeated calls to ALLOC allow us to find a ¯u and strategy ¯X such that all targets offer utility ¯u to the attacker (except for those with ra (t) < ¯u), using all resources. Next, we re-run ALLOC with ˇu = ¯u -mO(δ). Let ˆX be the resulted strategy profile, ˆc = cov( ˆX), and t∗ the target not covered to ˇu. Then, U a (ˆc, t∗ ) > ¯u + δ and U a (ˆc, t) = ˇu for all other t. So, the attacker is only likely to attack t∗ .

We argue that ˆX is resilient to any deviation xD of any proper subset D ⊂ N of defenders. Set c′ = cov( ˆX-D, xD). Let L be the targets, aside from t∗ , to which D allocated resources in ˆX, and L+ = L ∪ {t∗ }. Then, analogously to the NE case, no deviation of D can induce a likely attack outside L ∪ {t∗ }. They may, however, be able to alter the attack probabilities within L+. Let A be the targets that are likely to be attacked under xD. So, |U a (c′ , ti) -U a (c′ , tj)| < δ, for any ti, tj ∈ A. Now, recall that given D and xD, the remaining defenders - ¯D - can change their strategy. So, using only O(δ) resources per target, ¯D can raise the coverage of all but one target of t0 ∈ A, so that t0 offers at least δ more utility than all other targets. Since t0 ∈ L+, there exists at least one i ∈ D for which t0 ⪯cov(X) i t∗ . So, for this i, the deviation does not offer any (substantial) gain.

Resistance to Grand Coalition Deviations. We now show how to transform the above strategy to one resistant to grand coalition deviations. Let ˆudi be the utility of defender i under

ˆX. Consider the following linear program (with variables pt):

Let p∗ = (p∗t )mt=1 be a solution to LP 10 (there necessarily exists a solution, since p = ω(u(ˆc)) is a feasible one). Proposition 7.1 provides that with small changes to ¯u = (¯u, . . . , ¯u) the distribution p∗ can (essentially) be induced.

Proposition 7.1. For any probability distribution p and any u > 0, there exists a utility vector u s.t. ∥ω(u)-p∥∞ < m2 ϵ , and u ≤ ut < u + 2mδ for all t ∈ T .

Let ¯u∗ be the utility vector provided by invoking Proposition 7.1 with u = ¯u and p = p∗ . Since ¯u is implementable (by ¯X) and ¯u∗t ≥ ¯u for all t, then ¯u∗ is also implementable, by some strategy ¯X∗ . We now argue that ¯X∗ is an the ζapproximate α-core, for ζ = Aϵ + Bδ (for some constants A,B fully determined in the full proof). In the following arguments, interpret all statements "up to at most ζ gains".

To see that ¯X∗ resists grand coalition deviations, first note that we may assume that in any such deviation X′ , all elements of u′ = u(cov(X′ )) are close (within O(δ)) to ¯u. Otherwise, there must be targets that are more than δ apart in their utility, in which case it is possible to shift resources from the those with lesser u′t to the higher ones, without substantially changing the attack distribution (by Proposition 7.1). Now, any target where u′t > ¯u is not substantially better for any deviator, and any target where u′t < ¯u - δ is not likely to be attacked. By construction, p∗ maximizes the sum of defender utilities, subject to each getting at least as in ˆX. So, it is impossible that all defenders simultaneously get even more.

For subset deviations, consider D ⊂ N and suppose they have a deviation xD that guarantees all members of D more than in ¯X∗ (regardless of how the others play). But ¯X∗ offers essentially as much as the output of the linear program, which, by its constraints, offers each defender as much as ˆX. So, xD would also constitute a successful deviation from ˆX, which we proved cannot be. We thus obtain:

Theorem 7.2. There exists a polynomial algorithm, such that for any G there exist A, B, C, ϵ0, δ0 s.t. for any (δ, ϵ)-ABF ω with ϵ < ϵ0, δ < δ0, on input (G, ω) the algorithm outputs a strategy profile X that is a ζ-approximate α-core, for ζ = Bδ +Cϵ (provided that (G, ω) is not Aδ-saturated).

By Theorem 5.2, for any η > 0, any such solution is also an η-robust (ζ + bη)-approximate α-core.

γ-Core. Unlike the α-core, the approximate γ-core (see [Chander, 2010; Mutzari et al., 2022]) may be empty, as in the following example. There are 6 targets and 4 defenders. Targets 1-3 yield a reward of 6 and penalty of 5 to defenders 1 and 2, as do targets 4-6 to defenders 3 and 4. All other targets yield a reward 1 and penalty 0 to all other players (including the attacker). Then defenders 1+2 can γdeviate and get a utility ≥ 4 each, as can defenders 3+4, but no coalition structure can yield utility ≥ 4 to all defenders. See a full explanation in [Mutzari et al., 2022].