# Dynamic Adversarial Resource Allocation:
The dDAB Game

Daigo Shishika 1 * Yue Guan 2 * Jason R. Marden 3
Michael Dorothy 4 Panagiotis Tsiotras 2 Vijay Kumar 5
1 George Mason University 2 Georgia Institute of Technology
3 University of California Santa Barbara 4 United States Army Research
Laboratory
5 University of Pennsylvania

###### Abstract

This work proposes a dynamic and adversarial resource allocation problem in a
graph environment, which is referred to as the dynamic Defender-Attacker
Blotto (dDAB) game. A team of defender robots is tasked to ensure numerical
advantage at every node in the graph against a team of attacker robots. The
engagement is formulated as a discrete-time dynamic game, where the two teams
reallocate their robots in sequence and each robot can move at most one hop at
each time step. The game terminates with the attacker’s victory if any node
has more attacker robots than defender robots. Our goal is to identify the
necessary and sufficient number of defender robots to guarantee defense.
Through a reachability analysis, we first solve the problem for the case where
the attacker team stays as a single group. The results are then generalized to
the case where the attacker team can freely split and merge into subteams.
Crucially, our analysis indicates that there is no incentive for the attacker
team to split, which significantly reduces the search space for the attacker’s
winning strategies and also enables us to design defender counter-strategies
using superposition. We also present an efficient numerical algorithm to
identify the necessary and sufficient number of defender robots to defend a
given graph. Finally, we present illustrative examples to verify the efficacy
of the proposed framework.

††footnotetext: We gratefully acknowledge the support of ARL grant ARL DCIST
CRA W911NF-17-2-0181. The views expressed in this paper are those of the
authors and do not reflect the official policy or position of the United
States Army, Department of Defense, or the United States
Government.**footnotetext: The first two authors contributed equally as co-
first authors.

##  1 Introduction

Deploying resources (robots, sensors, or supplies) to appropriate locations at
the appropriate time is a fundamental problem in multi-agent systems, often
studied as the multi-robot task allocation (MRTA) problem [1, 2]. In real
world settings, resource allocation or MRTA are performed in a dynamically
changing environment. Time-varying demand is one of the major sources of
dynamics, exemplified by the applications in wireless network [3], ride-
sharing [4], power-grid [5], and cloud computing [6].

In this work, we study the dynamic resource allocation problem on a graph,
where nodes represent physical locations and edges represent the
traversability between those locations. The focus is on transporting the
resources effectively in the environment to satisfy demands that change
dynamically. Instead of achieving the desired allocation instantly, we require
the resources111We use the terms robots and resources interchangeably. The
term “player”, however, is reserved for the entity (the defender or the
attacker) that determines the allocation of these robots / resources. to
_traverse_ through the environment. Such consideration arises naturally when
dealing with embodied agents and resources, such as robots, or autonomous
vehicles.

To stress the dynamic aspect of the problem, we consider demands that are
generated by an adversary. Specifically, we formulate the problem as a dynamic
(turn-based) game played between a blue team of defender robots and a red team
of attacker robots. The defender team must ensure numerical advantage at every
node where the attacker robots are present. Whenever the attacker team has
more robots at any node, the attacker team wins the game. In that sense, the
demand imposed by the attacker team is a hard constraint that the defender
team must continuously satisfy throughout the game. Note that many other
safety-critical applications with dynamic demands (e.g., resilient power grid
[7], wildfire surveillance [8], etc.) can be formulated as such a hard-
constrained resource allocation problem.

Figure 1: Illustration of the adversarial resource allocation problem.

In this work, we consider centralized strategies for both teams. Namely, a
coordinator decides the next allocation for its own team and sends
instructions to the robots within its team to follow. Consequently, the only
intelligent agents are the defender coordinator and the attacker coordinator,
which we refer to as the defender and the attacker for simplicity. Our
formulation also leads to feedback strategies that re-allocate resources based
on the system state (the current allocation of the attacker team and the
defender team). The re-allocation is done with all possible next actions of
the opposing team in mind. This is a major difference from many prior works on
resource allocation in the robotics community, where the focus has been either
on achieving a desired terminal allocation that is fixed [9, 10], or on
scheduling to satisfy a time-varying but known demand (e.g., multiple
traveling salesman problem) [2].

The main contributions of this work are: (i) formulation of a novel resource
allocation problem that has high relevance to safety-critical applications;
(ii) identification of the critical amount of resources that are necessary and
sufficient to guarantee successful defense; (iii) derivation of the
corresponding strategies that guarantee the successful defense; and (iv)
development of efficient algorithms to construct these strategies.

###  1.1 Related Work

##### Population model on graphs:

The distributed resource allocation problem over a graph environment was
proposed in [9], where the authors developed stochastic control laws that
drive the population of robots to a desired distribution to meet a static
demand. The theory was later extended to accommodate heterogeneous robots and
tasks with more diverse needs [10, 11]. However, the theoretical analysis in
these works focused on the steady-state performance of the system, and a more
delicate transient response to dynamically changing conditions was ignored. In
contrast, our work focuses on the feedback mechanisms for a team to react to
external inputs, but with the simplification of being centralized. Our work
can be viewed as an “outer loop” that updates the desired allocation in
response to adversarial actions, which the distributed control laws in [9] can
track as an “inner loop” at a faster time scale.

##### Dynamic resource/task allocation:

Dynamical aspect of the resource allocation problem has been studied in
different ways. Scheduling is one such formulation that considers tasks that
must be completed in sequence [12]. On top of an efficient allocation
algorithm, an adaptation mechanism is proposed in [12] which reacts to robot
failures through a “market-based” optimizer to re-allocate the leftover tasks.
A distributed resource allocation on a graph environment has also been studied
with an adaptation mechanism [13], where the population dynamics are
controlled through the adaptation of individual behaviors based on local
sensing. These works provide scalable within-team interactions, but the
adaptation schemes are purely reactive and do not contain any anticipation of
the failure or changes that may occur in the future. In contrast, this paper
emphasizes the between-team (defender vs. attacker) strategic interactions,
where each team selects its action based on the anticipated optimal reactions
from the opposing team.222Note that in safety-critical systems, one can model
the environment as an adversarial agent/team that seeks to undermine the
performance of the deployed system.

##### Colonel Blotto Games:

The static version of the adversarial resource allocation problem is commonly
formulated as Colonel Blotto game [14, 15, 16, 17]. In the most standard
version [18] of the game, two colonels allocate their resources to multiple
locations. Whoever allocated more resource wins that location, and each
colonel seeks to maximize the number of locations s/he wins. Many variants of
the Colonel Blotto game have been studied, including asymmetric budget [14],
asymmetric information [19], etc. However, most of the formulations in the
existing literature consider static games, which assume that the desired
allocation is achieved instantly and thus ignore the dynamics that are
involved in the resource transportation. Although more recent works have
considered dynamical extensions of Colonel Blotto games [20, 21, 22], their
formulation does not capture the transportation of the resources in the
environment.

##### Preliminary work:

The conference version of this work [23] introduced the _dynamic Defender
Attacker Blotto (dDAB) game_ that combines the ideas from Colonel Blotto games
[18] and the population dynamics over graphs [10]. The conference version has
identified the critical resource ratios (CRR) for a special class of graphs
(ring graphs) and proposed a sampling-based algorithm that only provides
certificates for the attacker’s victory when the algorithm returns a solution.
The analysis on the defender side (e.g., necessary and sufficient conditions
for the defender’s victory, the defender’s strategies, etc.) was not fully
conducted in [23]. This paper provides a complete characterization of the dDAB
game on any given graph.

##  2 Problem Formulation

The dynamic Defender-Attacker Blotto (dDAB) game is played between two
players: the defender and the attacker. The environment is represented as a
directed graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where the $N$ nodes
represent locations, and the directed edges represent the traversability among
those locations. We assume that $\mathcal{G}$ is strongly connected [9], i.e.,
every node is reachable from any other node.333 The assumption of strongly
connected graph is used to avoid the degenerate cases with “sinks” in the
graph, which the defender resource cannot get out from once reached. See
Figure 13 in Appendix A for an example.  For notational simplicity, we assume
that the two players share the same graph, but the present analysis easily
extends to the case where the two players have different edge sets.

To capture the connectivity among the nodes, we define the graph adjacency
matrix $A\in\mathbb{R}^{N\times N}$ as follows:

$\left[A\right]_{ij}=\left\\{\begin{array}[]{cl}1&\text{if
$(j,i)\in\mathcal{E}$},\\\ 0&\text{otherwise}.\end{array}\right.$

The out-degree of node $i$ is denoted as $d_{i}=\sum_{j}[A]_{ji}$, and its
out-neighbors is denoted as
$\mathcal{N}_{i}=\\{j\in\mathcal{V}|(i,j)\in\mathcal{E}\\}$.

The total amount of resources for the defender and the attacker are denoted by
$X\in\mathbb{R}_{>0}$ and $Y\in\mathbb{R}_{>0}$, respectively. For some time
horizon $T$, the allocation of the defender’s resources over the graph at time
$t=0,1,\ldots,T$ is denoted by the state vector (allocation vector)
$\mathbf{x}_{t}\in\mathbb{R}^{N}$, which lies on a scaled simplex, such that
$[\mathbf{x}_{t}]_{i}\geq 0$ and $\sum_{i}[\mathbf{x}_{t}]_{i}=X$. The state
vector (allocation vector) $\mathbf{y}_{t}\in\mathbb{R}^{N}$ for the attacker
also satisfies the same conditions with $X$ replaced by $Y$. We use
$\Delta_{X}$ and $\Delta_{Y}$ to denote the state space of the defender and
the attacker. Note that continuous resources ($\mathbf{x}_{t}$ and
$\mathbf{y}_{t}$ are continuous variables) are considered in this work.444Such
an assumption on the state vector simplifies the analysis in [9, 10], however,
we will later show that our algorithms accommodate states that take discrete
values.

The major difference from the original Colonel Blotto game is that the dDAB
game is played over multiple time steps, and that the states evolve according
to the following discrete-time dynamics:

$\mathbf{x}_{t+1}=K_{t}\mathbf{x}_{t}\;\;\;\text{and}\;\;\;\mathbf{y}_{t+1}=F_{t}\mathbf{y}_{t},$
(1)

where $K_{t}$ and $F_{t}$ represent the _transition matrices_ for the defender
and the attacker, respectively. These matrices are left stochastic (column sum
is unity), and their $ij$-th entry can take nonzero values only when
$[A]_{ij}=1$. These matrices represent the action/control executed by the
players. For example, an action $K_{t}$ of the defender is admissible if and
only if it satisfies the following _linear_ constraints:

$\displaystyle\quad K_{t}^{\top}\mathbf{1}=\mathbf{1},$ (2)
$\displaystyle\quad[K_{t}]_{ij}\geq 0,\qquad$
$\displaystyle\forall\;i,j\in\mathcal{V},$ (3)
$\displaystyle\quad[K_{t}]_{ij}=0,\qquad$ $\displaystyle\text{if }A_{ij}=0.$
(4)

The entry $[K_{t}]_{ij}$ denotes the fraction of resource on node $j$ to be
transferred to node $i$ at the next time step. We denote the admissible set
for the matrices $K_{t}$ as $\mathcal{K}$, which depends only on the
underlying graph $\mathcal{G}$ and is time-invariant. The matrix $F_{t}$ for
the attacker also satisfies similar constraints, and we denote the set of all
admissible matrices $F_{t}$ as $\mathcal{F}$.555Under the assumption that the
two players have the same graph, we have $\mathcal{F}=\mathcal{K}$. For
consistency, we still use the notations of $\mathcal{K}$ and $\mathcal{F}$ to
denote the two action spaces.

Similar to the Colonel Blotto games [18], the engagement at each location is
modeled solely based on the amount of resources. Specifically, the defender
successfully _guards_ a location by allocating at least as many resources as
the attacker does, whereas the attacker _breaches_ a location by allocating
more than what the defender does. For the dDAB game, the defender wants to
prevent the attacker from breaching any location. In this work, we mainly
focus on a finite horizon $T$. The game terminates with the attacker’s victory
at the earliest time instance $t\in\\{0,\ldots,T\\}$ such that

$[\mathbf{y}_{t}]_{i}>[\mathbf{x}_{t}]_{i}\text{ for some }i\in\mathcal{V}.$
(5)

The defender wins the game if it can prevent the attacker from achieving
condition (5) for all $t\\!\in\\!\\{0,\ldots,T\\}$. If the defender can
prevent (5) for all time horizons $T\geq 1$, we say that the defender can
defend indefinitely.

For the information structure, we assume that the players make decisions in
sequence. Specifically, the defender acts first then the attacker acts next,
i.e., the attacker selects its action after observing how the defender
allocated its resources. The game outcome is evaluated after the attacker’s
move. To avoid the degenerate scenario where the attacker wins immediately in
the first time step, we let the attacker specify its initial allocation
$\mathbf{y}_{-1}$, followed by the defender freely picking its distribution
$\mathbf{x}_{0}$ after observing $\mathbf{y}_{-1}$. The timeline of the dDAB
game is presented in Figure 2. In a realistic scenario where the two players
make simultaneous actions, our problem formulation corresponds to a worst-case
scenario for the defender. Importantly, our setting accommodates state
feedback strategies in contrast to previous results with constant action
(transition) matrices [9, 10].

Figure 2: Sequence of events at every time step of the dDAB game. The defender
first moves its resources based on the observation of the current attacker
allocation. The attacker then observes and reallocates. Finally, the game
outcome at this time step is evaluated after the attacker’s move.

In summary, an instance of dDAB game is defined by: (i) the available
resources $X$ and $Y$, and (ii) the underlying graph $\mathcal{G}$. Given a
graph, our goal is to identify the necessary and sufficient amount of resource
for the defender to win the game. To formalize the goal above, we introduce
the following multiplicative factor.

######  Definition 1 (Critical Resource Ratio).

For a given (strongly-connected) graph $\mathcal{G}$ and a time horizon $T$,
the CRR, $\alpha_{T}\geq 1$, is the _smallest_ positive number such that, if

$X\geq\alpha_{T}Y,$ (6)

then the defender has a strategy to defend up to time step $T$ against any
admissible attacker strategy that starts at any initial state
$\mathbf{y}_{-1}\in\Delta_{Y}$. We use $\alpha_{\infty}$ to denote the CRR
that enables the defender to defend _indefinitely_.

The two main questions we address in this work are:

######  Problem 1.

Given a (strongly-connected) graph and a finite horizon $T$, what is the CRR
$\alpha_{T}$?

######  Problem 2.

When $X\geq\alpha_{T}Y$, what is the corresponding defender strategy that
guarantees defense over $T$ time steps? When the defender does not have enough
resources, what is the attacker strategy that ensures breaching?

##  3 Reachable Sets and Required Sets

This section introduces several concepts that are useful for the reachability
analysis in the sequel. Since the dynamics of the two players are symmetric,
we focus on the analysis of the defender’s reachable sets and its action space
$\mathcal{K}$.

###  3.1 Reachable Sets

There are two major disadvantages working directly with the action space
$\mathcal{K}$: (i) the higher dimensionality than the state space, i.e.
$|\mathcal{E}|\gg|\mathcal{V}|$, and (ii) the nonuniqueness in the action that
achieves a transition from $\mathbf{x}_{t}$ to $\mathbf{x}_{t+1}$. To avoid
these issues, we consider the possible states the defender can reach at the
next time step.

######  Definition 2 (Reachable Set from a Point).

The reachable set from a single point $\mathbf{x}_{t}$, denoted as
$\mathcal{R}(\mathbf{x}_{t})$, is the set of all states that the defender can
reach at the next time step with an admissible action. Formally,

$\mathcal{R}(\mathbf{x}_{t})=\\{\mathbf{x}\;|\;\exists
K\in\mathcal{K}~{}~{}\text{s.t.}~{}~{}\mathbf{x}=K\mathbf{x}_{t}\\}.$ (7)

######  Remark 1.

All points in the reachable set satisfy the conservation of resource. That is,
for all $\mathbf{x}_{t+1}\in\mathcal{R}(\mathbf{x}_{t})$, we have that
$\mathbf{1}^{\top}\mathbf{x}_{t+1}=\mathbf{1}^{\top}\mathbf{x}_{t}$.

To better understand the properties of the reachable sets, we first examine
the structure of the action space. Under the linear constraints in (2)–(4),
the set of admissible actions $\mathcal{K}$ is a bounded polytope in the
$|\mathcal{E}|$-dimensional space. We use the extreme points (vertices) of
this polytope to characterize $\mathcal{K}$.

Given the admissible action space $\mathcal{K}$, we define the set of extreme
actions as

$\hat{\mathcal{K}}=\big{\\{}K\in\mathcal{K}\;|\;[K]_{ij}\in\\{0,1\\}\big{\\}}.$
(8)

In words, $\hat{\mathcal{K}}$ contains all admissible actions $K$ whose
entries are either 0 or 1. The cardinality of $\hat{\mathcal{K}}$ is given by
$\big{|}\hat{\mathcal{K}}\big{|}=\prod_{j\in\mathcal{V}}d_{j}$, where $d_{j}$
is the out-degree of node $j$. We use $\ell$ to index the extreme actions in
$\hat{\mathcal{K}}$, i.e.
$\hat{\mathcal{K}}=\\{\hat{K}^{(\ell)}\\}_{\ell=1}^{|\hat{\mathcal{K}}|}$. The
following theorem reveals the connection between the extreme actions and the
admissible action set.

######  Theorem 1.

The extreme actions defined in (8) are the vertices of the polytope
$\mathcal{K}$. Formally,

$\mathcal{K}=\mathrm{Conv}\big{(}\hat{\mathcal{K}}\big{)}.$ (9)

Consequently, for any admissible action $K\in\mathcal{K}$, there is a set of
non-negative coefficients
$\bm{\lambda}=\\{\lambda^{(\ell)}\\}_{\ell=1}^{|\hat{\mathcal{K}}|}$ such that
$\sum_{\ell=1}^{|\hat{\mathcal{K}}|}\lambda^{(\ell)}=1$ and

$K=\sum_{\ell=1}^{|\hat{\mathcal{K}}|}\lambda^{(\ell)}\hat{K}^{(\ell)}.$ (10)

###### Proof.

See Appendix B. ∎

######  Remark 2.

The extreme action set $\hat{\mathcal{K}}$ depends only on the graph
$\mathcal{G}$, and it only needs to be constructed once.

The extreme action set for the attacker is denoted as $\hat{\mathcal{F}}$ and
is defined similarly; we use $\\{\hat{F}^{(r)}\\}_{r=1}^{|\hat{\mathcal{F}}|}$
to index the elements of $\hat{\mathcal{F}}$.

####  3.1.1 Reachable Sets as Polytopes

The reachable set $\mathcal{R}(\mathbf{x}_{t})$ is, in fact, a polytope in
$\Delta_{X}$, and it can be viewed as a transformation performed on the action
space $\mathcal{K}$. Formally, we have the following lemma, which is a direct
result of Theorem 1.

######  Lemma 1.

Given a point $\mathbf{x}_{t}$, the reachable set
$\mathcal{R}(\mathbf{x}_{t})$ is a polytope given by
$\mathcal{R}(\mathbf{x}_{t})=\mathrm{Conv}\big{(}\\{\hat{K}^{(\ell)}\mathbf{x}_{t}\\}_{\ell=1}^{|\hat{\mathcal{K}}|}\big{)}$.

###### Proof.

For any $\mathbf{x}\in\mathcal{R}(\mathbf{x}_{t})$, by definition, there is an
action $K_{t}\in\mathcal{K}$, such that $\mathbf{x}=K_{t}\mathbf{x}_{t}$.
Based on the characterization of $\mathcal{K}$ in (10), this $\mathbf{x}$ can
be represented as the following convex combination for some $\bm{\lambda}$:

$\mathbf{x}=K\mathbf{x}_{t}=\bigg{(}\sum_{\ell=1}^{|\hat{\mathcal{K}}|}\lambda^{(\ell)}\hat{K}^{(\ell)}\bigg{)}\mathbf{x}_{t}=\sum_{\ell=1}^{|\hat{\mathcal{K}}|}\lambda^{(\ell)}\left(\hat{K}^{(\ell)}\mathbf{x}_{t}\right).$
(11)

Define $\mathbf{v}^{(\ell)}_{t+1}=\hat{K}^{(\ell)}\mathbf{x}_{t}$ to be the
state achieved by propagating $\mathbf{x}_{t}$ with the extreme action
$\hat{K}^{(\ell)}$. Then, the convex hull of these vertices gives us the
polytope
$\mathcal{R}(\mathbf{x}_{t})=\mathrm{Conv}\big{(}\\{\mathbf{v}_{t+1}^{(\ell)}\\}_{\ell=1}^{|\hat{\mathcal{K}}|}\big{)}$,
which describes the set of states that the defender at $\mathbf{x}_{t}$ can
achieve at the next time step. ∎

Figure 3 presents an example of the reachable set for a three-node graph. For
discrete resources (robots) as illustrated in Figure 3(a), the defender is
able to achieve any discrete state (black dots) is are contained in the
reachable set.

Figure 3: Illustration of a defender reachable set. (a) A directed graph with
three nodes. (b) The defender’s reachable set. The small dots indicate the
discrete states if the defender’s resource consists of undividable
units/robots as depicted in (a).

Using the same argument, we can compute the attacker reachable set via
$\mathcal{R}(\mathbf{y}_{t})=\mathrm{Conv}\big{(}\\{\mathbf{w}^{(r)}_{t+1}\\}_{r}\big{)}$,
where the vertices are given by
$\mathbf{w}^{(r)}_{t+1}=\hat{F}^{(r)}\mathbf{y}_{t}$ for
$r=1,2,...,|\hat{F}|$.

Since any state in $\mathcal{R}(\mathbf{x}_{t})$ can be reached at the next
time step from $\mathbf{x}_{t}$, we view this polytope as the action space for
the defender at state $\mathbf{x}_{t}$. This definition of the action space
resolves the two issues raised at the beginning of this section:
dimensionality and nonuniqueness.

####  3.1.2 Reachable Sets of Polytopes

We extend the definition of the reachable set of a single point to the
reachable set of a (potentially unbounded) set, which will play a significant
role in our later analysis of the optimal strategies.

######  Definition 3 (Reachable Set from a Set).

Given a set $P\subseteq\mathbb{R}^{n}_{\geq 0}$, the reachable set from this
set, denoted as $\mathcal{R}(P)$, is the set of all states that the player can
reach at the next time step with an admissible action starting from a state
within $P$. Formally,

$\mathcal{R}(P)=\\{\mathbf{x}=K\mathbf{x}_{t}\;|\;K\in\mathcal{K},~{}\mathbf{x}_{t}\in
P\\}.$ (12)

######  Lemma 2.

Given a polytope $P$, the reachable set $\mathcal{R}(P)$ is also a polytope.

###### Proof.

Due to the resolution theorem [24], any point $\mathbf{x}_{t}\in P$ can be
expressed as

$\mathbf{x}_{t}=\sum_{r=1}^{R}\theta^{[r]}\mathbf{x}^{[r]}+\sum_{m=1}^{M}\phi^{[m]}\mathbf{h}^{[m]},$

where $\\{\mathbf{x}^{[r]}\\}_{r}$ is the set of vertices of $P$ and
$\\{\mathbf{h}^{[m]}\\}_{m}$ is the set of extreme rays. Then, it is
straightforward to show that

$\mathcal{R}(P)=\mathrm{Conv}\big{(}\\{\hat{K}^{[\ell]}\mathbf{x}^{[r]}\\}_{\ell,r}\big{)}+\mathrm{Cone}\big{(}\\{\hat{K}^{[\ell]}\mathbf{h}^{[m]}\\}_{\ell,m}\big{)},$

where $\mathrm{Cone}$ represents the conic hull of the rays and the summation
is a Minkowski sum. ∎

###  3.2 Required Set

In this subsection, we identify the set of defender states $\mathbf{x}_{t}$
that leads to immediate termination given the attacker’s previous allocation
$\mathbf{y}_{t-1}$. That is, the attacker has an action
$\mathbf{y}_{t}\in\mathcal{R}(\mathbf{y}_{t-1})$ to win the game by breaching
at least one node, after observing $\mathbf{x}_{t}$.

For the defender to defend every location at time $t+1$, it is necessary and
sufficient that the allocation vector $\mathbf{x}_{t+1}$ matches or outnumbers
$\mathbf{y}_{t+1}$ at every node $i$:

$[\mathbf{x}_{t+1}]_{i}\geq[\mathbf{y}_{t+1}]_{i}\quad\forall
i\in\mathcal{V}.$ (13)

Since the attacker takes its action after observing the defender’s allocation
$\mathbf{x}_{t+1}$, the question is whether there exists
$\mathbf{x}_{t+1}\in\mathcal{R}(\mathbf{x}_{t})$ such that (13) is true for
all $\mathbf{y}_{t+1}\in\mathcal{R}(\mathbf{y}_{t})$. This observation leads
to the following condition for selecting $\mathbf{x}_{t+1}$ to guarantee
defense at time $t+1$:

$[\mathbf{x}_{t+1}]_{i}\geq\max_{\mathbf{y}_{t+1}\in\mathcal{R}(\mathbf{y}_{t})}[\mathbf{y}_{t+1}]_{i}\quad\forall
i\in\mathcal{V}.$ (14)

Since $\mathcal{R}(\mathbf{y}_{t})$ is a bounded polytope, for each node $i$
the optimization
$\max_{\mathbf{y}_{t+1}\in\mathcal{R}(\mathbf{y}_{t})}[\mathbf{y}_{t+1}]_{i}$
can be viewed as a linear program, whose optimum is attained at one of the
vertices of $\mathcal{R}(\mathbf{y}_{t})$. Consequently, we define the minimum
required resource at $t+1$ as $\mathbf{x}^{\text{req}}_{t+1}$, whose elements
are given by

$[\mathbf{x}^{\text{req}}_{t+1}]_{i}=\max_{r}\left[\mathbf{w}_{t+1}^{(r)}\right]_{i},$
(15)

where
$\big{\\{}\mathbf{w}^{(r)}_{t+1}\big{\\}}_{r}=\big{\\{}\hat{F}^{(r)}\mathbf{y}_{t}\big{\\}}_{r}$
are the vertices of $\mathcal{R}(\mathbf{y}_{t})$. Then, the condition in (14)
can be expressed in the following (component-wise) vector inequality form

$\mathbf{x}_{t+1}\geq\mathbf{x}^{\text{req}}_{t+1}.$ (16)

######  Remark 3.

The defender’s minimum required resource at the _next_ time step,
$\mathbf{x}^{\text{req}}_{t+1}=\mathbf{x}^{\text{req}}_{t+1}(\mathbf{y}_{t})$,
is a function of the attacker’s _current_ state, $\mathbf{y}_{t}$.

We claim that the defender can guarantee defense at time $t+1$ by selecting
$\mathbf{x}_{t+1}$ inside the polytope
$\mathcal{P}_{\text{req}}(\mathbf{y}_{t})$ as follows.

######  Definition 4 (Required Set).

Given the attacker’s allocation $\mathbf{y}_{t}$ at time $t$, the required set
for the defender at time $t+1$ is defined as:

$\mathcal{P}_{\text{req}}(\mathbf{y}_{t})\triangleq\\{\mathbf{x}_{t+1}\;|\;[\mathbf{x}_{t+1}]_{i}\geq[\mathbf{x}^{\text{req}}_{t+1}(\mathbf{y}_{t})]_{i},\;\forall\;i\in\mathcal{V}\\}.$
(17)

######  Proposition 1.

The condition $\mathbf{x}_{t}\in\mathcal{P}_{\text{req}}(\mathbf{y}_{t-1})$ is
necessary and sufficient for the defender to defend time step $t$.

###### Proof.

By allocating at least $[\mathbf{x}^{\text{req}}_{t+1}]_{i}$ to node $i$, the
defender ensures that this node is defended against all feasible attacker
actions at time step $t+1$. If the defender allocates
$[\mathbf{x}_{t+1}]_{i}<[\mathbf{x}^{\text{req}}_{t+1}]_{i}$, then, after
observing the defender’s state (allocation), the attacker has a strategy
$\mathbf{y}_{t+1}\in\mathcal{R}(\mathbf{y}_{t})$ to win location $i$. Thus,
$\mathbf{x}^{\text{req}}_{t+1}$ is the necessary and sufficient amount of
resources for the defender to defend all locations at time $t+1$, given the
current attacker resource distribution $\mathbf{y}_{t}$. ∎

######  Remark 4.

The required set $\mathcal{P}_{\text{req}}(\mathbf{y}_{t})$ can be
equivalently expressed as

$\displaystyle\mathcal{P}_{\text{req}}(\mathbf{y}_{t})$
$\displaystyle=\\{\mathbf{x}_{t+1}\big{|}[\mathbf{x}_{t+1}]_{i}\geq\max_{\mathbf{y}_{t+1}\in\mathcal{R}(\mathbf{y}_{t})}[\mathbf{y}_{t+1}]_{i},\;\forall
i\in\mathcal{V}\\}$
$\displaystyle=\\{\mathbf{x}_{t+1}\big{|}[\mathbf{x}_{t+1}]_{i}\geq\max_{F_{t}\in\mathcal{F}}\;[F_{t}\mathbf{y}_{t}]_{i},\;\forall
i\in\mathcal{V}\\}.$

Given an attacker state $\mathbf{y}_{t}$, Figure 4 illustrates the
intersection between $\mathcal{P}_{\text{req}}(\mathbf{y}_{t})$ and the
defender’s state space $\Delta_{X}$. It is easy to see how the intersection
$\mathcal{P}_{\text{req}}(\mathbf{y}_{t})\cap\Delta_{X}$ can change as a
function of the defender’s resource $X$.

Figure 4: Illustration of the required set $\mathcal{P}_{\text{req}}$ for the
graph in Figure 3 when $\mathbf{y}=[1,0,2]^{\top}$. We conclude that
$\mathbf{x}^{\text{req}}=[3,1,2]^{\top}$ and hence $X^{\text{req}}=6$. The red
surface shows the boundary $\partial\mathcal{P}_{\text{req}}$. (a)
Intersection between $\mathcal{P}_{\text{req}}$ and $\Delta_{X}$ when $X=10$.
(b) The case when $X=6$.

Notice that
$X^{\text{req}}_{t+1}=\mathbf{1}^{\top}\mathbf{x}^{\text{req}}_{t+1}$ depends
on $\mathcal{G}$ and $\mathbf{y}_{t}$. Clearly, the defender does not have a
strategy to guarantee defense if $X^{\text{req}}_{t+1}>X$. This immediately
leads to the following result.

######  Theorem 2 (Degenerate Parameter Regime [23]).

Let $d_{\mathrm{max}}\triangleq\max_{i\in\mathcal{V}}d_{i}$ denote the maximum
outdegree of $\mathcal{G}$. If the total resources satisfy

$X<d_{\mathrm{max}}Y,$ (18)

then the attacker can win the game at time step $t=0$.

###### Proof.

Consider the scenario where the attacker initializes the game with
$\mathbf{y}_{-1}$ that concentrates all its resources at the node with the
maximum out-degree. If the defender does not allocate an equal amount or more
to every neighboring node at time $0$, the attacker can immediately win the
game by moving all its resources to the neighboring node where the defender’s
allocation $\mathbf{x}_{0}$ has less than $Y$ unit of resources, after
observing the defender’s move. ∎

Based on Theorem 2, the rest of the paper focuses on the case where

$X\geq d_{\mathrm{max}}Y.$

##  4 No-Splitting Attacker

This section develops the tools to construct optimal feedback strategies for
the defender and the attacker. We first focus on the case where the attacker
resources move as a single concentrated group (a blob). In Section 5, we
generalize the results to scenarios where the attacker splits its resource
into multiple subgroups. Note that throughout this paper, we do not restrict
the defender’s allocation strategies.

Let $\mathbf{e}_{i}\in\mathbb{R}^{n}$ be the unit vector with its $i$-th
element equal to one. In the sequel, we use the shorthand
${\mathbf{y}^{(i)}=Y\mathbf{e}_{i}}$ to denote the attacker allocation that is
fully concentrated on node $i$.

######  Definition 5 (No-splitting Attacker Strategy).

A no-splitting attacker strategy concentrates all attacker resources at one
node at each time $t$. That is, for all $t$,
$\mathbf{y}_{t}=\mathbf{y}^{(i_{t})}\triangleq Y\mathbf{e}_{i_{t}}$ for some
$i_{t}\in\mathcal{V}$.666 The no-splitting strategy can be achieved by
ensuring that $\mathbf{y}_{0}=\mathbf{y}^{(i)}$ for some $i$ and
$F_{t}\in\hat{\mathcal{F}}$ for all time step $t$, i.e., the attacker always
selects its action from the set of _extreme actions_ defined in (8).

###  4.1 K-step Safe Sets

To generate the defender strategy against no-splitting attacker strategies, we
define the following $k$-step safe set, later referred to as the Q-set.

######  Definition 6 ($k$-step Safe Set).

We define ${\mathcal{Q}}_{k}^{(i)}={\mathcal{Q}}_{k}^{(i)}(\mathcal{G})$ to be
the region in $\mathbb{R}^{n}_{\geq 0}$ such that for a no-splitting attacker
state $\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$, the defender’s state
$\mathbf{x}_{t}\in{\mathcal{Q}}_{k}^{(i)}$ is necessary and sufficient to
defend against any no-splitting attacker strategy until time step $t+k$
(included).777Specifically, there may exist a no-splitting attacker strategy
that wins at time step $t+k+1$ but not before that.

######  Theorem 3.

The following recursive expression provides the $k$-step safe set:

$\displaystyle{\mathcal{Q}}_{0}^{(i)}$
$\displaystyle=\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)}),$ (19a)
$\displaystyle{\mathcal{Q}}_{k}^{(i)}$
$\displaystyle=\Big{\\{}\mathbf{x}\;\big{|}\;\mathbf{x}\in\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})\text{
and
}\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{k-1}^{(j)}\neq\varnothing~{}\forall
j\in\mathcal{N}_{i}\Big{\\}}\quad$ $\displaystyle\forall~{}k\geq 1,$ (19b)

where $\mathcal{N}_{i}$ is the set of out-neighbors of node $i$.

###### Proof.

We break the proof into the following two lemmas, where Lemma 3 is for
sufficiency and Lemma 4 is for necessity. Although the proofs are elementary,
they provide insights into the mechanisms behind the Q-sets and are also
helpful for the construction of the strategies. ∎

######  Lemma 3 (Sufficiency of Q-sets).

Let the Q-sets be defined in (19), and suppose that the attacker starts with
$\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$. Then, by having
$\mathbf{x}_{t}\in{\mathcal{Q}}_{k}^{(i)}$, the defender can defend at least
until time step $t+k$.

###### Proof.

We provide a proof by induction.

Base Case: When $k=0$, we have
$\mathbf{x}_{t}\in{\mathcal{Q}}_{0}^{(i)}=\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$.
From Proposition 1, the defense is guaranteed at time $t$.

Inductive hypothesis: Suppose that for some $k\geq 1$, and for all
$i\in\mathcal{V}$, the condition $\mathbf{x}_{t}\in{\mathcal{Q}}_{k}^{(i)}$
guarantees defense until time $t+k$ given that
$\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$.

Induction: Given $\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$, we let
$\mathbf{x}_{t}\in{\mathcal{Q}}_{k+1}^{(i)}$. Under the no-splitting strategy,
suppose that the attacker selects $\mathbf{y}_{t}=\mathbf{y}^{(j)}$, for some
arbitrary $j\in\mathcal{N}_{i}$. The attacker cannot immediately win with this
(or any other) action since the defender state
$\mathbf{x}_{t}\in{\mathcal{Q}}_{k+1}^{(i)}\subseteq\mathcal{P}_{\text{req}}(\mathbf{y}_{t-1})$
guarantees defense at time step $t$. After observing
$\mathbf{y}_{t}=\mathbf{y}^{(j)}$, we let the defender select its next state
so that
$\mathbf{x}_{t+1}\\!\in\\!\mathcal{R}(\mathbf{x}_{t})\cap{\mathcal{Q}}_{k}^{(j)}$.
This new selection is reachable since
$\mathbf{x}_{t}\in{\mathcal{Q}}_{k+1}^{(i)}$ ensures that
$\mathcal{R}(\mathbf{x}_{t})\cap{\mathcal{Q}}_{k}^{(j)}\neq\varnothing$ (from
(19b)). After the defender’s action, we are at a situation where
$\mathbf{y}_{t}=\mathbf{y}^{(j)}$ and
$\mathbf{x}_{t+1}\in{\mathcal{Q}}_{k}^{(j)}$. From the inductive hypothesis,
the defender can defend another $k$ steps from this time on. The defender can
thus defend until time step $t\\!+\\!k\\!+\\!1$.

∎

######  Lemma 4 (Necessity of Q-sets).

Let the Q-sets be defined in (19), and suppose that the attacker starts with
$\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$. If
$\mathbf{x}_{t}\notin{\mathcal{Q}}_{k}^{(i)}$, the attacker can win the game
before or at time step $t+k$.

###### Proof.

We prove this lemma via an inductive argument.

Base case: Suppose
$\mathbf{x}_{t}\notin{\mathcal{Q}}_{0}^{(i)}=\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$.
Then, by the construction of $\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$,
there exists $j\in\mathcal{N}_{i}$ such that $\mathbf{y}_{t}=\mathbf{y}^{(j)}$
defeats $\mathbf{x}_{t}$ on node $j$.888 If
$\mathbf{x}_{t}\notin\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$, we know that
there exists at least one $\mathbf{y}_{t}\in\mathcal{R}(\mathbf{y}^{(i)})$
that breaches $\mathbf{x}_{t}$, and this $\mathbf{y}_{t}$ is not necessarily a
concentrated configuration. Suppose this (potentially split) $\mathbf{y}_{t}$
defeats $\mathbf{x}_{t}$ on node $j$. Since we are starting from a
concentrated state $\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$, the attacker can move
all its resource to the same node $j$, and this concentrated state would also
breach node $j$.  This corresponds to a defender defeat at time $t$.

Inductive hypothesis: Suppose that, for all $i$,
$\mathbf{x}_{t}\notin{\mathcal{Q}}_{k}^{(i)}$ implies that the attacker with
state $\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$ can win the game before or at time
step $t+k$.

Induction: Let the attacker start with $\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$ and
the defender select $\mathbf{x}_{t}\notin{\mathcal{Q}}_{k+1}^{(i)}$. From the
definition of ${\mathcal{Q}}_{k+1}^{(i)}$, we have either of the following two
cases: (i) $\mathbf{x}_{t}\notin\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$,
which leads to an immediate defeat at $t$; or (ii) there exists
$j\in\mathcal{N}_{i}$, such that
$\mathcal{R}(\mathbf{x}_{t})\cap{\mathcal{Q}}_{k}^{(j)}=\varnothing$. In the
latter case, the attacker can move to $\mathbf{y}_{t}=\mathbf{y}^{(j)}$. Then,
for all possible next defender allocation
$\mathbf{x}_{t+1}\in\mathcal{R}(\mathbf{x}_{0})$, we have that
$\mathbf{x}_{t+1}\notin{\mathcal{Q}}_{k}^{(j)}$. From the inductive
hypothesis, the defender will be defeated within $k$ steps from this time
$t+1$. Thus, the attacker can win the game before or at time step $t+k+1$.

∎

Next, we present two important properties of the Q-sets.

######  Remark 5.

For a fixed node $i\in\mathcal{V}$, the sequence
$\big{\\{}{\mathcal{Q}}_{k}^{(i)}\big{\\}}_{k}$ is a decreasing sequence of
sets. Formally, for all $i\in\mathcal{V}$ and $k\geq 0$,

${\mathcal{Q}}_{k+1}^{(i)}\subseteq{\mathcal{Q}}_{k}^{(i)}.$ (20)

The above remark follows directly from the definition of the Q-sets. That is,
if the defender can defend $k+1$ steps from some state, then it can clearly
defend $k$ steps.

######  Theorem 4.

All Q-sets are polytopes.

We delay the proof of Theorem 4 to the algorithmic section, where we introduce
additional tools to characterize and efficiently construct the Q-sets.

###  4.2 Indefinite Defense

The recursive definition of the Q-sets in (19) can be viewed as an operator
mapping from $\big{(}2^{\Delta_{X}}\big{)}^{|\mathcal{V}|}$ to itself, where
$2^{S}$ denotes the power set of set $S$. Consequently, (19) can be viewed as
an iterative algorithm, and its fixed point(s) is therefore of great interest
to study. Note that a fixed point of (19) is an element in
$\big{(}2^{\Delta_{X}}\big{)}^{|\mathcal{V}|}$.

######  Definition 7 (Indefinite Safe Set).

We define the indefinite safe sets
${\mathcal{Q}}_{\infty}^{(i)}\subseteq\Delta_{X}$ for $i\in\mathcal{V}$ as
follows:

${\mathcal{Q}}_{\infty}^{(i)}=\bigcap_{k\geq 0}{\mathcal{Q}}_{k}^{(i)}.$ (21)

######  Remark 6.

Since the Q-sets are nested (descending), the above definition is equivalent
to ${\mathcal{Q}}_{\infty}^{(i)}=\lim_{k\to\infty}{\mathcal{Q}}_{k}^{(i)}$.

######  Remark 7.

The indefinite safe sets are either all empty or all nonempty. In the first
case, the defender cannot defend indefinitely with a finite amount of
resource.

The first natural question is whether the collection of indefinite safe sets
defined in (21) is a fixed point of the recursive formula in (19).

######  Theorem 5.

If the indefinite safe sets defined in (21) are nonempty, they satisfy the
following fixed point relation for all nodes $i\in\mathcal{V}$:

${\mathcal{Q}}_{\infty}^{(i)}\\!=\\!\Big{\\{}\mathbf{x}\big{|}\mathbf{x}\in\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{\infty}^{(j)}\neq\varnothing~{}\forall
j\in\mathcal{N}_{i}\Big{\\}}.$ (22)

###### Proof.

See Appendix C. ∎

In the following theorem, we formalize the natural conjecture that indefinite
safe sets guarantee an indefinite defense for the defender.

######  Theorem 6.

If ${\mathcal{Q}}_{\infty}^{(i)}\neq\varnothing$, then
$\mathbf{x}_{t}\in{\mathcal{Q}}_{\infty}^{(i)}$ is necessary and sufficient
for indefinite defense given that the attacker is at
$\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$.

###### Proof.

The necessity is straightforward. If
$\mathbf{x}_{t}\notin{\mathcal{Q}}_{\infty}^{(i)}$, then
$\mathbf{x}_{t}\notin{\mathcal{Q}}_{k}^{(i)}$ for some finite $k$. From the
necessity of the $k$-step safe sets, we know that the defender will be
defeated within $k$ steps.

For the sufficiency, suppose at time step $t$, the system is at the state
$\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$ and
$\mathbf{x}_{t}\in{\mathcal{Q}}_{\infty}^{(i)}$. Since
${\mathcal{Q}}_{\infty}^{(i)}\subseteq\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$,
the defender can defend at least the current time step $t$. Next, suppose the
attacker moves to $\mathbf{y}_{t}=\mathbf{y}^{(j)}$, where
$j\in\mathcal{N}_{i}$. From (22), there is a state
$\mathbf{x}_{t+1}\in{\mathcal{Q}}_{\infty}^{(j)}$ that is reachable from
$\mathbf{x}_{t}$. Since
${\mathcal{Q}}_{\infty}^{(j)}\subseteq\mathcal{P}_{\text{req}}(\mathbf{y}^{(j)})$,
the defender can also defend the time step $t+1$. Through mathematical
induction, one can easily argue that being in ${\mathcal{Q}}_{\infty}^{(i)}$
when $\mathbf{y}_{t-1}=\mathbf{y}^{(i)}$ guarantees indefinite defense for all
_no-splitting_ attacker strategies.

∎

The conditions on the graph that guarantee convergence of the iterative
algorithm in (19) as well as the conditions for the existence of such fixed
point(s) is an ongoing research. Note that not all graphs have such a fixed
point, for example, a sink graph (see Figure 13 in Appendix A) does not have
one, since it requires infinite defender resources to guard indefinitely.
Empirically, we found that for all strongly-connected and undirected graphs,
the iterative algorithm in (19) converges within $N$ iterations, where
$N=|\mathcal{V}|$ is the number of nodes. A follow-up work would be to
establish the convergence guarantees.

###  4.3 Q-Set Propagation

The Q-set propagation process is described in Algorithm 1, which takes two
inputs: the graph environment $\mathcal{G}$ and the horizon of the game $T$.
We assume that the players do not care about their performance beyond $T$, and
therefore, Q-sets need not be computed beyond this horizon. The algorithm then
utilizes (19) to generate the Q-sets. The actual numerical implementation of
the algorithm uses an equivalent but more computationally efficient formula
(36) introduced later in Section 6. The iterative Q-set construction process
stops if the Q-sets converge, as described in line 4. In this case, we can
conclude that the defender has a strategy to defend indefinitely against all
no-splitting attacker strategies. The output $k_{\infty}$ gives the smallest
finite number such that
${\mathcal{Q}}_{k_{\infty}}^{(i)}={\mathcal{Q}}_{\infty}^{(i)}$ for all
$i\in\mathcal{V}$. This conclusion is formalized in Corollary 1.

Inputs: Graph $\mathcal{G}$, attacker total resource $Y$, game horizon $T$;

1 Set $k_{\infty}=\infty$ and set
${\mathcal{Q}}_{0}^{(i)}=\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$ for all
$i\in\mathcal{V}$;

2 for  _$k=1$ to $T$_ do

3 Construct ${\mathcal{Q}}_{k}^{(i)}$ using (36) for all $i\in\mathcal{V}$;

4 if  _${\mathcal{Q}}_{k}^{(i)}={\mathcal{Q}}_{k-1}^{(i)}$ for all
$i\in\mathcal{V}$_ then

5 $k_{\infty}=k-1$;

6 Break;

7

8 end if

9

10 end for

Return: $\\{{\mathcal{Q}}_{k}^{(i)}\\}_{i,k}$, $k_{\infty}$

Algorithm 1 Q-Prop

######  Corollary 1.

Suppose Algorithm 1 returns $k_{\infty}<\infty$. Then, for any no-splitting
attacker strategy, there is a defender strategy that can defend indefinitely.

###### Proof.

If the algorithm terminates at some $k_{\infty}<\infty$, we have
${\mathcal{Q}}_{k_{\infty}}^{(i)}={\mathcal{Q}}_{k_{\infty}+1}^{(i)}$ for all
nodes $i\in\mathcal{V}$, which implies that
$\\{{\mathcal{Q}}_{k_{\infty}}^{(i)}\\}_{i\in\mathcal{V}}$ is the limit in
(21). The corollary then follows directly from Theorem 6. ∎

For the rest of the paper, if Algorithm 1 converges, we denote the converged
Q-sets $\\{{\mathcal{Q}}_{k_{\infty}}^{(i)}\\}_{i}$ as
$\\{{\mathcal{Q}}_{\infty}^{(i)}\\}_{i}$ for simplicity.

###  4.4 K-step Strategies

The proof of Theorem 3 provides a guideline for the strategies that the
defender and the attacker would deploy under the no-splitting assumption. We
first summarize the defender strategy in the following two algorithms.

Inputs: Graph $\mathcal{G}$, defender total resource $X$, attacker total
resource $Y$, attacker initial allocation
$\mathbf{y}_{-1}=\mathbf{y}^{(i_{-1})}$, game horizon $T$;

1

2Construct Q-sets via Algorithm 1;

3
$k_{\mathrm{max},0}\leftarrow\operatorname*{arg\,max}_{k}\left\\{k\leq\min\\{T,k_{\infty}\\}|\Delta_{X}\cap{\mathcal{Q}}_{k}^{(i_{-1})}\neq\varnothing\right\\}$
$\triangleright$ find the longest defense time

4$\mathbf{x}_{0}\leftarrow$ any element in
${\mathcal{Q}}_{k_{\max,0}}^{(i_{-1})}$

Return: Initial allocation $\mathbf{x}_{0}$, guaranteed defense time
$k_{\max,0}$

Algorithm 2 Initial Defender Allocation (against No-Splitting Attacker)

Inputs: Q-sets, previous defender allocation $\mathbf{x}_{t-1}$, previous
attacker allocation $\mathbf{y}_{t-1}=\mathbf{y}^{(i_{t-1})}$, game horizon
$T$;

1

2$k_{\max,t}\leftarrow\operatorname*{arg\,max}_{k}\left\\{k\leq\min\\{T,k_{\infty}\\}|\mathcal{R}(\mathbf{x}_{t-1})\cap{\mathcal{Q}}_{k}^{(i_{t-1})}\neq\varnothing\right\\}$
$\triangleright$ exploit attacker’s mistake

3 $\mathbf{x}_{t}\leftarrow$ any element in
${\mathcal{Q}}_{k_{\max,t}}^{(i_{t-1})}$;

4

Return: New allocation $\mathbf{x}_{t}$, guaranteed defense time $k_{\max,t}$

Algorithm 3 Feedback Defender Strategy (against No-Splitting Attacker)

Algorithm 3 presents the feedback strategy for the defender. Suppose
$k_{\max,0}=k_{\infty}$ in Algorithm 2, then the defender can indefinitely
defend regardless of the attacker’s no-splitting strategy. In this case, the
defender observes $\mathbf{y}_{t-1}=\mathbf{y}^{(i_{t-1})}$ and reallocates
its resources to the corresponding Q-set:
${\mathcal{Q}}_{k_{\infty}}^{(i_{t-1})}={\mathcal{Q}}_{\infty}^{(i_{t-1})}$.

On the other hand, if Algorithm 2 outputs $k_{\max,0}<k_{\infty}$, then either
Algorithm 1 did not converge, or the defender does not have enough resource to
achieve indefinite defense. By the construction of Q-sets, the defender has a
guarantee to defend up to time step $t=k_{\max,0}$. If we also have
$k_{\max,0}<T$, then the attacker will identify a strategy to win at
$t=k_{\max,0}+1$ (shown later in Algorithms 4 and 5). Under the rational
strategies by both players, $k_{\max,t}$ will reduce by 1 at each time step,
and the game terminates with attacker’s win at $t=k_{\max,0}+1\leq T$.
However, if the attacker does not play rationally, the defender may be able to
delay the breaching. The search / optimization performed in line 1 of
Algorithm 3 ensures that the defender exploits such opportunity.999Note that
if $k_{\max,0}=T<k_{\infty}$, we do not have an estimate of when the attacker
will be able to breach, even if the game continued beyond $t=T$. However, the
defender still has a guarantee to defend up to time step $T$, and that is
sufficient to identify the outcome of the finite-horizon game.

The following two algorithms describe the attacker strategy under the
restriction of no-splitting. In particular, Algorithm 4 presents the initial
allocation for the attacker, and Algorithm 5 provides the feedback attacker
strategy at time steps $t\geq 0$. As we will show later in Corollary 2, the
attacker has no incentive to split, i.e., if the attacker can win a dDAB game
by splitting, it can also win the game without splitting. Consequently, the
algorithms presented here are sufficient for the attacker to play the dDAB
game.

Inputs: Graph $\mathcal{G}$, defender total resource $X$, attacker total
resource $Y$, game horizon $T$;

1 Construct Q-sets using Algorithm 1;

2 if  _$\exists k\leq\min\\{T,k_{\infty}\\}$ and $i\in\mathcal{V}$ such that
$\Delta_{X}\cap{\mathcal{Q}}_{k}^{(i)}=\varnothing$_ then

3
$k_{\mathrm{min},-1}\leftarrow\operatorname*{arg\,min}_{k}\left\\{k\leq\min\\{T,k_{\infty}\\}\;|\;\Delta_{X}\cap{\mathcal{Q}}_{k}^{(i)}=\varnothing\right\\}$
$\triangleright$ find the earliest breach

4 $i_{-1}^{*}\leftarrow$ any element in
$\\{i\,|\,\Delta_{X}\cap{\mathcal{Q}}_{k_{\mathrm{min},-1}}^{(i)}=\varnothing$
};

5 else

6 $k_{\mathrm{min},-1}\leftarrow\infty$;

7 $i_{-1}^{*}\leftarrow$ any element in node set $\mathcal{V}$;

8

9 end if

Return: Initial allocation $\mathbf{y}_{-1}=\mathbf{y}^{(i_{-1}^{*})}$,
guaranteed breach time $k_{\min,-1}$.

Algorithm 4 Attacker Initial Allocation

Inputs: Q-sets, observed defender allocation $\mathbf{x}_{t}$, planning
horizon $T$;

1 if  _$\exists k\leq\min\\{T,k_{\infty}\\}$ and $i\in\mathcal{N}_{i_{t-1}}$
such that $\mathbf{x}_{t}\notin{\mathcal{Q}}_{k}^{(i)}$_ then

2 $k_{\mathrm{min},t}\leftarrow$ $\triangleright$ exploit defender’s mistake

$\operatorname*{arg\,min}_{k}\left\\{k\leq\min\\{T,k_{\infty}\\}\;|\;\mathbf{x}_{t}\notin{\mathcal{Q}}_{k}^{(i)},\,i\in\mathcal{N}_{i_{t-1}}\right\\}$

;

3 $i_{t}^{*}\leftarrow$ any element in
$\\{i\in\mathcal{N}_{i_{t-1}}\,|\,\mathbf{x}_{t}\notin{\mathcal{Q}}_{k_{\mathrm{min},t}}^{(i)}$
};

4

5 else

6 $k_{\mathrm{min},t}\leftarrow\infty$;

7 $i_{t}^{*}\leftarrow$ any element in $\mathcal{N}_{i_{t-1}}$;

8

9 end if

Return: Next allocation $\mathbf{y}_{t}=\mathbf{y}^{(i_{t}^{*})}$, guaranteed
breach time $k_{\min,t}$.

Algorithm 5 Feedback Attacker Strategy

The attacker can defeat the defender only when the defender allocates
resources outside the Q-sets. Since we formulated the dDAB game as a game of
kind without any performance metric, when the defender allocates resources
within ${\mathcal{Q}}_{k}^{(i)}$, the defender is guaranteed to defend the
next $k$ steps, and thus the attacker does not have preference over which node
to move to next. Therefore, we have arbitrary selections in line 7 of
Algorithm 4 and line 6 of Algorithm 5. Introducing a cost for the defender’s
reallocation is a potential extension of this work. Our recent work [25]
explored this idea and developed a more general framework based on convex body
chasing [26], where the Q-sets are the convex bodies to be chased.

##  5 Main Results

This section generalizes the defender strategy in the previous section to
scenarios where the attacker can split its resources to multiple nodes. In
particular, we show that if the defender has sufficient amount of resources to
defend against any no-splitting attacker strategy, then it can defend against
any attacker strategy, including the splitting ones. This result implies that
the attacker can win the game if and only if it can win using a no-splitting
strategy, and consequently the attacker does not have any incentive to split
its resources to win the game. Finally, we obtain the critical resource ratio
(CRR), which describes the necessary and sufficient amount of the defender
resource required to guarantee defense against any attacker strategy.

###  5.1 Generalization to Splitting Attacker

To extend the analysis from no-splitting strategies to more general
strategies, we introduce the notion of subteams.

######  Definition 8 (Attacker Subteam).

We refer to the attacker resource allocated to each node as an _attacker
subteam_. The size of the $i$-th attacker subteam (on node $i$) at time $t$ is
$[\mathbf{y}_{t}]_{i}$.

In general, any attacker action can be viewed as a superposition of the
subteam actions, which results in the splitting and merging of subteams into a
new set of subteams. Figure 5 illustrates an example where two attacker
subteams split and merge into a new set of three subteams. Note that the
attacker’s action to achieve the allocation in Figure 5(c) from Figure 5(a) is
non-unique.

Figure 5: Splitting and merging of an attacker subteam. Self-loops on each
node is omitted for clarity. (a) Two attacker subteams at $t$: a 3-unit
subteam on node 2 and a 4-unit subteam on node 3. (b) Each subteam splits into
two: magenta-purple and yellow-red. (Note that the game is still in time step
$t$.) (c) The re-allocation (action) of each subteam at $t$. (d) The resultant
three subteams on nodes 1,3 and 4 at $t+1$.

Based on the necessity and sufficiency of Q-sets, we define the $i$-th
defender subteam as the subset of the defender resource that can defend
against the $i$-th attacker subteam, assuming that the attacker subteam does
_not_ further split in the future.

######  Definition 9 (Defender Subteam).

The $i$-th defender subteam is defined as

$\mathbf{x}_{t,T}^{(i)}\triangleq\frac{[\mathbf{y}_{t-1}]_{i}}{Y}\hat{\mathbf{x}}_{t}^{(i)},\text{\;where\;}\hat{\mathbf{x}}_{t}^{(i)}\in{\mathcal{Q}}_{T-t}^{(i)},$
(23)

where the first subscript $t$ tracks the current time step, and the second
subscript $T$ tracks the expected terminal time.

Note that the Q-set in (19) is defined based on the full attacker team size
$Y$, and $\hat{\mathbf{x}}$ is used to denote an element of the original
Q-sets. On the other hand, a defender subteam is its scaled version according
to the size of the corresponding attacker subteam, and hence the scaling
factor in (23).

Figure 6(a) shows an example of a valid defender subteam
$\mathbf{x}_{t,\infty}^{(2)}$ placed against an attacker subteam at node 2.
Figure 6(b) shows how the attacker team may split into multiple subteams:
magenta with size 1 and red with size 2. Based on the observed attacker
action, the defender resources also split into two: cyan and blue that reacts
against magenta and red, respectively. Finally, Figure 6(c) shows how the
defender subteam may react to the observed attacker action.

Figure 6: Splitting of an attacker subteam and the response of corresponding
defender subteam. Self-loops on each node is omitted for clarity. (a) Initial
state with a valid defender subteam placed against an attacker subteam at node
2. (b) The attacker resource splits into two: magenta with size 1 and red with
size 2. Based on the observed attacker action, the original defender subteam
also splits into two: cyan and blue that reacts against magenta and red,
respectively. (c) The reaction of each defender subteams (cyan and blue)
against corresponding attacker subteams.

In the following, we formally present the guarantees on the defense time
(Theorem 7) as well as the defender’s feedback strategy (Algorithms 6 and 7).
We first present the main result of this section and provide the supporting
lemmas later on.

######  Theorem 7.

Suppose that, for a given terminal time $T$, and for some
$t\in\\{0,1,...,T\\}$, the defender’s state can be described as a
superposition of the subteams:101010This condition is implicitly dependent on
$\mathbf{y}_{t-1}$ through the definition of the subteams in (23).

$\mathbf{x}_{t}=\sum_{i=1}^{N}\mathbf{x}_{t,T}^{(i)}.$ (24)

Then, the defender has a strategy to guarantee defense until time step $T$
against any admissible attacker strategy.

###### Proof.

We break the proof into three steps. Step I: In Lemma 5, we show that (24) is
a sufficient condition for the defender to defend during the current time
step. Step II: Lemma 6 provides a strategy to maintain condition (24) at the
next time step against any admissible attacker strategy. In other words, for
$t\in\\{0,\ldots,T-1\\}$, if $\mathbf{x}_{t}$ satisfies (24) for a given
$\mathbf{y}_{t-1}$, then for any
$\mathbf{y}_{t}\in\mathcal{R}(\mathbf{y}_{t-1})$, there is an admissible
action $K_{t}$ such that $\mathbf{x}_{t+1}=K_{t}\mathbf{x}_{t}$ satisfies (24)
at $t+1$. Step III: Based on mathematical induction, condition (24) is
satisfied for all time steps. Therefore, the defense is guaranteed until time
$T$. ∎

######  Remark 8.

Theorem 7 states the sufficiency for the defender to defend a certain number
of time steps against all admissible attacker strategies. The tightness
(necessity) of this condition will be discussed in terms of the required
amount of resources (i.e., CRR) in Lemma 7 and Corollary 2.

######  Lemma 5 (One-step Safety Guarantee).

If the defender state $\mathbf{x}_{t}$ satisfies (24), then we have
$\mathbf{x}_{t}\in\mathcal{P}_{\text{req}}(\mathbf{y}_{t-1})$. In other words,
(24) provides sufficiency for the defender to defend the current time step
$t$.

###### Proof.

Recalling the definition of defender subteams in (23), the condition (24) can
be written as

$\mathbf{x}_{t}=\sum_{i=1}^{N}\frac{[\mathbf{y}_{t-1}]_{i}}{Y}\hat{\mathbf{x}}_{t}^{(i)}.$

By definition $\hat{\mathbf{x}}_{t}^{(i)}\in{\mathcal{Q}}_{T-t}^{(i)}$, which
implies
$\hat{\mathbf{x}}^{(i)}_{t}\in\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$.
Therefore for any $F_{t-1}\in\mathcal{F}$ we have

$[\hat{\mathbf{x}}^{(i)}_{t}]_{j}\geq[F_{t-1}\mathbf{y}^{(i)}]_{j}=Y[F_{t-1}\mathbf{e}_{i}]_{j},\quad\forall\;j\in\mathcal{V}.$

Multiplying both sides with $\frac{1}{Y}[\mathbf{y}_{t-1}]_{i}$, it follows
that

$\frac{1}{Y}[\mathbf{y}_{t-1}]_{i}[\hat{\mathbf{x}}^{(i)}_{t}]_{j}\geq[\mathbf{y}_{t-1}]_{i}[F_{t-1}\mathbf{e}_{i}]_{j}.$

By taking the sum over $i$, we obtain

$\displaystyle[\mathbf{x}_{t}]_{j}$
$\displaystyle=\frac{1}{Y}\sum_{i\in\mathcal{V}}[\mathbf{y}_{t-1}]_{i}[\hat{\mathbf{x}}^{(i)}_{t}]_{j}\geq\sum_{i\in\mathcal{V}}[\mathbf{y}_{t-1}]_{i}[F_{t-1}\mathbf{e}_{i}]_{j}$
$\displaystyle=\sum_{i\in\mathcal{V}}\left[[\mathbf{y}_{t-1}]_{i}F_{t-1}\mathbf{e}_{i}\right]_{j}=\Big{[}F_{t-1}\sum_{i\in\mathcal{V}}[\mathbf{y}_{t-1}]_{i}\mathbf{e}_{i}\Big{]}_{j}$
$\displaystyle=\left[F_{t-1}\mathbf{y}_{t-1}\right]_{j}.$

Since the above inequality holds for all $F_{t-1}\in\mathcal{F}$, it follows
that $\mathbf{x}_{t}\in\mathcal{P}_{\text{req}}(\mathbf{y}_{t-1})$ (see Remark
4). Consequently, $\mathbf{x}_{t}$ can defend the current time step $t$.

∎

The next lemma shows that the defender can preserve the condition in (24)
against any attacker strategy.

######  Lemma 6 (Inductive Condition).

Suppose the defender’s state at time $t$ satisfies

$\mathbf{x}_{t}=\sum_{i=1}^{N}\mathbf{x}_{t,T}^{(i)}.$ (25)

Then, for any attacker action
$\mathbf{y}_{t}\in\mathcal{R}(\mathbf{y}_{t-1})$, there exists a defender’s
reaction $\mathbf{x}_{t+1}\in\mathcal{R}(\mathbf{x}_{t})$ such that

$\mathbf{x}_{t+1}=\sum_{i=1}^{N}\mathbf{x}_{t+1,T}^{(i)},$ (26)

i.e., the defender’s state at the next time step can also be written as a
combination of valid subteams defined in (23).

###### Proof.

Denote an attacker’s action that takes $\mathbf{y}_{t-1}$ to $\mathbf{y}_{t}$
as $F_{t-1}$.111111 This action may be non-unique as discussed in Section 3.1,
but its existence suffices for the purpose of this proof. Let $\bm{f}_{i}$ be
the $i$-th column of $F_{t-1}$, i.e.,
$F_{t-1}=[\bm{f}_{1},\bm{f}_{2},...,\bm{f}_{N}]$, where
$\bm{f}_{i}^{\top}\bm{1}=1$ (since $F_{t-1}$ is left stochastic). We can
interpret $\bm{f}_{i}$ to be the splitting action of the attacker subteam on
node $i$ at time $t-1$, where the fraction of a (possibly empty) subteam on
node $i$ relocating to node $j$ is given by $[\bm{f}_{i}]_{j}$.

For notational convenience, we drop the second subscript $T$, when denoting
the defender subteams, $\mathbf{x}_{t,T}^{(i)}$. From Definition 9, we have
that the re-scaled $i$-th defender subteam satisfies
$\hat{\mathbf{x}}_{t}^{(i)}=(Y\mathbf{x}_{t}^{(i)})/[\mathbf{y}_{t-1}]_{i}\in{\mathcal{Q}}_{T-t}^{(i)}.$
From the Q-set definition, we can always construct a satisficing defender
action $K^{(i\to j)}$ against a no-splitting attacker moving from node $i$ to
$j$, which guarantees that $\hat{\mathbf{x}}_{t+1}^{(i\to j)}=K^{(i\to
j)}\hat{\mathbf{x}}_{t}^{(i)}\in{\mathcal{Q}}_{T-t-1}^{(j)}.$

Intuitively, the $i$-th defender subteam should react to the splitting of the
$i$-th attacker subteam in the following manner. First, the $i$-th defender
subteam is divided into “sub-subteams”, according to the $i$-th attacker
subteam’s splitting action $\bm{f}_{i}$ from the previous time step (see
Figure 6). The $j$-th defender sub-subteam of its $i$-th subteam then
counteracts the $j$-th attacker sub-subteam that moves from node $i$ to node
$j$. This counteraction is achieved by the defender sub-subteam applying the
action $K^{(i\to j)}$.

Following the intuition above, the $j$-th sub-subteam of the $i$-th defender
subteam at time step $t$ has the configuration
$[\bm{f}_{i}]_{j}\mathbf{x}_{t}^{(i)}=\frac{[\bm{f}_{i}]_{j}[\mathbf{y}_{t-1}]_{i}}{Y}\hat{\mathbf{x}}^{(i)}_{t}$,
and it applies the action $K^{(i\to j)}$ to counteract the attacker sub-
subteam that moved from node $i$ to node $j$. The next configuration achieved
by this defender sub-subteam is then given by

$\mathbf{x}_{t+1}^{(i\to
j)}=\frac{[\bm{f}_{i}]_{j}[\mathbf{y}_{t-1}]_{i}}{Y}K^{(i\to
j)}\hat{\mathbf{x}}_{t}^{(i)}=\frac{[\bm{f}_{i}]_{j}[\mathbf{y}_{t-1}]_{i}}{Y}\hat{\mathbf{x}}_{t+1}^{(i\to
j)}.$

Note that $\mathbf{x}_{t+1}^{(i\to j)}$ is only a part of the new $j$-th
defender subteam, which originated from the previous $i$-th subteam.

By collecting defender resources originating from different subteams that
reacted to the attacker resources that ended up at node $j$ (i.e.,
$\mathbf{x}_{t+1}^{(i\to j)}$ for $i\in\mathcal{N}_{j}$), the new $j$-th
defender subteam can be computed as

$\mathbf{x}_{t+1}^{(j)}=\sum_{i\in\mathcal{V}}\mathbf{x}_{t+1}^{(i\to
j)}=\sum_{i\in\mathcal{V}}\frac{[\bm{f}_{i}]_{j}[\mathbf{y}_{t-1}]_{i}}{Y}\hat{\mathbf{x}}_{t+1}^{(i\to
j)}.$ (27)

We now verify that this is a valid defender subteam, i.e., it is a state in
the corresponding Q-set (scaled by the size of the attacker subteam). By the
definition in (23), the rescaled new $j$-th subteam is

$\hat{\mathbf{x}}_{t+1}^{(j)}=\frac{Y}{[\mathbf{y}_{t}]_{j}}\mathbf{x}_{t+1}^{(j)}=\sum_{i}\frac{[\bm{f}_{i}]_{j}[\mathbf{y}_{t-1}]_{i}}{[\mathbf{y}_{t}]_{j}}\hat{\mathbf{x}}_{t+1}^{(i\to
j)}.$ (28)

Noting that
$\sum_{i}[\bm{f}_{i}]_{j}[\mathbf{y}_{t-1}]_{i}=\sum_{i}[F_{t-1}]_{ji}[\mathbf{y}_{t-1}]_{i}=[\mathbf{y}_{t}]_{j}$,
we see that $\hat{\mathbf{x}}_{t+1}^{(j)}$ is a convex combination of the
states $\\{\hat{\mathbf{x}}_{t+1}^{(i\to j)}\\}_{i}$. Since Q-sets are
polytopes (Theorem 4), and also since $\hat{\mathbf{x}}_{t+1}^{(i\to
j)}\in{\mathcal{Q}}_{k-1}^{(j)}$ for all $i\in\mathcal{V}$ by construction, we
conclude that $\hat{\mathbf{x}}_{t+1}^{(j)}\in{\mathcal{Q}}_{k-1}^{(j)}$.
Thus, the new configuration at time $t+1$ can be written as a superposition of
valid subteams.

Finally, since
$\mathbf{x}_{t}=\sum_{i,j}\frac{[\mathbf{y}_{t-1}]_{i}[\bm{f}_{i}]_{j}}{Y}\hat{\mathbf{x}}_{t}^{(i)}$,
we can construct the overall defender action $K_{t}$ that takes
$\mathbf{x}_{t}$ in (25) to $\mathbf{x}_{t+1}$ in (26) based on the sub-
subteam actions $K^{(i\to j)}$ (see Lemma 11 in Appendix D), which completes
the proof.

∎

A minimum working example that illustrates the concepts in the above proof is
presented in Figure 7. The readers can use the figure as a roadmap for better
understanding of the intuition behind Theorem 7.

Figure 7: A minimum working example for the proof of Lemma 6.

As a direct consequence of Theorem 7, we can generalize the defender strategy
in Section 4 to scenarios where the attacker splits its resource over multiple
nodes.

Inputs: Graph $\mathcal{G}$, total resources $X$ and $Y$, attacker initial
allocation $\mathbf{y}_{-1}$, game horizon $T$;

1 Construct Q-sets via Algorithm 1;

2 $\mathcal{I}_{-1}\leftarrow\\{i\,|\,[\mathbf{y}_{-1}]_{i}>0\\}$;

3
$k_{\mathrm{max},0}\leftarrow\operatorname*{arg\,max}_{k}\big{\\{}k\;|\;\Delta_{X}\cap{\mathcal{Q}}_{k}^{(i)}\neq\varnothing\;\forall
i\in\mathcal{I}_{-1}\big{\\}}$;

4 for  _$i\in\mathcal{I}_{-1}$_ do

5 $\hat{\mathbf{x}}^{(i)}_{0}\leftarrow$ any element in
$\Delta_{X}\cap{\mathcal{Q}}_{k_{\max,0}}^{(i)}$

6 end for

7$\mathbf{x}_{0}\leftarrow\sum\frac{[\mathbf{y}_{-1}]_{i}}{Y}\hat{\mathbf{x}}^{(i)}_{0}$;

Return: Initial allocation $\mathbf{x}_{0}$, initial subteams
$\\{\hat{\mathbf{x}}_{0}^{(i)}\\}_{i}$, longest guaranteed defense time
$k_{\max,0}$

Algorithm 6 Initial Defender Allocation

Inputs: Q-sets, previous scaled subteams
$\\{\hat{\mathbf{x}}_{t-1}^{(i)}\\}_{i}$, observed attacker allocations
$\mathbf{y}_{t-1}$ and $\mathbf{y}_{t-2}$;

1 $\mathcal{I}_{t-1}\leftarrow\\{i\,|\,[\mathbf{y}_{t-1}]_{i}>0\\}$;

2
$k_{\mathrm{max},t}\leftarrow\operatorname*{arg\,max}_{k}\left\\{k\;|\;\mathcal{R}(\hat{\mathbf{x}}_{t-1}^{(i)})\cap{\mathcal{Q}}_{k}^{(i)}\neq\varnothing\;\forall\;i\in\mathcal{I}_{t-1}\right\\}$;
$\triangleright$ find the longest survival time

// Generate defender subteams’ actions

3 for  _$i\in\mathcal{V}$ s.t. $\hat{\mathbf{x}}_{t-1}^{(i)}\neq\bm{0}$_ do

4

5 $\bm{f}_{i}\leftarrow$ $i$-th column of $F_{t-2}$;

// Reaction to attacker subteam i splitting

6 for  _$j\in\mathcal{V}$ s.t. $[\bm{f}_{i}]_{j}\neq 0$_ do

7 $\hat{\mathbf{x}}^{(i\to j)}_{t}\leftarrow$ element in
$\mathcal{R}{(\mathbf{x}_{t-1}^{(i)})}\cap{\mathcal{Q}}_{k_{\max,t}}^{(j)}$;

8 $K^{(i\to j)}\leftarrow$ action s.t. $\hat{\mathbf{x}}^{(i\to
j)}_{t}=K^{(i\to j)}\hat{\mathbf{x}}_{t-1}^{(i)}$;

9 end for

10

11 end for

12

// New subteams

13 for  _$i\in\mathcal{V}$_ do

14
$\mathbf{x}_{t}^{(i)}\leftarrow\sum_{j}\frac{[\mathbf{y}_{t-2}]_{j}}{Y}[\bm{f}_{j}]_{i}\hat{\mathbf{x}}^{(j\to
i)}_{t}$131313 Note that
$\mathbf{x}_{t}^{(i)}=\frac{[\mathbf{y}_{t-1}]_{i}}{Y}\hat{\mathbf{x}}_{t}^{(i)}=\frac{[\mathbf{y}_{t-1}]_{i}}{Y}\sum_{j}\frac{[\mathbf{y}_{t-2}]_{j}}{[\mathbf{y}_{t-1}]_{i}}[\bm{f}_{j}]_{i}\hat{\mathbf{x}}^{(j\to
i)}_{t}=\sum_{j}\frac{[\mathbf{y}_{t-2}]_{j}}{Y}[\bm{f}_{j}]_{i}\hat{\mathbf{x}}^{(j\to
i)}_{t}$, for $i$ such that $[\mathbf{y}_{t-1}]_{i}>0$. If
$[\mathbf{y}_{t-1}]_{i}=0$, then there is no need to create a subteam
designated for node $i$. ;

15 end for

16$\mathbf{x}_{t}=\sum_{i}\mathbf{x}_{t}^{(i)}$;

17$K_{t}\leftarrow$ overall action from (42);

18

Return: Action $K_{t}$, resultant subteams
$\\{\hat{\mathbf{x}}_{t+1}^{(i)}\\}_{i}$, guaranteed defense time
$k_{\max,t}$.

Algorithm 7 Feedback Defender Strategy

###  5.2 The Critical Resource Ratio

Before we move on to our formal analysis, we present some basic properties of
CRR that are straightforward to obtain.

######  Proposition 2.

The sequence $(\alpha_{T})_{T=1}^{\infty}$ is monotonically nondecreasing with
respect to horizon $T$.

This property is obvious from the fact that the ability to defend over $T$
time steps immediately implies the ability to defend any duration less than
$T$. 1313footnotetext:  Note that
$\mathbf{x}_{t}^{(i)}=\frac{[\mathbf{y}_{t-1}]_{i}}{Y}\hat{\mathbf{x}}_{t}^{(i)}=\frac{[\mathbf{y}_{t-1}]_{i}}{Y}\sum_{j}\frac{[\mathbf{y}_{t-2}]_{j}}{[\mathbf{y}_{t-1}]_{i}}[\bm{f}_{j}]_{i}\hat{\mathbf{x}}^{(j\to
i)}_{t}=\sum_{j}\frac{[\mathbf{y}_{t-2}]_{j}}{Y}[\bm{f}_{j}]_{i}\hat{\mathbf{x}}^{(j\to
i)}_{t}$, for $i$ such that $[\mathbf{y}_{t-1}]_{i}>0$. If
$[\mathbf{y}_{t-1}]_{i}=0$, then there is no need to create a subteam
designated for node $i$.

######  Proposition 3 (Lowerbound of $\alpha_{T}$ [23]).

For a general graph and an arbitrary $T$, $\alpha_{T}$ is bounded from below
by $\underline{\alpha}=d^{+}_{\mathrm{max}}$, where
$d^{+}_{\mathrm{max}}=\max_{j\in\mathcal{V}}d^{+}_{j}$ is the maximum out-
degree of the graph.

This property can be proved by considering the case where the attacker
initially concentrates all its resources at the node with the maximum out
degree. Unless the defender allocates an equal amount or more to every one of
the neighboring nodes, the attacker will have an action to win the game, i.e.,
move all the attacker resources to the neighboring node where the defender
allocates less than $Y$ unit of resources.

######  Proposition 4 (Upperbound of $\alpha_{T}$).

For a strongly-connected graph and an arbitrary $T\in[0,\infty]$, $\alpha_{T}$
is bounded from above by $\bar{\alpha}=\sum_{i\in\mathcal{V}}L_{i}$, where
$L_{i}$ is the length of the shortest loop that passes through node $i$.

###### Proof.

Since the graph is strongly connected, for every node $i$, there is a loop
that passes through $i$. Then, for every node $i$, the defender can have
$L_{i}Y$ unit of resource patrolling the shortest loop that passes through
$i$, resulting every node on the loop (in particular, node $i$) having $Y$
unit of defender resource at all time. ∎

We leverage the results in the previous sections to identify the critical
resource ratio (CRR, see Definition 1). In Section 4, we have shown that being
in ${\mathcal{Q}}_{k}^{(i)}$ is the necessary and sufficient for the defender
to defend against any no-splitting attacker strategy that starts from
$\mathbf{y}_{-1}=\mathbf{y}^{(i)}$ for $k$ steps. This leads to an
intermediate version of the CRR defined for the case of no-splitting attacker
starting on node $i$:

$\beta_{k}^{(i)}\triangleq\min_{\mathbf{x}\in{\mathcal{Q}}_{k}^{(i)}}\mathbf{1}^{\top}\mathbf{x}.$
(29)

Given that the attacker can freely select its initial state $\mathbf{y}_{-1}$,
we define the k-step CRR given a no-splitting attacker as

$\beta_{k}\triangleq\max_{i\in\mathcal{V}}\beta_{k}^{(i)}.$ (30)

######  Proposition 5.

If ${\mathcal{Q}}_{\infty}^{(i)}\neq\varnothing$ for some $i\in\mathcal{V}$,
then $\beta_{\infty}^{(i)}=\beta_{\infty}^{(j)}<\infty$ for all
$i,j\in\mathcal{V}$.

###### Proof.

Note that for any finite $k$, $\beta_{k+1}^{(i)}\geq\beta_{k}^{(j)}$ for all
$j\in\mathcal{N}_{i}$, since for a defender to defend an attacker starting
from node $i$ for $k+1$ steps, it has to be able to defend $k$ steps after the
attacker moves to node $j$. Consequently, we have
$\beta_{\infty}^{(i)}\geq\beta_{\infty}^{(j)}$ for all $j\in\mathcal{N}_{i}$.
Since the graph is strongly connected, there exists a directed path from $j$
to $i$. One can then cascade the inequality along the path from $j$ to $i$,
and it follows that $\beta_{\infty}^{(j)}\geq\beta_{\infty}^{(i)}$. ∎

The following result shows that the general CRR is identical to the one
defined for no-splitting attacker.

######  Lemma 7 (Sufficient resource).

Suppose that the defender has enough resource to defend against all no-
splitting attacker strategies for $k$ time steps. Then, the defender can guard
against any attacker strategy for $k$ time steps, which implies

$\alpha_{k}=\beta_{k}.$ (31)

###### Proof.

It is obvious that $\alpha_{k}\geq\beta_{k}$, since it is necessary to guard
against no-splitting strategies. Consequently, it suffices to show that
$X=\beta_{k}{}Y$ is sufficient to guard against any admissible attacker
strategy, including the ones with splitting.

Using the result of Theorem 7 with $t=0$ and $T=k$, consider the following
initial defender state that is sufficient to guard against any given
$\mathbf{y}_{-1}$ over the next $k$ time steps:

$\mathbf{x}_{0}=\frac{1}{Y}\sum_{i}[\mathbf{y}_{-1}]_{i}\,\hat{\mathbf{x}}_{0}^{(i)},\text{\;\;where\;}\hat{\mathbf{x}}_{0}^{(i)}\in{\mathcal{Q}}_{k}^{(i)}.$
(32)

The minimum amount of resource required to achieve the above allocation is
given by

$\displaystyle\min_{(\hat{\mathbf{x}}_{0}^{(1)},\ldots,\hat{\mathbf{x}}_{0}^{(|\mathcal{V}|)})\in{\mathcal{Q}}_{k}^{(1)}\times\cdots\times{\mathcal{Q}}_{k}^{(|\mathcal{V}|)}}\bm{1}^{\top}\Big{(}\frac{1}{Y}\sum_{i}[\mathbf{y}_{-1}]_{i}\,\hat{\mathbf{x}}_{0}^{(i)}\Big{)}=$
$\displaystyle=\frac{1}{Y}\sum_{i}[\mathbf{y}_{-1}]_{i}\,\Big{(}\min_{\hat{\mathbf{x}}_{0}^{(i)}\in{\mathcal{Q}}_{k}^{(i)}}\bm{1}^{\top}\hat{\mathbf{x}}_{0}^{(i)}\Big{)}=\frac{1}{Y}\sum_{i}[\mathbf{y}_{-1}]_{i}\,\beta_{k}^{(i)}X$
$\displaystyle\leq\frac{1}{Y}\sum_{i}[\mathbf{y}_{-1}]_{i}\beta_{k}X=\beta_{k}X,$

where the equality is given when the attacker initial state $\mathbf{y}_{-1}$
places all its resources on the node
$i^{*}\in\operatorname*{arg\,max}_{i\in\mathcal{V}}\beta_{k}^{(i)}$. Hence, we
have $\alpha_{k}=\beta_{k}$. ∎

######  Corollary 2 (No Incentive to Split).

For a given graph $\mathcal{G}$ and resources $X$ and $Y$, the attacker has a
strategy to win the dDAB game if and only if it has a no-splitting winning
strategy.

###### Proof.

The sufficiency is given trivially. The necessity comes as a direct
consequence of Lemma 7. If the attacker can win a dDAB game with some
strategy, we have that $Y\geq\alpha_{k}X$. From Lemma 7, we obtain
$Y\geq\alpha_{k}X=\beta_{k}X$, which implies that the attacker can also win
with a no-splitting strategy.

∎

The following corollary regarding the indefinite defense is a direct
consequence of Corollary 2.

######  Corollary 3.

If an indefinite defense is feasible against all no-splitting attacker
strategies, the defender can also indefinitely defend against any attacker
strategies.

###### Proof.

Note that if an attacker can win the game with a splitting strategy, it must
breach a node at some finite time step. From Corollary 2, it can also win
without splitting, which contradicts the assumption.

∎

##  6 Algorithmic Solution

In this section, we first develop an algorithm to numerically construct the
Q-sets. The proposed algorithm also helps us prove Theorem 4, which states
that all Q-sets are polytopes. Recall that we treated the next state
$\mathbf{x}_{t+1}$ in the reachable set as the action for the defender to take
at time step $t$. In reality, however, the defender needs to find a feasible
action $K_{t}\in\mathcal{K}$ to reach $\mathbf{x}_{t+1}$. In the second
subsection, we formulate this action extraction problem as a linear program,
which can be solved efficiently.

###  6.1 Q-set Construction

Recall the recursive definition of the Q-sets in (19b):

${\mathcal{Q}}_{k}^{(i)}=\Big{\\{}\mathbf{x}\;\big{|}\;\mathbf{x}\in\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{k-1}^{(j)}\neq\varnothing~{}\forall
j\in\mathcal{N}_{i}\Big{\\}}.$

To numerically construct the Q-sets, we first examine the properties of the
set
$\\{\mathbf{x}|\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{k}^{(j)}\neq\varnothing\\}$.
This set consists of states from which the defender can reach
${\mathcal{Q}}_{k}^{(j)}$ at the next time step. It is unclear yet, whether
these “inverse reachable sets” induce nice properties for the Q-sets.

We formally define the inverse reachable set of some set $P$ as follow:

######  Definition 10 (Inverse Reachable Set).

Given a set $P\subseteq\mathbb{R}^{N}_{\geq 0}$, we define the inverse
reachable set of $P$ as

$\mathcal{R}^{-1}(P)=\left\\{\mathbf{x}\;\big{|}\;\mathcal{R}(\mathbf{x})\cap
P\neq\varnothing\right\\}.$ (33)

With the notion of the inverse reachable set, we can simplify the recursive
construction of Q-sets in (19) as

$\displaystyle{\mathcal{Q}}_{0}^{(i)}$
$\displaystyle=\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)}),$ (34a)
$\displaystyle{\mathcal{Q}}_{k}^{(i)}$
$\displaystyle=\left(\bigcap_{j\in\mathcal{N}_{i}}\mathcal{R}^{-1}({\mathcal{Q}}_{k-1}^{(j)})\right)\;\cap\;\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})\quad$
$\displaystyle\forall~{}k\geq 1.$ (34b)

We now discuss the computation of the inverse reachable sets. Note that any
admissible action $K\in\mathcal{K}$ can be reversed. That is, if one can use
an action to reach $\mathbf{x}_{t+1}$ from some $\mathbf{x}_{t}$, then one can
also find a reverse action that brings the defender’s allocation from
$\mathbf{x}_{t+1}$ to $\mathbf{x}_{t}$. Based on this intuition, we introduce
the notion of a reversed graph, which has the same node set as the original
graph but with all the directed edges reversed.

######  Definition 11.

For a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with connectivity matrix
$A$, its reversed graph
$\widetilde{\mathcal{G}}=(\mathcal{V},\widetilde{\mathcal{E}})$ is defined
based on the connectivity matrix $\widetilde{A}=A^{\top}$.

We denote $\widetilde{\mathcal{K}}$ as the admissible action set of
$\widetilde{\mathcal{G}}$. The reachable set for the reversed graph is then
defined as

$\widetilde{\mathcal{R}}(\mathbf{x})=\left\\{\mathbf{x}^{\prime}\;|\;\exists\widetilde{K}\in\widetilde{\mathcal{K}}~{}~{}\text{s.t.}~{}~{}\mathbf{x}^{\prime}=\widetilde{K}\mathbf{x}\right\\}.$

The following lemma relates the (forward) actions and the reversed actions.

######  Lemma 8.

Given an arbitrary admissible action under the original graph
$K\in\mathcal{K}$ and an arbitrary starting state $\mathbf{x}$, suppose the
resultant state is $\mathbf{x}^{\prime}=K\mathbf{x}$. We can reverse the
action using an admissible action under the reversed graph
$\widetilde{K}\in\widetilde{\mathcal{K}}$ to achieve
$\mathbf{x}=\widetilde{K}\mathbf{x}^{\prime}$. The reverse action
$\widetilde{K}$ can be constructed as

$\left[\widetilde{K}\right]_{ij}=\begin{cases}\frac{[K]_{ji}[\mathbf{x}]_{i}}{[\mathbf{x}^{\prime}]_{j}}&\text{if
}[\mathbf{x}^{\prime}]_{j}>0,\\\
\frac{1}{\sum_{i}\left[\widetilde{A}\right]_{ij}}&\text{if
}[\mathbf{x}^{\prime}]_{j}=0\text{ and }[\widetilde{A}]_{ij}=1,\\\ 0&\text{if
}[\mathbf{x}^{\prime}]_{j}=0\text{ and }[\widetilde{A}]_{ij}=0.\end{cases}$
(35)

###### Proof.

See Appendix E. ∎

Based on the above result, we have the equivalence between the inverse
reachable set of the graph $\mathcal{G}$ and the reachable set of the reversed
graph $\widetilde{\mathcal{G}}$.

######  Lemma 9.

For any graph $\mathcal{G}$, we have

$\mathcal{R}^{-1}(P)=\widetilde{\mathcal{R}}(P)\qquad\forall\;P\subseteq\mathbb{R}_{\geq
0}^{N}.$

###### Proof.

See Appendix E. ∎

Lemma 9 leads directly to the following computationally-friendly definition of
the Q-sets:

$\displaystyle{\mathcal{Q}}_{0}^{(i)}$
$\displaystyle=\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)}),$ (36a)
$\displaystyle{\mathcal{Q}}_{k}^{(i)}$
$\displaystyle=\Big{(}\bigcap_{j\in\mathcal{N}_{i}}\widetilde{\mathcal{R}}({\mathcal{Q}}_{k-1}^{(j)})\Big{)}\;\cap\;\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})\quad$
$\displaystyle\forall~{}k\geq 1.$ (36b)

Based on the above result, we can easily prove that the Q-sets are polytopes.

See 4

###### Proof.

Recall that the reachable set of a polytope is also a polytope (see Lemma 2).
With the equivalent Q-set definition in (36), one can easily show through an
inductive argument that all Q-sets are polytopes. ∎

As a direct consequence of Q-sets being polytopes, we have the following
corollary.

######  Corollary 4.

The k-step CRR, $\alpha_{k}$, is attained at one of the vertices of the Q-set.

###### Proof.

Since the Q-sets are polytopes, the optimization for $\beta_{k}^{(i)}$ is a
linear program as in (29). Furthermore, since the CRR is bounded from below by
zero, an optimal solution is attainable and can be attained on one of the
vertices. ∎

###  6.2 Action Extraction From Q-Sets

Recall that all the results we obtained in the previous sections directly
considered the states in the reachable set as the actions of the defender.
However, when a dDAB game is played, the Player still needs to deploy a
feasible action $K_{t}$ to achieve the desired next state. Formally, the
action extraction problem is formulated as:

######  Problem 3 (Action Extraction).

Given defender’s current state
$\mathbf{x}_{t}\in{\mathcal{Q}}_{t}^{(i_{t-1})}$ and the observed attacker’s
next state $i_{t}\in\mathcal{N}_{i_{t-1}}$, find the feasible action
$K_{t}\in\mathcal{K}$ that takes the defender to a new state
$\mathbf{x}_{t+1}\in\mathcal{R}(\mathbf{x}_{t})\cap{\mathcal{Q}}_{t}^{(i_{t})}$.

By the construction of ${\mathcal{Q}}_{t}^{(i_{t})}$, the existence of such
new state $\mathbf{x}_{t+1}$ is guaranteed. We propose to find a feasible
action $K_{t}$ that transitions the system to $\mathbf{x}_{t+1}$ by solving a
simple matrix equation. Recall the characterization of
$\mathcal{R}(\mathbf{x}_{t})$ in Lemma 1. Specifically, if
$\mathbf{x}_{t+1}\in\mathcal{R}(\mathbf{x}_{t})\cap{\mathcal{Q}}_{t}^{(i_{t})}\subseteq\mathcal{R}(\mathbf{x}_{t})$,
it satisfies

$\displaystyle\mathbf{x}_{t+1}=\sum_{\ell}\lambda^{(\ell)}\left(\hat{K}^{(\ell)}\mathbf{x}_{t}\right).$
(37)

Any $\mathbf{x}_{t+1}$ in the intersection would have the safety guarantee,
and consequently the selection can be arbitrary. Since the intersection set is
a bounded polytope, one may simply select the centroid or a vertex of the
intersection as $\mathbf{x}_{t+1}$. Since $\mathbf{x}_{t}$ and
$\\{\hat{K}^{(\ell)}\\}_{\ell}$ are all known variables at time step $t$, the
vector-form coefficients $\bm{\lambda}$ can be found by solving the following
problem:

$\Phi\bm{\lambda}=\mathbf{x}_{t+1},~{}~{}\text{s.t.}~{}~{}\bm{\lambda}\geq
0\text{ and }\sum_{\ell}\lambda^{(\ell)}=1,$ (38)

where the matrix $\Phi\in\mathbb{R}^{|\mathcal{V}|\times|\hat{\mathcal{K}}|}$
has
$\left(\hat{K}^{(\ell)}\mathbf{x}_{t}\right)_{\ell=1}^{|\hat{\mathcal{K}}|}$
as its columns. Again, the feasibility of (38) is guaranteed, due to the
construction of $\mathcal{R}(\mathbf{x}_{t})$. With the solved $\bm{\lambda}$,
the feasible action that brings the defender from $\mathbf{x}_{t}$ to
$\mathbf{x}_{t+1}$ is given by

$K_{t}=\sum_{\ell}\lambda^{(\ell)}\hat{K}^{(\ell)}.$

##  7 Numerical Illustrations

This section provides numerical examples that illustrate the results developed
in the previous sections.

###  7.1 Q-set Propagation

Figure 8 illustrates how the Q-sets, ${\mathcal{Q}}_{k}^{(i)}$, change with
the horizon $k$. For the three-node graph selected for this example, the
propagation in Algorithm 1 converges after four iterations, at which point the
algorithm finds that $k_{\infty}=4$. The CRR for this graph is
$\alpha_{\infty}=3$.

Figure 8: Illustration of Q-sets evolution with different horizons $k$. (a)
The three node graph used for this example. (b) We consider a single unit of
attacker resource, and ${\mathcal{Q}}_{k}^{(i)}$ for nodes $i=\\{1,2\\}$ and
horizon $k=\\{0,2,4\\}$ are shown here for brevity. The red dot in each figure
indicates the element in the Q-set that achieves the smallest amount of
resource for $k$-step defense, i.e., $\beta_{k}^{(i)}$ in (29). (c) The
evolution of $\beta_{k}^{(i)}$ on each node, until they converge at
$k_{\infty}=6$.

It is worth noting that the Q-set for a given node may not change at every
time step: e.g., ${\mathcal{Q}}_{k}^{(1)}$ changes only twice between $k=1$ to
$2$ and between $k=3$ to $4$.

We can verify the monotonicity of the Q-sets described in Remark 5 by
observing how the Q-sets get “carved off” and become smaller as $k$ increases.
Specifically, some regions of the state space with small amount of resources
get excluded when $k$ changes from $0$ to $2$ and similarly from $2$ to $4$.
As an example, the state $\mathbf{x}=[0,0,1]\in{\mathcal{Q}}_{0}^{(1)}$ can
guard against any immediate next action made by a unit attacker at node 1
(i.e., $\mathbf{y}^{(1)}$). This is shown by the red dot in
${\mathcal{Q}}_{0}^{(1)}$ (top left subfigure in Figure 8). However, this
state is insufficient to defend over two time steps, and thus it is not
included in ${\mathcal{Q}}_{2}^{(1)}$. Similarly, we can see that the state
$\mathbf{x}=[0,0,2]\in{\mathcal{Q}}_{2}^{(1)}$ is sufficient to guard over two
time steps, but not for four or more time steps. The vertices of
${\mathcal{Q}}_{4}^{(1)}$ (top right subfigure) are $[0,0,3]$, $[1,1,1]$,
$[1,0,2]$, and $[0,2,1]$. One can verify that any of these states, as well as
any convex combination of these states is sufficient to guard against one unit
of no-splitting attacker indefinitely.

###  7.2 Effect of Edges on CRR

The relationship between the CRR and the graph structure is not
straightforward. One might, for example, expect a positive correlation between
the number of edges and the CRR, since an increase in the number of outgoing
edges from a node increases the number of neighboring nodes that must be
covered by the defender. However, we show by a counter-example (found by the
algorithm) that this is not the case.

The following example illustrates how the effect of additional edges can
drastically change the CRR. Figure 9 provides examples of directed graphs with
five nodes but with different edge sets. The corresponding indefinite-defense
CRR $\alpha_{\infty}$ for each graph is obtained using Algorithm 1.

In the simplest case of the ring graph, the defender only needs the same
amount of resources as the attacker to guarantee indefinite defense, which
matches the results in [23]. Interestingly, by adding only one directed edge
connecting node 3 and node 4 to the graph, the CRR changes drastically to
$\alpha_{\infty}=5$. By further adding a self-loop on node 4, the CRR further
increases to $7$. Notably, this is greater than the number of nodes on this
graph. We conjecture that $\alpha_{\infty}>|\mathcal{E}|$ only occurs for
directed graphs, but this remains to be verified. However, if we add a self-
loop to node 3 instead of node $4$, the CRR $\alpha_{\infty}$ decreases from 5
to $3$, which implies that additional edges may benefit the defender as well.

Figure 9: Examples of how CRR changes with the graph structure. All self-loops
are explicitly presented. The necessary and sufficient amount of blue agents
are placed in the safe set for a given red agent in each figure.

###  7.3 Non-integer Resource Ratio

Another natural conjecture regarding the CRR is that it is always integer-
valued. However, through the following dDAB example over a six-node graph (see
Figure 12), we show that the resource ratio can be non-integer-valued for
finite-horizon dDAB games. For this example, Algorithm 1 returns that
$\alpha_{2}=3.5$. In other words, 3 units of defender resources is not enough
for a two-step defense against a single unit of attacker resource, but 3.5
units is sufficient.

Figure 10: A six-node graph. All self-loops are explicitly presented.

Figure 11 presents a game tree where 3 units of defender resource fail to
defend against a single attacker. The attacker selects to start on node 3,
i.e. $\mathbf{y}_{-1}=\mathbf{y}^{(3)}$. The initial defender allocation
corresponds to the only feasible state with three unit of defender resource in
the $\mathcal{P}_{\text{req}}(\mathbf{y}^{(3)})$. The attacker then moves from
node 3 to node 2 at time step 0. Note that with the attacker on node 2, it is
necessary for the defender to place one unit of resource on both nodes 5 and 6
to be in the required set, which leads to the three possible configurations at
the beginning of time step 1. For each of the configurations, the attacker has
a corresponding move, which leads to a $\mathcal{P}_{\text{req}}$ (marked with
light blue) that the defender cannot achieve at the beginning of time step 2.
For example, in trajectory (i), the attacker moves from node 2 to node 5 at
time step 1. This move leads to a $\mathcal{P}_{\text{req}}$ that has one unit
of defender on each of the nodes 2, 3 and 5, which cannot be achieved by the
defender.141414Notice that node 2 does not have a self-loop. Consequently, the
attacker has a strategy to defeat the defender at the end of time step 2.

Figure 11: A two-time step game tree starting with one unit of attacker and
three unit of defender. Regardless the strategy used by the defender, the
defender will be defeated at the end of time step 2.

Figure 12 presents the game tree starting with 3.5 units of defender resource,
and we show that regardless of the (no-splitting) strategy used by the
attacker, the defender can defend until the end of time step 2. Since
$\alpha_{2}=3.5$ is attained with $\beta_{2}^{(3)}=3.5$, we let the attacker
start with $\mathbf{y}_{-1}=\mathbf{y}^{(3)}$. It is easy to verify that the
initial defender state $\mathbf{x}_{0}$ is in
$\mathcal{P}_{\text{req}}(\mathbf{y}^{(3)})$. The attacker has three feasible
moves at $t=0$: move to node 2, move to node 5, or stay at node 3. We only
present the first two moves in Figure 12, since for the third move, the
defender can just maintain its current state as a countermeasure and does not
lose any defense time.151515Even though node 2 does not have a self-loop, the
defender resources on nodes 2 and 5 can swap locations to keep the current
configuration. Furthermore, we focus on explaining the attacker’s move to node
2, since the defense against attacker moving to node 5 can be achieved without
using the half unit of resource on node 6. After observing that the attacker
moves to node 2, the defender takes action (a)161616Action (a) splits defender
resources so that the unit of defender on node 2 moves to node 6; the half
unit on node 3 moves to node 2 and the other half stays on node 3; the half
unit on node 6 moves to node 1, and finally the unit on node 5 stays. and
arrives at the state at the beginning of time step 1. The attacker then has
two options, either move to node 5 or to node 6. Suppose the attacker moves to
node 6, the defender initiates action (b)171717Action (b) moves the half unit
on node 1 to node 5; the half unit on node 2 to node 5, the unit on node 6 to
node 1, and the rest of the resources on nodes 3 and 5 stay., which ensures
that the configuration at the beginning of time step 2 is still in the
required set. Similar moves can be made for trajectory (ii) to ensure the
defense until the end of time step 2. For more details regarding the defender
actions (a) to (c), see Appendix F.

Through splitting and re-grouping its resources, the defender achieves defense
with only an additional half unit of resource. The strategy presented is found
by the algorithms in Section 4, which verifies the efficacy of the proposed
approach.

Figure 12:  (Left) The two time-step game tree over a six-node graph. All
self-loops are explicitly presented. The attacker and defender resources are
visualized as red and blue boxes, and the blue triangles represent half unit
of defender resource. Different blue colors are introduced to better visualize
the splitting and regrouping of the defender resources. (Right) The evolution
of $\beta_{k}^{(i)}$ on each node, until they converge to
$\alpha_{\infty}\\!=\\!4$ at horizon $k_{\infty}\\!=\\!6$.

##  8 Open Problems

The Q-prop algorithm in Algorithm 1 is an iterative algorithm that finds the
Q-sets. Through the sink problem in Section A, we have shown that there are
graphs on which the Q-prop algorithm does not converge. Perhaps there are
general conditions on the graph that guarantees that the Q-prop algorithm
converges to the indefinite defense Q-sets. It is also of interest to see the
convergence behavior of the algorithm, i.e. asymptotic vs. finite iteration.

Empirically, we observed that the critical resource ratio $\alpha_{\infty}$
for undirected graph is always integer-valued. We further observed that
$\alpha_{\infty}\leq|\mathcal{V}|$ for all undirected graphs and
$\alpha_{\infty}>|\mathcal{V}|$ only for directed graphs. It is unclear
whether these two observations can be formally proved or if additional
strengthened conditions on the underlying graphs are required.

##  9 Conclusion

In this work, we formulated a dynamic adversarial resource-allocation problem
by combining the Colonel Blotto game with ideas from population dynamics on
graphs. Instead of achieving a desired allocation instantly, we require the
resources of each player to traverse through the edges of the graph. An
efficient reachable-set approach is developed to predict the evolution of the
player’s states. We provide a full characterization of the game by deriving
the necessary and sufficient condition (the Q-sets) for either of the player
to win the game and the associated strategies to achieve that. The efficacy of
the proposed approach is verified through numerical simulations. Future work
will investigate conditions required for the convergence of the Q-prop
algorithm, which leads to guaranteed indefinite defense. It is also of
interest to consider heterogeneous resources as in [10] and decentralized
decision-making via the common-information approach [27].

## References

  * [1] G. A. Korsah, A. Stentz, and M. B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” _The International Journal of Robotics Research_ , vol. 32, no. 12, pp. 1495–1512, 2013.
  * [2] A. Khamis, A. Hussein, and A. Elmogy, “Multi-robot task allocation: A review of the state-of-the-art,” _Cooperative Robots and Sensor Networks 2015_ , pp. 31–51, 2015.
  * [3] Y. Xu, G. Gui, H. Gacanin, and F. Adachi, “A survey on resource allocation for 5G heterogeneous networks: Current research, future trends, and challenges,” _IEEE Communications Surveys & Tutorials_, vol. 23, no. 2, pp. 668–695, 2021.
  * [4] X. Bei and S. Zhang, “Algorithms for trip-vehicle assignment in ride-sharing,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 32, no. 1, 2018.
  * [5] A. S. Nair, T. Hossen, M. Campion, D. F. Selvaraj, N. Goveas, N. Kaabouch, and P. Ranganathan, “Multi-agent systems for resource allocation and scheduling in a smart grid,” _Technology and Economics of Smart Grids and Sustainable Energy_ , vol. 3, no. 1, pp. 1–15, 2018.
  * [6] V. Anuradha and D. Sumathi, “A survey on resource allocation strategies in cloud computing,” in _International Conference on Information Communication and Embedded Systems (ICICES2014)_. IEEE, 2014, pp. 1–7.
  * [7] A. Ashok, M. Govindarasu, and J. Wang, “Cyber-physical attack-resilient wide-area monitoring, protection, and control for the power grid,” _Proceedings of the IEEE_ , vol. 105, no. 7, pp. 1389–1407, 2017.
  * [8] K. D. Julian and M. J. Kochenderfer, “Distributed wildfire surveillance with autonomous aircraft using deep reinforcement learning,” _Journal of Guidance, Control, and Dynamics_ , vol. 42, no. 8, pp. 1768–1778, 2019.
  * [9] S. Berman, A. Halász, M. A. Hsieh, and V. Kumar, “Optimized stochastic policies for task allocation in swarms of robots,” _IEEE Transactions on Robotics_ , vol. 25, no. 4, pp. 927–937, 2009.
  * [10] A. Prorok, M. A. Hsieh, and V. Kumar, “The impact of diversity on optimal control policies for heterogeneous robot swarms,” _IEEE Transactions on Robotics_ , vol. 33, no. 2, pp. 346–358, 2017.
  * [11] H. Ravichandar, K. Shaw, and S. Chernova, “STRATA: unified framework for task assignments in large teams of heterogeneous agents,” _Autonomous Agents and Multi-Agent Systems_ , vol. 34, no. 2, pp. 1–25, 2020.
  * [12] V. Tereshchuk, J. Stewart, N. Bykov, S. Pedigo, S. Devasia, and A. G. Banerjee, “An efficient scheduling algorithm for multi-robot task allocation in assembling aircraft structures,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 4, pp. 3844–3851, 2019.
  * [13] K. Lerman, C. Jones, A. Galstyan, and M. J. Matarić, “Analysis of dynamic task allocation in multi-robot systems,” _The International Journal of Robotics Research_ , vol. 25, no. 3, pp. 225–241, 2006.
  * [14] B. Roberson, “The colonel Blotto game,” _Economic Theory_ , vol. 29, no. 1, pp. 1–24, 2006.
  * [15] R. Powell, “Sequential, nonzero-sum “Blotto”: Allocating defensive resources prior to attack,” _Games and Economic Behavior_ , vol. 67, no. 2, pp. 611–615, 2009.
  * [16] R. Chandan, K. Paarporn, and J. R. Marden, “When showing your hand pays off: Announcing strategic intentions in colonel Blotto games,” in _American Control Conference (ACC)_ , Denver, CO, 2020, pp. 4632–4637.
  * [17] D. Kovenock and B. Roberson, “The optimal defense of networks of targets,” _Economic Inquiry_ , vol. 56, no. 4, pp. 2195–2211, 2018.
  * [18] O. Gross and R. Wagner, “A continuous colonel Blotto game,” RAND Corporation, Tech. Rep., 1950.
  * [19] K. Paarporn, R. Chandan, M. Alizadeh, and J. R. Marden, “Characterizing the interplay between information and strength in Blotto games,” in _Conference on Decision and Control (CDC)_ , Nice, France, 2019, pp. 5977–5982.
  * [20] K. A. Konrad, “Budget and effort choice in sequential colonel Blotto campaigns,” _CESifo Economic Studies_ , vol. 64, no. 4, pp. 555–576, 2018\.
  * [21] M. Hajimirsaadeghi and N. B. Mandayam, “A dynamic colonel Blotto game model for spectrum sharing in wireless networks,” in _Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2017, pp. 287–294.
  * [22] T. Klumpp, K. A. Konrad, and A. Solomon, “The dynamics of majoritarian Blotto games,” _Games and Economic Behavior_ , vol. 117, pp. 402–419, 2019\.
  * [23] D. Shishika, Y. Guan, M. Dorothy, and V. Kumar, “Dynamic defender-attacker Blotto game,” in _2022 American Control Conference (ACC)_ , Atlanta, GA, 2022, pp. 4422–4428.
  * [24] D. Bertsimas and J. N. Tsitsiklis, _Introduction to Linear Optimization_. Athena Scientific Belmont, MA, 1997, vol. 6.
  * [25] Y. Guan, L. Pan, D. Shishika, and P. Tsiotras, “Chasing convex bodies generated by an adversary,” _arXiv preprint arXiv:2209.13606_ , 2022.
  * [26] J. Friedman and N. Linial, “On convex body chasing,” _Discrete & Computational Geometry_, vol. 9, no. 3, pp. 293–321, 1993.
  * [27] Y. Guan, M. Afshari, and P. Tsiotras, “Zero-sum games between mean-field teams: A common information and reachability based analysis,” _arXiv preprint arXiv:2303.12243_ , 2023.

##  Appendix A Example of Degenerate Case with Non-strongly-connected Graph

In Section 1, we assumed that the graph is strongly connected. Namely, for any
pair of node $i,j\in\mathcal{V}$, there is a directed path from node $i$ to
node $j$. This assumption is used to avoid the degenerate case, where a subset
of the graph is a sink for the defender, as shown in Figure 13.

Figure 13: An example of a graph with a sink (node 1). The graph is not
strongly connected, since there is no directed path from node 1 to node 3.

One can easily see that by having a single attacker on node 3, the defender
must maintain at least one defender resource on node 2. This one unit of
defender resource will be forced to move to node 1 at the next time step and
will stay on node 1 forever. Consequently, the defender must “sacrifice” a
unit of its resource at every time step in order to guard node2, and the
attacker can trivially win the game by staying on node 3 and wait till the
defender runs out of resource and leaves node 2 unattended.

##  Appendix B Proof of Theorem 1

See 1

###### Proof.

We provide a proof by double inclusion. The direction of
$\mathrm{Conv}\big{(}\hat{\mathcal{K}}\big{)}\subseteq\mathcal{K}$ is easy to
show, as the extreme actions are all admissible actions and the linear
constraints in (2)–(4) hold under convex combinations.

To show that
$\mathcal{K}\subseteq\mathrm{Conv}\big{(}\hat{\mathcal{K}}\big{)}$, we provide
a formula of $\\{\lambda^{(\ell)}\\}_{\ell}$ in (10) for an arbitrary
$K\in\mathcal{K}$. We first define the active edge set $\mathcal{I}^{(\ell)}$
for the extreme action $\hat{K}^{(\ell)}\in\hat{\mathcal{K}}$ as

$\mathcal{I}^{(\ell)}=\left\\{(j,i)\Big{|}[\hat{K}^{(\ell)}]_{ij}=1\right\\}.$

Then, given any admissible action $K\in\mathcal{K}$, the coefficients
$\lambda^{(\ell)}$ corresponding to the extreme action $\hat{K}^{(\ell)}$ can
be computed as

$\lambda^{(\ell)}=\prod_{(j,i)\in\mathcal{I}^{(\ell)}}[K]_{ij}.$ (39)

One can further verify that the above formula satisfies (10) and
$\sum_{\ell=1}^{|\hat{\mathcal{K}}|}\lambda^{(\ell)}=1$. Consequently, any
admissible action is in the convex hull of the extreme actions. With the
double inclusion, we have proved the relation in (9). ∎

##  Appendix C Fixed-Point Results

######  Lemma 10.

Let $A$ be a compact set, $\\{B_{k}\\}$ be a sequence of descending closed
sets, i.e. $B_{0}\supseteq B_{1}\supseteq B_{2}\supseteq\cdots$. Define
$B=\bigcap_{k}B_{k}$. Suppose that $A\cap B_{k}\neq\varnothing$, then $A\cap
B\neq\varnothing$.

###### Proof.

Let $x_{k}\in A\cap B_{k}$. Since $A$ is compact, there is a convergent
subsequence $x_{k_{n}}$ such that $\lim_{n\to\infty}x_{k_{n}}=x$ and $x\in A$.
We will show that $x\in B$.

Suppose $x\notin B$, then $x\notin B_{K}$ for some $K$. Furthermore, since
$\\{B_{k}\\}$ are descending, $x\notin B_{k}$ for all $k\geq K$. Let $N$ be a
large enough integer such that $k_{N}\geq K$. Since $B_{K_{N}}$ is closed, we
have that $\mathrm{dist}(x,B_{k_{N}})=\min_{y\in B_{K_{N}}}\lVert
x-y\rVert=\epsilon>0$. Furthermore, since $B_{k_{N}}\supseteq
B_{k_{N+1}}\supseteq\cdots$, we have for all $n\geq N$ that

$\mathrm{dist}(x,B_{k_{n}})\geq\mathrm{dist}(x,B_{k_{N}})=\epsilon>0,$

which implies that $\lVert x_{k_{n}}-x\rVert\geq\epsilon>0$ for all $n\geq N$.
However, we have that $x_{k_{n}}\to x$, which is a contradiction. Thus, we
have $x\in B$.

∎

See 5

###### Proof.

We provide a proof via double inclusion. Denote
$F=\Big{\\{}\mathbf{x}\big{|}\mathbf{x}\in\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})\wedge\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{\infty}^{(j)}\neq\varnothing~{}\forall
j\in\mathcal{N}_{i}\Big{\\}}.$

We first show that ${\mathcal{Q}}_{\infty}^{(i)}\subseteq F$. Consider an
arbitrary $\mathbf{x}\in{\mathcal{Q}}_{\infty}^{(i)}$. Clearly,
$\mathbf{x}\in{\mathcal{Q}}_{k}^{(i)}\subseteq\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$.
Furthermore, for all $j\in\mathcal{N}_{i}$, we have
$\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{k}^{(j)}\neq\varnothing$ for all
$k$. Since $\mathcal{R}(\mathbf{x})$ is compact and all
${\mathcal{Q}}_{k}^{(j)}$ are closed, we can apply Lemma 10 and conclude that
$\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{\infty}^{(i)}\neq\varnothing$.
Consequently, ${\mathcal{Q}}_{\infty}^{(i)}\subseteq F$.

Next, consider an arbitrary $\mathbf{x}\in F$. Clearly,
$\mathbf{x}\in\mathcal{P}_{\text{req}}(\mathbf{y}^{(i)})$. Furthermore, since
${\mathcal{Q}}_{\infty}^{(j)}=\bigcap_{k=0}^{\infty}{\mathcal{Q}}_{k}^{(j)}$,
we have $\mathcal{R}(\mathbf{x})\cap{\mathcal{Q}}_{k}^{(j)}\neq\varnothing$
for all $k$ and $j\in\mathcal{N}_{i}$ from the definition of $F$.
Consequently, $\mathbf{x}\in{\mathcal{Q}}_{k}^{(i)}$ for all $k$.

∎

##  Appendix D Combinition of Subteam Actions

######  Lemma 11 (Overall action).

Suppose the defender allocation at time $t$ is given as a convex combination:

$\mathbf{x}_{t}=\sum_{i}\xi_{i}\mathbf{x}_{i,t},$ (40)

where $\xi_{i}\geq 0$ and $\sum_{i}\xi_{i}=1$. Then, for any set of actions
$K_{i,t}\in\mathcal{K}$, there exists an admissible overall action
$K\in\mathcal{K}$ such that:

$\mathbf{x}_{t+1}=K_{t}\mathbf{x}_{t}=\sum_{i}\xi_{i}K_{i,t}\mathbf{x}_{i,t}.$
(41)

Furthermore, the $pq$-th entry of the overall action is given by

$\left[K_{t}\right]_{pq}=\begin{cases}\sum_{i}\left[\frac{\xi_{i}\left[\mathbf{x}_{i,t}\right]_{q}}{\left[\mathbf{x}_{t}\right]_{q}}\left[K_{i,t}\right]_{pq}\right]&\text{if
}[\mathbf{x}_{t}]_{q}>0,\\\ \frac{1}{d^{+}_{q}}&\text{if
}[\mathbf{x}_{t}]_{q}=0\text{ and }A_{pq}=1,\\\ 0&\text{if
}[\mathbf{x}_{t}]_{q}=0\text{ and }A_{pq}=0.\end{cases}$ (42)

###### Proof.

Let the set $\mathcal{I}=\\{i\;|\;[\mathbf{x}_{t}]_{i}>0\\}$ denote the set of
nodes that have non-zero defender resource at time step $t$. Note that
$[\mathbf{x}_{t}]_{q}=0$ implies $[\mathbf{x}_{i,t}]_{q}=0$ for all $i$. From
(41), we have

$\displaystyle[\mathbf{x}_{t+1}]_{p}$
$\displaystyle=\left[\sum_{i}\xi_{i}K_{i,t}\mathbf{x}_{i,t}\right]_{p}$
$\displaystyle=\sum_{i}\xi_{i}\sum_{q}\left[K_{i,t}\right]_{pq}\left[\mathbf{x}_{i,t}\right]_{q}$
$\displaystyle=\sum_{i}\xi_{i}\Bigg{(}\sum_{q\in\mathcal{I}}\frac{\left[K_{i,t}\right]_{pq}\left[\mathbf{x}_{i,t}\right]_{q}}{\left[\mathbf{x}_{t}\right]_{q}}\left[\mathbf{x}_{t}\right]_{q}+\sum_{\begin{subarray}{c}q\notin\mathcal{I}\\\
A_{pq}=1\end{subarray}}\frac{1}{d^{+}_{q}}\underbrace{\left[\mathbf{x}_{i,t}\right]_{q}}_{=0}+\sum_{\begin{subarray}{c}q\notin\mathcal{I}\\\
A_{pq}=0\end{subarray}}0\underbrace{\left[\mathbf{x}_{i,t}\right]_{q}}_{=0}\Bigg{)}$
$\displaystyle=\sum_{q\in\mathcal{I}}\left[\sum_{i}\frac{\xi_{i}\left[\mathbf{x}_{i,t}\right]_{q}}{\left[\mathbf{x}_{t}\right]_{q}}\left[K_{i,t}\right]_{pq}\right]\left[\mathbf{x}_{t}\right]_{q}+\sum_{\begin{subarray}{c}q\notin\mathcal{I}\\\
A_{pq}=1\end{subarray}}\frac{1}{d^{+}_{q}}\underbrace{\left[\mathbf{x}_{t}\right]_{q}}_{=0}+\sum_{\begin{subarray}{c}q\notin\mathcal{I}\\\
A_{pq}=0\end{subarray}}0\underbrace{\left[\mathbf{x}_{t}\right]_{q}}_{=0}$
$\displaystyle=\sum_{q}[K_{t}]_{pq}[\mathbf{x}_{t}]_{q}.$

The node $p$ with $[\mathbf{x}_{t}]_{q}=0$ can be ignored, since the
relocation action for node $q$ has no effect on $\mathbf{x}_{t+1}$ where there
is no resource on node $q$. The additional two cases are presented in (42) to
solely ensure that the overall action is admissible and well-defined.

Next, we show that the overall action (42) is admissible. That is it satisfies
the three conditions for admissible actions:

  1. 1.

$K_{t}\geq 0$ is obvious.

  2. 2.

$[K_{t}]_{pq}>0$ only if $[A]_{pq}=1$ is also obvious. For the case
$[\mathbf{x}_{t}]_{q}>0$ in (42), $[K_{t}]_{pq}>0$ only if at least one of
$[K_{i,t}]_{pq}>0$. Since $K_{i,t}$ is admissible, its $pq$-th entry can be
positive only if $[A]_{pq}=1$. For the last two cases where
$[\mathbf{x}_{t}]_{q}=0$, the admissibility of $K_{t}$ is straightforward.

  3. 3.

The column sum of $K$ is unity. For the case where $[\mathbf{x}_{t}]_{q}\neq
0$, it follows from

$\displaystyle\sum_{p}\left[K_{t}\right]_{pq}$
$\displaystyle=\sum_{p}\sum_{i}\frac{\xi_{i}\left[\mathbf{x}_{i,t}\right]_{q}}{\left[\mathbf{x}_{t}\right]_{q}}\left[K_{i,t}\right]_{pq}$
$\displaystyle=\sum_{i}\frac{\xi_{i}\left[\mathbf{x}_{i,t}\right]_{q}}{\left[\mathbf{x}_{t}\right]_{q}}\sum_{p}\left[K_{i,t}\right]_{pq}$
$\displaystyle=\sum_{i}\frac{\xi_{i}\left[\mathbf{x}_{i,t}\right]_{q}}{\left[\mathbf{x}_{t}\right]_{q}}=1.$

When $[\mathbf{x}_{t}]_{q}=0$, we have

$\sum_{p}\left[K_{t}\right]_{pq}=\sum_{p\in\\{(q,p)\in\mathcal{E}\\}}\frac{1}{d_{q}^{+}}=1.$

In summary, we have shown that there exists an overall action that satisfies
(41), and it is also admissible. ∎

##  Appendix E Results on Reversed Graphs

See 8

###### Proof.

When $[\mathbf{x}^{\prime}]_{j}=0$, the actions applied on node $j$ has no
influence on the next configuration. Consequently, we ignore such cases. The
readers can refer to the proof of Lemma 11 for a proper handling of cases
where $[\mathbf{x}^{\prime}]_{j}=0$.

We first verify that the reverse action $\widetilde{K}$ in (35) is admissible.
It is easy to see that $\widetilde{K}$ satisfies the underlying graph
constraints, since the $ij$-th entry of $\widetilde{K}$ depends on the $ji$-th
entry of the $K$ matrix. Each column of $\widetilde{K}$ also sums to unity,
since

$\sum_{i}\left[\widetilde{K}\right]_{ij}=\sum_{i}\frac{[K]_{ji}[\mathbf{x}]_{i}}{[\mathbf{x}^{\prime}]_{j}}=\frac{\sum_{i}[K]_{ji}[\mathbf{x}]_{i}}{[\mathbf{x}^{\prime}]_{j}}=\frac{[\mathbf{x}^{\prime}]_{j}}{[\mathbf{x}^{\prime}]_{j}}=1.$

Finally, we show that $\widetilde{K}\mathbf{x}^{\prime}=\mathbf{x}$.

$\displaystyle\left[\widetilde{K}\mathbf{x}^{\prime}\right]_{i}$
$\displaystyle=\sum_{j}\widetilde{K}_{ij}[\mathbf{x}^{\prime}]_{j}=\sum_{j}\frac{[K]_{ji}[\mathbf{x}]_{i}}{[\mathbf{x}^{\prime}]_{j}}[\mathbf{x}^{\prime}]_{j}$
$\displaystyle=\sum_{j}[K]_{ji}[\mathbf{x}]_{i}=[\mathbf{x}]_{i},$

which completes the proof.

∎

See 9

###### Proof.

We prove the equality through a double inclusion. To show that
$\mathcal{R}^{-1}(P)\subseteq\widetilde{\mathcal{R}}(P)$, select an arbitrary
point $\mathbf{x}\in\mathcal{R}^{-1}(P)$, then there exists $K\in\mathcal{K}$
and $\mathbf{x}^{\prime}\in P$, such that $\mathbf{x}^{\prime}=K\mathbf{x}$.
According to Lemma 8, we can construct an inverse action
$\widetilde{K}\in\widetilde{\mathcal{K}}$ such that
$\mathbf{x}=\widetilde{K}\mathbf{x}^{\prime}$. Thus, we have
$\mathbf{x}\in\widetilde{\mathcal{R}}(P)$.

Consider a point $\mathbf{x}\in\widetilde{\mathcal{R}}(P)$. By definition,
there exists a point $\mathbf{x}^{\prime}\in P$ and an admissible action
$\widetilde{K}\in\widetilde{\mathcal{K}}$ such that
$\mathbf{x}=\widetilde{K}\mathbf{x}^{\prime}$. Note that we can regard the
original graph $\mathcal{G}$ as a reversed graph of its reversed graph
$\widetilde{\mathcal{G}}$. Consequently, per Lemma 8, there exists an action
$K\in\mathcal{K}$ such that $\mathbf{x}^{\prime}=K\mathbf{x}$. Since
$\mathbf{x}^{\prime}\in P$, we have shown that
$\mathbf{x}\in\mathcal{R}^{-1}(P)$. ∎

##  Appendix F Details of Numerical Examples

The defender actions (a) to (c) used in Figure 12 are given as follows.

$\text{(a)}=\left[\begin{array}[]{cccccc}0&0&0&1&0&1\\\ 0&0&0.5&0&0&0\\\
1&0&0.5&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&0&1&0\\\ 0&1&0&0&0&0\\\
\end{array}\right],\qquad\text{(b)}=\left[\begin{array}[]{cccccc}0&0&0&0&0&1\\\
0&0&0&0&0&0\\\ 0&0&1&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&1&1&0\\\ 1&1&0&0&0&0\\\
\end{array}\right],\qquad\text{(c)}=\left[\begin{array}[]{cccccc}0&0&0&0&0&0\\\
0&0&0&0&1&0\\\ 1&0&1&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&1&0&1\\\ 0&1&0&0&0&0\\\
\end{array}\right].$