# The Defense of Networked Targets
in General Lotto games

Adel Aghajan  Keith Paarporn  Jason R. Marden  A. Aghajan and J. R. Marden are
with the Department of Electrical and Computer Engineering at the University
of California, Santa Barbara, CA. K. Paarporn is with the Department of
Computer Science at the University of Colorado, Colorado Springs. Contact:
<EMAIL_ADDRESS><EMAIL_ADDRESS>This work is supported by ONR
grant #N00014-20-1-2359, AFOSR grants #FA9550-20-1-0054 and #FA9550-21-1-0203,
and the Army Research Lab through the ARL DCIST CRA #W911NF-17-2-0181.

###### Abstract

Ensuring the security of networked systems is a significant problem,
considering the susceptibility of modern infrastructures and technologies to
adversarial interference. A central component of this problem is how defensive
resources should be allocated to mitigate the severity of potential attacks on
the system. In this paper, we consider this in the context of a General Lotto
game, where a defender and attacker deploys resources on the nodes of a
network, and the objective is to secure as many links as possible. The
defender secures a link only if it out-competes the attacker on both of its
associated nodes. For bipartite networks, we completely characterize
equilibrium payoffs and strategies for both the defender and attacker.
Surprisingly, the resulting payoffs are the same for any bipartite graph. On
arbitrary network structures, we provide lower and upper bounds on the
defender’s max-min value. Notably, the equilibrium payoff from bipartite
networks serves as the lower bound. These results suggest that more connected
networks are easier to defend against attacks. We confirm these findings with
simulations that compute deterministic allocation strategies on large random
networks. This also highlights the importance of randomization in the
equilibrium strategies.

##  1 Introduction

Networks are ingrained in modern technological society, thanks to advances in
computing, communication, and control. Critical infrastructures,
transportation networks, and cyber-physical systems are a few among many
examples of systems that operate through complex interconnections. While their
distributed nature gives rise to operations at unprecedented scale and
efficiency, it also introduces vulnerabilities to adversarial interference.

A central component of ensuring the security of networked systems is the
strategic allocation of limited resources to defend against potential attacks.
For example, allocating firewall and malware detectors, ensuring secure state
estimation in critical infrastructures, and deploying defensive assets are
among many problems requiring the strategic allocation of limited resources
[7, 27, 9, 3, 35, 27, 37, 4, 5, 23, 10, 12, 1, 11, 38].

In this paper, we focus on the competitive allocation of resources between an
attacker and a defender of a network. We formulate such a setting in the
context of a General Lotto game. The General Lotto game is a popular variant
of the famous Colonel Blotto game, wherein two opponents simultaneously
allocate their limited resources against each other in order to secure
multiple valuable battlefields [6, 15, 29, 31, 36, 24, 17, 22]. Colonel Blotto
games and General Lotto games have been studied for well over 100 years, where
its primary line of research has focused on characterizing equilibrium
strategies and payoffs. More recently, they have been utilized to model
complex adversarial environments that are relevant to many applications of
interest [12, 16, 33, 25, 26, 2].

In its classic formulation, a player’s objective is to accumulate as much
value as possible by securing individual battlefields. While this model is
descriptive of many types of applications, this classic objective fails to
precisely capture many other important scenarios. In particular, the operation
of electricity grids, cyber networks, oil pipelines, and logistics chains
requires uninterrupted interaction and communication between collaborating
network nodes. In these applications, the defender’s success in protecting
such networked systems depends on securing certain _subsets_ of nodes, rather
than securing as many individual nodes as possible. Ensuring the security of
networked systems often requires the protection of certain graph
characteristics, such as sub-networks or connected paths [32, 30, 16, 33, 13,
2].

In this paper, we formulate a networked General Lotto game where a defender
and attacker allocate resources to the nodes of a network. The defender’s
objective is to preserve the functioning of as many edges in the network as
possible – an edge is able to function if both of its endpoint nodes are under
the control of the defender. Thus, in order to secure any given edge in the
network, the defender is required to send more resources to _both_ endpoint
nodes than the attacker. On the other hand, the attacker’s objective is to
disrupt the functioning of as many edges in the network as possible. As such,
the attacker only needs to control _at least one_ of the endpoint nodes to
disrupt the edge. The performance for each player is measured by the fraction
of total edges in the network that it has secured. These objectives highlight
the inherent asymmetry that exists in attack-defense scenarios. Namely, the
asymmetry favors attackers, as attacks are more easily amplified by the
network’s connectivity properties (e.g. spreading of malware, disruption of
communications, etc.).

The networked setting vastly differs from the classical formulation, and
consequently the resulting equilibrium strategies will be vastly different. To
illustrate, consider the figure below:

There are three battlefields. In the classic setup, the objective is to win as
many battlefields as possible, wherein each battlefield has a value of $1/3$.
For the allocation strategies shown, the blue player (defender) wins two
battlefields and thus obtains a payoff of $2/3$. However, for the same
allocation strategies in the networked setup, the defender still wins both
battlefields, but _does not_ attain any positive payoff. This is because it is
necessary (but not sufficient) for the defender to win the center battlefield
in order to secure any of the two edges (here, each are worth 1/2).

Thus, one expects the equilibrium (equivalently, optimal) strategies in such
settings to depend on the network structure under which the battlefields are
arranged. Indeed, one of the main goals of this paper is to derive equilibrium
strategies in networked General Lotto games of the above form. Moreover, a
central question we seek to address in this paper is how the performance of
the attacker and defender may change depending on characteristics of the
network structure. We further illustrate the intricacies that can arise in
simplified examples below.

###  1.1 First illustrative examples

To generate some initial intuition, we consider the following simplified
setup. The defender ${\mathcal{X}}$ has a budget of $X\in\mathbb{R}_{\geq 0}$
resources, and the attacker ${\mathcal{Y}}$ has $Y\in\mathbb{R}_{\geq 0}$
resources. Each must decide how to allocate their resources to the nodes of a
network (suppose there are $n$ nodes). The set of feasible allocations for
${\mathcal{X}}$ is the set of vectors
$\\{(x_{1},\ldots,x_{n})\in\mathbb{R}_{\geq 0}^{n}:\sum_{i=1}^{n}x_{i}=X\\}$
(and similarly for ${\mathcal{Y}}$). Performance is measured as the fraction
of edges that a player secures. In order to secure an edge of the network,
${\mathcal{X}}$ must win both endpoint nodes, whereas ${\mathcal{Y}}$ only
needs to win at least one. If they tie on a node, then we will assume the node
is awarded to the attacker ${\mathcal{Y}}$. Three different networks are shown
in Figure 1, where each player has a budget of 6 resources. Here, we
illustrate that the graph structures significantly impact the players’
attainable performances.

(a) Notice that in the star graph with six nodes (leftmost diagram), the
attacker is guaranteed to secure the entire network by allocating resources
only to the center node. This is because all edges are connected to the
center. The defender here does not have enough resources to counter this
strategy, and thus cannot secure a single edge.

(b) Let us now consider the ring graph with six nodes (center diagram). For
the same budgets, the attacker now cannot guarantee that it secures the entire
network. This is because the attacker wins at least two edges by securing a
single node, regardless of what the defender does. The best payoff it can
guarantee itself on this network is two edges out of six.

(c) A similar analysis applies to the line graph with five nodes (rightmost
diagram). The attacker here can only guarantee that it secures two edges out
of four.

Clearly, the players’ performance guarantees in these simplified examples are
shaped by the structure of the networks. This paper focuses on analyzing the
_Network General Lotto_ game (Section 2), wherein randomized allocations that
satisfy the budget in expectation are permitted. Surprisingly, our analysis
finds that in the Network General Lotto game, the performance guarantees _do
not change_ across the three networks shown in Figure 1. That is, a player’s
performance in an equilibrium is _identical_ on the star, ring, and line
network. A summary of our main contributions are given below.

###  1.2 Our Contributions

Among the primary contributions of this paper, we establish equilibrium
payoffs and strategies for the Network General Lotto game in the class of
bipartite networks (Theorem 3.1), which includes star graphs, rings with an
even number of nodes, line graphs, tree graphs, and many others. Despite the
variety of topologies that belong to the class of bipartite networks, the
equilibrium payoffs for any bipartite network are _identical_ , and depends
only on the relative budgets between the players. Hence, the payoffs are
independent of any other characteristics. However, the equilibrium allocation
strategies are intimately linked to the specific network topology.

Beyond bipartite networks, we identify analytical lower and upper bounds on
the defender’s security payoff guarantee on any network (Theorem 4.1). The
lower bound coincides with the equilibrium payoff attained on any bipartite
network. This suggests that bipartite networks are the “easiest” networks to
attack and “hardest” to defend. The defender can guarantee the lower bound
payoff by implementing its equilibrium strategy characterized for bipartite
networks.

We further highlight the dependence of network structure by considering
scenarios where the defender can only use deterministic strategies, as in
Figure 1. Here, we identify bipartite and complete graphs as the two extreme
structures determining the range of the defender’s effectiveness – on complete
graphs, a positive payoff is ensured against the widest range of attacker
budgets compared to arbitrary graphs. On bipartite graphs, a positive payoff
is ensured for the smallest range of attacker budgets (Proposition 6.1). These
results are corroborated through numerical simulations on various random
Erdös-Rényi graphs. Moreover, the simulations highlight the importance for the
defender to implement randomized strategies, as there is a significant
degradation in performance compared to the lower bound of performance in
Theorem 4.1.

Figure 1: Three examples of a simplified setup where players are restricted to
pure allocations. Here, we illustrate the max-min allocation strategy for the
attacker (red) on three distinct networks – that is, the highest payoff the
attacker can guarantee regardless of the defender’s (blue) allocation. Here,
the defender and attacker each have 6 resource units, and we assume ties are
awarded to the attacker. (Left) The attacker can guarantee that it secures
every edge in the star network simply by sending all resources to the center
node. There is no strategy that the defender can use to secure a single edge.
(Center) On the ring graph of six nodes, the attacker can only guarantee that
it secures two out of six edges. (Right) In the line network of five nodes,
the attacker can only guarantee that it secures two out of four edges. In
these examples, the topology of the graph impacts the performance guarantees
for the players.

###  1.3 Related work

A wide array of recent literature studies resource allocation over networks
using a variety of different formulations in order to study the security of
networked systems [32, 16]. The impact of cyber attacks on dynamic networked
systems is a central area of study in control and cyber-physical systems [5,
28, 23]. Game-theoretic approaches have focused on the problem of how a
network of agents will invest in costly security protection resources [18, 1].
The work of [1] considers a behavioral attack graph model and determines pure-
strategy equilibrium security investments among multiple defenders of a
network. Another formulation considers resources that can dynamically be re-
allocated via network links [33, 8].

The Colonel Blotto game and its variants are emerging as a flexible framework
for studying complex adversarial interactions. As previously discussed, the
most well-known results here are for settings where each player’s objective is
to accumulate as much value as possible by securing individual valuable
battlefields [20]. As such, alternate player objectives are a central focus in
the Colonel Blotto literature, where success depends on securing subsets of
battlefields rather than securing individual battlefields [34, 14, 20, 32, 21,
16, 2]. In [21], a defender has a weakest-link objective associated with
securing multiple networks, while the attacker has a best-shot objective
associated with only securing a single network. Network Colonel Blotto games
are considered in [16], where a defender’s payoff is determined by whether it
can preserve certain network characteristics such as its connectivity or
average degree. This work primarily showcases computational methods to find
approximate solutions in a model with integer-restricted allocations. In [32],
pure strategy equilibria are found in a network formation Blotto game, where
players succeed if they secure connected components of a graph. Our work
contributes to this literature by featuring analytical characterizations of
equilibrium mixed strategies in Network General Lotto games.

Notation: We denote $[n]=\\{1,\ldots,n\\}$ as the set of the first $n$ natural
numbers. For a subset $B\subseteq[n]$ and a vector $x\in\mathbb{R}^{n}$, we
write $x_{B}=(x_{d})_{d\in B}\in\mathbb{R}^{|B|}$. We denote the set of non-
negative real numbers as $\mathbb{R}_{+}$. We will use bold lettering to
denote random variables, i.e. ${\bf x}\sim F$ is a random variable with
realization $x$ over some distribution $F$.

##  2 Problem Formulation

Consider a graph $G=(V,E)$, where $V\triangleq[n]$ is the set of vertices (or
nodes) and $E\subseteq V\times V$ is the set of edges. We will use terms
“network” and “graph” interchangeably. In this paper, we consider networks
containing at least one edge, i.e., $E\not=\varnothing$. In a Network General
Lotto game over the graph $G$, there are two opposing players ${\mathcal{X}}$
and ${\mathcal{Y}}$, each aiming to secure as many edges as possible by
allocating resources to the nodes. In order to secure an edge $\\{i,j\\}\in
E$, player ${\mathcal{X}}$ is required to out-compete ${\mathcal{Y}}$, i.e.
send more resources, on both nodes $i,j\in V$. Player ${\mathcal{Y}}$ secures
the edge $\\{i,j\\}$ if ${\mathcal{X}}$ fails to secure it. Indeed, it is more
difficult for ${\mathcal{X}}$, who we refer to as the defender, to secure
edges than it is for ${\mathcal{Y}}$, who we refer to as the attacker.

Formally, an allocation for player ${\mathcal{X}}$ is a vector
$x=(x_{i})_{i\in[n]}\in\mathbb{R}_{+}^{n}$, and similarly a vector
$y\in\mathbb{R}_{+}^{n}$ for player ${\mathcal{Y}}$. Player ${\mathcal{X}}$
(player ${\mathcal{Y}}$) has a limited resource budget $X$ (budget $Y$) to
allocate in expectation. An admissible strategy for ${\mathcal{X}}$ is any
${n}$-variate (cumulative) distribution function
$F_{\mathcal{X}}:\mathbb{R}_{+}^{n}\rightarrow[0,1]$ that belongs to

$\mathbb{F}(X)\triangleq\left\\{F_{\mathcal{X}}:\mathbb{E}_{{\bf x}\sim
F_{\mathcal{X}}}\left[\sum_{i\in[n]}{\bf x}_{i}\right]\leq X\right\\}.$ (1)

In words, player ${\mathcal{X}}$ can implement any randomization of
allocations as long as it does not exceed its budget in _expectation_. The
admissible strategies belonging to (1) are the defining feature of General
Lotto games relative to Colonel Blotto games [24, 17, 22]: in Blotto games,
the distribution $F_{\mathcal{X}}$ must not have support over any allocation
that exceeds the budget [29, 22].

If $x$ and $y$ are allocations for players ${\mathcal{X}}$ and
${\mathcal{Y}}$, the payoff awarded to player ${\mathcal{X}}$ is

$\displaystyle\pi_{\mathcal{X}}(x,y;G)\triangleq\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}1_{\\{x_{i}\geq y_{i},x_{j}\geq y_{j}\\}},$ (2)

where

$\displaystyle 1_{\\{x_{i}\geq y_{i},x_{j}\geq
y_{j}\\}}\triangleq\begin{cases}1,&\text{if }x_{i}\geq y_{i},x_{j}\geq
y_{j}\\\ 0,&\text{otherwise}\end{cases}.$

In other words, player ${\mathcal{X}}$ secures the edge $\\{i,j\\}$, if he
wins both nodes $i,j$. Conversely, player ${\mathcal{Y}}$ secures the edge
$\\{i,j\\}$ if he wins at least one of the nodes $i,j$. Therefore, the payoff
awarded to player ${\mathcal{Y}}$ is
$\pi_{\mathcal{Y}}(x,y)=1-\pi_{\mathcal{X}}(x,y)$, i.e. it is a constant-sum
game. Given a strategy profile
$(F_{\mathcal{X}},F_{\mathcal{Y}})\in\mathbb{F}(X)\times\mathbb{F}(Y)$, the
_expected payoffs_ to each player are denoted as

$\displaystyle\pi_{\mathcal{X}}(F_{\mathcal{X}},F_{\mathcal{Y}};G)$
$\displaystyle=\mathbb{E}_{{\bf x}\sim F_{\mathcal{X}},{\bf y}\sim
F_{\mathcal{Y}}}[\pi_{\mathcal{X}}({\bf x},{\bf y};G)],$ (3)
$\displaystyle\pi_{\mathcal{Y}}(F_{\mathcal{X}},F_{\mathcal{Y}};G)$
$\displaystyle=\mathbb{E}_{{\bf x}\sim F_{\mathcal{Y}},{\bf y}\sim
F_{\mathcal{Y}}}[\pi_{\mathcal{Y}}({\bf x},{\bf y};G)].$

We will denote a Network General Lotto game over a graph $G$ with budgets
$X,Y$ as the triple $(X,Y,G)$.

###### Definition 2.1

An equilibrium of $(X,Y,G)$ is a strategy profile
$(F_{\mathcal{X}}^{*},F_{\mathcal{Y}}^{*})\in\mathbb{F}(X)\times\mathbb{F}(Y)$
that satisfies

$\displaystyle\pi_{\mathcal{X}}(F_{\mathcal{X}},F_{\mathcal{Y}}^{*};G)\leq\pi_{\mathcal{X}}(F_{\mathcal{X}}^{*},F_{\mathcal{Y}}^{*};G)\leq\pi_{\mathcal{X}}(F_{\mathcal{X}}^{*},F_{\mathcal{Y}};G)$
(4)

for all $F_{\mathcal{X}}\in\mathbb{F}(X)$ and
$F_{\mathcal{Y}}\in\mathbb{F}(Y)$.

We will often omit the dependence of $\pi_{\mathcal{X}}$ on the graph $G$ when
the context is clear.

##  3 Bipartite networks

In this section, we will restrict attention to the class of bipartite graphs.
The definition of a bipartite graph is given below:

###### Definition 3.1

A graph $G=(V,E)$ is _bipartite_ if there are two disjoint subsets of nodes
$B_{1},B_{2}$ such that $B_{1}\cup B_{2}=V$, and no edges exist between nodes
in the same subset.

Equivalently, a bipartite graph is a graph that does not contain any odd-
length cycles. Recall that the example networks from Figure 1, i.e. star, ring
(even number of nodes), and line, were all bipartite. In the simplified
setting from the examples where only deterministic integer allocations were
permitted, the players’ performance guarantees heavily depended on the
network’s structure.

###  3.1 Equilibrium characterizations

We present our main result below, which is an equilibrium characterization of
the Network Lotto game for any bipartite network.

Figure 2: Illustration of equilibrium strategies on bipartite networks
(Theorem 3.1) in the regime $X<2Y$. The case $X\geq 2Y$ is similar. (Left) The
defender’s equilibrium strategy is to draw a sample $u$ from the density
function shown. Using a total of $u$ resources, it distributes to each node in
the network proportionally to their degree centralities, i.e.
$x_{i}=\frac{d_{i}}{2|E|}u$. Observe that with probability $1-\frac{X}{2Y}$,
no resources are allocated at all. (Right) The attacker’s equilibrium strategy
is to first choose one of the node partitions $B_{k}$, $k\in\\{1,2\\}$ with
probability 1/2. It then draws a sample $u$ from the uniform density function
shown. Using a total of $u$ resources, it distributes to each node $i$ in
$B_{k}$ proportionally to their degree centralities, i.e.
$y_{i}=\frac{d_{i}}{|E|}u$. For each node $i\notin B_{k}$, no resources are
allocated. The payoffs that result from this strategy profile is identical for
every bipartite network.

###### Theorem 3.1

Consider a Network General Lotto game $(X,Y,G)$, where $G$ is bipartite. The
equilibrium payoff to ${\mathcal{X}}$ is given by

$\gamma(X,Y)\triangleq\begin{cases}1-\frac{Y}{X},&\text{if }X\geq 2Y\\\
\frac{X}{4Y},&\text{if }X<2Y\\\ \end{cases},$ (5)

and the payoff to ${\mathcal{Y}}$ is $1-\gamma(X,Y)$. An equilibrium strategy
profile $(F_{\mathcal{X}}^{*},F_{\mathcal{Y}}^{*})$ is given as follows. Let
$B_{1},B_{2}$ be the bipartite partition of $G$.

If $X<2Y$:

$\displaystyle F_{\mathcal{X}}^{*}(x)$
$\displaystyle=1-\frac{X}{2Y}+\frac{X|E|}{4Y^{2}}\min\left\\{\left\\{\frac{x_{i}}{d_{i}}\right\\}_{i\in
V},\frac{2Y}{|E|}\right\\}$ (6) $\displaystyle F_{\mathcal{Y}}^{*}(y)$
$\displaystyle=\frac{|E|}{4Y}\sum_{k=1,2}\min\left\\{\left\\{\frac{y_{i}}{d_{i}}\right\\}_{i\in
B_{k}},\frac{2Y}{|E|}\right\\}$

If $X\geq 2Y$:

$\displaystyle F_{\mathcal{X}}^{*}(x)$
$\displaystyle=\frac{|E|}{X}\min\left\\{\left\\{\frac{x_{i}}{d_{i}}\right\\}_{i\in
V},\frac{X}{|E|}\right\\}$ (7) $\displaystyle F_{\mathcal{Y}}^{*}(y)$
$\displaystyle=1-\frac{2Y}{X}+\frac{Y|E|}{X^{2}}\sum_{k=1,2}\min\left\\{\left\\{\frac{y_{i}}{d_{i}}\right\\}_{i\in
B_{k}},\frac{X}{|E|}\right\\}$

The equilibrium payoff (5) is _identical_ for any bipartite graph $G$, and are
hence _independent_ of any other graph characteristics. It only depends on the
relative budgets $X$ and $Y$. The equilibrium strategies
$(F_{\mathcal{X}}^{*},F_{\mathcal{Y}}^{*})$, however, are strongly linked to
the particular structure of the bipartite graph. We elaborate on the
equilibrium strategies specified by (6) and (7) below.

###  3.2 Interpretation of equilibrium strategies

For the case $X<2Y$ (6), the defender’s strategy
$F_{\mathcal{X}}^{*}\in\mathbb{F}(X)$ randomizes over allocations as follows.
With probability $1-\frac{X}{2Y}$, no resources are allocated at all. With
probability $\frac{X}{2Y}$, a single sample $u\sim\text{Unif}[0,4Y]$ is drawn,
and the allocation is determined as $x_{i}=\frac{d_{i}}{2|E|}\cdot u$ for each
node $i\in V$. In other words, ${\mathcal{X}}$ allocates a total of $u$
resources among the nodes proportionally to their degree centralities. The
allocations to each node $x_{i}$ are random, but correlated through the
uniform sample $u$. One can verify that this strategy is budget-feasible in
expectation. An illustration is depicted in Figure 2 (left).

The attacker’s strategy $F_{\mathcal{Y}}^{*}\in\mathbb{F}(Y)$ randomizes over
allocations as follows. With probability 1/2, it allocates resources only to
nodes in the partition $B_{k}$, $k\in\\{1,2\\}$, in the following manner. A
single sample $u\sim\text{Unif}[0,2Y]$ is drawn. The allocation to each node
$i\in B_{k}$ is determined as $y_{i}=\frac{d_{i}}{|E|}\cdot u$ and to each
node $i\in B_{-k}$ as $y_{i}=0$. An illustration is depicted in Figure 2
(right).

A similar interpretation applies for the case $X\geq 2Y$. The difference here
is that ${\mathcal{X}}$ is the “stronger” player, and will not give up
(allocate nothing) with a non-zero probability. As the “weaker” player,
${\mathcal{Y}}$ assigns a non-zero probability to give up.

Revisiting the examples from Figure 1, we can begin to reason why the initial
intuition would not apply to the full Network Lotto game. Considering the star
network, even if the attacker has more resources than the defender, and
allocates only to the center node, the defender is able to counter this
strategy because the admissible strategy space $\mathbb{F}(X)$ enables it to
randomize over allocations that exceed the attack on the center. Thus, the
attacker itself needs to randomize its allocation to other nodes in the
network as well.

##  4 Beyond Bipartite Graphs

In this section, we investigate the players’ performance on graphs that are
not bipartite. While we do not provide equilibrium characterizations for
arbitrary graphs $G$, we seek to provide bounds on the defender’s optimal
security payoff:

$S_{\mathcal{X}}^{*}(X,Y,G)\triangleq\max_{F_{\mathcal{X}}\in\mathbb{F}(X)}\min_{F_{\mathcal{Y}}\in\mathbb{F}(Y)}\pi_{\mathcal{X}}(F_{\mathcal{X}},F_{\mathcal{Y}};G)$
(8)

In the result below, we establish lower and upper bounds on player
${\mathcal{X}}$’s optimal security payoff for arbitrary graphs.

###### Theorem 4.1

Consider a Network General Lotto game $(X,Y,G)$, where $G=(V,E)$ is any graph
with $n=|V|\geq 2$ nodes. Then

$\gamma(X,Y)\leq S_{\mathcal{X}}^{*}(X,Y,G)\leq\gamma_{n}(X,Y)$ (9)

where $\gamma(X,Y)$ is defined in (5), and

$\gamma_{n}(X,Y)\triangleq\begin{cases}1-\frac{n}{2(n-1)}\frac{Y}{X},&\text{if
}X\geq\frac{n}{n-1}Y\\\ \frac{n-1}{2n}\frac{X}{Y},&\text{if
}X<\frac{n}{n-1}Y\end{cases}$ (10)

for $n=2,3,\ldots$.

There are several interesting things to note in Theorem 4.1. Player
${\mathcal{X}}$ can find a strategy $F_{\mathcal{X}}\in\mathbb{F}(X)$ that
guarantees itself a payoff of at least $\gamma(X,Y)$, regardless of the graph
$G$ and ${\mathcal{Y}}$’s strategy. The fact that ${\mathcal{X}}$ can ensure a
payoff of at least $\gamma(X,Y)$ on any network suggests that bipartite graphs
are the “most difficult” to defend. As such, Theorem 4.1 implies that the
optimal performance guarantee cannot decrease by adding any amount of
additional edges to an existing bipartite network. Thus, only the defender can
benefit from adding edges to the network, e.g. by forming cliques or odd-
length cycles. An illustration summarizing Theorems 3.1 and 4.1 is provided in
Figure 3.

Figure 3: Theorem 3.1 states $\gamma(X,Y)$ (5) is the equilibrium payoff to
the defender ${\mathcal{X}}$ on any bipartite network (left and center
networks). The right network is not bipartite – Theorem 4.1 states upper and
lower bounds on the max-min value for ${\mathcal{X}}$.

The upper bound of (9) indicates that ${\mathcal{Y}}$ can find a strategy
$F_{\mathcal{Y}}\in\mathbb{F}(Y)$ that ensures ${\mathcal{X}}$ cannot obtain a
payoff that exceeds $\gamma_{n}(X,Y)$. We informally describe such a strategy
now and in Figure 4. A detailed analysis is provided in Section 5.3. For any
graph $G=(V,E)$, consider the collection of $n$ vertex covers
$V_{i}=V\backslash\\{i\\}$. With probability $1/n$, the strategy
$F_{\mathcal{Y}}$ selects the vertex cover $V_{k}$, $k\in V$, and allocates a
total of $u\sim\text{Unif}[0,2Y]$ resources among nodes $i\in V_{k}$
proportionally according to

$y_{i}=\frac{u}{2|E|}\cdot\begin{cases}d_{i},&\text{if
}i\notin\mathcal{N}_{k}\\\ d_{i}+1,&\text{if }i\in\mathcal{N}_{k}\end{cases}$
(11)

The first entry above indicates that the share of resources sent to nodes not
connected to $k$ is proportional to their degree centralities. The second
entry above places slightly more weight to nodes that are direct neighbors of
$k$. The motivation to add extra weight to these nodes is because each one
uniquely covers the edges $\\{i,k\\}$, $i\in\mathcal{N}_{k}$. There is more
redundancy for any other edge $\\{i,j\\}$ in the graph, since at least two
nodes $i,j\notin\mathcal{N}_{k}$ are able to cover it.

Figure 4: Illustration of the attacker’s strategy on arbitrary graphs that
places the upper bound $\gamma_{n}$ on the defender’s attainable payoff
(Theorem 4.1). Resources are allocated proportionally according to (11). Here,
$u\sim\text{Unif}[0,2Y]$ is the randomization on total resources.

##  5 Analysis and proofs

In this section, we highlight analytical techniques and provide the proofs for
our main results.

###  5.1 Correlated allocation strategies

Before proceeding with the proofs, we first define a class of randomized
allocation strategies which we term _correlated allocation strategies_. This
class of strategies serves as the basis for our analysis, and generalizes the
randomized allocation strategies that were detailed in Sections 3 and 4.

###### Definition 5.1

Consider a player ${\mathcal{Z}}\in\\{{\mathcal{X}},{\mathcal{Y}}\\}$ with
resource budget $Z$, and a finite collection of subsets of nodes
${\mathcal{D}}\subseteq 2^{V}$. A _correlated allocation strategy_ is
specified by a cumulative distribution function
$F_{\mathcal{Z}}\in\mathbb{F}(Z)$ for $z\in\mathbb{R}_{+}^{|V|}$ of the form

$\displaystyle F_{\mathcal{Z}}(z)$
$\displaystyle=1-\delta+\frac{\delta^{2}}{2Z}\sum_{D\in{\mathcal{D}}}p_{D}\min\left\\{\left\\{\frac{z_{i}}{w_{D,i}}\right\\}_{i\in
D},\frac{2Z}{\delta}\right\\},$ (12)

for some $\delta\in[0,1]$, probabilities $\\{p_{D}\\}_{D\in{\mathcal{D}}}$
s.t. $\sum_{D\in{\mathcal{D}}}p_{D}=1$, and positive weights
$\\{w_{D,i}\\}_{i\in D}$ for each $D\in{\mathcal{D}}$ s.t. $\sum_{i\in
D}w_{D,i}=1$.

A correlated allocation strategy can more intuitively be described as follows.
To generate a sample allocation ${\bf z}\sim F_{\mathcal{Z}}$, player
${\mathcal{Z}}$ first randomly selects a subset of nodes $D$ from the
collection ${\mathcal{D}}$ according to the probability vector
$\\{p_{D}\\}_{D\in{\mathcal{D}}}$. Player ${\mathcal{Z}}$ then allocates
resources only to nodes $i\in D$ in the following fashion. With probability
$1-\delta$, no resources are allocated at all. With probability $\delta$, a
single sample from the uniform distribution on the interval
$\left[0,\frac{2Z}{\delta}\right]$ is taken, i.e.
$\mathbf{u}\sim\text{Unif}\left[0,\frac{2Z}{\delta}\right]$. Then, the
resources are allocated according to ${\bf z}_{i}=w_{D,i}\cdot\mathbf{u}$ for
$i\in D$ and ${\bf z}_{i}=0$ for $i\notin D$. It follows that the strategy
(12) is budget-feasible, i.e. $\mathbb{E}_{{\bf z}\sim
F_{\mathcal{Z}}}\left[\sum_{i=1}^{n}{\bf z}_{i}\right]=Z$.

Thus, the random variable $\mathbf{u}$ serves as a correlating device on the
player’s allocations to nodes in $D$, where the amounts are proportional to
the weights $w_{D,i}$. We identify the following structural property regarding
best responses against correlated allocation strategies.

###### Lemma 5.1

Consider a correlated allocation strategy $F_{\mathcal{X}}\in\mathbb{F}(X)$
for player ${\mathcal{X}}$ of the form (12). Then for any
$F_{\mathcal{Y}}\in\mathbb{F}(Y)$, there exists a
$F_{\mathcal{Y}}^{\prime}\in\mathbb{F}(Y)$ such that

  * •

$\pi_{\mathcal{Y}}(F_{\mathcal{Y}}^{\prime},F_{\mathcal{X}})\geq\pi_{\mathcal{Y}}(F_{\mathcal{Y}},F_{\mathcal{X}})$,
and

  * •

for all $i\in V$ s.t. $i\in D$ for some $D\in{\mathcal{D}}$, we have

$\displaystyle\mathbb{P}_{{\bf y}\sim F_{\mathcal{Y}}^{\prime}}\left({\bf
y}_{i}>\frac{2X\max_{D\in{\mathcal{D}}}\\{w_{D,i}\\}}{\delta}\right)=0.$ (13)

Here, we assume $w_{D,i}=0$ if $i\notin D$. An identical result holds with
player indices reversed.

In words, a player prefers not to randomize over allocations outside of the
support of the other player’s correlated allocation strategy. This is because
for some distribution $F_{\mathcal{Y}}\in\mathbb{F}(Y)$ such that
$\mathbb{P}_{{\bf y}\sim F_{\mathcal{Y}}}\left({\bf
y}_{i}>\frac{2X\max_{D\in{\mathcal{D}}}\\{w_{D,i}\\}}{\delta}\right)>0$, we
can use another distribution $F^{\prime}_{\mathcal{Y}}$ such that

$\displaystyle
F_{\mathcal{Y}}^{\prime}\left(y\right)=\begin{cases}F(y),&y<\frac{2X\max_{D\in{\mathcal{D}}}\\{w_{D,i}\\}}{\delta}\\\
1,&\text{otherwise}\end{cases},$

without losing any payoff.

###  5.2 Equilibrium characterizations on bipartite graphs

Consider a bipartite graph $G=(V,E)$ with partition $B_{1},B_{2}$. Let $d_{i}$
be the degree of node $i\in V$. Recall the profile
$(F_{\mathcal{X}}^{*},F_{\mathcal{Y}}^{*})$ of correlated allocation
strategies defined in (6) and (7). To reiterate,

$\bullet$ If $X<2Y$: ${\mathcal{X}}$ uses the correlated allocation strategy
with ${\mathcal{D}}=\\{V\\}$, $\delta=\frac{X}{2Y}$, and
$w_{V,i}=\frac{d_{i}}{2|E|}$ for $i\in V$. From (12), we recover

$\displaystyle
F_{\mathcal{X}}^{*}(x)=1-\frac{X}{2Y}+\frac{X|E|}{4Y^{2}}\min\left\\{\left\\{\frac{x_{i}}{d_{i}}\right\\}_{i\in
V},\frac{2Y}{|E|}\right\\}.$ (14)

Player ${\mathcal{Y}}$ uses the correlated allocation strategy with
${\mathcal{D}}=\\{B_{1},B_{2}\\}$, $p_{B_{k}}=1/2$ for $k\in\\{1,2\\}$,
$\delta=1$, and $w_{B_{k},i}=\frac{d_{i}}{|E|}$ for $k\in\\{1,2\\}$ and $i\in
B_{k}$. From (12), we recover

$\displaystyle
F_{\mathcal{Y}}^{*}(y)=\frac{|E|}{4Y}\sum_{k=1,2}\min\left\\{\left\\{\frac{y_{i}}{d_{i}}\right\\}_{i\in
B_{k}},\frac{2Y}{|E|}\right\\}.$ (15)

$\bullet$ If $X\geq 2Y$: ${\mathcal{X}}$ uses the correlated allocation
strategy with ${\mathcal{D}}=\\{V\\}$, $\delta=1$, and
$w_{V,i}=\frac{d_{i}}{2|E|}$ for $i\in V$. From (12),

$\displaystyle
F_{\mathcal{X}}^{*}(x)=\frac{|E|}{X}\min\left\\{\left\\{\frac{x_{i}}{d_{i}}\right\\}_{i\in
V},\frac{X}{|E|}\right\\}.$ (16)

Player ${\mathcal{Y}}$ uses the correlated allocation strategy with
${{\mathcal{D}}=\\{B_{1},B_{2}\\}}$, $p_{B_{k}}=1/2$ for $k\in\\{1,2\\}$,
$\delta=\frac{2Y}{X}$, and $w_{B_{k},i}=\frac{d_{i}}{|E|}$ for $k\in\\{1,2\\}$
and $i\in B_{k}$. From (12),

$\displaystyle
F_{\mathcal{Y}}^{*}(y)=1-\frac{2Y}{X}+\frac{Y|E|}{X^{2}}\sum_{k=1,2}\min\left\\{\left\\{\frac{y_{i}}{d_{i}}\right\\}_{i\in
B_{k}},\frac{X}{|E|}\right\\}.$ (17)

We are now ready to prove Theorem 3.1.

Proof of Theorem 3.1: To prove the theorem, we proceed with the following
steps:

  1. 1.

We prove for every $F_{\mathcal{X}}\in\mathbb{F}(X)$,
$\pi_{\mathcal{X}}(F_{\mathcal{X}},F^{*}_{\mathcal{Y}})\leq\pi^{*}_{\mathcal{X}}(X,Y)$
for some $\pi^{*}_{\mathcal{X}}(X,Y)\in\mathbb{R}_{+}$ which is the payoff of
player ${\mathcal{X}}$.

  2. 2.

Then, we show
$\pi_{\mathcal{X}}(F^{*}_{\mathcal{X}},F^{*}_{\mathcal{Y}})=\pi^{*}_{\mathcal{X}}(X,Y)$.

  3. 3.

Finally, we prove $\pi_{\mathcal{Y}}(F^{*}_{\mathcal{X}},F_{\mathcal{Y}})\leq
1-\pi^{*}_{\mathcal{X}}(X,Y)$ for every $F_{\mathcal{Y}}\in\mathbb{F}(Y)$.

Since
$\pi_{\mathcal{Y}}(F^{*}_{\mathcal{X}},F^{*}_{\mathcal{Y}})=1-\pi_{\mathcal{X}}(F^{*}_{\mathcal{X}},F^{*}_{\mathcal{Y}})=1-\pi^{*}_{\mathcal{X}}(X,Y)$,
we also have
$\pi_{\mathcal{Y}}(F_{\mathcal{X}},F_{\mathcal{Y}})=1-\pi^{*}_{\mathcal{X}}(X,Y)$.
Therefore, from the definition of equilibrium (4), proving these steps shows
that $(F^{*}_{\mathcal{X}},F^{*}_{\mathcal{Y}})$ is an equilibrium with
equilibrium payoff $\pi^{*}_{\mathcal{X}}(X,Y)$ for player ${\mathcal{X}}$ and
payoff $1-\pi^{*}_{\mathcal{X}}(X,Y)$ for player ${\mathcal{Y}}$.

We start the proof for the case $X\geq 2Y$. For any distribution
$F_{\mathcal{X}}\in\mathbb{F}(X)$ for player ${\mathcal{X}}$, we have

$\displaystyle\pi_{\mathcal{X}}(F_{\mathcal{X}},F^{*}_{\mathcal{Y}})$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}},F^{*}_{\mathcal{Y}}}[\pi_{\mathcal{X}}({\bf
x},{\bf y})]$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\mathbb{E}_{F^{*}_{\mathcal{Y}}}[\pi_{\mathcal{X}}({\bf
x},{\bf y})\mid{\bf x}]\right],$

which follows from the law of total expectation. From above equality and the
payoff function for player ${\mathcal{X}}$ (2), we have

$\displaystyle\pi_{\mathcal{X}}($ $\displaystyle
F_{\mathcal{X}},F^{*}_{\mathcal{Y}})$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\mathbb{E}_{F^{*}_{\mathcal{Y}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}1_{\\{{\bf x}_{i}\geq{\bf y}_{i},{\bf x}_{j}\geq{\bf y}_{j}\\}}\bigg{|}{\bf
x}\right]\right]$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{E}_{F^{*}_{\mathcal{Y}}}\left[1_{\\{{\bf x}_{i}\geq{\bf y}_{i},{\bf
x}_{j}\geq{\bf y}_{j}\\}}\bigg{|}{\bf x}\right]\right]$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{E}_{F^{*}_{{\mathcal{Y}},\\{i,j\\}}}\left[1_{\\{{\bf x}_{i}\geq{\bf
y}_{i},{\bf x}_{j}\geq{\bf y}_{j}\\}}\bigg{|}{\bf x}\right]\right],$

which follows from the fact that $1_{\\{{\bf x}_{i}\geq{\bf y}_{i},{\bf
x}_{j}\geq{\bf y}_{j}\\}}$ does not depend on ${\bf
x}_{[n]\setminus\\{i,j\\}},{\bf y}_{[n]\setminus\\{i,j\\}}$. Here, we denote
$F_{{\mathcal{Z}},e}$, where
${\mathcal{Z}}\in\\{{\mathcal{X}},{\mathcal{Y}}\\}$ and $e=\\{i,j\\}\in E$, as
the (two-dimensional) marginal distribution of $F_{\mathcal{Z}}$ over ${\bf
x}_{i},{\bf x}_{j}$. Therefore, from above equality, we have

$\displaystyle\pi_{\mathcal{X}}(F_{\mathcal{X}},F^{*}_{\mathcal{Y}})$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{P}({\bf x}_{i}\geq{\bf y}_{i},{\bf x}_{j}\geq{\bf y}_{j}|{\bf
x})\right]$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}F^{*}_{{\mathcal{Y}},\\{i,j\\}}({\bf x}_{\\{i,j\\}})\right].$

From (17), the bi-variate marginal distribution w.r.t allocation to nodes $i$
and $j$ is

$\displaystyle F$ ${}^{*}_{{\mathcal{Y}},\\{i,j\\}}(x_{\\{i,j\\}})$
$\displaystyle=F^{*}_{\mathcal{Y}}(x)\big{|}_{x_{k}=\infty,k\in[n]\setminus{\\{i,j\\}}}$
$\displaystyle=1-\frac{2Y}{X}+\frac{Y|E|}{X^{2}}\left(\min\left\\{\frac{x_{i}}{d_{i}},\frac{X}{|E|}\right\\}+\min\left\\{\frac{x_{j}}{d_{j}},\frac{X}{|E|}\right\\}\right)$
$\displaystyle=1-\frac{2Y}{X}+\frac{Y|E|}{X^{2}}\left(\frac{x_{i}}{d_{i}}+\frac{x_{j}}{d_{j}}\right).$

The last equality follows from Lemma 5.1. We then have

$\displaystyle\pi_{\mathcal{X}}$
$\displaystyle(F_{\mathcal{X}},F^{*}_{\mathcal{Y}})$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\left(1-\frac{2Y}{X}+\frac{Y|E|}{X^{2}}\left(\frac{{\bf
x}_{i}}{d_{i}}+\frac{{\bf x}_{j}}{d_{j}}\right)\right)\right]$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[1-\frac{2Y}{X}+\frac{Y}{X^{2}}\sum_{\\{i,j\\}\in
E}\left(\frac{{\bf x}_{i}}{d_{i}}+\frac{{\bf x}_{j}}{d_{j}}\right)\right].$

Since

$\displaystyle\sum_{\\{i,j\\}\in
E}\left(\frac{x_{i}}{d_{i}}+\frac{x_{j}}{d_{j}}\right)=\sum_{i\in[n]}d_{i}\left(\frac{x_{i}}{d_{i}}\right)=\sum_{i\in[n]}x_{i},$
(18)

the above equality implies

$\displaystyle\pi_{\mathcal{X}}(F_{\mathcal{X}},F^{*}_{\mathcal{Y}})$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[1-\frac{2Y}{X}+\frac{Y}{X^{2}}\sum_{i=1}^{n}{\bf
x}_{i}\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}1-\frac{2Y}{X}+\frac{Y}{X}$
$\displaystyle=1-\frac{Y}{X},$

where $(a)$ follows from $\mathbb{E}_{F_{\mathcal{X}}}\left[\sum_{i=1}^{n}{\bf
x}_{i}\right]\leq X$. Also, note that since
$\mathbb{E}_{F^{*}_{\mathcal{X}}}\left[\sum_{i=1}^{n}{\bf x}_{i}\right]=X$, we
have
$\pi_{\mathcal{X}}(F^{*}_{\mathcal{X}},F^{*}_{\mathcal{Y}})=1-\frac{Y}{X}$.

Similarly, for any distribution $F_{\mathcal{Y}}\in\mathbb{F}(Y)$ for player
${\mathcal{Y}}$, we have

$\displaystyle\pi_{\mathcal{Y}}($ $\displaystyle
F^{*}_{\mathcal{X}},F_{\mathcal{Y}})$ (19)
$\displaystyle=1-\mathbb{E}_{F^{*}_{\mathcal{X}},F_{\mathcal{Y}}}[\pi_{\mathcal{X}}({\bf
x},{\bf y})]$ (20)
$\displaystyle=1-\mathbb{E}_{F_{\mathcal{Y}}}\left[\mathbb{E}_{F^{*}_{\mathcal{X}}}[\pi_{\mathcal{X}}({\bf
x},{\bf y})\mid{\bf x}]\right]$ (21)
$\displaystyle=1-\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{E}_{F^{*}_{{\mathcal{X}},\\{i,j\\}}}\left[1_{\\{{\bf x}_{i}\geq{\bf
y}_{i},{\bf x}_{j}\geq{\bf y}_{j}\\}}\bigg{|}{\bf y}\right]\right]$ (22)
$\displaystyle=1-\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{P}({\bf x}_{i}\geq{\bf y}_{i},{\bf x}_{j}\geq{\bf y}_{j}|{\bf
y})\right].$ (23)

Moreover, we have

$\displaystyle\mathbb{P}({\bf x}_{i}\geq{\bf y}_{i},{\bf x}_{j}\geq{\bf
y}_{j}|{\bf y})$ $\displaystyle=1+F^{*}_{{\mathcal{X}},\\{i,j\\}}({\bf
y}_{i},{\bf y}_{j})$ $\displaystyle\quad-F^{*}_{{\mathcal{X}},\\{i\\}}({\bf
y}_{i})-F^{*}_{{\mathcal{X}},\\{j\\}}({\bf y}_{j})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}1+\frac{|E|}{X}\min\left\\{\frac{{\bf
y}_{i}}{d_{i}},\frac{{\bf y}_{j}}{d_{j}}\right\\}$
$\displaystyle\quad-\frac{|E|}{X}\frac{{\bf
y}_{i}}{d_{i}}-\frac{|E|}{X}\frac{{\bf y}_{j}}{d_{j}}$
$\displaystyle=1-\frac{|E|}{X}\max\left\\{\frac{{\bf y}_{i}}{d_{i}},\frac{{\bf
y}_{j}}{d_{j}}\right\\},$

where $(a)$ follows from (16). Plugging above equality into (19) gives

$\displaystyle\pi_{\mathcal{Y}}(F^{*}_{\mathcal{X}},F_{\mathcal{Y}})$
$\displaystyle=\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{1}{X}\sum_{\\{i,j\\}\in
E}\max\left\\{\frac{{\bf y}_{i}}{d_{i}},\frac{{\bf
y}_{j}}{d_{j}}\right\\}\right]$
$\displaystyle\leq\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{1}{X}\sum_{\\{i,j\\}\in
E}\left(\frac{{\bf y}_{i}}{d_{i}}+\frac{{\bf y}_{j}}{d_{j}}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{1}{X}\sum_{i=1}^{n}{{\bf
y}_{i}}\right]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{Y}{X},$

where $(a)$ follows from the same argument as (18), and $(b)$ follows from
$\mathbb{E}_{F_{\mathcal{Y}}}\left[\sum_{i=1}^{n}{\bf y}_{i}\right]\leq Y$.

The proof for the case $X<2Y$ follows the similar idea to the case $X\geq 2Y$.
For completeness, we provide the main lines of the proof for the case $X<2Y$.
For any $F_{\mathcal{X}}\in\mathbb{F}(X)$, we have

$\displaystyle\pi_{\mathcal{X}}($ $\displaystyle
F_{\mathcal{X}},F^{*}_{\mathcal{Y}})$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\mathbb{E}_{F^{*}_{\mathcal{Y}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}1_{\\{{\bf x}_{i}\geq{\bf y}_{i},{\bf x}_{j}\geq{\bf y}_{j}\\}}\bigg{|}{\bf
x}\right]\right]$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{E}_{F^{*}_{{\mathcal{Y}},\\{i,j\\}}}\left[1_{\\{{\bf x}_{i}\geq{\bf
y}_{i},{\bf x}_{j}\geq{\bf y}_{j}\\}}\bigg{|}{\bf x}\right]\right]$
$\displaystyle=\mathbb{E}_{F_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}F^{*}_{{\mathcal{Y}},\\{i,j\\}}({\bf x}_{\\{i,j\\}})\right]$
$\displaystyle=\mathbb{E}_{F^{\prime}_{\mathcal{X}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\frac{|E|}{4Y}\left(\frac{{\bf x}_{i}}{d_{i}}+\frac{{\bf
x}_{j}}{d_{j}}\right)\right]$
$\displaystyle=\mathbb{E}_{F^{\prime}_{\mathcal{X}}}\left[\frac{1}{4Y}\sum_{i=1}^{n}{\bf
x}_{i}\right]\leq\frac{X}{4Y}.$

For any $F_{\mathcal{Y}}\in\mathbb{F}(Y)$, we have

$\displaystyle\pi_{\mathcal{Y}}($ $\displaystyle
F^{*}_{\mathcal{X}},F_{\mathcal{Y}})$
$\displaystyle=1-\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{E}_{F^{*}_{{\mathcal{X}},\\{i,j\\}}}\left[1_{\\{{\bf x}_{i}\geq{\bf
y}_{i},{\bf x}_{j}\geq{\bf y}_{j}\\}}\bigg{|}{\bf y}\right]\right]$
$\displaystyle=1-\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{1}{|E|}\sum_{\\{i,j\\}\in
E}\mathbb{P}({\bf x}_{i}\geq{\bf y}_{i},{\bf x}_{j}\geq{\bf y}_{j}|{\bf
y})\right]$
$\displaystyle=1-\frac{X}{2Y}+\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{X}{4Y^{2}}\sum_{\\{i,j\\}\in
E}\max\left\\{\frac{{\bf y}_{i}}{d_{i}},\frac{{\bf
y}_{j}}{d_{j}}\right\\}\right]$ $\displaystyle\leq
1-\frac{X}{2Y}+\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{X}{4Y^{2}}\sum_{\\{i,j\\}\in
E}\left(\frac{{\bf y}_{i}}{d_{i}}+\frac{{\bf y}_{j}}{d_{j}}\right)\right]$
$\displaystyle=1-\frac{X}{2Y}+\mathbb{E}_{F_{\mathcal{Y}}}\left[\frac{X}{4Y^{2}}\sum_{i=1}^{n}{{\bf
y}_{i}}\right]$ $\displaystyle=1-\frac{X}{4Y}.$

###  5.3 Security bounds for general graphs

Next, we provide the proof for the lower and upper bounds on the defender’s
security value $S_{\mathcal{X}}^{*}$ detailed in Theorem 4.1.

Proof of Theorem 4.1: To establish the lower bound $\gamma(X,Y)\leq
S_{\mathcal{X}}^{*}(X,Y,G)$ (9), consider an arbitrary graph $G$ and suppose
player ${\mathcal{X}}$ allocates according to the strategy (16) if $X\geq 2Y$,
and according to the strategy (14) if $X<2Y$. For $X\geq 2Y$, we have

$\displaystyle\max_{F_{\mathcal{X}}\in\mathbb{F}(X)}\min_{F_{\mathcal{Y}}\in\mathbb{F}(Y)}\pi_{\mathcal{X}}(F_{\mathcal{X}},F_{\mathcal{Y}})$
$\displaystyle\geq\min_{F_{\mathcal{Y}}\in\mathbb{F}(Y)}\pi_{\mathcal{X}}(F^{*}_{\mathcal{X}},F_{\mathcal{Y}})$
$\displaystyle=\min_{F_{\mathcal{Y}}\in\mathbb{F}(Y)}1-\pi_{\mathcal{Y}}(F^{*}_{\mathcal{X}},F_{\mathcal{Y}})$
$\displaystyle\geq 1-\frac{Y}{X}=\gamma(X,Y),$

where the last inequality follows the similar argument to the proof of Theorem
3.1. The proof for the case $X<2Y$ is similar.

To establish the upper bound $S_{\mathcal{X}}^{*}(X,Y,G)\leq\gamma_{n}(X,Y)$
(9), we consider the following correlated allocation strategy
$G_{\mathcal{Y}}$ for player ${\mathcal{Y}}$. ${\mathcal{D}}$ is the
collection of $n$ vertex covers $\\{V_{k}\\}_{k\in[n]}$, where we define the
$k$th vertex cover as $V_{k}=V\backslash\\{k\\}\in{\mathcal{D}}$ for each
$k\in V$. In words, the $k$th vertex cover $V_{k}$ is the set of all nodes
except node $k$. We assume each vertex cover is chosen with equal probability
$1/n$. For simplicity, let $w_{V_{k},i}\triangleq w_{k,i}$. We set the weights
$w_{k,i}$ as follows. For any $k\in V$ and $i\in V\backslash\\{k\\}$,

$w_{k,i}=\begin{cases}\frac{d_{i}}{2|E|},&\text{if }k\notin\mathcal{N}_{i}\\\
\frac{d_{i}+1}{2|E|},&\text{if }k\in\mathcal{N}_{i}\end{cases},$ (24)

where $\mathcal{N}_{i}$ is the neighbor set of node $i$ for $i\in V$. In
words, the weight of node $i$ in vertex cover $k$ is determined by how many
nodes it “covers”. For each neighbor already in $V_{k}$, node $i$ accumulates
a weight $\frac{1}{2|E|}$ (they do not need to be covered). If $k$ is a
neighbor, then $i$ accumulates a weight of $\frac{1}{|E|}$. It then follows
that the sum of weights in any vertex cover is normalized, i.e.
$w_{k}\triangleq\sum_{i\neq k}w_{k,i}=1$. An example illustration of this
strategy was provided in Figure 4.

From (12), the strategy $G_{\mathcal{Y}}$ is explicitly written as

$G_{\mathcal{Y}}(y)=1-\delta+\frac{\delta^{2}}{2Yn}\sum_{k=1}^{n}\min\left\\{\left\\{\frac{y_{i}}{w_{k,i}}\right\\}_{i\in
V_{k}},\frac{2Y}{\delta}\right\\},$ (25)

where $\delta\in[0,1]$ is a tunable parameter. The bi-variate marginal
distribution over $i,j\in V$ is then given by

$\displaystyle G_{{\mathcal{Y}},\\{i,j\\}}$
$\displaystyle\left(y_{\\{i,j\\}}\right)=$ (26) $\displaystyle
1-\delta+\frac{\delta^{2}}{2Yn}\Bigg{(}\min\left\\{\frac{y_{i}}{w_{j,i}},\frac{2Y}{\delta}\right\\}+\min\left\\{\frac{y_{j}}{w_{i,j}},\frac{2Y}{\delta}\right\\}$
$\displaystyle\hskip 71.13188pt+\sum_{k\neq
i,j}\min\left\\{\frac{y_{i}}{w_{k,i}},\frac{y_{j}}{w_{k,j}},\frac{2Y}{\delta}\right\\}\Bigg{)}.$

For any $F_{X}\in\mathbb{F}(X)$ with the property of Lemma 5.1, i.e.
$\mathbb{P}_{F_{\mathcal{X}}}({\bf x}_{i}>\frac{2Y}{\delta|E|})=0$, the
expected payoff $\pi_{\mathcal{X}}(F_{\mathcal{X}},G_{\mathcal{Y}})$ to
${\mathcal{X}}$ is

$\displaystyle\pi_{\mathcal{X}}(F_{\mathcal{X}},G_{\mathcal{Y}})$
$\displaystyle=\frac{1}{|E|}\mathbb{E}_{F_{\mathcal{X}}}\left[\sum_{\\{i,j\\}\in
E}G_{{\mathcal{Y}},\\{i,j\\}}({\bf x}_{\\{i,j\\}})\right]$ (27)
$\displaystyle=1-\delta+\frac{\delta^{2}}{2Yn|E|}\mathbb{E}_{F_{\mathcal{X}}}\left[A_{1}({\bf
x})+A_{2}({\bf x})\right],$

where

$\displaystyle A_{1}(x)$ $\displaystyle\triangleq\sum_{\\{i,j\\}\in
E}\sum_{k\neq
i,j}\min\left\\{\frac{x_{i}}{w_{k,i}},\frac{x_{j}}{w_{k,j}}\right\\},$ (28)
$\displaystyle A_{2}(x)$ $\displaystyle\triangleq\sum_{\\{i,j\\}\in
E}\left(\frac{x_{i}}{w_{j,i}}+\frac{x_{j}}{w_{i,j}}\right).$ (29)

Due to $\min\\{a,b\\}\leq\frac{a+b}{2}$, we have

$\displaystyle A_{1}(x)$ $\displaystyle\leq\frac{1}{2}\sum_{\\{i,j\\}\in
E}\sum_{k\neq i,j}\left(\frac{x_{i}}{w_{k,i}}+\frac{x_{j}}{w_{k,j}}\right)$
(30) $\displaystyle=\frac{1}{2}\sum_{\\{i,j\\}\in
E}\left(x_{i}\left(\sum_{k\neq
i,j}\frac{1}{w_{k,i}}\right)+x_{j}\left(\sum_{k\neq
i,j}\frac{1}{w_{k,j}}\right)\right),$

For each $\\{i,j\\}\in E$, we calculate

$\displaystyle\sum_{k\neq i,j}\frac{1}{w_{k,i}}$
$\displaystyle=\sum_{k\in\mathcal{N}_{i}\backslash\\{j\\}}\frac{1}{w_{k,i}}+\sum_{k\notin\mathcal{N}_{i}}\frac{1}{w_{k,i}}$
(31)
$\displaystyle=\frac{2|E|(d_{i}-1)}{d_{i}+1}+\frac{2|E|(n-(d_{i}+1))}{d_{i}}$
$\displaystyle=2|E|\left(\frac{n-1}{d_{i}}-\frac{2}{d_{i}+1}\right)\triangleq\Gamma_{i},$

where we have used (24). We then obtain

$\displaystyle A_{1}(x)$ $\displaystyle=\sum_{\\{i,j\\}\in
E}\left(x_{i}\Gamma_{i}+x_{j}\Gamma_{j}\right)$ (32)
$\displaystyle=|E|\sum_{i\in
V}x_{i}d_{i}\left(\frac{n-1}{d_{i}}-\frac{2}{d_{i}+1}\right),$

We can also express the second term from (28),

$\displaystyle A_{2}(x)$ $\displaystyle=|E|\sum_{i\in
V}x_{i}\sum_{j\in\mathcal{N}_{i}}\frac{1}{w_{j,i}}$
$\displaystyle=|E|\sum_{i\in V}x_{i}\frac{2d_{i}}{d_{i}+1},$

which is derived using (24). We thus obtain the following upper bound on the
payoff for player ${\mathcal{X}}$

$\displaystyle\pi_{\mathcal{X}}(F_{\mathcal{X}},G_{\mathcal{Y}})=1-\delta+\frac{\delta^{2}}{2Yn|E|}\mathbb{E}_{F_{\mathcal{X}}}\left[A_{1}({\bf
x})+A_{2}({\bf x})\right]$ (33) $\displaystyle\leq
1-\delta+\frac{\delta^{2}}{2Yn}\mathbb{E}_{F_{\mathcal{X}}}\\!\\!\left[\sum_{i\in
V}{\bf
x}_{i}d_{i}\\!\\!\left(\frac{n-1}{d_{i}}-\frac{2}{d_{i}+1}+\frac{2}{d_{i}+1}\right)\right]$
$\displaystyle=1-\delta+\frac{\delta^{2}(n-1)}{2Yn}\mathbb{E}_{F_{\mathcal{X}}}\left[\sum_{i\in
V}{\bf x}_{i}\right]$
$\displaystyle=1-\delta+\frac{\delta^{2}(n-1)}{2n}\frac{X}{Y}.$

Recall that the variable $\delta\in[0,1]$ is a parameter that player
${\mathcal{Y}}$ can tune. The optimal $\delta^{*}$ that minimizes the upper
bound above is given by

$\delta^{*}=\begin{cases}\frac{nY}{(n-1)X},&\text{if }X\geq\frac{n}{n-1}Y\\\
1,&\text{if }X<\frac{n}{n-1}Y\end{cases}.$ (34)

Therefore, player ${\mathcal{Y}}$, using $F_{\mathcal{Y}}$, can ensure player
${\mathcal{X}}$ obtains a payoff no greater than

$\gamma_{n}(X,Y,G)=\begin{cases}1-\frac{nY}{2(n-1)X},&\text{if
}X\geq\frac{n}{n-1}Y\\\ \frac{n-1}{2n}\frac{X}{Y},&\text{if
}X<\frac{n}{n-1}Y\end{cases}.$ (35)

##  6 Performance of deterministic strategies

In this section, we highlight the importance of randomized allocation
strategies by considering scenarios where the defender (${\mathcal{X}}$) does
not have the ability to randomize its allocation, i.e. it must select a
deterministic strategy

$x\in\Delta(X)\triangleq\left\\{x^{\prime}\in\mathbb{R}_{+}^{n}:\sum_{i=1}^{n}x_{i}^{\prime}\leq
X\right\\}.$ (36)

Recall the performance lower bound $\gamma(X,Y)$ from Theorem 4.1 is achieved
through the randomized strategy (16). While this lower bound has no explicit
dependence on the network structure $G$, we will highlight the dependence of
payoff guarantees on network structure when restricted to deterministic
strategies through numerical studies.

We first present some general properties regarding conditions on graph
structure and opponent budget $Y$ for which ${\mathcal{X}}$ can guarantee a
positive payoff. We then define a heuristic class of deterministic strategies
for ${\mathcal{X}}$ and evaluate its performance via numerical simulations on
random graphs. These studies not only highlight the the importance of
randomized allocations and the impact of different graph structures on
performance.

###  6.1 General properties of deterministic strategies

The following result illustrates some general properties regarding
deterministic strategies for ${\mathcal{X}}$ on structured networks.

###### Proposition 6.1

Let

$\displaystyle
S_{\mathcal{X}}^{d}(X,Y,G)\triangleq\max_{x\in\Delta(X)}\min_{y\in\Delta(Y)}\pi_{\mathcal{X}}(x,y;G)$

be the security value for ${\mathcal{X}}$ under deterministic strategies on
any graph $G$. We have

  1. (a)

If $G$ is bipartite, $S_{\mathcal{X}}^{d}(X,Y,G)>0$ iff $Y\leq\frac{X}{2}$.

  2. (b)

If $G$ is a complete graph, $S_{\mathcal{X}}^{d}(X,Y,G)>0$ iff
${Y\leq\frac{n-1}{n}X}$.

  3. (c)

$S_{\mathcal{X}}^{d}(X,Y,G)=0$ if $Y>\frac{n-1}{n}X$.

  4. (d)

$S_{\mathcal{X}}^{d}(X,Y,G)>0$ if $Y\leq X/2$.

Proposition 6.1 identifies bipartite and complete graphs as the two extreme
network structures determining a defender’s effectiveness. Indeed, bipartite
networks provide positive payoff guarantees on the smallest range of
parameters, i.e. $Y\in[0,X/2]$ (property (a)). Complete networks provide
positive payoff guarantees on the widest range of parameters, i.e. for any
$Y\in[0,\frac{n-1}{n}X]$ (property (b)). The range of parameters where this
guarantee holds for an arbitrary graph $G$ must lie somewhere in between, i.e.
$Y\in[0,fX]$ for some $\frac{1}{2}\leq f\leq\frac{n-1}{n}$ (property (c)-(d)).
The proof of the Proposition is provided in Section 5.

######  Proof 6.1.

First, we prove parts (c) and (d).

To prove part (c), let set $A_{i}=[n]\setminus\\{i\\}$ for $i\in[n]$. First,
note that $A_{i}$s are vertex cover. Therefore, if for some $i\in[n]$,
$Y>X_{i}\triangleq\sum_{j\in A_{i}}x_{j},$ assigning
${y_{j}=x_{j}+\frac{Y-X_{i}}{n-1}}$ for all $j\in A_{i}$, player
${\mathcal{Y}}$ wins all vertices in $A_{i}$, and hence, wins all the edges.
On the other hand, We have

$\displaystyle\sum_{i=1}^{n}\sum_{j\in
A_{i}}x_{j}=\sum_{j=1}^{n}(n-1)x_{j}=(n-1)X.$

This implies

$\displaystyle\min_{j\in[n]}\left\\{\sum_{j\in
A_{j}}x_{j}\right\\}\leq\frac{n-1}{n}X,$

which completes the proof of $S_{\mathcal{X}}(X,Y,G)=0$ if $Y>\frac{n-1}{n}X$.

To prove part (d), suppose that there is an edge between nodes $i$ and $j$,
and $x_{i}=x_{j}=\frac{X}{2}$. Therefore, in order for player ${\mathcal{Y}}$
to win this edge, $Y$ should be strictly greater $\frac{X}{2}$.

For part (a), note that “if” part is implied by part (d). To prove the the
other direction, let $B_{1}$ and $B_{2}$ be the vertex set of two part of the
a bipartite graph $G$, i.e., $B_{1}\cup B_{2}=V$, and there is no edge between
any two vertices in $B_{1}$ or $B_{2}$. Since $\sum_{j\in
B_{1}}x_{j}+\sum_{j\in B_{2}}x_{j}=X$, we have

$\displaystyle\min\left\\{\sum_{j\in B_{1}}x_{j},\sum_{j\in
B_{2}}x_{j}\right\\}\leq\frac{X}{2}.$

Therefore, if $Y>\frac{X}{2}$, player ${\mathcal{Y}}$ can win all vertices in
$B_{1}$ or $B_{2}$, and hence, win all the edges.

For part (b), note that “only if” part is implied by part (c). To prove the
the other direction, we note that every vertex cover in a complete graph has
$n-1$ vertices. If player ${\mathcal{X}}$ assign his budget uniformly, i.e.,
$x_{i}=\frac{X}{n}$ for $i\in[n]$, $Y$ has to be strictly greater than
$\frac{n-1}{n}X$ in order for player ${\mathcal{Y}}$ to win all edges.

In the following, we will quantify and compare the performance of a certain
class of deterministic strategies on various networks through simulations.
These experiments corroborate the findings of Proposition 6.1.

###  6.2 Numerical simulations

On arbitrary networks, we evaluate the performance of the following
deterministic strategy for ${\mathcal{X}}$:

$x_{i}^{(d)}\triangleq\frac{d_{i}}{2|E|}X,\quad\forall i\in V,$ (37)

where $d_{i}$ is the degree of node $i$. In words, the amount of resources
${\mathcal{X}}$ allocates to any node is proportional to its degree
centrality111This deterministic strategy is inspired by its randomized
counterpart (16), which is optimal for bipartite graphs..

In response, player ${\mathcal{Y}}$ then selects a _deterministic_ strategy
$y\in\Delta(Y)$. The best-response problem for ${\mathcal{Y}}$, i.e
$\max_{y\in\Delta(Y)}\pi_{\mathcal{Y}}(x,y)$ for any $x\in\Delta(X)$ is known
as a _budgeted maximum coverage_ problem, which is NP-hard. To evaluate the
performance of a defender that implements $x^{(d)}$, we adapt a greedy
algorithm from [19] to approximate ${\mathcal{Y}}$’s best-response, which we
detail in Algorithm 1. This gives a performance factor222Other methods can
improve the guarantee to $1-1/e$ [19]. We do not utilize these, however,
because they come with a much higher computational cost than Algorithm 1,
especially on large scale networks. of $1-1/\sqrt{e}$.

Figure 5: Simulations showing the deterministic-to-randomized performance
ratio $u_{\mathcal{X}}^{(d)}/\gamma(X,Y)$ on a variety of networks. We fix
$n=100$ for all graphs considered. For ER random graphs, we average the
performance over 100 independent samples at each value of $Y$. Here, $p$ is
the independent link formation probability. Deterministic strategies perform
better on more densely connected networks. In all simulations, we fix $X=2$.

We denote the resulting payoff to ${\mathcal{X}}$ as
$u_{\mathcal{X}}^{(d)}\triangleq\pi_{\mathcal{X}}(x^{(d)},y(x^{(d)}))$, where
$y(x^{(d)})\in\Delta(Y)$ is the response generated from Algorithm 1. Figure 5
shows numerical simulations characterizing the performance ratio
$u_{\mathcal{X}}^{(d)}/\gamma(X,Y)$ on Erdös-Rényi (ER) random networks, where
$\gamma(X,Y)$ is the lower bound (5) on the payoff that ${\mathcal{X}}$’s can
ensure on any graph using randomized strategies (Theorem 4.1). Hence,
$\gamma(X,Y)$ serves as a benchmark comparison.

There are two main conclusions from these experiments. First, $x^{(d)}$
performs better on graphs with higher edge density. The performance is worst
on star, ring, and line networks, improves on ER random networks for higher
link parameter $p\in[0,1]$, and performs best on the complete network (Figure
5, right). These numerical findings are consistent with the results
established in Proposition 6.1. Second, deterministic strategies perform
significantly worse relative to randomized strategies. Considering that we use
the lower bound $\gamma(X,Y)$ as the benchmark comparison, and the greedy
response is sub-optimal for ${\mathcal{Y}}$, the performance ratio
$u_{\mathcal{X}}^{(d)}/\gamma(X,Y)$ serves as an upper bound on the
performance of $x^{(d)}$. Specifically, it is an upper bound on the ratio
wherein ${\mathcal{Y}}$ implements a best response and the denominator is
taken as the actual max-min value for ${\mathcal{X}}$ (LHS of (9)).

######  Remark 6.2.

The strategy $x^{(d)}$ is a heuristic strategy for ${\mathcal{X}}$ used for
the purpose of making performance comparisons on arbitrary networks via
numerical simulations. It is not proven here that $x^{(d)}$ is optimal among
deterministic strategies, i.e. one that solves
$\max_{x\in\Delta(X)}\min_{y\in\Delta(Y)}\pi_{\mathcal{X}}(x,y)$. Such a
problem is difficult to solve, since the inner minimization alone is NP-hard.

Algorithm 1 Greedy response of ${\mathcal{Y}}$ to $x\in\Delta(X)$ on
$G=(V,E)$. This algorithm is adapted from [19]. We define
$\mathcal{E}(N)\triangleq|\\{(i,j)\in E:i\text{ or }j\in N\\}|$ as the number
of edges connected to the subset of nodes $N\subset V$ (line 7).

1:procedure greedy($x,Y,G$)

2: $y_{i}\leftarrow 0$, $\forall i\in V$ $\triangleright$ initialize response

3: $i^{*}\leftarrow\max_{i\in V}\mathcal{E}(i)$ $\triangleright$ highest
degree node

4: $N\leftarrow\varnothing$ $\triangleright$ nodes to secure

5: while $V\neq\varnothing$ do

6: $D=\arg\max_{i\in V}\\{\frac{\mathcal{E}(N\cup
i)-\mathcal{E}(N)}{x_{i}}\\}$

7: $u\leftarrow\arg\min_{v\in D}x_{v}$ $\triangleright$ cheapest node in $D$

8: if $\sum_{j\in N\cup u}x_{j}\leq Y$ then $\triangleright$ budget-feasible

9: $N\leftarrow N\cup u$ $\triangleright$ update secured nodes

10: $V\leftarrow V\setminus u$

11: $\mathcal{E}^{*}\leftarrow\max\left\\{1(x_{i^{*}}\leq
Y)\cdot\mathcal{E}(i^{*}),\mathcal{E}(N)\right\\}$

12: if $\mathcal{E}^{*}=\mathcal{E}(N)$ then

13: $y_{i}\leftarrow x_{i}$, $\forall i\in N$

14: else

15: $y_{i^{*}}\leftarrow x_{i^{*}}$

16: return $y\in\Delta(Y)$ $\triangleright$ greedy response

##  7 Conclusion and Future Research

In the context of General Lotto games, we studied a competitive resource
allocation scenario between an attacker and defender of a network. The
objective for each player is to secure as many edges of the network as
possible, where the defender is required to win both endpoint nodes in order
to secure an edge. We completely characterized equilibrium payoffs and
strategies for both players when the network is bipartite. On arbitrary
networks, we provided lower and upper bounds on the defender’s max-min
performance. To further demonstrate the impact of network topology, we then
considered a defender restricted to deterministic strategies. We identified
bipartite and complete graphs as the two extreme structures that determine the
defender’s effectiveness. These findings were corroborated through numerical
simulations.

It is of interest to extend our equilibrium results to larger classes of
networks. In Section 6, we saw that the performance of deterministic
strategies is highly dependent on the network structure. We would like to
identify the salient network characteristics, e.g. edge density, cluster
coefficients, etc, that contribute to the performance.

## References

  * [1] M. Abdallah, P. Naghizadeh, A. R. Hota, T. Cason, S. Bagchi, and S. Sundaram.  Behavioral and game-theoretic security investments in interdependent systems modeled by attack graphs.  IEEE Transactions on Control of Network Systems, 7(4):1585–1596, 2020.
  * [2] A. Aghajan, K. Paarporn, and J. R. Marden.  Extension theorems for general lotto games with applications to network security.  IEEE Transactions on Control of Network Systems, pages 1–12, 2023\.
  * [3] T. Alpcan and T. Basar.  Network Security: A Decision and Game-Theoretic Approach.  Cambridge University Press, 2010.
  * [4] S. Amini, F. Pasqualetti, and H. Mohsenian-Rad.  Dynamic load altering attacks against power system stability: Attack models and protection schemes.  IEEE Transactions on Smart Grid, 9(4):2862–2872, 2016.
  * [5] C.-Z. Bai, F. Pasqualetti, and V. Gupta.  Data-injection attacks in stochastic control systems: Detectability and performance tradeoffs.  Automatica, 82:251–260, 2017.
  * [6] E. Borel.  La théorie du jeu les équations intégrales à noyau symétrique.  Comptes Rendus de l’Académie, 173, 1921.
  * [7] A. Cardenas, S. Amin, B. Sinopoli, A. Giani, A. Perrig, S. Sastry, et al.  Challenges for securing cyber physical systems.  In Workshop on future directions in cyber-physical systems security, volume 5. Citeseer, 2009.
  * [8] A. K. Chen, B. L. Ferguson, D. Shishika, M. Dorothy, J. R. Marden, G. J. Pappas, and V. Kumar.  Path defense in dynamic defender-attacker blotto games (ddab) with limited information.  arXiv preprint arXiv:2204.04176, 2022.
  * [9] J. Cortes, S. Martinez, T. Karatas, and F. Bullo.  Coverage control for mobile sensing networks.  IEEE Transactions on Robotics and Automation, 20(2):243–255, 2004\.
  * [10] X. Duan, M. George, and F. Bullo.  Markov chains with maximum return time entropy for robotic surveillance.  IEEE Transactions on Automatic Control, 65(1):72–86, 2020.
  * [11] S. R. Etesami and T. Başar.  Dynamic games in cyber-physical security: An overview.  Dynamic Games and Applications, 9(4):884–913, 2019.
  * [12] A. Ferdowsi, W. Saad, and N. B. Mandayam.  Colonel blotto game for sensor protection in interdependent critical infrastructure.  IEEE Internet of Things Journal, 8(4):2857–2874, 2021.
  * [13] B. L. Ferguson, D. Shishika, and J. R. Marden.  Ensuring the defense of paths and perimeters in dynamic defender-attacker blotto games (ddab) on graphs.  In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1–7, 2022.
  * [14] R. Golman and S. E. Page.  General Blotto: games of allocative strategic mismatch.  Public Choice, 138(3-4):279–299, 2009.
  * [15] O. Gross and R. Wagner.  A continuous Colonel Blotto game.  Technical report, RAND Project, Air Force, Santa Monica, 1950.
  * [16] S. Guan, J. Wang, H. Yao, C. Jiang, Z. Han, and Y. Ren.  Colonel Blotto games in network systems: Models, strategies, and applications.  IEEE Transactions on Network Science and Engineering, 7(2):637–649, 2020.
  * [17] S. Hart.  Discrete Colonel Blotto and General Lotto games.  International Journal of Game Theory, 36(3-4):441–460, 2008.
  * [18] A. R. Hota and S. Sundaram.  Interdependent security games on networks under behavioral probability weighting.  IEEE Transactions on Control of Network Systems, 5(1):262–273, 2016\.
  * [19] S. Khuller, A. Moss, and J. S. Naor.  The budgeted maximum coverage problem.  Information processing letters, 70(1):39–45, 1999.
  * [20] D. Kovenock and B. Roberson.  Conflicts with multiple battlefields.  In M. Garfinkel and S. Skaperdas, editors, The Oxford Handbook of the Economics of Peace and Conflict. Oxford University Press, Oxford, 2012\.
  * [21] D. Kovenock and B. Roberson.  The optimal defense of networks of targets.  Economic Inquiry, 56(4):2195–2211, 2018.
  * [22] D. Kovenock and B. Roberson.  Generalizations of the general Lotto and Colonel Blotto games.  Economic Theory, pages 1–36, 2021.
  * [23] J. Milošević, H. Sandberg, and K. H. Johansson.  Estimating the impact of cyber-attack strategies for stochastic networked control systems.  IEEE Transactions on Control of Network Systems, 7(2):747–757, 2020\.
  * [24] R. B. Myerson.  Incentives to cultivate favored minorities under alternative electoral systems.  American Political Science Review, 87(4):856–869, 1993.
  * [25] K. Paarporn, R. Chandan, M. Alizadeh, and J. R. Marden.  The division of assets in multiagent systems: A case study in team blotto games.  In 2021 60th IEEE Conference on Decision and Control (CDC), pages 1663–1668. IEEE, 2021.
  * [26] K. Paarporn, R. Chandan, M. Alizadeh, and J. R. Marden.  Asymmetric battlefield uncertainty in general lotto games.  IEEE Control Systems Letters, 6:2822–2827, 2022.
  * [27] F. Pasqualetti, F. Dörfler, and F. Bullo.  Attack detection and identification in cyber-physical systems.  IEEE transactions on automatic control, 58(11):2715–2729, 2013\.
  * [28] F. Pasqualetti, F. D orfler, and F. Bullo.  Control-theoretic methods for cyberphysical security: Geometric principles for optimal cross-layer resilient control systems.  IEEE Control Systems Magazine, 35(1):110–127, 2015.
  * [29] B. Roberson.  The Colonel Blotto game.  Economic Theory, 29(1):1–24, 2006.
  * [30] H. Sandberg, S. Amin, and K. H. Johansson.  Cyberphysical security in networked control systems: An introduction to the issue.  IEEE Control Systems Magazine, 35(1):20–23, 2015.
  * [31] G. Schwartz, P. Loiseau, and S. S. Sastry.  The heterogeneous Colonel Blotto game.  In Int. Conf. on NETwork Games, COntrol and OPtimization, pages 232–238, Oct 2014.
  * [32] E. M. Shahrivar and S. Sundaram.  Multi-layer network formation via a Colonel Blotto game.  In 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 838–841, Dec 2014.
  * [33] D. Shishika, Y. Guan, M. Dorothy, and V. Kumar.  Dynamic defender-attacker blotto game.  In 2022 American Control Conference (ACC), pages 4422–4428. IEEE, 2022.
  * [34] M. Shubik and R. J. Weber.  Systems defense games: Colonel blotto, command and control.  Naval Research Logistics Quarterly, 28(2):281–287, 1981.
  * [35] M. Tambe.  Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned.  Cambridge University Press, 2011.
  * [36] C. Thomas.  N-dimensional Blotto game with heterogeneous battlefield values.  Economic Theory, 65(3):509–544, 2018.
  * [37] K. G. Vamvoudakis, J. P. Hespanha, B. Sinopoli, and Y. Mo.  Detection in adversarial environments.  IEEE Transactions on Automatic Control, 59(12):3209–3223, 2014\.
  * [38] W. Xing, X. Zhao, T. Basar, and W. Xia.  Security investment in cyber-physical systems: Stochastic games with asymmetric information and resource constrained players.  IEEE Transactions on Automatic Control, 2021.

[] Adel Aghajan received a B.Sc., and M.Sc. degrees in Electrical Engineering
from Isfahan University of Technology, Isfahan, Iran, in 2009, and 2012,
respectively, and a Ph.D. degree in Electrical Engineering at University of
California, San Diego, in 2021. He is currently a Postdoctoral Scholar with
the Department of Electrical and Computer Engineering, the University of
California, Santa Barbara. His research interests include game theory,
distributed computation and optimization , random dynamics, and information
theory.

[] Keith Paarporn is an Assistant Professor in the Department of Computer
Science at the University of Colorado, Colorado Springs. He received a B.S. in
Electrical Engineering from the University of Maryland, College Park in 2013,
an M.S. in Electrical and Computer Engineering from the Georgia Institute of
Technology in 2016, and a Ph.D. in Electrical and Computer Engineering from
the Georgia Institute of Technology in 2018. From 2018 to 2022, he was a
postdoctoral scholar in the Electrical and Computer Engineering Department at
the University of California, Santa Barbara. His research interests include
game theory, control theory, and their applications to multi-agent systems and
security.

[] Jason Marden is a Professor in the Department of Electrical and Computer
Engineering at the University of California, Santa Barbara. Jason received a
BS in Mechanical Engineering in 2001 from UCLA, and a PhD in Mechanical
Engineering in 2007, also from UCLA, under the supervision of Jeff S. Shamma,
where he was awarded the Outstanding Graduating PhD Student in Mechanical
Engineering. After graduating from UCLA, he served as a junior fellow in the
Social and Information Sciences Laboratory at the California Institute of
Technology until 2010 when he joined the University of Colorado. Jason is a
recipient of the NSF Career Award (2014), the ONR Young Investigator Award
(2015), the AFOSR Young Investigator Award (2012), the American Automatic
Control Council Donald P. Eckman Award (2012), and the SIAG/CST Best SICON
Paper Prize (2015). Jason’s research interests focus on game theoretic methods
for the control of distributed multiagent systems.