Multi-defender Security Games with Schedules

Abstract

Stackelberg Security Games are often used to model strategic interactions in high-stakes security settings. The majority of existing models focus on single-defender settings where a single entity assumes command of all security assets. However, many realistic scenarios feature multiple heterogeneous defenders with their own interests and priorities embedded in a more complex system. Furthermore, defenders rarely choose targets to protect. Instead, they have a multitude of defensive resources or schedules at its disposal, each with different protective capabilities. In this paper, we study security games featuring multiple defenders and schedules simultaneously. We show that unlike prior work on multi-defender security games, the introduction of schedules can cause non-existence of equilibrium even under rather restricted environments. We prove that under the mild restriction that any subset of a schedule is also a schedule, non-existence of equilibrium is not only avoided, but can be computed in polynomial time in games with two defenders. Under additional assumptions, our algorithm can be extended to games with more than two defenders and its computation scaled up in special classes of games with compactly represented schedules such as those used in patrolling applications. Experimental results suggest that our methods scale gracefully with game size, making our algorithms amongst the few that can tackle multiple heterogeneous defenders.

Z. Song—Independent Researcher.

Equal contribution between authors Song and Ling.

1 Introduction

The past decades have seen a wave of interest in Stackelberg Security Games (SSG), with applications to infrastructure [23], wildlife poaching [5,6,7] and cybersecurity [2, 21, 29]. SSGs are played between a single defender allocating defensive resources over a finite set of targets and an attacker who, after observing this allocation, best responds by attacking the target least defended [25].

Numerous variants of SSGs better reflecting the real world have been proposed. Amongst the most well-researched extension are settings with scheduling constraints. Instead of guarding a single target, the defender chooses a set of targets instead, making it possible to model real world problems such as planning patrols for anti-poaching [3, 5, 7, 28] and the US coast guard [22, 24], infrastructure protection [12], and optimal placement of police checkpoints [11]. Another less explored extension is the multi-defender setting, where multiple defenders (e.g., city, state and federal law enforcement), each utilize distinct resources in tandem, potentially resulting in miscoordination [13]. Recent work in [8, 9] solved the challenging problem of finding equilibrium when defenders are heterogeneous, both in the coordinated and uncoordinated case.

Unfortunately, there is almost no literature on settings exhibiting both scheduling and multiple defenders. Our work fills this non-trivial gap. In contrast to the positive results of [8, 9], we show that equilibrium may not exist with the inclusion of scheduling constraints, even under extremely stringent constraints on other aspects of the problem. We then guarantee existence of equilibrium in two defender settings when restricted to schedules satisfying the subset-of-a-schedule-is-also-a-schedule structure [16], on top of other mild restrictions. We construct polynomial time algorithms for computing equilibrium in such restricted settings and propose two extensions. The first utilizes an additional assumption of Monotone Schedules to handle the general multi-defender setting. The second scales to scenarios with a large (possibly exponential) number of schedules in structured domains such as patrolling. Empirically, our algorithms scale gracefully, making them viable for use in the real world.

2 Background and Related Work

Our work is motivated by the security application played on the layered network in Fig. 1a, where vertices represent neighborhoods and edges represent connecting roads. Distinct law enforcement agencies (e.g., local and federal police) patrol along a path starting from vertex a to vertex e. Patrols provide defence, or coverage to the neighborhoods they pass (Fig. 1a). By randomizing or splitting their patrols, agencies can broaden coverage at the expense of thinning them (Fig. 1b). Coverage at each neighborhood is accumulated over patrols (Fig. 1c). An attacker chooses a single neighborhood to attack based on this coverage, giving negative reward to law enforcement agencies. Neighborhoods and law enforcement are non-homogeneous: neighborhoods differ in density and demographics, local police value local businesses and inhabitants, while federal agencies focus on federal government assets. Given these competing objectives, how should law enforcement agencies plan their patrols?

Fig. 1.

Multi-defender Patrolling on Layered Networks. Vertices are targets and black edges are roads connecting targets. (a) The green path shows a patrol route by a single defender, passing through $b_2$, $c_3$ and $d_4$. Protected nodes are shaded, with the darkness indicating degree of protection. (b) A coverage obtained by splitting/randomizing patrols. Thinner arrows indicate smaller patrols. Compared to Fig. (a), more targets are covered, but with lower intensity. (c) A joint patrol with two defenders; the first employs the route in Fig. (b) and the second follows the blue paths. The orange edge is used by both defenders. (Color figure online)

The closest pieces of work to us are by Lou et al. [20] and Gan et al. [8, 9]. The work by Gan et. al. [8] focuses on the case with multiple heterogeneous defenders without schedules, showing that an equilibrium always exists and can be computed in polynomial time in both the coordinated and uncoordinated case by extending the classic water-filling algorithm [15]. However, their model is limited by the lack of schedules. This is not merely an issue of computation: our work shows that the inclusion of schedules can trigger non-existence of equilibrium. The work by Lou et al. [20] consider multiple defenders and scheduling, analyzing equilibrium in terms of the Price of Anarchy between defenders and giving conditions for their existence.¹ However, the bulk of their work concerns homogeneous defenders; their results for heterogeneous defenders limited (e.g., having every target completely covered). Here, they acknowledge possible non-existence of equilibrium, proposing approximate solvers based on Mixed-Integer Program with quadratic constraints. In contrast, our work makes additional assumptions but guarantees existence and polynomial time solutions.

SSGs as a whole have a long and illustrious history. First introduced by von Stackelberg [26] to model competitive firms and the first mover’s advantage, it saw a resurgence beginning with [27] alongside a wave of applications primarily in the domain of security which modeled defenders as first movers or leaders [1, 25]. Since then, an enormous amount of literature has surfaced, e.g., computing equilibrium in sequential settings [4, 17, 19], handling bounded rationality of defenders [14], and various other structural assumptions such games on networks [18], each catering to different variants of security applications.

3 Nash-Stackelberg Equilibrium with Scheduling

Our setting involves n heterogeneous defenders, T heterogeneous targets and a single attacker. Each defender allocates defensive resources which induce coverage over targets, a quantitative measure of the degree to which each target is protected. For example, coverage can refer to the average number of police officers patrolling at a particular neighborhood (Fig. 1). As is customary in security games, we employ Stackelberg leadership models. Each defender first independently commits to its coverage. The attacker then chooses to attack a target $t \in [T]$ with the lowest total coverage under this commitment.

Formally, each defender i has an attainable set of coverage $V^i \subset \mathbb {R}_+^T$ (which we define concretely later), from which it chooses a coverage vector $v^i \in V^i$, where defender i contributes $v^i(j)$ coverage to target j. A coverage profile $\textbf{v} = (v^1, v^2, \cdots ,v^n) \in V^1 \times V^2 \cdots \times V^n$ is an ordered tuple of coverages from each defender. We assume that coverage accumulates across defenders additively, such that for a given coverage profile $\textbf{v}$, the total coverage of all defenders is $v^{total} = \sum _{i\in [n]} v^i$. The total coverage on target j is $v^{total}(j) = \sum _{i\in [n]} v^i(j) \ge 0$.

We assume coverage independent payoffs: each defender’s payoff is based on the attacked target, but not on the coverage itself. In practical terms, this means that an attack would “always succeed”, and the purpose of coverage is to redirect the attacker elsewhere. For example, security officers may not be able to prevent a determined terrorist attack, but having more officers in crowded areas may make the cost of attack prohibitively high such that the attack occurs at a less populated area. This assumption means there is no need to work explicitly with numerical values for defender payoffs. Instead, each defender i has a fixed order of preference over targets given by the total order $\succ _i$. We write $j \succ _i k$ (resp. $j \prec _i k$ ) if defender i prefers target j over k to be attacked (resp. not attacked). We assume that there are no ties in defender preferences, hence $j=_i k$ if and only if $j=k$. We write $j \succeq _i k$ if and only if $j \succ _i k$ or $j =_i k$, with $j \preceq _i k$ being defined analogously. Preference orders differ between defenders, hence $j \succ _i k$ does not imply $j \succ _{i'} k$ for $i \ne i'$. For any target $t \in [T]$, we define the set $\mathcal {T}^{\succ _i}_t = \left\{ k \in [T] | k \succ _i t \right\}$, i.e., the set of targets which defender i strictly prefers to be attacked over target t. $\mathcal {T}^{\prec _i}_t$, $\mathcal {T}^{\succeq _i}_t$, and $\mathcal {T}^{\preceq _i}_t$ are defined analogously.

We now define formally define the Nash-Stackelberg equilibrium (NSE) given $V^i$ and $\succ _i$ for each defender. We call a tuple $(v^1, \dots , v^n, t) \in V^1 \times \dots \times V^n \times [T]$ a strategy profile, abbreviated by $(\textbf{v}, t)$. Strategy profiles are an NSE when (i) the attacker is attacking a least covered target and (ii) neither defender i is willing to unilaterally deviate their coverage from $v^i$ to $\widehat{v}^i \in V^i$ (written as $v^i \rightarrow \widehat{v}^i$), assuming that the attacker could react to this deviation by possibly adjusting its target from t to $\widehat{t}$. The NSE is named as such because the attacker best responds to the total coverage as if it was a Stackelberg follower, while defenders interact amongst themselves as if it were Nash. The former condition is formalized easily.

Definition 1 (Attacker’s Best Response Set)

Given a total coverage $v^{total} \in \mathbb {R}_+^T$, its attacker best response set is²

$$\begin{aligned} B(v^{total}) = \mathop {\textrm{Argmin}}\limits _{t \in [T]} v^{total}(t) = \left\{ t \in [T] \Big | v^{total}(t) = \min _{t' \in [T]} v^{total}(t') \right\} \end{aligned}$$

(1)

Definition 2 (Attacker Incentive Compatibility (AIC))

A strategy profile $(\textbf{v}, t)$ is attacker incentive compatible if and only if $t \in B(v^{total})$.

Essentially, a tuple $(\textbf{v}, t)$ is AIC when the attacker does not strictly prefer some target $\widehat{t} \ne t$ over t. Naturally, we desire profiles which are AIC.

As noted by [9], condition (ii) contains an important nuance: if defender i deviates via $v^i \rightarrow \widehat{v}^i$ such that $\widehat{v}^{total}$ does not have a unique minimum coverage (i.e., $|B(\widehat{v}^{total})| > 1$), how should the attacker break ties? In single-defender scenarios, one typically breaks ties in favor of the defender, also called the Strong Stackelberg equilibrium. With multiple defenders, this is ambiguous since defenders are heterogeneous. This is a non-trivial discussion, since the way the attacker breaks ties significantly affects the space of equilibrium. There are two natural choices for breaking ties: either punish or prioritize the deviating defender. These choices mirror the concepts of weak and strong Stackelberg equilibrium in single-defender settings. As [9] argue, the second convention of benefiting the deviating defender can lead to spurious deviations from defenders. For example, a defender may make a trivial “identity” deviation from $v^i \rightarrow v^i$, yet demand a nontrivial change in attacked target. As such we adopt the former concept. This means that deviating players are pessimistic towards any change in attacked target after their deviation (this pessimism exists only for deviations).

Definition 3

(Defender i -Weakly Attacker Incentive Compatibility (i -WAIC)). A strategy profile $(\textbf{v}, t)$ is i-WAIC if and only if (i) $t \in B(v^{total})$ and (ii) $\widehat{t} \in B(v^{total}) \implies \widehat{t} \succeq _i t$.

Definition 4

(Defender i -Incentive Compatibility (i-IC)). A strategy profile $(\textbf{v}, t)$ is i-IC if and only if there does not exist $\widehat{v}^i\in V^i$ and $\widehat{t} \succ _i t$ such that $(v^1, v^2, \cdots , v^{i - 1}, \widehat{v}^i, v^{i+1}, \cdots , v^n, \widehat{t})$ is i-WAIC.

Definition 5 (Nash-Stackelberg Equilibrium (NSE))

A strategy profile $(\textbf{v}, t)$ is an NSE if and only if it is AIC and i-IC for all $i \in [n]$.

Put simply, $(\textbf{v}, t)$ is i-WAIC if it is AIC and the choice of t is made such as to break ties against defender i (clearly, this is a strictly stronger condition than AIC). Consequently, $(\textbf{v}, t)$ is i-IC if there is no deviation $v^i \rightarrow \widehat{v}^i$ such that defender i benefits strictly when the attacker changes it’s best-response $t \rightarrow \widehat{t}$ while breaking ties against defender i. Thus, any candidate NSE $(\textbf{v}, t)$ is only required be AIC, allowing us to freely choose how the attacker tiebreaks, as though t was the “agreed upon norm” target for the attacker. However, if defender i deviates, we use the stronger notion of WAIC for post-deviation tiebreaking.

Remark 1

Our model does not completely generalize [9] due to coverage independent payoffs and additive coverage. However, these assumptions are related to their cases of correlated defenders and non-overlapping payoffs respectively.

4 Analysis and Algorithms

Clearly, the existence and computation of NSE depends on the set $V^i$. The simplest specification of $V^i$ is obtained by explicitly specifying schedules and requiring clearance constraints. Suppose each defender $i \in [n]$ has 1 unit of divisible defensive resource to allocate across a set of $S^i > 0$ schedules $\mathcal {S}^i = \{ s^i_1, s^i_2,\cdots s^i_{S^i} \}$. Each $s^i_z \in \mathbb {R}^T_+$ is the non-negative coverage over all T targets when defender i allocates its entire defensive resource to the z-th schedule. $s^i_z(j), j \in [T]$ is the coverage specific to target j. Each defender $d_i$’s strategy is a distribution $x^i \in \mathbb {R}^{S^i}_+$ over its set of schedules, where $\sum _{s_z^i \in \mathcal {S}^i} x^i(s_z^i) = 1$.

Assumption 1

(Clearance). Given schedules $\mathcal {S}^i$, the coverage vector $v^i$ is said to satisfy clearance if all defensive resources are fully utilized, i.e.,

$$\begin{aligned} V^i = \left\{ v \in \mathbb {R}_+^T \Bigg | \exists x^i \ \text {such that } \forall j \in [T] \ v(j) = \sum _{s_z^i \in \mathcal {S}^i} x^i(s_z^i) \cdot s_{z}^i (j) \right\} . \end{aligned}$$

The clearance constraint on $V^i$ essentially requires defenders to expend as much as they can, preventing them from “slacking off”. When each schedule attacks a distinct target, i.e., $S^i = \{ e_1, e_2, \dots , e_T \}$, clearance constraints reduce to the setting of [9] and equilibria will exist. However, our focus is on the scheduled setting. Indeed, we now demonstrate an instance where NSE do not exist.³

Fig. 2.

Illustration of Example 1. (a) Target labels. Defender 1 prefers diagonal (green) targets attacked; defender 2 prefers off diagonal (blue) targets. (b–e) Defender schedules $s_1^1, s_2^1, s_1^2$ and $s_2^2$. (f) Cyclic behavior. Green/blue arrows indicate changes in targets induced by defender 1/2 deviating. (Color figure online)

Example 1

The game in Fig. 2 has $n=2$ defenders and $T=4$ targets. Targets 11, 12, 21, 22 are organized in a $2\times 2$ matrix. Defender 1 has preferences $22 \succ _1 11 \succ _1 12 \succ _1 21$ (i.e., prefers diagonal targets attacked) while defender 2 has them in reverse, $21 \succ _2 12 \succ _2 11 \succ _2 22$ (i.e., prefers off diagonal targets attacked). Each has 2 schedules, $s_1^1=(1-\epsilon , 1, k\epsilon , 0)$, $s_2^1=(0, k\epsilon , 1, 1-\epsilon )$ and $s_1^2 = (1, 0, 1-\epsilon , k\epsilon )$, $s_2^2=(k\epsilon , 1-\epsilon , 0, 1)$, where $k \ge 1$, $0 \le \epsilon \ll 1$ and $k\epsilon < 1$.

Suppose (for now) that $\epsilon =0$ in Example 1. Then, defender 1 decides how to split its coverage across rows, while defender 2 the columns. Suppose $(\textbf{v}, t)$ is a NSE. If $t = 11$, defender 2 is incentivized to deviate to $\widehat{v}^2 = s_1^2$ regardless of $v^1$, since this always causes 12 to have the “lowest” coverage and $12 \succ _2 11$. The same may be said for $t=22$, $t=12$ and $t=21$, where the latter two have defender 1 deviating. This “cyclic” behavior (Fig. 2f) implies that no equilibrium exists.

The above argument is only partially correct. When $\epsilon =0$, Example 1 has a NSE $(\textbf{v}, 11)$ where $v^1=v^2=(0.5, 0.5, 0.5, 0.5)$. If defender 2 deviates to $\widehat{v}^2 = s_1^2$, the attacker tiebreaks, choosing target 22 over target 12, which hurts defender 2. It may be verified that this is indeed a NSE. Introducing $\epsilon =10^{-3}$ and $k=100$ fixes this, ensuring target 12 possesses the strictly lowest coverage after deviation regardless of $v^1$. The full derivation is deferred to the extended version.

The non-existence is caused by the rigid enforcement of schedules. For example, even though defender 1 prefers 11 to be attacked over 12, defending 11 through schedule $s^1_1$ forces it to simultaneously defend 12, which it rather not defend. Our fix expands the attainable coverage $V^i$: instead of clearance, defenders may provide less coverage than what they could have. This assumption was used by [16] and is quite reasonable. For example, a patroller may deliberately let down their guard at areas of lower priority, encouraging attacks there.

Assumption 2

(Subset-of-a-Schedule-is-Also-a-Schedule (SSAS))

$$\begin{aligned} V^i = \left\{ v \in \mathbb {R}_+^T \Bigg | \exists x^i \text { such that } \forall j \in [T] \ v(j) \le \sum _{s_z^i \in \mathcal {S}^i} x^i(s_z^i) \cdot s_{z}^i (j) \right\} . \end{aligned}$$

Fig. 3.

Left to right: reductions to obtain t-standard coverage for defender 1

Assumption 2 is obtained from Assumption 1 by replacing the equality constraint by an inequality. Checking if $v^i \in V^i$ is done efficiently using linear programs. Clearly, $V^i$ under SSAS is a superset of that under clearance. Under SSAS, Example 1 with $\epsilon =0$ has a NSE $(v^1, v^2, 11)$, where $v^1=(0, 0.5, 0.5, 0)$, $v_2 = (0, 0, 0, 1.0)$. Details, alongside the $\epsilon > 0$ case are in the extended version.

4.1 Existence and Computation of NSE Assuming SSAS

For now, we restrict ourselves to 2 defenders. Under SSAS, any NSE can be converted into a simpler canonical form, which we exploit to guarantee existence for all $\mathcal {S}^i$, together with a polynomial time algorithm. We present these results via a series of reductions. All proofs are deferred to the appendix.

Lemma 1

If $(v^1, v^2, t)$ is an NSE, then there exists another NSE $(\widetilde{v}^1, v^2, t)$ such that (i) $\widetilde{v}^1(t) = 0$ and (ii) $\widetilde{v}^1(j)=v^1(j)$ for all targets $j\ne t \in [T]$.

Applying Lemma 1 to each defender guarantees that each NSE $(\textbf{v}, t)$ must correspond to an NSE with zero coverage on t. If we knew the attacked target t, we can reduce our search to coverage profiles with zero coverage on t. Now, for some NSE $(\textbf{v}, t)$ consider defender 1’s coverage profile $v^1$ based on defender 2’s preference ordering. For illustration, assume WLOG that the targets are ordered in decreasing order of defender 2’s preference of attacked target. An example is shown in Fig. 3(a), where $t=4$ and $T=8$, and the height of each bar corresponds to $v^1(j)$ for each target j. Lemma 1 simply says that the coverage profile in Fig. 3(b) would also constitute an NSE.

Suppose defender 1’s goal is to discourage defender 2 from deviating. Since target 4 is attacked, defender 2 benefits from deviating if and only if it can induce some target in $\mathcal {T}^{\succ _2}_4$ to be the new attack target. It does so by increasing coverage over targets in $\mathcal {T}^{\preceq _2}_4$ (potentially reducing $v^2$ elsewhere). Conversely, defender 1 prevents this deviation by ensuring that its minimum coverage $v^1$ over $\mathcal {T}^{\succ _2}_4$ is as high as possible. Since $v^1$ shown in in Fig. 3 is part of an NSE, defender 2 does not have a coverage $\widehat{v}^2$ such that $\widehat{v}^2(j) > 3$ for all $\mathcal {T}^{\preceq _2}_4$. If such a $\widehat{v}^2$ existed, defender 2 could simply deviate to that (placing no coverage on targets in $\mathcal {T}^{\succ _2}_4$), This induces either target $6 \succ _2 4$ to be attacked. Hence, for defender 1 to discourage deviations from defender 2, it should reduce $v^1$ in all targets belonging to $\mathcal {T}^{\succ _2}_4$ to be 3, and similarly for all $\mathcal {T}^{\preceq _2}_4$, as shown in Fig. 3(c). This new coverage remains a NSE. Lemma 2 formalizes the above argument.

Lemma 2

Suppose $(v^1, v^2, t)$ is an NSE with $v^1(t) = v^2(t) = 0$. Then there exists another coverage $\widetilde{v}^1$ where (i) $\widetilde{v}^1(t) = 0$, (ii) $\widetilde{v}^1(j) = 0$ for all $j \prec _2 t$, and (iii) $\widetilde{v}^1(j) = \min _{k \succ _2 t }v^1(k)$ for all $j \succ _2 t$, such that $(\widetilde{v}^1, v^2, t)$ is an NSE.

Lemma 2 allows us to transform any NSE $(v^1, v^2, t)$ into a new NSE by adjusting $v^1$ appropriately. Clearly, a similar process can be done for defender 2 and $v^2$. Applying Lemma 2 for both player yields coverages with simpler structures.

Definition 6

(t-standard Coverage). For fixed $t \in [T]$, $v^1 \in V^1$ is a t-standard coverage for defender 1 if (i) there exists $h^1 \ge 0$ and $v^1(j) = h^1$ for all $j \succ _2 t$, and (ii) $v^1(j) = 0$ for all $j \preceq _2 t$. The same holds for defender 2.

Reducing a coverage in an NSE $(v^1, v^2, t)$ into one containing t-standard coverage is done by first applying Lemma 1 to each player, followed by Lemma 2 to each player. Figure 3 illustrates how $v^1$ evolves according to this reduction as per the prior discussions. Let $\mathcal {H}$ be the (possibly empty) set of NSE $(v^1, v^2, t)$ such that both $v^1$ and $v^2$ are t-standard coverage. For a fixed $t\in [T]$, we define $\mathcal {H}_t$ to be all NSE $(v^1, v^2, t)$ in $\mathcal {H}$ where t is attacked. By definition, we have (i) $\mathcal {H}_t$ and $\mathcal {H}_{t'}$ are disjoint when $t \ne t'$, and (ii) $\mathcal {H}=\bigcup _{t \in [T]} \mathcal {H}_t$. The existence of NSE is equivalent to saying that $\mathcal {H}$ is non-empty.

Our algorithm for computing an NSE under Assumption 2 is straightforward: iterate over all targets $t \in [T]$ and search for some element in $\mathcal {H}_t$. Finding some element (if it exists) of $\mathcal {H}_t$ for any t is done in polynomial time by solving 4 linear programs with size polynomial in $S^i$, n and T, as shown in Algorithm 1. MaximinCov$(\mathcal {T}, V^i)$ is an oracle finding the coverage $v^i \in V^i$ which maximizes the minimum coverage over a given set of targets $\mathcal {T}$. MaximinCov returns $+ \infty$ when $\mathcal {T} = \emptyset$. When $V^i$ is defined by a finite set of schedules $\mathcal {S}^i$ and SSAS, MaximinCov can be implemented via linear programming (Algorithm 2).

Fig. 4.

Left: Solving NSE in 2 defender games. Right: A linear program finding the Maximin coverage for defender i when $V^i$ is given by schedules $\mathcal {S}^i$ and SSAS.

Theorem 1

Under the SSAS assumption (Assumption 2), $\mathcal {H} \ne \emptyset$, i.e., an NSE always exists. Consequently, Algorithm 1 is guaranteed to return an NSE.

4.2 Efficiency of NSE

Blindly applying Algorithm 1 can lead to a pathology where the attacked target is undesirable for both players, i.e., a NSE $(\textbf{v}, t)$ can have $v^1(\widetilde{t}) \ge 0$ and $v^2(\widetilde{t}) \ge 0$ when $\widetilde{t} \succ _1 t$ and $\widetilde{t} \succ _2 t$. For example, suppose $1 \succ _1 2 \succ _1 3$ and $1 \succ _2 2 \succ _2 3$ where defenders possess identity schedules, i.e., $\mathcal {S}^i = \{ (1, 0, 0), (0, 1, 0), (0, 0, 1) \}$. Setting $\widetilde{v}^1=\widetilde{v}^2=(1,0,0)$, we find that $(\mathbf {\widetilde{v}}, 2)$ is an NSE as it is AIC and neither defender can give target 1 a coverage strictly greater than 1 by deviating. However, both defenders prefer target 1 to be attacked. Indeed, a trivial NSE is $(\textbf{v}, 1)$ where $v^1=v^2=(0, 0, 0)$, i.e., the profile $(\textbf{v}, 1)$ “Pareto dominates” $(\mathbf {\widetilde{v}}, 2)$.

Definition 7 (Inefficiency)

An NSE $(v^1, v^2, t) \in \mathcal {H}_t$ is inefficient (resp. efficient) if and only if there exists j where $j \succ _1 t$ and $j \succ _2 t$. Targets constituting inefficient (resp. efficient) NSE are called inefficient targets.

Targets where $\mathcal {H}_t=\emptyset$ are neither efficient nor inefficient. There may exist multiple efficient NSE. However, we show that efficient NSE exists under SSAS.

Lemma 3

Let $j, t \in [T]$ such that $\mathcal {H}_t\ne \emptyset$, $j \succ _1 t$ and $j \succ _2 t$. Then, $\mathcal {H}_j\ne \emptyset$.

4.3 Exploiting Additional Structure in $V^i$

We now move towards characterizing and solving for equilibrium in two classes of games which contain even more structure in $V^i$.

Finding NSE Under Monotone Schedules. The first is the case of Monotone Schedules, where each defender’s schedule places less coverage on targets preferred to be attacked. This allows us to efficiently solve for NSE when $n\ge 2$.

Assumption 3

(Monotone schedules (MS)). A schedule $s^i_z \in \mathcal {S}^i$ is Monotone if $j \succ _i t \implies s^i_z(j) \le s^i_z(t)$. The game possesses Monotone Schedules (MS) if all defender schedules are monotone.

Theorem 2

Under both MS and SSAS, a NSE exists for $n \ge 2$. It can be computed in polynomial time in the number of schedules, n, and T.

Proof

Define $\pi _i(t) \in [T]$ such that target t is the $\pi _i(t)$-th preferred target of defender i. Define a matrix $\mathcal {M}\in \mathbb {R}^{n\times T}$, where $\mathcal {M}_{i, \pi _i(j)} = \textsc {MaximinCov}(\mathcal {T}_{j}^{\preceq _i}, V^i)$ for each defender i and target j.⁴ $\mathcal {M}$ is non-decreasing from left to right. Let $F(t) = \max _{i} \mathcal {M}_{i, \pi _i(t)}$. For convenience, we assume $F(t)\ne F(t')$ for $t\ne t'$ such that $\mathop {\textrm{Argmin}}\limits \nolimits _{t} F(t)=\{ k^* \}$. We construct a NSE $(\textbf{v}, k^*)$ where:

• 1. for all defenders i, $v^i(k^*) = 0$ such that $v^{total}(k^*)=0$, and

• 2. for every $t \ne k^*$, we find a defender i where $\mathcal {M}_{i, \pi _i(t)} = F(t)$. We set coverage $v^i(t) = F(k^*)$ and $v^{i'}(t) = 0$ for all $i' \in [n] \backslash \{i\}$.

Clearly, the above algorithm runs polynomial time. In Step 2, we have by definition at least one defender i satisfying $\mathcal {M}_{i, \pi _i(t)} = F(t)$. We first show that $\textbf{v}$ is achievable, i.e., $v^i \in V^i$ for all defenders i. Fix $i \in [n]$. Let $\mathcal {T}$ be the set of targets covered by it, each with coverage $F(k^*)$. By Step 1, $k^*\notin \mathcal {T}$. Furthermore, $\mathcal {T} \subseteq \mathcal {T}_{k^*}^{\prec _i}$. If target $j\in \mathcal {T}$ and $j \succ _i k^*$, then $\mathcal {M}_{i, \pi _i(j)}\le \mathcal {M}_{i, \pi _i(k^*)}$ since $\mathcal {M}$ is non-decreasing. This contradicts $\mathcal {M}_{i, \pi _i(j)} = F(j) > F(k^*) \ge \mathcal {M}_{i, \pi _i(k^*)}$ from the definition of F and $k^*$. Now, let $j^*$ be defender i’s most preferred target in $\mathcal {T}$. Consider a coverage $\widetilde{v}^i$ with $\widetilde{v}^i(j) = F(j^*)$ for $j \preceq _i j^*$ and $\widetilde{v}^i(j) = 0$ otherwise. In Step 2, $v^i(j^*) > 0$ implies $F(j^*) = \mathcal {M}_{i, \pi _i(j^*)}$, because only targets j such that $F(j) = \mathcal {M}_{i, \pi _i(j)}$ are covered by i. Hence, $F(j^*) = \mathcal {M}_{i, \pi _i(j^*)} = \textsc {MaximinCov}(\mathcal {T}_{j^*}^{\preceq _i}, V^i)$ and $\widetilde{v}^i \in V^i$. Since $F(j^*)\ge F(k^*)$, $\widetilde{v}^i(j) \ge v^i(j)$ for $j \in [T]$, i.e., coverage of $\widetilde{v}^i$ is no less than $v^i$. Because $\widetilde{v}^i \in V^i$, $v^i\in V^i$ by SSAS.

Lastly, we show that $(\textbf{v}, k^*)$ is indeed an NSE. It is AIC since $v^{total}(k^*) = 0$. Next, we prove that for any defender i, any $\widehat{v}^i\in V^i$ and any target $t \succ _i k^*$, $(v^1, \cdots , \widehat{v}^i, \cdots , v^n, t)$ is not i-WAIC. First, we show that $\widehat{v}^{total}(t) \ge F(k^*)$. We have $\widehat{v}^{total}(t) = \widehat{v}^i(t) + \sum _{i'\ne i}v^{i'}(t) \ge \sum _{i'\ne i}v^{i'}(t)$. Since $v^i$ has no coverage on $\mathcal {T}_{k^*}^{\succ _i}$, $v^i(t) = 0$. Therefore, $\sum _{i'\ne i}v^{i'}(t) = v^{total}(t) = F(k^*)$. We have $\widehat{v}^{total}(t) \ge \sum _{i'\ne i}v^{i'}(t) = F(k^*)$. Second, $\widehat{v}^{total}(k^*)\le F(k^*)$. $\widehat{v}^{total}(k^*) = \widehat{v}^{i}(k^*)$ since $v^{i'}(k^*) = 0$ for any $i'\ne i$. We claim that $\widehat{v}^{i}(k^*) \le F(k^*)$. If $\widehat{v}^{i}(k^*) > F(k^*)$, defender i can cover all targets in $\mathcal {T}_{k^*}^{\preceq _i}$ with $\widehat{v}^{i}(k^*) > F(k^*)$ by MS. Therefore, $\mathcal {M}_{i, \pi _i(k^*)} > F(k^*)$, which conflicts with $F(k^*) = \max _{i'} \mathcal {M}_{i', \pi _{i'}(k^*)}$. We have $\widehat{v}^{total}(k^*) = \widehat{v}^{i}(k^*) \le F(k^*)$. In conclusion, $\widehat{v}^{total}(t) \ge \widehat{v}^{total}(k^*)$. If $t\in B(\widehat{v}^{total})$, $k^*\in B(\widehat{v}^{total})$ holds, so $(v^1, \cdots , \widehat{v}^i, \cdots , v^n, t)$ is not i-WAIC. $(\textbf{v}, k^*)$ is i-IC. $\blacksquare$

Efficient Solvers when $V^i$ is Compactly Represented. In Algorithm 1, we were required to optimize over t-standard coverage for each defender. This involves solving linear programs. Unfortunately, the number of schedules can be prohibitively large. For example, in patrolling on layered networks, the number of schedules is exponential in its depth and is computationally infeasible for large games. Fortunately, both our proof of existence and algorithm operate in the space of attainable coverage $V^i$ and not directly on x and $S^i$. In our example, $V^i$ can be expressed as flows in the network (and more generally, any directed acyclic graph with a source and a sink), which in turn is a polyhedron with a polynomial number of constraints (in terms of the number of edges and vertices).

Fig. 5.

Public Security Game with $m=4$, $r=2$, using the L1-distance. (a) Preference profiles for defenders. Size of nodes represent relative values of targets for each defender. (b) Coverage by the defender 1, $v^1$ by evenly distributing resource between buildings marked by in green. Darker targets enjoy a higher coverage. Note that overlapping regions get double the coverage. (c) Same as (b), but for defender 2. (d) Total coverage $v^{total}$ accrued over both entities. (Color figure online)

5 Experiments

Our experiments are conducted on an Intel(R) Core(TM) i7-7700K CPU @ 4.20 GHz. We use Gurobi [10] to solve linear programs. We seek to answer the following. (i) Can NSE be practically computed for reasonable environments? How does computational time scale with parameters such as T, $S^i$, $V^i$, and n? (ii) How does an NSE look like qualitatively? When $n=2$, how many NSE are efficient? What proportion of targets are included in some NSE? (iii) What is the quality (in terms of the attacked target) in the multiple-defender setting as compared to single defender settings? We explore 3 synthetically generated games, where defender preferences $\succ _i$ are generated uniformly at random.

• Randomly Generated Schedules (RGS). We generate games with random schedules where each $s^i_j$ is a random integer from [0, 10], and the number of schedules $S^i$, T are specified. In some cases, we limit each schedule’s support size to be smaller than T (with the support again randomly selected).

• Public Security on Grids (PSG). An event is held in the streets of Manhattan, which we abstract as a $m \times m$ grid (Fig. 5), where each vertex represents a target (building). The security for the event is managed by two entities: the city police and VIP security detail, each with different priorities. Each places checkpoints distributed across buildings in the city, which provide coverage in a radius r. The level of coverage is dependent on the average number of officers allocated to it. An example with $m=4, r=2$ is shown in Fig. 5.

• Patrolling on Layered Networks (PLN). We follow the motivating example in Sect. 2, varying the width and number of layers. Each patrol can only change its “level” (position on the y-axis) by at most one step between layers. Unlike the public security game, there are now an exponential number of paths, hence computational costs become an important consideration as well.

Fig. 6.

Wallclock time to find one efficient NSE using the algorithm in Fig. 4.

5.1 Computational Costs of Computing NSE

We first restrict ourselves to 2-defender settings under SASS. We evaluate computational efficiency of the algorithms of Fig. 4, with results for RGS, PSG and PLN summarized in Figs. 6 and 7. For PLN, we utilized the efficient method in Sect. 4.3. We ran 100 trials for each parameter setting and report the mean computation time and their standard errors (which were mostly negligible).

In RGS, we varied T, $S^i$ and the support size of each schedule. As expected, the average running time increases superlinearly with T (Fig. 6a), since the loop in Algorithm 1 is repeated more times, and calls to MaximinCov also incur a higher cost. However, Fig. 6b shows that as $S^i$ increases, the required running time increases linearly. This is unexpected, since $S^i$ is involved in the MaximinCov subroutine, whose constraint matrix grows linearly with $S^i$. This suggests that the runtime of MaximinCov grows linearly with $S^i$, atypical of linear programs. This could be because (i) our problems are small by standards of modern solvers, or (ii) the solver exploits additional structure under the hood. Lastly, Fig. 6c shows that adjusting support size does not impact running time. This is unsurprising since the solver is not explicitly told to exploit sparsity.

In PSG, we varied T by increasing the grid size m from 4 to 10. As with RGS, Fig. 7aa running time superlinearly with T. We also indirectly adjusted the support size by adjusting r, the radius of security coverage (Fig. 7b). Once again, we did not notice any appreciable difference in running times. Similarly for PLN, we note a superlinear growth in running time as the network enlarges, be it from increasing layers or width of the network (Fig. 7c and 7d).

Fig. 7.

Top: Wallclock time to compute NSE for PSG using the algorithm in Fig. 4. Bottom: Computing NSE for PLN using the method in Sect. 4.3.

Fig. 8.

Top: Running time for RGS under MSS assumptions. Top: Wallclock time as n increases. Bottom: Running time as T and $S^i$ vary.

We now examine multiple defenders in RGS under SSAS and MSS. Again, we ran 100 rounds for each scenario and report the means (standard errors were negligible) in Fig. 8. We observe running times increasing linearly with n and schedules (omitted due to space constraints), but superlinearly with T.

5.2 Quality of NSE Computed

We now investigate the quality of NSE that are computed with 2 defenders, under the SSAS assumption. If there only defender 1 existed (e.g., $V^2 = \{ 0 \})$), then defender 1 simply chooses $v^1 = 0$ and t to be its most desired target to be attacked. The existence of defender 2 makes it such that both defenders must compromise to reach an NSE, with the target to be attacked worsened from defender 1’s perspective. In essence, this is the “cost of partnership”.

We investigate this degradation in quality of attacked target (in ordinal terms) from the perspective of a single defender. In each run, we compute all the efficient NSE and their attacked target’s rank in terms of the preference order $\succ _i$. This rank suboptimality is a measure of the degradation of policy. Since there are multiple efficient NSE, we consider 3 cases: (i) the optimistic case where we tiebreak to benefit defender 1, (ii) tiebreaking by averaging and (iii) the pessimistic case we tiebreak against defender 1. For each of these settings, we run the experiment 100 times and report the frequency of every rank suboptimality (Fig. 9).

Fig. 9.

Rank suboptimality. From top to bottom: RGS with 10 targets, schedules, and full suport, PSG with $m=4$, $r=2$, PLN with 5 layers each of width 5.

Fig. 10.

Top (resp. bottom): #targets (resp. ratio over T) that are efficient NSE as T increases. Left to right: Results for RGS, PSG and PLN respectively.

5.3 Number of Targets Included in NSE

Recall that each of the T targets may be efficient, inefficient or not part of any NSE. We investigate for randomly generated 2 defender games in RGS, PSG and PLN the number and proportion of these targets as T varies. For RGS, we fix $S^i = 200$. Our results are reported in Fig. 10. We can see that in all our experiments, the number of efficient targets (or NSE) increase linearly with T, the proportion of such targets decreases and tapers off at around 100 targets.

6 Conclusion

In this paper, we explored the problem of multidefender security games in the presence of schedules in the restricted setting of coverage dependant utilities. We show that even in this restricted case, equilibrium may not exist under clearance constraints in contrast to prior work. We show that equilibrium is guaranteed under SSAS and present polynomial time solvers, as well as several extensions. Future work include removing the restriction on coverage dependant utilities as well as extensions to the non-additive or uncoordinated setting.

A Appendix

1.1 A.1 Proof of Lemma 1

Proof

Since $v^1\in V^1$ and $\widetilde{v}^1(j) \le v^1(j)$ for all $j \in [T]$, we have $\widetilde{v}^1\in V^1$ by Assumption 2. We now show that $(\widetilde{v}^1, v^2, t)$ is AIC, 1-IC, and 2-IC.

• 1. $(\widetilde{v}^1, v^2, t)$ is AIC. For all $j\in [T]$ and $j\ne t$, we have

  $$\begin{aligned} \widetilde{v}^1(j) + v^2(j) \underbrace{= v^1(j) + v^2(j)}_{\text {definition of }\widetilde{v}^1} \ge \underbrace{v^1(t) + v^2(t)}_{(v^1, v^2, t) \text { is AIC}} \ge \underbrace{\widetilde{v}^1(t) + v^2(t)}_{\text {by definition of }\widetilde{v}^1}. \end{aligned}$$

• 2. $(\widetilde{v}^1, v^2, t)$ is 1-IC. If not, there exists $\widehat{v}^1\in \mathcal {V}^1, j\succ _1 t$ where $(\widehat{v}^1, v^2, j)$ is 1-WAIC, implying $(v^1, v^2, t)$ is not 1-IC and not an NSE.

• 3. $(\widetilde{v}^1, v^2, t)$ is 2-IC. Suppose otherwise. Then there exists $\widehat{v}^2\in \mathcal {V}^2, j \succ _2 t$ where $(\widetilde{v}^1, \widehat{v}^2, j)$ is 2-WAIC, implying that $\widetilde{v}^1(k) +\widehat{v}^2(k) > \widetilde{v}^1(j) +\widehat{v}^2(j)$ for $k \prec _2 j$, and $\widetilde{v}^1(k) +\widehat{v}^2(k) \ge \widetilde{v}^1(j) +\widehat{v}^2(j)$ for $k \succ _2 j$. Then for any $k \succ _2 j (\succ _2 t)$, $\widetilde{v}^1(k) +\widehat{v}^2(k) \ge \widetilde{v}^1(j) +\widehat{v}^2(j)$ indicates that $v^1(k) +\widehat{v}^2(k) \ge v^1(j) +\widehat{v}^2(j)$ by definition of $\widetilde{v}^1$ that $\widetilde{v}^1(k) = v^1(k), \widetilde{v}^1(j) = v^1(j)$. Besides, for any $k\prec _2 j$,

  $$\begin{aligned} v^1(k) + \widehat{v}^2(k) \underbrace{\ge \widetilde{v}^1(k) + \widehat{v}^2(k)}_{\text {by definition of }\widetilde{v}^1} > \underbrace{\widetilde{v}^1(j) + \widehat{v}^2(j)}_{(\widetilde{v}^1, \widehat{v}^2, j)\text { is 2-WAIC}} = \underbrace{v^1(j) + \widehat{v}^2(j)}_{\text {by definition of }\widetilde{v}^1}. \end{aligned}$$

  Since $(v^1, \widehat{v}^2, j)$ is 2-WAIC, $(v^1, v^2, t)$ is not 2-IC and not an NSE.

1.2 A.2 Proof of Lemma 2

Proof

$v^1\in V^1$ and $\widetilde{v}^1$ has no more coverage than $v^1$, so $\widetilde{v}^1\in V^1$ by the SSAS assumption. By the definition of NSE, it is sufficient to show that $(\widetilde{v}^1, v^2, t)$ is AIC, 1-IC, and 2-IC to prove the Lemma.

• 1. $(\widetilde{v}^1, v^2, t)$ is AIC. $t\in B(\widetilde{v}^1, v^2)$ because $\widetilde{v}^1(t) + v^2(t) = 0$.

• 2. $(\widetilde{v}^1, v^2, t)$ is 1-IC. If not, then there exists $\widehat{v}^1\in V^1, j\succ _1 t$ such that $(\widehat{v}^1, v^2, j)$ is 1-WAIC. Therefore, $(v^1, v^2, t)$ is also not 1-IC, contradicting the assumption that $(v^1, v^2, t)$ is an NSE.

• 3. $(\widetilde{v}^1, v^2, t)$ is 2-IC. We prove this by contradiction. Suppose $(\widetilde{v}^1, v^2, t)$ is not 2-IC, then there exists $\widehat{v}^2\in V^2, j \succ _2 t$ where $(\widetilde{v}^1, \widehat{v}^2, j)$ is 2-WAIC. By definition of 2-WAIC, we have that $\widetilde{v}^1(k') +\widehat{v}^2(k') > \widetilde{v}^1(j) +\widehat{v}^2(j)$ for any target $k' \prec _2 j$, and $\widetilde{v}^1(k') +\widehat{v}^2(k') \ge \widetilde{v}^1(j) +\widehat{v}^2(j)$ for any target $k' \succ _2 j$. Consider $u^2\in V^2$ such that $u^2(k') = \widehat{v}^2(k')$ for any target $k' \preceq _2 t$ and $u^2(k') = 0$ for any target $k' \succ _2 t$. Notice that there always exist a unique target $k \in [T]$ such that $(v^1, u^2, k)$ is 2-WAIC. We claim that if k is the target that $(v^1, u^2, k)$ is 2-WAIC, then $k \succ _2 t$. We prove this by excluding other targets $e \preceq _2 t$. Notice that there is a target $m \succ _2 t$ that $v^1(m) = \min _{{k'}\succ _2 t }v^1({k'})$. Consider a target $e \preceq _2 t$, then

  $$\begin{aligned} v^1(e) + u^2(e) &\underbrace{\ge \widetilde{v}^1(e) + u^2(e)}_{\text {by definition of }\widetilde{v}^1} \underbrace{=\widetilde{v}^1(e) + \widehat{v}^2(e)}_{\text {by definition of }u^2} \underbrace{> \min _{{k'}\succ _2 t}\{\widetilde{v}^1({k'}) + \widehat{v}^2({k'})\}}_{(\widetilde{v}^1, \widehat{v}^2, j)\text { is 2-WAIC}} \\ & \underbrace{\ge \min _{{k'}\succ _2 t}\widetilde{v}^1({k'})}_{\widehat{v}^2({k'})\ge 0} \underbrace{ = v^1(m)}_{\text {by definition of }m} \underbrace{ = v^1(m) + u^2(m)}_{u^2(m) = 0}. \end{aligned}$$

  Thus, e has more coverage than m, so $(v^1, u^2, e)$ is not 2-WAIC. Then $k \preceq _2 t$ does not hold. There exists a target $k \succ _2 t$ such that $(v^1, u^2, k)$ is 2-WAIC, so $(v^1, v^2, t)$ is not 2-IC, which contradicts that $(v^1, v^2, t)$ is an NSE. $\blacksquare$

1.3 A.3 Proof of Theorem 1

To better understand the structure of $\mathcal {H}$, we introduce partial sets $\mathcal {H}^1_t\subset V^1, \mathcal {H}^2_t\subset V^2$ for $\mathcal {H}_t$ and show how they compose the set $\mathcal {H}_t$.

Definition 8

$\mathcal {H}_t^1$ is the set of $v^1\in V^1$ such that there exists $h^1\ge 0$, $v^1(j) = h^1$ for any target $j \in \mathcal {T}_t^{\succ _2}$, $v^1(j) = 0$ for any target $j \in \mathcal {T}_t^{\preceq _2}$,and there does not exist $j\succ _2 t$ and $\widehat{v}^2\in V^2$, $(v^1, \widehat{v}^2, j)$ is 2-WAIC. Similar for $\mathcal {H}_t^2$.

Theorem 3

$\mathcal {H}_t = \mathcal {H}^1_t \times \mathcal {H}^2_t \times \{t\}$.

Proof

For any $(v^1, v^2, t)\in \mathcal {H}_t$, $v^1$ and $v^2$ are t-standard coverage. Since $\mathcal {H}_t$ only contains NSEs, $(v^1, v^2, t)$ is 1-IC and 2-IC. Thus, $v^1\in \mathcal {H}^1_t, v^2\in \mathcal {H}^2_t$. We now show that for any coverage $v^1\in \mathcal {H}_t^1$ and $v^2\in \mathcal {H}_t^2$, $(v^1, v^2, t)\in \mathcal {H}_t$. First, $(v^1, v^2, t)$ is an NSE. $(v^1, v^2, t)$ is AIC because $v^1(t) = v^2(t) = 0$. Also, $(v^1, v^2, t)$ is 1-IC and 2-IC by definition of $\mathcal {H}^1_t$ and $\mathcal {H}^2_t$. Second, $v^1$ and $v^2$ are t-standard coverage. Thus, $(v^1, v^2, t) \in \mathcal {H}_t$. $\blacksquare$

Theorem 3 decomposes the space of $\mathcal {H}_t$. Next we consider how to compute $\mathcal {H}^1_t$ and $\mathcal {H}^2_t$, which provides us an NSE in $\mathcal {H}_t$. We first consider the reduction of the set containing deviation strategies.

Lemma 4

For a target t and a coverage $v^1 \in \mathcal {H}_t^1$, if there is a $\widehat{v}^2\in V^2$ and $j \succ _2 t$ such that $(v^1, \widehat{v}^2, j)$ is 2-WAIC, we construct $u^2\in V^2$ such that $u^2(k) = 0$ for $k \in \mathcal {T}_t^{\succ _2}$ and $u^2(k) = \min _{k' \preceq _2 t} \widehat{v}^2(k')$ for $k \in \mathcal {T}_t^{\preceq _2}$, then there exists a target $m\succ _2 t$ such that $(v^1, u^2, m)$ is 2-WAIC.

Proof

In a 2-WAIC strategy profile $(v^1, \widehat{v}^2, j)$ and $j\succ _2 t$, $v^1(k) + \widehat{v}^2(k) > v^1(j) + \widehat{v}^2(j)$ for any target $k\preceq _2 t$. Since $v^1\in \mathcal {H}_t^1$, $v^1(k) = 0$ for any target $k\preceq _2 t$. So, $\min _{k\preceq _2 t}\widehat{v}^2(k) > v^1(j) + \widehat{v}^2(j)$. We have $u^2(k) > v^1(j) + \widehat{v}^2(j)$ by definition of u, so any target $k\in \mathcal {T}_t^{\preceq _2}$ is not the attacked target. There always exists a target m such that $(v^1, u^2, m)$ is 2-WAIC, and here $m \succ _2 t$. $\blacksquare$

Lemma 4 reduces the deviation $\widehat{v}^2$ to $u^2$ with a canonical structure that $u^2(k)$ are equal for targets $k \in \mathcal {T}_t^{\preceq _2}$, but $u^2(k) = 0$ elsewhere. The computation of $u^2$ is related to the oracle $\textsc {MaximinCov}$. For convenience, we use $M^i(\mathcal {T})$ instead of $\textsc {MaximinCov}(\mathcal {T}, V^i)$ when the set of coverage is default to be $V^i$. Formally, $M^i(\mathcal {T}) = \max _{v^i \in V^i}\min _{j \in \mathcal {T}} v^i(j)$ for $\mathcal {T} \ne \emptyset$, and $M^i(\mathcal {T}) = + \infty$ for $\mathcal {T} = \emptyset$. With this notation, we give a sufficient and necessary condition for $\mathcal {H}_t^i \ne \emptyset$.

Theorem 4

$\mathcal {H}_t^1 \ne \emptyset$ if and only if $M^1(\mathcal {T}_t^{\succ _2}) \ge M^2(\mathcal {T}_t^{\preceq _2})$. Similarly, $\mathcal {H}_t^2 \ne \emptyset$ if and only if $M^2(\mathcal {T}_t^{\succ _1}) \ge M^1(\mathcal {T}_t^{\preceq _1})$.

Proof

We prove the first claim for $\mathcal {H}_t^1\ne \emptyset$, and it is same for $\mathcal {H}_t^2\ne \emptyset$.

• 1. When $M^1(\mathcal {T}_t^{\succ _2}) \ge M^2(\mathcal {T}_t^{\preceq _2})$, we consider a coverage $v^1\in V^1$ of defender 1 such that $v^1(k) = M^1(\mathcal {T}_t^{\succ _2})$ for target $k \succ _2 t$, and $v^1(k) = 0$ elsewhere. For any coverage $\widehat{v}^2 \in V^2$, there is a target $m\in \mathcal {T}_t^{\preceq _2}$ such that $v^1(m) + \widehat{v}^2(m) \le M^2(\mathcal {T}_t^{\preceq _2}) \le v^1(k)$ for any target $k\in \mathcal {T}_t^{\succ _2}$. Any target $k\in \mathcal {T}_t^{\succ _2}$ has no less coverage than target m given coverage $(v^1, \widehat{v}^2)$, so there does not exist target $j\succ _2 t$ such that $(v^1, \widehat{v}^2, j)$ is 2-WAIC. Thus, $v^1\in \mathcal {H}_t^1$ by definition.

• 2. When $M^1(\mathcal {T}_t^{\succ _2}) < M^2(\mathcal {T}_t^{\preceq _2})$, we want to show that $\mathcal {H}_t^1 = \emptyset$. $M^1(\mathcal {T}_t^{\succ _2}) \ne +\infty$, so for any $v^1\in V^1$, there exists target $j\succ _2 t$ such that $v^1(j) \le M^1(\mathcal {T}_t^{\succ _2})$. Then consider a coverage $\widehat{v}^2\in V^2$ of defender 2 such that $\widehat{v}^2(k) = M^2(\mathcal {T}_t^{\preceq _2})$ for targets $k\in \mathcal {T}_t^{\preceq _2}$ and $\widehat{v}^2(k) = 0$ for other targets. In the coverage profile $(v^1, \widehat{v}^2)$, target $k\in \mathcal {T}_t^{\preceq _2}$ has strictly more coverage than target j. Notice that there always exists a target $j'$ such that $(v^1, \widehat{v}^2, j')$ is 2-WAIC. Thus, for any $v^1\in V^1$, there exists $\widehat{v}^2\in V^2$, such that there exists $j'\succ _2 t$ and $(v^1, \widehat{v}^2, j')$ is 2-WAIC. Therefore, $\mathcal {H}_t^1 = \emptyset$. $\blacksquare$

Corollary 1

For any defender $i\in [2]$, there exists $t\in [T]$ such that $\mathcal {H}_t^i \ne \emptyset$.

Proof

Let $i'\ne i$ be another defender. There exists a target t such that for any target $j \in [T]$, $t \succeq _{i'} j$. Then $M^{i}(\mathcal {T}_t^{\succ _{i'}}) = M^{i}(\emptyset ) = +\infty$. However, $M^{i'}(\mathcal {T}_k^{\preceq {i'}}) = M^{i'}([T])$ is finite. Therefore, $\mathcal {H}_t^i \ne \emptyset$. $\blacksquare$

Lemma 5

For any set of targets $\mathcal {T}' \subset \mathcal {T}$, $M_i(\mathcal {T}')\ge M_i(\mathcal {T})$ holds.

Proof

Let $v^{i*}$ be the coverage when $M_i(\mathcal {T})$ achieves the maximum. Let $v^i = v^{i *}$, then we have $\min _{t_j \in \mathcal {T}'} v^i(j) \ge M_{i}(\mathcal {T}).$ Therefore $M_i(\mathcal {T}') \ge M_i(\mathcal {T})$. $\blacksquare$

Lemma 6

For two defenders $i, i'$ and targets $t \succ _{i'} j$, if $\mathcal {H}_j^i \ne \emptyset$, then $\mathcal {H}_t^i \ne \emptyset$.

Proof

Since $t \succ _{i'} j$, we have $\mathcal {T}_t^{\succ _{i'}} \subset \mathcal {T}_j^{\succ _{i'}}$ and $\mathcal {T}_j^{\preceq _{i'}} \subset \mathcal {T}_t^{\preceq _{i'}}$. By $\mathcal {H}_j^i \ne \emptyset$, we have $M^i(\mathcal {T}_j^{\succ _{i'}}) \ge M^{i'}(\mathcal {T}_j^{\preceq _{i'}})$. Then using Lemma 5, we get $M^i(\mathcal {T}_t^{\succ _{i'}}) \ge M^i(\mathcal {T}_j^{\succ _{i'}}) \ge M^{i'}(\mathcal {T}_j^{\preceq _{i'}}) \ge M^{i'}(\mathcal {T}_t^{\preceq _{i'}})$. By Theorem 4, $\mathcal {H}_k^i \ne \emptyset$. $\blacksquare$

Theorem 5

$\mathcal {H}\ne \emptyset$.

Proof

Suppose $\mathcal {T}^1 = \{t\in [T] | \mathcal {H}_t^2 \ne \emptyset \}$ and $\mathcal {T}^2 = \{t\in [T] | \mathcal {H}_t^1 \ne \emptyset \}$. By Corollary 1, $\mathcal {T}^1, \mathcal {T}^2 \ne \emptyset$ and $\mathcal {T}^2 \ne \emptyset$. There is a unique ${j_1} \in \mathcal {T}^1$ (${j_2} \in \mathcal {T}^2$) such that for any $t \in \mathcal {T}^1$, $t \succeq _1 {j_1}$ (for any $t \in \mathcal {T}^2$, $t \succeq _2 {j_2}$). It is sufficient to show that $\mathcal {T}^1 \cap \mathcal {T}^2 \ne \emptyset$. If we show this, then there is a target $j\in \mathcal {T}^1\cap \mathcal {T}^2$. We have $\mathcal {H}_j^1\ne \emptyset , \mathcal {H}_j^2\ne \emptyset$, and thus $\mathcal {H}\ne \emptyset$. Next we prove $\mathcal {T}^1 \cap \mathcal {T}^2 \ne \emptyset$ by contradiction.

Suppose $\mathcal {T}^1 \cap \mathcal {T}^2 = \emptyset$. Since $\mathcal {T}^1, \mathcal {T}^2 \ne \emptyset$ and $\mathcal {T}^1 \cap \mathcal {T}^2 = \emptyset$, we have $\overline{\mathcal {T}^1} = [T]\setminus \mathcal {T}^1\ne \emptyset$, and $\overline{\mathcal {T}^2} = [T]\setminus \mathcal {T}^2\ne \emptyset$. There is a unique ${k_1}\in \overline{\mathcal {T}^1}$ (${k_2}\in \overline{\mathcal {T}^2}$) such that for any $t\in \overline{\mathcal {T}^1}$, ${k_1} \succeq _1 t$ (for any $t\in \overline{\mathcal {T}^2}$, ${k_2} \succeq _2 t$). By Lemma 6, for any target $t \succ _1 {j_1}$, $t \in \mathcal {T}^1$, and for any target $t \succ _2 {j_2}$, $t \in \mathcal {T}^2$. Therefore, ${j_1} \succ _1 {k_1}$ and ${j_2} \succ _2 {k_2}$. Then we have $\mathcal {T}_{k_1}^{\succ _1} = \mathcal {T}^1, \mathcal {T}_{k_1}^{\preceq _1} = \overline{\mathcal {T}^1}$, and $\mathcal {T}_{k_2}^{\succ _2} = \mathcal {T}^2, \mathcal {T}_{k_2}^{\preceq _2} = \overline{\mathcal {T}^2}$. By Theorem 4 and $\mathcal {H}^2_{k_1} = \emptyset , \mathcal {H}^1_{k_2} = \emptyset$, we have $M^2(\mathcal {T}^1) < M^1(\overline{\mathcal {T}^1})$ and $M^1(\mathcal {T}^2) < M^2(\overline{\mathcal {T}^2})$. By $\mathcal {T}^1\cap \mathcal {T}^2 = \emptyset$, $\mathcal {T}^2 \subset \overline{\mathcal {T}^1}$ and $\mathcal {T}^1 \subset \overline{\mathcal {T}^2}$. By Lemma 5, $M^1(\overline{\mathcal {T}^1})< M^1(\mathcal {T}^2)$ and $M^2(\overline{\mathcal {T}^2})< M^2(\mathcal {T}^1)$. Combining this with previous inequality, we get $M^2(\mathcal {T}^1)< M^1(\mathcal {T}^2)$ and $M^1(\mathcal {T}^2) < M^2(\mathcal {T}^1)$, which are contradictory.

Therefore, $\mathcal {T}^1\cap \mathcal {T}^2 \ne \emptyset$. There is a target $j\in \mathcal {T}^1\cap \mathcal {T}^2$. By definition of $\mathcal {T}^1, \mathcal {T}^2$, we have $\mathcal {H}_j^1, \mathcal {H}_j^2\ne \emptyset$. Thus, $\mathcal {H}_j\ne \emptyset$ by Theorem 3. $\mathcal {H}_j\subset \mathcal {H}$, so $\mathcal {H}\ne \emptyset$. $\blacksquare$

1.4 A.4 Proof of Lemma 3

Proof

By Theorem 3 in the appendix, $\mathcal {H}_t = \mathcal {H}^1_t \times \mathcal {H}^2_t \times \{t\}$. $\mathcal {H}_t \ne \emptyset$, so $\mathcal {H}^1_t, \mathcal {H}^2_t \ne \emptyset$. Since $j \succ _1 t, j \succ _2 t$, further by Lemma 6 in the appendix, we have $\mathcal {H}^1_j, \mathcal {H}^2_j \ne \emptyset$. Use Theorem 3 again, $\mathcal {H}_j = \mathcal {H}^1_j \times \mathcal {H}^2_j \times \{j\}$. Therefore, $\mathcal {H}_j \ne \emptyset$. $\blacksquare$

1.5 A.5 Proof of Theorem 2 where $F(t)\ne F(t')$

Proof

Here, $\mathop {\textrm{Argmin}}\limits _{t} F(t)$ may not be a singleton, and we handle the edge case of selecting a specific $k^*$ from $\mathop {\textrm{Argmin}}\limits _{t} F(t)$. Consider the set $\mathcal {F} = \mathop {\textrm{Argmin}}\limits _{t} F(t)$ and let $\underline{F} = \min _{t'\in [T]} F(t')$. For any $t, j\in \mathcal {F}, t\ne j$, we say $t \triangleleft j$ if for any defender i, $\mathcal {M}_{i, \pi _i(t)} = \underline{F} \implies t \succ _i j$. We show that $\triangleleft$ is transitive. Suppose $t\triangleleft j$ and $j\triangleleft j'$. Hence, $t \succ _i j$ for any defender i where $\mathcal {M}_{i, \pi _i(t)} = \underline{F}$. On one hand, $\mathcal {M}_{i, \pi _i(j)}\ge \mathcal {M}_{i, \pi _i(t)} \ge \underline{F}$ since $t\succ _i j$. On the other hand, $j\in \mathcal {F}$, so $\mathcal {M}_{i, \pi _i(j)} \le \underline{F}$. Therefore, $\mathcal {M}_{i, \pi _i(j)} = \underline{F}$. Using a similar argument on $j\triangleleft j'$ gives us $\mathcal {M}_{i, \pi _i(t)} = \mathcal {M}_{i, \pi _i(j')} = \underline{F}$ and $t\succ _i j\succ _i j'$. So, $t\triangleleft j'$ and $\triangleleft$ is transitive.

We claim there exists a target $k^*\in \mathcal {F}$ such that $\not \exists t\in \mathcal {F}$, $t \triangleleft k^*$. If not, then for any $k_q\in \mathcal {F}$, there exists $k_{q+1}\in \mathcal {F}$ where $k_{q+1} \triangleleft k_q$. Thus, we can construct an infinite sequence $\cdots \triangleleft k_2 \triangleleft k_1$. Since $\triangleleft$ is transitive, each $k_q$ must be distinct, which is not possible with a finite number of targets. Now we select a target $k^*$.

Once $k^*$ is selected, we set $v^i(k^*) = 0$ for all defenders i. For any $t\ne k^*$, we have $F(t) \ge F(k^*)$. For a fixed t, there are two cases: (i) if $F(t) > F(k^*)$, for any defender i such that $\mathcal {M}_{i, \pi _i(t)} = F(t)$, we have $k^* \succ _i t$, since $\mathcal {M}_{i, \pi _i(t)} > F(k^*) \ge \mathcal {M}_{i, \pi _i(k^*)}$. (ii) If $F(t) = F(k^*)$, there is at least one defender i satisfying $\mathcal {M}_{i, \pi _i(t)} = F(t)$ such that $k^* \succ _i t$, otherwise $t\triangleleft k^*$, contradicting the choice of $k^*$. Thus, for any $t\ne k^*$, there always exists a defender i where $\mathcal {M}_{i, \pi _i(t)} = F(t)$ and $k^* \succ _i t$. Our construction sets $v^i(t) = F(k^*)$ and $v^{i'}(t) = 0$ for $i'\ne i$. Showing $\textbf{v}$ is feasible and $(\textbf{v}, k^*)$ is an NSE is same with the main proof of Theorem 2.$\blacksquare$