# A risk-security tradeoff in graphical coordination games

Keith Paarporn, Mahnoosh Alizadeh, and Jason R. Marden K. Paarporn
(kpaarporn@ucsb.edu), M. Alizadeh (alizadeh@ucsb.edu), and J. R. Marden
<EMAIL_ADDRESS>are with the Department of Electrical and Computer
Engineering at the University of California, Santa Barbara, CA. A preliminary
version of this paper has been submitted for conference publication (CDC 2019)
and can be found at https://ece.ucsb.edu/j̃rmarden/files/MardenC9.pdf. The
analysis of randomized operator strategies extends the previous results.
Complete proofs are also provided here. This work is supported by UCOP Grant
LFR-18-548175, ONR grant #N00014-17-1-2060, and NSF grant #ECCS-1638214.

###### Abstract

A system relying on the collective behavior of decision-makers can be
vulnerable to a variety of adversarial attacks. How well can a system operator
protect performance in the face of these risks? We frame this question in the
context of graphical coordination games, where the agents in a network choose
among two conventions and derive benefits from coordinating neighbors, and
system performance is measured in terms of the agents’ welfare. In this paper,
we assess an operator’s ability to mitigate two types of adversarial attacks -
1) broad attacks, where the adversary incentivizes all agents in the network
and 2) focused attacks, where the adversary can force a selected subset of the
agents to commit to a prescribed convention. As a mitigation strategy, the
system operator can implement a class of distributed algorithms that govern
the agents’ decision-making process. Our main contribution characterizes the
operator’s fundamental trade-off between security against worst-case broad
attacks and vulnerability from focused attacks. We show that this tradeoff
significantly improves when the operator selects a decision-making process at
random. Our work highlights the design challenges a system operator faces in
maintaining resilience of networked distributed systems.

##  I Introduction

Networked distributed systems typically operate without centralized planning
or control, and instead rely on local interactions and communication between
the comprising agents. These systems arise in a variety of engineering
applications such as teams of mobile robots and sensor networks [1, 2, 3].
They are also prevalent in social dynamics [4, 5] and biological populations
[6].

The transition from a centralized to a distributed architecture may leave a
system vulnerable to a variety of adversarial attacks. An adversary may be
able to manipulate the decision-making processes of the agents. Such dynamical
perturbations can potentially lead to unwanted outcomes. For example in social
networks, individual opinions can be shaped from external information sources,
resulting in a polarized society [7, 8]. When feasible, a system operator
takes measures to mitigate adversarial influences. The literature on cyber-
physical system security studies many aspects of this interplay. For instance,
optimal controllers are designed to mitigate denial-of-service, estimation,
and deception attacks [9, 10, 11, 12, 13].

This paper investigates security measures that a system operator can take
against adversarial influences when the underlying system is a graphical
coordination game [5, 14], where agents in a network decide between two
choices, $x$ or $y$. One may think of these choices as two competing products,
e.g. iPhone vs Android, two conflicting social norms, or two opposing
political parties. Each agent derives a positive benefit from interactions
with coordinating neighbors, and zero benefits from mis-coordinating ones. The
system’s efficiency is defined by the ratio of total benefits of all agents to
the maximal attainable benefits over all configurations of choices.

The goal of the system operator is to design a local decision-making rule for
each agent in the system so that the emergent collective behavior optimizes
system efficiency. One algorithm that achieves this goal is known as log-
linear learning [15, 16, 17]. More formally, the agents follow a “perturbed”
best reply dynamics where the agents’ local objectives are precisely equal to
their local welfare. We seek to address the question of whether this
particular algorithm is robust to adversarial influences. That is, does this
algorithm preserve system efficiency when the agents’ decision-making
processes are manipulated by an adversary? If not, can the operator alter the
agents’ local objectives to mitigate such attacks?

We consider two adversarial attack models - _broad_ and _focused_ attacks. In
broad attacks, the adversary incentivizes every agent in the network (hence
broad) with a convention, influencing their decision-making process. This
could depict distributing political ads with the intention of polarizing
voters. In focused attacks, the adversary targets a specific set of agents in
the network, forcing them to commit to $x$ or $y$. These targeted, or fixed
agents consequently do not update their choices over time but still influence
the decisions of others. For instance, they could portray loyal consumers of a
brand or product, or staunch supporters of a political party. Fixed agents and
their effects on system performance have been extensively studied in the
context of opinion dynamics and optimization algorithms [18, 19, 13].

The first contribution of this paper is a characterization of worst-case risk
metrics from both adversarial attacks as a function of the operator’s
algorithm design parameter (Section III). We define risk in this paper as the
system’s distance to optimal efficiency. By worst-case here we mean the
maximum risk among all connected network topologies subject to any admissible
adversarial attack. Hence, our analysis identifies the network topologies on
which worst-case risks are attained (Section V). We extend this analysis to
randomized operator strategies (Sections IV, VI).

The second contribution of this paper answers the question “if the operator
succeeds in protecting the system from one type of attack, how vulnerable does
it leave the system to the other?” We identify a fundamental tradeoff between
security against broad attacks and risks from focused attacks. We then show
randomized operator strategies significantly improves the set of attainable
risk levels and their associated tradeoffs (Section IV).

By characterizing this interplay, we contribute to previous work that studied
the impact of adversarial influence in graphical coordination games [20, 21,
22]. These works analyze worst-case damages that can be inflicted by varying
degrees of adversarial sophistication and intelligence in the absence of a
system operator. However, these results were derived only in specific graph
structures, namely ring graphs, whereas our analysis considers adversarial
influence in any graph topology.

##  II Preliminaries

###  II-A Graphical coordination games

A graphical coordination game is played between a set of agents
$\mathcal{N}=\\{1,\ldots,N\\}$ over a connected undirected network
$G=(\mathcal{N},\mathcal{E})$ with node set $\mathcal{N}$ and edge set
$\mathcal{E}\subset\mathcal{N}\times\mathcal{N}$. Agent $i$’s set of neighbors
is written as $\mathcal{N}_{i}=\\{j:(i,j)\in\mathcal{E}\\}$. Each agent $i$
selects a choice $a_{i}$ from its action set $\mathcal{A}_{i}=\\{x,y\\}$. The
choices of all the agents constitutes an action profile
$a=(a_{1},\ldots,a_{N})$, and we denote the set of all action profiles as
$\mathcal{A}=\Pi_{i=1}^{N}\mathcal{A}_{i}$. The local interaction between two
agents $(i,j)\in\mathcal{E}$ is based on a $2\times 2$ matrix game, described
by the payoff matrix $V:\\{x,y\\}^{2}\rightarrow\mathbb{R}$,

|  | Player $j$
---|---|---
|  | $x$ | $y$
Player $i$ | $x$ | $1+\alpha_{\text{sys}},1+\alpha_{\text{sys}}$ | $0,0$
$y$ | $0,0$ | $1,1$
(1)

where $\alpha_{\text{sys}}>0$ is the system _payoff gain_. It indicates that
$x$ is an inherently superior product over $y$ when users coordinate. Here,
agents would rather coordinate than not, but prefer to coordinate on $x$.
Agent $i$’s _benefit_ is the sum of payoffs derived from playing the game (1)
with each of its network neighbors:

$W_{i}(a_{i},a_{-i}):=\sum_{j\in\mathcal{N}_{i}}V(a_{i},a_{j})\ .$ (2)

A measure of system _welfare_ defined over $\mathcal{A}$ is

$W(a):=\sum_{i=1}^{N}W_{i}(a_{i},a_{-i}),$ (3)

which is simply the sum of all agent benefits. The _system efficiency_ for
action profile $a\in\mathcal{A}$ is defined as

$\frac{W(a)}{\max_{a^{\prime}\in\mathcal{A}}W(a^{\prime})}.$ (4)

For $\mathcal{A}=\\{x,y\\}^{N}$, the all-$x$ profile $\vec{x}$ maximizes
welfare. This does not necessarily hold for arbitrary action spaces.

###  II-B Log-linear learning algorithm

Log-linear learning is a distributed stochastic algorithm governing how
players’ decisions evolve over time [16, 14, 15]. It may be applied to any
instance of a game with each player having a well-defined local utility
function $U_{i}:\mathcal{A}\rightarrow\mathbb{R}$ over a set of action
profiles $\mathcal{A}$ with an underlying interaction graph $G$. That is,
agent $i$’s local utility is a function of its action $a_{i}$ and actions of
its neighbors in $G$.

Agents update their decisions $a(t)\in\mathcal{A}$ over discrete time steps
$t=0,1,\ldots$. Assume $a(0)$ is arbitrarily determined. For step $t\geq 1$,
one agent $i$ is selected uniformly at random from the population. It updates
its action to $a_{i}(t)=z\in\mathcal{A}_{i}$ with probability

$\frac{\text{exp}(\beta
U_{i}(z,a_{-i}(t-1))}{\sum_{z^{\prime}\in\mathcal{A}_{i}}\text{exp}(\beta
U_{i}(z^{\prime},a_{-i}(t-1))},$ (5)

where $\beta>0$ is the rationality parameter. All other agents repeat their
previous actions: $a_{-i}(t)=a_{-i}(t-1)$. For large values of $\beta$, $i$
selects a best-response to the previous actions of others with high
probability, and for values of $\beta$ near zero, $i$ randomizes among its
actions $\mathcal{A}_{i}$ uniformly at random. This induces an irreducible
Markov chain over the action space $\mathcal{A}$, with a unique stationary
distribution $\pi_{\beta}\in\Delta(\mathcal{A})$. The _stochastically stable
states_ (SSS) $a\in\mathcal{A}$ are the action profiles contained in the
support of the stationary distribution in the high rationality limit: they
satisfy $\pi(a)=\lim_{\beta\rightarrow\infty}\pi_{\beta}(a)>0$. Such a
limiting distribution exists and is unique [23, 15, 24]. We write the set of
stochastically stable states as

$\text{LLL}(\mathcal{A},\\{U_{i}\\}_{i\in\mathcal{N}};G).$ (6)

For graphical coordination games, the log-linear learning algorithm specified
by the action set $\mathcal{A}=\\{x,y\\}^{N}$ and utilities
$\\{W_{i}\\}_{i\in\mathcal{N}}$ selects the welfare-maximizing profile
$\vec{x}$ as the stochastically stable state irrespective of the graph
topology $G$. This can be shown using standard potential game arguments [16]
(we provide these details in Section V). That is,
$\vec{x}=\text{LLL}(\mathcal{A},\\{W_{i}\\}_{i\in\mathcal{N}};G)$ for all
$G\in\mathcal{G}_{N}$, where $\mathcal{G}_{N}$ is the set of all connected
undirected graphs on $N$ nodes.

However, if an adversary is able to manipulate the agents’ local decision-
making rules, this statement may no longer hold true. A system operator may be
able to alter the agents’ local utility functions with the goal of mitigating
the loss of system efficiency in the presence of adversarial influences. In
particular, we consider the class of local utility functions
$\\{U_{i}^{\alpha}\\}_{i\in\mathcal{N}}$ parameterized by $\alpha>0$.
Specifically, $U_{i}^{\alpha}$ takes the same form as the benefit function (2)
where $\alpha_{\text{sys}}$ is replaced with a _perceived gain_ $\alpha$ that
is under the operator’s control. We next introduce models of adversarial
attacks in graphical coordination games. We then evaluate the performance of
this class of distributed algorithms in the face of adversarial attacks.

(a)

(b)

Figure 1: (Left) An example three-node line network under a broad adversarial
attack. The imposter nodes are depicted as the labelled smaller circles and
agents in the network are the bigger circles. The color of each circle
indicates the node’s action - green for $x$, blue for $y$. In this example,
maximum welfare is $\max_{a\in\mathcal{A}}W(a)=4(1+\alpha_{\text{sys}})$,
achieved when all three agents play $x$. The adversary’s target set $S$
attaches an $x$-imposter to node 1 and $y$-imposters to nodes $2$ and $3$. For
operator gains $\alpha\leq\frac{1}{2}$, $a=(a_{1},a_{2},a_{3})=(x,y,y)$ is the
welfare-minimizing SSS, i.e. it satisfies
$a=\underset{a\in\text{LLL}(\mathcal{A},\alpha,S;G)}{\operatorname{arg}\,\operatorname{min}}\;W(a)$.
This gives a risk of
$R_{\text{b}}(\alpha,S;G)=1-\frac{1}{2(1+\alpha_{\text{sys}})}$. For
$\alpha>\frac{1}{2}$, the welfare-minimizing SSS is $(x,x,x)$. This gives
optimal efficiency, i.e. a risk of $0$. (Right) An example of a four node star
network under a focused attack where a subset $F$ of three nodes are targeted
to be fixed (squares). Only the center node is unfixed. In this example, the
maximum welfare is $\max_{a\in\mathcal{A}_{F}}W(a)=4$, achieved when the
center plays $y$. This is because the alternative action (when center plays
$x$) gives the suboptimal welfare $2(1+\alpha_{\text{sys}})<4$ due to
$\alpha_{\text{sys}}<1$. For operator gains $\alpha<1$, the center node plays
$y$ in the SSS. This yields optimal efficiency, i.e. the risk is
$R_{\text{f}}(\alpha,F;G)=0$. For $\alpha\geq 1$, the center node plays $x$,
giving a risk of $R_{\text{f}}(\alpha,F;G)=1-\frac{1+\alpha_{\text{sys}}}{2}$.
The methods to calculate stochastically stable states under both types of
attacks follow standard potential game arguments and are detailed in Section
V.

##  III Models of adversarial influence

In this section, we outline two models of adversarial attacks in graphical
coordination games - _broad_ and _focused_ attacks. The system operator
specifies the local utility functions $\\{U_{i}^{\alpha}\\}$ that govern the
log-linear learning algorithm by selecting the perceived payoff gain
$\alpha>0$. Our goal is to assess the performance of this range of algorithms
on two corresponding worst-case risk metrics, which we define and
characterize. We then identify fundamental tradeoff relations between these
two risk metrics.

###  III-A Broad attacks and worst-case risk metric

We consider a scenario where the system is subject to broad adversarial
attacks. For each agent in the network, the adversary attaches a single
imposter node that acts as a neighbor that always plays $x$ or $y$. These
nodes are not members of the network but affect the decision making of agents
that are. Let $S_{x}\subseteq\mathcal{N}$ ($S_{y}$) be the set of agents
targeted with an imposter $x$ ($y$) node. We call the _target set_
$S=(S_{x},S_{y})$. Any target set satisfies $S_{x}\cap S_{y}=\varnothing$ and
$S_{x}\cup S_{y}=\mathcal{N}$. We call $\mathcal{T}(G)$ the set of all
possible target sets $S$ on the graph $G$. Given $\alpha>0$, the agents’
_perceived_ utilities are

$\tilde{U}_{i}^{\alpha}(a_{i},a_{-i}):=\begin{cases}U_{i}^{\alpha}(a_{i},a_{-i})+\mathds{1}(a_{i}=y)\quad&i\in
S_{y}\\\ U_{i}^{\alpha}(a_{i},a_{-i})+(1+\alpha)\mathds{1}(a_{i}=x)&i\in
S_{x}\end{cases}.$ (7)

(a)

(b)

Figure 2: (a) The worst-case risk from broad attacks
$R_{\text{b}}^{*}(\alpha)$ (11) is a piecewise constant function defined over
countably infinite half-open intervals. The graphs and their corresponding
target set which attain each level of worst-case broad risk are illustrated
for $\alpha<1$. Here, the $x,y$ labels indicate the type of imposter influence
on the agents (circles) in the network, and the color of the circles depict
the action played in the welfare-minimizing SSS (green=$x$, blue=$y$). If
$\alpha\in I_{k}$, $k=1,2,\ldots$(recall (12)), the worst-case risk is
achieved on a star graph of $k+2$ nodes where all nodes but one are targeted
with a $y$ imposter. The one leaf node has an $x$ imposter attached, giving a
single miscoordinating link in the network. (b) The worst-case risk from
focused attacks $R_{\text{f}}^{*}(\alpha)$ (16). The graphs and their
corresponding fixed sets which attain the worst-case focused risks are
illustrated for $\alpha=\frac{1}{2},1$, and $2$. The nodes’ color represents
the worst-case SSS at $\alpha$ (blue $=y$, green $=x$). The targeted fixed
agents are represented as squares and the unfixed agents as circles. Here
$\frac{1}{2}<\alpha_{\text{sys}}<1$. The proofs establishing all worst-case
graphs are detailed in Section V.

In the notation of (6), the set of stochastically stable states is written
$\text{LLL}(\mathcal{A},\\{\tilde{U}_{i}^{\alpha}\\}_{i\in\mathcal{N}};G)$.
However for more specificity, we will refer to it in this context as
$\text{LLL}(\mathcal{A},\alpha,S;G)$. The induced network _efficiency_ is
defined as

$\displaystyle J_{\text{b}}(\alpha,S;G)$
$\displaystyle:=\frac{\min_{a\in\text{LLL}(\mathcal{A},\alpha,S;G)}W(a)}{\max_{a^{\prime}\in\mathcal{A}}W(a^{\prime})}$
(8)
$\displaystyle=\frac{\min_{a\in\text{LLL}(\mathcal{A},\alpha,S;G)}W(a)}{(1+\alpha_{\text{sys}})|\mathcal{E}|},$

which is the ratio of the welfare induced by the welfare-minimizing SSS to the
optimal welfare. The second equality above is due to the fact that optimal
welfare is attained at $\vec{x}$ (all play $x$). We re-iterate that the
imposter nodes serve only to modify the stochastically stable states, and do
not contribute to the system welfare $W(a)$ (3). The _risk_ from broad attacks
faced by the system operator in choosing gain $\alpha$ is defined as

$R_{\text{b}}(\alpha,S;G):=1-J_{\text{b}}(\alpha,S;G).$ (9)

Risk measures the distance from optimal efficiency under operating gain
$\alpha$. Fig. 1(a) illustrates an example of a three-node network subject to
a broad adversarial attack. The extent to which systems are susceptible to
broad attacks is captured by the following definition of worst-case risk.

######  Definition 1.

The _worst-case risk_ to broad attacks is given by

$R_{\text{\emph{b}}}^{*}(\alpha):=\max_{N\geq
3}\max_{G\in\mathcal{G}_{N}}\max_{S\in\mathcal{T}(G)}R_{\text{\emph{b}}}(\alpha,S;G),\\\
$ (10)

The quantity $R_{\text{b}}^{*}(\alpha)$ is the cost metric that the system
operator wishes to reduce given uncertainty of the network structure and
target set.

######  Theorem 1.

Let $\alpha>0$. The worst-case broad risk is

$R_{\text{\emph{b}}}^{*}(\alpha)=\begin{cases}1-\left(\frac{k}{k+1}\right)\left(\frac{1}{1+\alpha_{\text{sys}}}\right)\
&\text{if }\alpha\in I_{k},\ \text{for }k=1,2,\ldots\\\
1-\frac{1}{1+\alpha_{\text{sys}}}&\text{if
}\alpha\in\left[1,\frac{3}{2}\right]\\\ 0&\text{if
}\alpha>\frac{3}{2}\end{cases}$ (11)

where

$I_{k}:=\left(\frac{k-1}{k},\frac{k}{k+1}\right].$ (12)

It is a piecewise constant function on half-open intervals that is
monotonically decreasing in $\alpha$. An illustration is given in Figure 2(a),
along with the graphs and target sets that achieve the worst-case risks. For
sufficiently high gains $\alpha>3/2$, the system is safeguarded from any broad
adversarial attack, i.e. the worst-case risk is zero. By inflating the value
of the $x$-convention, the adversary is unable to induce any mis-coordinating
links or agents to play $y$. The technical results needed for the proof are
given in Section V.

###  III-B Focused attacks and worst-case risk metric

An adversary is able to choose a strict subset of agents and force them to
commit to prescribed choices. This causes them to act as _fixed agents_ , or
agents that do not update their choices over time. One could consider this as
allowing the adversary an unlimited number of imposter nodes (instead of one)
at its dispatch to attach to each agent in the subset, thereby solidifying
their choices. This focused influence on a single agent is stronger than the
influence a broad attack has on a single agent in the sense that the latter
type does not require the agent to commit to a choice - it merely incentivizes
the agent towards one particular choice.

Let $F_{x}\subset\mathcal{N}$ $(F_{y})$ be the set of fixed $x$ ($y$) agents.
We call the _fixed set_ $F=(F_{x},F_{y})$, which satisfies $F_{x}\cap
F_{y}=\varnothing$ and $F_{x}\cup F_{y}\subset\mathcal{N}$. We call
$\mathcal{F}(G)$ the set of all feasible fixed sets on a graph
$G\in\mathcal{G}_{N}$. A fixed set $F\in\mathcal{F}(G)$ restricts the action
space to $\mathcal{A}(F)$, where $\mathcal{A}_{i}(F)=\\{x\\}$ ($\\{y\\}$)
$\forall i\in F_{x}$ ($F_{y}$) and $\mathcal{A}_{i}(F)=\\{x,y\\}$ $\forall
i\notin F$. We assume the adversary selects at least one fixed agent. The
strict subset assumption avoids pathological cases (e.g. alternating $x$ and
$y$ fixed nodes for an entire line network yields an efficiency of zero).

The set of stochastically stable states given a fixed set $F$ is written as
$\text{LLL}(\mathcal{A}(F),\\{U_{i}^{\alpha}\\}_{i\in\mathcal{N}};G)$. However
for brevity, we will refer to it as $\text{LLL}(\mathcal{A}(F),\alpha;G)$. The
induced efficiency is

$J_{\text{f}}(\alpha,F;G):=\frac{\min_{a\in\text{LLL}(\mathcal{A}(F),\alpha;G)}W(a)}{\max_{a\in\mathcal{A}(F)}W(a)},$
(13)

which is the ratio of the welfare induced by the worst-case stable state to
the optimal welfare given the fixed set $F$. The risk faced by the system
operator in choosing $\alpha$ is defined as

$R_{\text{f}}(\alpha,F;G):=1-J_{\text{f}}(\alpha,F;G)\ .$ (14)

Again, risk measures the distance from optimal efficiency when choosing
$\alpha$. The fixed nodes here differ from the imposter nodes in that they
contribute to the true measured welfare (3) in addition to modifying the SSS
by restricting the action set and influencing the decisions of their non-fixed
neighbors. Figure 1(b) provides an illustrative example of a network with
three fixed agents and one unfixed agent. The extent to which the system is
susceptible to focused attacks is defined by the following worst-case risk
metric.

######  Definition 2.

The _worst-case risk from focused attacks_ is given by

$R_{\text{\emph{f}}}^{*}(\alpha):=\max_{N\geq
3}\max_{G\in\mathcal{G}_{N}}\max_{F\in\mathcal{F}(G)}R_{\text{\emph{f}}}(\alpha,F;G)\
.$ (15)

The quantity $R_{\text{f}}^{*}(\alpha)$ is the cost metric that a system
operator wishes to reduce given uncertainty on the graph structure and
composition of fixed agents in the network.

######  Theorem 2.

The worst-case risk from focused attacks is

$R_{\text{\emph{f}}}^{*}(\alpha)=\begin{cases}1-\frac{1+\alpha}{1+\alpha_{\text{sys}}},\
&\text{if }\alpha<\alpha_{\text{sys}}\\\ 0,&\text{if
}\alpha=\alpha_{\text{sys}}\\\
1-\frac{1+\alpha_{\text{sys}}}{1+\alpha},&\text{if
}\alpha>\alpha_{\text{sys}}\end{cases}.$ (16)

The technical results needed for the proof are given in Section V. An
illustration of this quantity as well as the graphs that induce worst-case
risk are portrayed in Figure 2(b). We observe the choice
$\alpha=\alpha_{\text{sys}}$ recovers optimal efficiency for any
$G\in\mathcal{G}_{N}$ and $F\in\mathcal{F}(G)$. In other words, by operating
at the system gain $\alpha_{\text{sys}}$, the system operator safeguards
efficiency from any focused attack. Furthermore, $R_{\text{f}}^{*}(\alpha)$
monotonically increases for $\alpha>\alpha_{\text{sys}}$, approaching 1 in the
limit $\alpha\rightarrow\infty$. Intuitively, the risk in this regime comes
from inflating the benefit of the $x$ convention, which can be harmful to
system efficiency when there are predominantly fixed $y$ nodes in the network.
For $\alpha<\alpha_{\text{sys}}$, $R_{\text{f}}^{*}(\alpha)$ monotonically
decreases. The risk here stems from de-valuing the $x$ convention, which hurts
efficiency when coordinating with fixed $x$ nodes is more valuable than
coordinating with fixed $y$ nodes.

###  III-C Fundamental tradeoffs between risk and security

We describe the operator’s tradeoffs between the two worst-case risk metrics.
That is, given a level of security $\gamma\in[0,1]$ is ensured on one worst-
case risk, what is the minimum achievable risk level of the other? These
relations are direct consequences of Theorems 1 and 2.

######  Remark 1.

Before presenting the tradeoff relations, we first observe that since
$R_{\text{\emph{f}}}^{*}(\alpha)$ is decreasing on
$\alpha<\alpha_{\text{sys}}$ and $R_{\text{\emph{b}}}^{*}(\alpha)$ is
decreasing in $\alpha$, the operator should not select any gain
$\alpha<\alpha_{\text{sys}}$, as it worsens both risk levels. Hence for the
rest of this paper, we only consider gains greater than $\alpha_{\text{sys}}$.

######  Corollary 1.

Fix $\gamma_{\text{\emph{f}}}\in[0,1)$. Suppose
$R_{\text{\emph{f}}}^{*}(\alpha)\leq\gamma_{\text{\emph{f}}}$ for some
$\alpha$. Then

$R_{\text{\emph{b}}}^{*}(\alpha)\geq
R_{\text{\emph{b}}}^{*}\left(\frac{1+\alpha_{\text{sys}}}{1-\gamma_{\text{\emph{f}}}}-1\right).$
(17)

###### Proof.

From (16), $R_{\text{f}}^{*}(\alpha)\leq\gamma_{\text{f}}$ implies
$\alpha\leq\frac{1+\alpha_{\text{sys}}}{1-\gamma_{\text{f}}}-1$. Since
$R_{\text{b}}^{*}(\alpha)$ is a decreasing function in $\alpha$, we obtain the
result. ∎

In words, as the security from worst-case focused attacks improves
($\gamma_{\text{f}}$ lowered), the risk from worst-case broad attacks
increases. A tradeoff relation also holds in the opposite direction.

######  Corollary 2.

Fix $\gamma_{\text{\emph{b}}}\in\left[0,1\right]$. Suppose
$R_{\text{\emph{b}}}^{*}(\alpha)\leq\gamma_{\text{\emph{b}}}$ for some
$\alpha$. Suppose $\alpha_{\text{sys}}\in I_{k_{\text{sys}}}$ for some
$k_{\text{sys}}\in\\{1,2,\ldots\\}$. Then

$R_{\text{\emph{f}}}^{*}(\alpha)\begin{cases}\geq 0&\text{if
}\gamma_{\text{\emph{b}}}\in\left[1-\frac{k_{\text{sys}}}{k_{\text{sys}}+1}\frac{1}{1+\alpha_{\text{sys}}},1\right]\\\
>R_{\text{\emph{f}}}^{*}\left(\frac{k}{k+1}\right)&\text{if
}\gamma_{\text{\emph{b}}}\in\left[1-\frac{k}{k+1}\frac{1}{1+\alpha_{\text{sys}}},1-\frac{k-1}{k}\frac{1}{1+\alpha_{\text{sys}}}\right)\\\
&\quad\text{for }k=k_{\text{sys}},k_{\text{sys}}+1,\ldots\\\ \geq
R_{\text{\emph{f}}}^{*}(1)&\text{if
}\gamma_{\text{\emph{b}}}=1-\frac{1}{1+\alpha_{\text{sys}}}\\\
>R_{\text{\emph{f}}}^{*}\left(\frac{3}{2}\right)&\text{if
}\gamma_{\text{\emph{b}}}\in\left[0,1-\frac{1}{1+\alpha_{\text{sys}}}\right)\end{cases}$
(18)

If $\alpha_{\text{sys}}\in[1,3/2]$,

$R_{\text{\emph{f}}}^{*}(\alpha)\begin{cases}\geq 0&\text{if
}\gamma_{\text{\emph{b}}}\in\left[1-\frac{1}{1+\alpha_{\text{sys}}},1\right]\\\
>R_{\text{\emph{f}}}^{*}\left(\frac{3}{2}\right)&\text{if
}\gamma_{\text{\emph{b}}}\in\left[0,1-\frac{1}{1+\alpha_{\text{sys}}}\right)\end{cases}$
(19)

If $\alpha_{\text{sys}}>\frac{3}{2}$, then
$R_{\text{\emph{f}}}^{*}(\alpha)\geq 0$ for any $\gamma_{\text{\emph{b}}}$.

###### Proof.

All bounds are computed by finding $\inf_{\alpha}R_{\text{f}}^{*}(\alpha)$
s.t. $R_{\text{b}}^{*}(\alpha)\leq\gamma_{\text{b}}$. The relations $\geq$ and
$>$ follow from the fact that $R_{\text{f}}^{*}(\alpha)$ is increasing in
$\alpha>\alpha_{\text{sys}}$, and depending on whether $R_{\text{f}}^{*}$ can
attain the resulting value. ∎

Here, as the security from worst-case broad attacks improves
($\gamma_{\text{b}}$ lowered), the risk from worst-case focused attacks
increases. Each of the broad risk levels can be attained for a range of
focused risks. An illustration of the attainable worst-case risk levels is
given in Fig. 3 (blue).

##  IV Randomized operator strategies

In this section, we consider the scenario where the operator randomizes over
multiple gains. We present a definition and a characterization of worst-case
expected risks. We then identify the risk-security tradeoffs available in the
randomized gain setting. We observe they significantly improve upon the
deterministic gain setting (Fig. 3). We then identify ways to further improve
these tradeoffs through different randomizations.

###  IV-A Worst-case expected risks

Suppose the operator selects a gain from the $M$ distinct values
$\bm{\alpha}=\\{\alpha_{k}\\}_{k=1}^{M}$ satisfying
$\alpha_{1}<\alpha_{2}<\cdots<\alpha_{M}$ with the probability distribution
$\bm{p}=[p_{1},\ldots,p_{M}]^{\top}\in\Delta_{M}$. Here we denote
$\Delta_{M}=\\{\bm{p}\in\mathbb{R}^{M}_{+}:\sum_{j=1}^{M}p_{j}=1\\}$ as the
set of all $M$-dimensional probability vectors. In other words, the operator
employs the payoff gain $\alpha_{j}$ with probability $p_{j}$.

We consider the following natural definitions of expected risks. Given a graph
$G\in\mathcal{G}_{N}$ and target set $S\in\mathcal{T}(G)$, let
$\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{b}}|S,G]:=\sum_{j=1}^{M}p_{j}R_{\text{b}}(\alpha_{j},S;G)$
be the expected adversarial risk of the operator’s strategy
$\bm{\alpha},\bm{p}$. The worst-case expected risk from broad attacks is
defined as

$\mathbb{E}_{\bm{\alpha},\bm{p}}^{*}[R_{\text{b}}]:=\max_{N\geq
3}\max_{G\in\mathcal{G}_{N}}\max_{S\in\mathcal{T}(G)}\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{b}}|S,G].$
(20)

Similarly, given a fixed set $F\in\mathcal{F}(G)$, let
$\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{f}}|F,G]:=\sum_{j=1}^{M}p_{i}R_{\text{f}}(\alpha_{j},F;G)$
be the expected risk from focused attacks. The worst-case expected risk from
focused attacks is defined as

$\mathbb{E}_{\bm{\alpha},\bm{p}}^{*}[R_{\text{f}}]:=\max_{N\geq
3}\max_{G\in\mathcal{G}_{N}}\max_{F\in\mathcal{F}(G)}\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{f}}|F,G].$
(21)

######  Theorem 3.

Suppose the operator randomizes with gains
$\bm{\alpha}=\\{\alpha_{k}\\}_{k=1}^{M}$ according to $\bm{p}\in\Delta_{M}$.
Then the worst-case expected broad risk is

$\mathbb{E}_{\bm{\alpha},\bm{p}}^{*}[R_{\text{\emph{b}}}]=\\!\max_{k=1,\ldots,M}\left\\{\\!\\!\left(\sum_{j=1}^{k}p_{j}\right)R_{\text{\emph{b}}}^{*}(\alpha_{k})\right\\}.$
(22)

The worst-case expected focused risk is

$\mathbb{E}_{\bm{\alpha},\bm{p}}^{*}[R_{\text{\emph{f}}}]=\\!\max_{k=1,\ldots,M}\left\\{\\!\\!\left(\sum_{j=k}^{M}p_{j}\\!\right)R_{\text{\emph{f}}}^{*}(\alpha_{k})\right\\}.$
(23)

The proofs are given in Section VI. The characterization of worst-case
expected risk is a discounted weighting of a deterministic worst-case risk
level. This suggests that the risk levels achievable by randomization can
improve upon the risks induced from a deterministic gain.

###  IV-B Risk tradeoffs under randomized operator strategies

Given a level of security $\gamma\in[0,1]$ is ensured on one expected worst-
case metric, what is the the minimum achievable risk level on the other? We
find this can be calculated through a linear program. We formalize these
tradeoffs in the following two statements, which are analogous to Corollaries
1 and 2.

######  Corollary 3.

Fix $\gamma_{\text{\emph{f}}}\in[R_{\text{\emph{f}}}^{*}(\alpha_{1}),1]$ and a
set of gains $\bm{\alpha}=\\{\alpha_{j}\\}_{j=1}^{M}$. Suppose
$\mathbb{E}_{\bm{\alpha},\bm{p}}^{*}[R_{\text{\emph{f}}}]\leq\gamma_{\text{\emph{f}}}$
for some $\bm{p}\in\Delta_{M}$. Then

$\mathbb{E}_{\bm{\alpha},\bm{p}}^{*}[R_{\text{\emph{b}}}]\geq
v_{\text{\emph{b}}}(\gamma_{\text{\emph{f}}},\bm{\alpha}),$ (24)

where $v_{\text{b}}(\gamma,\bm{\alpha})$ is the value of the following linear
program.

$\displaystyle v_{\text{b}}(\gamma_{\text{\emph{f}}},\bm{\alpha})$
$\displaystyle=\min_{\bm{p}^{\prime},v}v$ (25) $\displaystyle\text{\emph{s.t.}
}\sum_{i=1}^{M}p^{\prime}_{i}=1,\ p_{i}\geq 0\ \forall i=1,\ldots,M$
$\displaystyle v\in[0,1]$ $\displaystyle
A_{\text{\emph{LP}}}\begin{bmatrix}\bm{p}^{\prime}\\\
v\end{bmatrix}\preceq\begin{bmatrix}0_{M}\\\
\gamma_{\text{\emph{f}}}\mathds{1}_{M}\end{bmatrix}$

where $\preceq$ denotes elementwise $\leq$, $0_{M}$ and $\mathds{1}_{M}$ are
column $M$-vectors of zeros and ones respectively, and $A_{\text{\emph{LP}}}$
is the $2M\times(M+1)$ matrix

${\small
A_{\text{\emph{LP}}}=\left[\begin{array}[]{cccc;{2pt/2pt}c}R_{\text{\emph{b}}}^{*}(\alpha_{1})&0&\cdots&0&-1\\\
R_{\text{\emph{b}}}^{*}(\alpha_{2})&R_{\text{\emph{b}}}^{*}(\alpha_{2})&\cdots&\vdots&\vdots\\\
\vdots&&\ddots&0&\\\
R_{\text{\emph{b}}}^{*}(\alpha_{M})&\cdots&\cdots&R_{\text{\emph{b}}}^{*}(\alpha_{M})&-1\\\
\hdashline[2pt/2pt]R_{\text{\emph{f}}}^{*}(\alpha_{1})&\cdots&\cdots&R_{\text{\emph{f}}}^{*}(\alpha_{1})&0\\\
0&R_{\text{\emph{f}}}^{*}(\alpha_{2})&\cdots&R_{\text{\emph{f}}}^{*}(\alpha_{2})&\vdots\\\
\vdots&&\ddots&\vdots&\\\
0&\cdots&0&R_{\text{\emph{f}}}^{*}(\alpha_{M})&0\end{array}\right]}.$ (26)

Moreover, $v_{\text{b}}(\gamma_{\text{\emph{f}}},\bm{\alpha})$ is decreasing
in $\gamma_{\text{\emph{f}}}$.

###### Proof.

We need to show equivalence between the linear program (25) and the
optimization problem

$\min_{\bm{p}^{\prime}\in\Delta_{M}}\mathbb{E}^{*}_{\bm{\alpha},\bm{p}^{\prime}}[R_{\text{b}}]\
\text{subject to}\
\mathbb{E}^{*}_{\bm{\alpha},\bm{p}^{\prime}}[R_{\text{f}}]\leq\gamma_{\text{f}}.$
(27)

Let $A_{\text{b}}(\bm{\alpha})\in\mathbb{R}^{M\times M}$ be the matrix defined
by the upper left block of (26) and $A_{\text{f}}(\bm{\alpha})$ by the bottom
left block. From Theorem 3, we can express
$\mathbb{E}_{\bm{\alpha},\bm{p}^{\prime}}^{*}[R_{\text{b}}]$ as the maximum
element of the $M$-vector $A_{\text{b}}(\bm{\alpha})\bm{p}^{\prime}$, and
similarly $\mathbb{E}_{\bm{\alpha},\bm{p}^{\prime}}^{*}[R_{\text{f}}]$ as the
maximum element of $A_{\text{f}}(\bm{\alpha})\bm{p}^{\prime}$. Hence,
$\mathbb{E}^{*}_{\bm{\alpha},\bm{p}^{\prime}}[R_{\text{f}}]\leq\gamma_{\text{f}}$
is the linear constraint
$[A_{\text{f}}(\bm{\alpha})\bm{p}^{\prime}]_{i}\leq\gamma$ for all
$i=1,\ldots,M$. The objective
$\min_{\bm{p}^{\prime}\in\Delta_{M}}\mathbb{E}^{*}_{\bm{\alpha},\bm{p}^{\prime}}[R_{\text{b}}]$
itself can be cast as a linear objective with linear constraints, i.e.
$\min_{\bm{p}^{\prime}\in\Delta_{M},v\in[0,1]}v\ \text{s.t.}\
[A_{\text{b}}(\bm{\alpha})\bm{p}^{\prime}]_{i}\leq v$. Combining these two, we
obtain (25). The claim $v_{\text{b}}(\gamma,\bm{\alpha})$ is decreasing in
$\gamma$ follows as a consequence of the linear program (25). ∎

We note that a worst-case expected focused risk
$\mathbb{E}^{*}_{\bm{\alpha},\bm{p}}[R_{\text{f}}]<R_{\text{f}}^{*}(\alpha_{1})$
is not attainable because $\alpha_{1}$ is the smallest gain it mixes with.
Hence, the linear program (25) is infeasible for
$\gamma_{\text{f}}<R_{\text{f}}^{*}(\alpha_{1})$. The following tradeoff
relation holds in the opposite direction.

Figure 3: Security-risk tradeoffs are depicted by the achievable worst-case
risk levels from deterministic gains (blue) and randomized gains (red, green,
black). The Pareto frontiers for three different randomized strategies
$\bm{\alpha}^{1},\bm{\alpha}^{2}\in\mathbb{R}_{+}^{5}$, and
$\bm{\alpha}^{3}\in\mathbb{R}_{+}^{300}$, are shown in increasing order of
improvement. The strategies $\bm{\alpha}^{1}$ and $\bm{\alpha}^{2}$ randomize
over the highest three broad risk levels in addition to the lowest two. The
strategy $\bm{\alpha}^{3}$ randomizes over the highest 298 broad risk levels
and the lowest two. We chose the values as follows. For $k=1,2$, we set
$\alpha_{1}^{k}=\alpha_{\text{sys}}$,
$\alpha_{j}^{k}=(1-\epsilon_{k})\frac{j-1}{j}+\epsilon_{k}\frac{j}{j+1}\in
I_{j}$ for $j=2,3$, $\alpha_{4}^{k}=1+\epsilon_{k}$, and
$\alpha_{5}^{k}=\frac{3}{2}+\epsilon_{k}$. We have set $\epsilon_{1}=0.5$ and
$\epsilon_{2}=.01$. Hence, Par($\bm{\alpha}^{2}$) improves upon
Par($\bm{\alpha}^{1}$) via Claim 1. For $k=3$, we set
$\alpha_{1}^{3}=\alpha_{\text{sys}}$,
$\alpha_{j}^{3}=(1-\epsilon_{3})\frac{j-1}{j}+\epsilon_{3}\frac{j}{j+1}\in
I_{j}$, $j=2,3,\ldots,298$, $\alpha_{299}^{3}=1+\epsilon_{3}$, and
$\alpha_{5}^{3}=\frac{3}{2}+\epsilon_{3}$. Claim 2 ensures
Par($\bm{\alpha}^{3}$) improves upon Par($\bm{\alpha}^{2}$). We chose
$\epsilon_{3}=.01$ and $\alpha_{\text{sys}}=1/4$.

######  Corollary 4.

Fix $\gamma_{\text{\emph{b}}}\in[R_{\text{\emph{b}}}^{*}(\alpha_{M}),1]$ and a
set of gains $\bm{\alpha}=\\{\alpha_{j}\\}_{j=1}^{M}$. Suppose
$\mathbb{E}^{*}_{\bm{\alpha},\bm{p}}[R_{\text{\emph{b}}}]\leq\gamma_{\text{\emph{b}}}$
for some $\bm{p}\in\Delta_{M}$. Then

$\mathbb{E}^{*}_{\bm{\alpha},\bm{p}}[R_{\text{\emph{f}}}]\geq
v_{\text{\emph{f}}}(\gamma_{\text{\emph{b}}},\bm{\alpha}),$ (28)

where $v_{\text{\emph{f}}}(\gamma_{\text{\emph{b}}},\bm{\alpha})$ is the value
of the following linear program.

$\displaystyle v_{\text{\emph{f}}}(\gamma_{\text{\emph{b}}},\bm{\alpha})$
$\displaystyle=\min_{\bm{p},v}v$ (29) $\displaystyle\text{\emph{s.t.}
}\sum_{i=1}^{M}p_{i}=1,\ p_{i}\geq 0\ \forall i=1,\ldots,M$ $\displaystyle
v\in[0,1]$
$\displaystyle\left[\begin{array}[]{c;{2pt/2pt}c}A_{\text{\emph{f}}}(\bm{\alpha})&-\mathds{1}_M\\\
\hdashline[2pt/2pt]A_{\text{\emph{b}}}(\bm{\alpha})&0_M\end{array}\right]\begin{bmatrix}\bm{p}\\\
v\end{bmatrix}\preceq\begin{bmatrix}0_{M}\\\
\gamma_{\text{\emph{b}}}\mathds{1}_{M}\end{bmatrix},$

where $A_{\text{\emph{f}}}(\bm{\alpha})$ and
$A_{\text{\emph{b}}}(\bm{\alpha})$ are defined as the bottom and top left
blocks of (26), respectively. Furthermore,
$v_{\text{\emph{f}}}(\gamma_{\text{\emph{b}}},\bm{\alpha})$ is decreasing in
$\gamma_{\text{\emph{b}}}$.

We omit the proof as it is similar to that of Corollary 3. Note a worst-case
expected broad risk
$\mathbb{E}^{*}_{\bm{\alpha},\bm{p}}[R_{\text{b}}]<R_{\text{b}}^{*}(\alpha_{M})$
is not attainable since $\alpha_{M}$ is the highest gain it mixes with - (29)
is infeasible for $\gamma_{\text{b}}<R_{\text{b}}^{*}(\alpha_{M})$. Fig. 3
plots the best achievable risk levels of three randomized operator strategies
(red, green, and black).

###  IV-C Improvement of risk tradeoffs

The tradeoff relations describe the best achievable level on one risk metric
given the other is subject to a security constraint when the gains
$\bm{\alpha}$ are fixed. One way to improve the achievable risks is to
decrease the available gains.

######  Claim 1.

Let $\bm{\alpha},\bm{\alpha}^{\prime}\in\mathbb{R}^{M}$. Suppose
$\alpha_{j}\in I_{k_{j}}$ (recall (12)), $j=1,\ldots,M$ for some non-
decreasing subsequence $k_{j}\geq 1$. Let $\bm{\alpha}^{\prime}$ satisfy
$\alpha_{j}^{\prime}\in I_{k_{j}}$ with $\alpha_{j}^{\prime}<\alpha_{j}$. Then
for all $\gamma_{\text{\emph{b}}}\in[R_{\text{\emph{b}}}^{*}(\alpha_{M}),1]$,
$v_{\text{\emph{f}}}(\gamma_{\text{\emph{b}}},\bm{\alpha}^{\prime})\leq
v_{\text{\emph{f}}}(\gamma_{\text{\emph{b}}},\bm{\alpha})$. Similarly, for all
$\gamma_{\text{\emph{f}}}\in[R_{\text{\emph{f}}}^{*}(\alpha_{1}),1]$,
$v_{\text{\emph{b}}}(\gamma_{\text{\emph{f}}},\bm{\alpha}^{\prime})\leq
v_{\text{\emph{b}}}(\gamma_{\text{\emph{f}}},\bm{\alpha})$.

Randomizing over additional gains can also improve the achievable risks.

######  Claim 2.

Suppose $\bm{\alpha}\in\mathbb{R}^{M}$ and
$\bm{\alpha}^{\prime}\in\mathbb{R}^{M^{\prime}}$ with $M<M^{\prime}$, and
assume $\bm{\alpha}^{\prime}$ contains the elements of $\bm{\alpha}$. Then the
assertion of Claim 1 holds.

The proofs of the above two Claims follow directly from the formulation of the
LPs (25), (29), and hence we omit them.

Fig. 3 depicts the best achievable risk levels of three randomized operator
strategies of increasing improvement due to Claims 1 and 2 (red, green, and
black curves). In particular, these plots constitute the _Pareto frontier_ of
all attainable expected risks among distributions $\bm{p}$ given a fixed set
of gains. That is, for any $\bm{\alpha}$, we say a risk level
$\begin{bmatrix}\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{f}}]\\\
\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{b}}]\end{bmatrix}\in\mathbb{R}^{2}$
belongs to the frontier Par($\bm{\alpha}$) if there does not exist a
$\bm{p}^{\prime}\neq\bm{p}$ such that
$\begin{bmatrix}\mathbb{E}_{\bm{\alpha},\bm{p}^{\prime}}[R_{\text{f}}]\\\
\mathbb{E}_{\bm{\alpha},\bm{p}^{\prime}}[R_{\text{b}}]\end{bmatrix}\preceq\begin{bmatrix}\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{f}}]\\\
\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{b}}]\end{bmatrix}$. Within
Par($\bm{\alpha}$), the operator can only improve upon one worst-case risk
metric by sacrificing performance on the other.

From Corollary 4, the frontier given gains $\bm{\alpha}$ is the set of points

$\displaystyle\text{Par}(\bm{\alpha})=\left\\{\begin{bmatrix}v_{\text{f}}(\gamma_{\text{b}},\bm{\alpha})\\\
\gamma_{\text{b}}\end{bmatrix}\in\mathbb{R}^{2}:\gamma_{\text{b}}\in[R_{\text{b}}^{*}(\alpha_{M}),R_{\text{b}}^{*}(\alpha_{1})]\right\\}.$
(30)

The parameter $\gamma_{\text{b}}$ is upper bounded here by
$R_{\text{b}}^{*}(\alpha_{1})$ since any risk level with
$\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{b}}]>R_{\text{b}}^{*}(\alpha_{1})$
is unattainable under $\bm{\alpha}$. Hence, the values
$v_{\text{f}}(\gamma_{\text{b}},\bm{\alpha})$ and
$v_{\text{f}}(R_{\text{b}}^{*}(\alpha_{1}),\bm{\alpha})$ are equivalent for
$\gamma_{\text{b}}>R_{\text{b}}^{*}(\alpha_{1})$. The frontiers in Fig. 3 are
generated by numerically solving the linear program (29) for a finite grid of
points
$\gamma_{\text{b}}\in[R_{\text{b}}^{*}(\alpha_{M}),R_{\text{b}}^{*}(\alpha_{1})]$.

As we have seen, the transition from deterministic to randomized gains ensures
a reduction of risk levels. Randomizing over only a few different gains
substantially improves upon the attainable deterministic worst-case risks.
However, a detailed quantification of such improvements remains a challenge
due to the high dimensionality of the model. In particular, we have yet
identified a “limit” frontier that could be obtained by repeated modifications
to the gain vector detailed by Claims 1 and 2.

##  V Proof of Theorems 1 and 2: Deterministic worst-case risks

In this section, we develop the technical results that characterize the worst-
case risk metrics $R_{\text{b}}^{*}(\alpha)$ and $R_{\text{f}}^{*}(\alpha)$
(Theorems 1 and 2). Before presenting the proofs, we first present some
preliminaries on potential games [25], which are essential to calculating
stochastically stable states. We then define relevant notations for the
forthcoming analysis.

###  V-A Potential games

Graphical coordination games fall under the class of potential games - games
where individual utilities $\\{U_{i}\\}_{i\in\mathcal{N}}$ are aligned with a
global objective, or potential function. A game is a potential game if there
exists a potential function $\phi:\mathcal{A}\rightarrow\mathbb{R}$ which
satisfies

$\phi(a_{i},a_{-i})-\phi(a_{i}^{\prime},a_{-i})=U_{i}(a_{i},a_{-i})-U_{i}(a_{i}^{\prime},a_{-i})$
(31)

for all $i\in\mathcal{N}$, $a\in\mathcal{A}$, and $a_{i}^{\prime}\neq a_{i}$
[25]. In potential games, the set of stochastically stable states (6) are
precisely the action profiles that maximize the potential function [15, 16].
Specifically,
$\text{LLL}(\mathcal{A},\\{U_{i}\\}_{i\in\mathcal{N}};G)=\underset{a\in\mathcal{A}}{\operatorname{arg}\,\operatorname{max}}\;\phi(a)$.
Our analysis relies on characterizing a potential function for the graphical
coordination game in the presence of adversarial influences. This allows us to
compute stochastically stable states in a straightforward manner.

###  V-B Relevant notations for analysis

Any action profile $a$ on a graph
$G=(\mathcal{N},\mathcal{E})\in\mathcal{G}_{N}$ decomposes $\mathcal{N}$ into
$x$ and $y$-partitions. A node that belongs to a $y$-partition ($x$-partition)
has $a_{i}=y$ ($x$). The partitions are enumerated
$\\{\mathcal{P}_{y}^{1},\ldots,\mathcal{P}_{y}^{k_{y}}\\}$ and
$\\{\mathcal{P}_{x}^{1},\ldots,\mathcal{P}_{x}^{k_{x}}\\}$, are mutually
disjoint, and cover the graph. Each partition is a connected subgraph of $G$.
It is possible that $k_{x}=0$ with $k_{y}=1$ (when $a=\vec{y}$), $k_{x}=1$
with $k_{y}=0$ (when $a=\vec{x}$), or $k_{y},k_{x}\geq 1$.

For any subset of nodes $A,B\subseteq\mathcal{N}$, let us denote

$e(A,B):=\\{(i,j)\in\mathcal{E}:i\in A,j\in B\\}$ (32)

as the set of edges between $A$ and $B$. We write $A^{c}$ as the complement of
$A$. We extensively use the notation

$W^{\alpha}(E,a):=\sum_{(i,j)\in E}V^{\alpha}(a_{i},a_{j})$ (33)

as the welfare due to edge set $E\subseteq\mathcal{E}$ in action profile $a$,
where $V^{\alpha}$ is of the form (1) with $\alpha_{\text{sys}}$ replaced by
$\alpha$. For compactness, we will denote $W(E,a)$ as
$W^{\alpha_{\text{sys}}}(E,a)$ for the local system welfare generated by the
edges $E$. Our analysis will also rely on the following mediant inequality.

######  Fact 1.

Suppose $n_{i}\geq 0$ and $d_{i}>0$ for each $i=1,\ldots,m\in\mathbb{N}$. Then

$\frac{\sum_{i=1}^{m}n_{i}}{\sum_{i=1}^{n}d_{i}}\geq\min_{i}\frac{n_{i}}{d_{i}}.$
(34)

We refer to the LHS above as the _mediant sum_ of the $\frac{n_{i}}{d_{i}}$.

###  V-C Characterization of $R_{\text{b}}^{*}$: worst-case broad risk

To prove Theorem 1, we seek a pair $(S,G)$ with $G\in\mathcal{G}_{N}$ of any
size $N\geq 3$ and $S\in\mathcal{T}(G)$, that minimizes efficiency
$J_{\text{b}}(\alpha,S;G)$ (maximizes risk $R_{\text{b}}(\alpha,S;G)$). Our
method to find the minimizer is to show any $(S,G)$ can be transformed into a
star network with a particular target set that has lower efficiency, when
$\alpha<1$. Thus, in this regime the search for the worst-case graph reduces
to the class of star networks of arbitrary size. For $\alpha\geq 1$,
structural properties allow us to deduce the minimal efficiency.

The graphical coordination game defined by $\mathcal{A}=\\{x,y\\}^{N}$,
perceived utilities $\\{\tilde{U}_{i}^{\alpha}\\}_{i\in\mathcal{N}}$ (7),
target set $S$, and graph $G$ falls under the class of potential games [25]. A
potential function is given by

$\frac{1}{2}W^{\alpha}(a)+(1+\alpha)\sum_{i\in
S_{x}}\mathds{1}(a_{i}=x)+\sum_{i\in S_{y}}\mathds{1}(a_{i}=y)$ (35)

where

$W^{\alpha}(a):=\sum_{i\in\mathcal{N}}U_{i}^{\alpha}(a).$ (36)

Hence, the stochastically stable states $\text{LLL}(\mathcal{A},\alpha,S;G)$
are maximizers of (35). Suppose
$\hat{a}=\underset{a\in\text{LLL}(\mathcal{A},\alpha,S;G)}{\operatorname{arg}\,\operatorname{min}}\;W(a)$
is the welfare-minimizing SSS inducing the partitions
$\\{\mathcal{P}_{z}^{k}\\}_{k=1}^{k_{z}}$, $z=x,y$. We can express its
efficiency from (8) as

$\frac{\sum_{k=1}^{k_{y}}|e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k})|+(1+\alpha_{\text{sys}})\sum_{k=1}^{k_{x}}|e(\mathcal{P}_{x}^{k},\mathcal{P}_{x}^{k})|}{(1+\alpha_{\text{sys}})(\sum_{k=1}^{k_{y}}|e(\mathcal{P}_{y}^{k},\mathcal{N})|+\sum_{k=1}^{k_{x}}|e(\mathcal{P}_{x}^{k},\mathcal{P}_{x}^{k})|)}.$
(37)

Note the denominator is simply the number of edges in $G$ multiplied by
$1\\!+\\!\alpha_{\text{sys}}$. From (35), each $y$-partition
$\mathcal{P}_{y}^{k}$ in $\hat{a}$ satisfies111Since we are seeking worst-case
pairs $(S,G)$, we may consider any $y$-partition as only having $y$ imposters
placed among its nodes. This is because any $x$ imposters that were placed in
a resulting $y$-partition can be replaced by $y$-imposters and retain
stability. We reflect this generalization in (V-C) and (V-C), where influence
from only $y$ ($x$) imposters is considered.

$\displaystyle|\mathcal{P}_{y}^{k}|+|e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k})|\geq$
$\displaystyle\max_{a_{\mathcal{P}_{y}^{k}}\neq\vec{y}_{\mathcal{P}_{y}^{k}}}\\!\\!W^{\alpha}(e(\mathcal{P}_{y}^{k},\mathcal{N}),(a_{\mathcal{P}_{y}^{k}},\hat{a}_{-\mathcal{P}_{y}^{k}}))$
$\displaystyle+\sum_{i\in\mathcal{P}_{y}^{k}}\\!\\!\mathds{1}(a_{i}=y).$ (CY)

In words, no subset of agents in $\mathcal{P}_{y}^{k}$ can deviate from $y$ to
improve the collective perceived welfare of $\mathcal{P}_{y}^{k}$. A similar
stability condition holds for each $x$-partition $\mathcal{P}_{x}^{k}$.

$\displaystyle(1\\!+\\!\alpha)$
$\displaystyle\\!\left(|\mathcal{P}_{x}^{k}|\\!+\\!|e(\mathcal{P}_{x}^{k},\mathcal{P}_{x}^{k})|\right)\geq$
$\displaystyle\max_{a_{\mathcal{P}_{x}^{k}}\neq\vec{x}_{\mathcal{P}_{x}^{k}}}\\!\\!\\!W^{\alpha}\\!(e(P_{x}^{k},\mathcal{N}),(a_{\mathcal{P}_{x}^{k}},\hat{a}_{-\mathcal{P}_{x}^{k}}))$
$\displaystyle\quad+(1+\alpha)\\!\\!\\!\sum_{i\in\mathcal{P}_{x}^{k}}\\!\\!\mathds{1}(a_{i}=x)$
(CX)

The following result characterizes the threshold on $\alpha$ above which any
network is safeguarded from any imposter attack.

######  Lemma 1.

Let $N\geq 3$. Then $\alpha>\frac{N}{N-1}$ if and only if

$\min_{G\in\mathcal{G}_{N}}\min_{S\in\mathcal{T}(G)}J_{\text{\emph{b}}}(\alpha,S;G)=1.$
(38)

###### Proof.

$(\Rightarrow)$ Let $\alpha>\frac{N}{N-1}$. Suppose there is a pair $(S,G)$
with $J_{\text{b}}(\alpha,G,S)<1$. Then there must exist a $y$-partition
$\mathcal{P}_{y}\subset\mathcal{N}$. From (V-C),

$|\mathcal{P}_{y}|+|e(\mathcal{P}_{y},\mathcal{P}_{y})|\geq(1+\alpha)|e(\mathcal{P}_{y},\mathcal{N})|>2|e(\mathcal{P}_{y},\mathcal{N})|.$
(39)

Since $G$ is connected,
$|e(\mathcal{P}_{y},\mathcal{P}_{y})|\geq|\mathcal{P}_{y}|-1$ and there is at
least one outgoing link from $\mathcal{P}_{y}$, i.e.
$|e(\mathcal{P}_{y},\mathcal{P}_{y}^{c})|\geq 1$. Consequently,
$|e(\mathcal{P}_{y},\mathcal{N})|\geq|\mathcal{P}_{y}|$, from which we obtain

$|e(\mathcal{P}_{y},\mathcal{N})|+|e(\mathcal{P}_{y},\mathcal{P}_{y})|>2|e(\mathcal{P}_{y},\mathcal{N})|.$
(40)

which is impossible.

$(\Leftarrow)$ Assume
$\min_{G\in\mathcal{G}_{N}}\min_{S\in\mathcal{T}(G)}J_{\text{b}}(\alpha,S;G)=1$.
Then no $y$-partition can exist for any graph. In particular, (V-C) is
violated for $\mathcal{P}_{y}=\mathcal{N}$.

$N+|\mathcal{E}|<(1+\alpha)|\mathcal{E}|\Rightarrow\alpha>\frac{N}{|\mathcal{E}|}.$
(41)

Since $|\mathcal{E}|\geq N-1$, we obtain $\alpha>\frac{N}{N-1}$. ∎

We also deduce the following minimal efficiencies for any graph when
$1\leq\alpha\leq\frac{N}{N-1}$.

######  Lemma 2.

Suppose $N\geq 3$. Then $\alpha\in[1,\frac{N}{N-1}]$ if and only if

$\min_{G\in\mathcal{G}_{N}}\min_{S\in\mathcal{T}(G)}J_{\text{\emph{b}}}(\alpha,S;G)=\frac{1}{1+\alpha_{\text{sys}}}.$
(42)

###### Proof.

The ($\Rightarrow$) direction follows the same argument as Lemma 1.

($\Leftarrow$) The assumption implies the only $y$-partition that is
stabilizable is $\mathcal{N}$. Then for any
$\mathcal{P}_{y}\subset\mathcal{N}$, (V-C) is violated, i.e.

$|\mathcal{P}_{y}|+|e(\mathcal{P}_{y},\mathcal{P}_{y})|<(1+\alpha)|e(\mathcal{P}_{y},\mathcal{N})|.$
(43)

Since $G$ is connected and there is at least one outgoing edge from
$\mathcal{P}_{y}$, we obtain

$\frac{2|\mathcal{P}_{y}|-1}{|\mathcal{E}|}<1+\alpha$ (44)

The above holds for any graph $G=(\mathcal{N},\mathcal{E})$ and subset of
nodes $\mathcal{P}_{y}\subset\mathcal{N}$. From the facts that
$|\mathcal{P}_{y}|\leq N-1$ and $|\mathcal{E}|\geq N-1$, we have
$\alpha>\frac{N-2}{N-1}$ for any $N\geq 3$. Consequently, $\alpha\geq 1$ and
Lemma 1 establishes that $\alpha\leq\frac{N}{N-1}$. ∎

The class of star graphs is central to the worst-case analysis in the interval
$0<\alpha<1$.

######  Definition 3.

Let $\mathbb{S}_{N}$ be the set of all $(S,G)$ where $G$ is the star graph
with $N$ nodes, $S_{y}$ contains the center node, and
$S_{x}=\mathcal{N}\backslash S_{y}$.

An immediate consequence of this definition is the leaf nodes satisfy (V-C).
The efficiency is then proportional to the fraction of leaf nodes that are
stable to $y$, if any. Furthermore, the stability condition (V-C) of
$\mathcal{P}_{y}=S_{y}$ for members of $\mathbb{S}_{N}$ simplifies to

$2|e(\mathcal{P}_{y},\mathcal{P}_{y})|+1\geq(1+\alpha)(N-1).$ (45)

In other words, stability of the target set $S_{y}$ as a $y$-partition hinges
on (V-C) being satisfied for the selection $a_{\mathcal{P}_{y}}=\vec{x}$. The
following result reduces the search space for efficiency minimizers to
$\mathbb{S}_{N}$ when $\alpha<1$.

######  Lemma 3.

Suppose $0<\alpha<1$ and $n\geq 3$. Consider any $(S,G)$ with
$G\in\mathcal{G}_{N}$, $S\in\mathcal{T}(G)$. Then there is a
$(S^{\prime},G^{\prime})\in\mathbb{S}_{N^{\prime}}$ such that
$J_{\text{\emph{b}}}(\alpha,S^{\prime};G^{\prime})\leq
J_{\text{\emph{b}}}(\alpha,S;G)$ for some $N^{\prime}\geq N$.

The idea of the proof is to construct a member of $\mathbb{S}_{N^{\prime}}$ by
re-casting the $y$ and $x$-partitions of $(S,G)$ as star subgraphs while
preserving the same number and type of edges, thus preserving efficiency.
Further efficiency reduction can be achieved by converting excess $x$ links
into $y$ links in this star configuration. We provide the proof detailing the
constructive procedure in the Appendix. We now characterize the minimal
efficiency for the star graph of size $N$,
$J_{N}^{*}(\alpha):=\min_{(G,S)\in\mathbb{S}_{N}}J_{\text{b}}(\alpha,S;G)$ for
$\alpha<1$.

######  Lemma 4.

Suppose $\alpha<1$ and fix $N\geq 3$. Then

$J_{N}^{*}(\alpha)=\frac{1}{(1+\alpha_{\text{sys}})(N-1)}\left\lceil\frac{(1+\alpha)(N-1)-1}{2}\right\rceil.$
(46)

###### Proof.

The goal is to find the smallest $y$-partition of the $n$ star that is still
stabilizable under a gain $\alpha$. This is written

$\displaystyle J^{*}_{N}(\alpha)=$
$\displaystyle\min_{N_{y}}\frac{1}{1+\alpha_{\text{sys}}}\frac{N_{y}}{N-1}$
(47) s.t. $\displaystyle\begin{cases}N_{y}\leq N-1\ &\text{(size of
$y$-partition)}\\\ 2N_{y}+1\geq(1+\alpha)(N-1)\
&\text{(stability)}\end{cases}$

The smallest integer $N_{y}$ that satisfies the constraints is
$\left\lceil\frac{(1+\alpha)(N-1)-1}{2}\right\rceil$ for $\alpha\in(0,1)$.

∎

###### Proof of Theorem 1.

For $\alpha<1$, by Lemma 3, the worst-case efficiency is

$\min_{N\geq
3}\min_{(G,S)\in\mathbb{S}_{N}}J_{\text{b}}(\alpha,S;G)=\min_{N\geq
3}J_{N}^{*}(\alpha).$ (48)

Using the formula of Lemma 4, we obtain the first entry in (11). Lemma 2
asserts the minimal efficiency is $\frac{1}{1+\alpha_{\text{sys}}}$ for
$\alpha\in[1,\frac{3}{2}]$ because the upper bound $\frac{N}{N-1}$ is
maximized at $N=3$ (for $N\geq 3$). This gives the second entry in (11).
Lastly, Lemma 1 asserts the minimal efficiency is 1 for $\alpha>\frac{3}{2}$.
∎

###  V-D Characterization of $R_{\text{\emph{f}}}^{*}$: worst-case focused
risk

Our approach for the proof of Theorem 2 differs from that of
$R_{\text{b}}^{*}$. Instead of reducing the search of worst-case graphs, we
simply provide an upper bound on $R_{\text{f}}^{*}(\alpha,F;G)$ for any $G$
and fixed set $F\in\mathcal{F}(G)$, and show one can construct a graph with
fixed nodes that achieves it. .

We observe $\frac{1}{2}W^{\alpha}(a):\mathcal{A}(F)\rightarrow\mathbb{R}$
serves as a potential function (recall (36)) for the game with restricted
action set $\mathcal{A}(F)$ and utilities
$\\{U_{i}^{\alpha}\\}_{i\in\mathcal{N}}$. Hence, the stochastically stable
states $\text{LLL}(\mathcal{A}(F),\alpha;G)$ are maximizers of
$\frac{1}{2}W^{\alpha}(a)$. Suppose
$\hat{a}=\underset{a\in\text{LLL}(\mathcal{A}(F),\alpha;G)}{\operatorname{arg}\,\operatorname{min}}\;W(a)$
decomposes the graph into the $x$ and $y$-partitions
$\\{\mathcal{P}_{z}^{k}\\}_{k=1}^{k_{z}}$, $z=x,y$. We express its efficiency
(13) as

$\frac{\sum_{k=1}^{k_{y}}|e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k})|+(1+\alpha_{\text{sys}})\sum_{k=1}^{k_{x}}|e(\mathcal{P}_{x}^{k},\mathcal{P}_{x}^{k})|}{\sum_{k=1}^{k_{y}}W^{\alpha_{\text{sys}}}(e(\mathcal{P}_{y}^{k},\mathcal{N}),a^{*})+\sum_{k=1}^{k_{x}}W^{\alpha_{\text{sys}}}(e(\mathcal{P}_{x}^{k},\mathcal{P}_{x}^{k}),a^{*})}$
(49)

where
$a^{*}=\underset{a\in\mathcal{A}(F)}{\operatorname{arg}\,\operatorname{max}}\;W(a)$
is the welfare-maximizing action profile. Similar to (V-C), each $y$-partition
$\mathcal{P}_{y}^{k}$ formed from $\hat{a}$ satisfies the stability condition

$|e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k})|\geq\max_{a_{\mathcal{P}_{y}^{k}}\neq\vec{y}}W^{\alpha}(e(\mathcal{P}_{y}^{k},\mathcal{N}),(a_{\mathcal{P}_{y}^{k}},\hat{a}_{-\mathcal{P}_{y}^{k}})).$
(CYE)

To reduce cumbersome notation, it is understood the max is taken over actions
of unfixed nodes, $a_{\mathcal{P}_{y}^{k}\backslash F}$. Likewise, each
$x$-partition $\mathcal{P}_{x}^{k}$ satisfies

$(1+\alpha)|e(\mathcal{P}_{x}^{k},\mathcal{P}_{x}^{k})|\geq\max_{a_{\mathcal{P}_{x}^{k}}\neq\vec{x}}W^{\alpha}(e(\mathcal{P}_{x}^{k},\mathcal{N}),(a_{\mathcal{P}_{x}^{k}},\hat{a}_{-\mathcal{P}_{x}^{k}})).$
(CXE)

The following lemma asserts that agents playing $y$ in the SSS under the gain
$\alpha$ remain playing $y$ under a lower gain $\alpha^{\prime}<\alpha$. The
result is crucial for establishing a lower bound on efficiency for any graph
$G$ with arbitrary fixed set $F\in\mathcal{F}(G)$.

######  Lemma 5.

Suppose $\alpha^{\prime}<\alpha$. Denote
$\hat{a}^{\prime}=\underset{a\in\text{LLL}(\mathcal{A}(F),\alpha^{\prime};G)}{\operatorname{arg}\,\operatorname{min}}\;W(a)$
as the welfare-minimizing SSS under $\alpha^{\prime}$. Then for any
$y$-partition $\mathcal{P}_{y}$ induced from $\alpha$,
$\hat{a}_{i}^{\prime}=y$ for all $i\in\mathcal{P}_{y}\backslash F$.

###### Proof.

Condition (CYE) asserts for all $a_{\mathcal{P}_{y}}\neq\vec{y}$ that

$W^{\alpha}(e(\mathcal{P}_{y},\mathcal{N}),(\vec{y}_{\mathcal{P}_{y}},\hat{a}_{-\mathcal{P}_{y}}))\geq
W^{\alpha}(e(\mathcal{P}_{y},\mathcal{N}),(a_{\mathcal{P}_{y}},\hat{a}_{\mathcal{P}_{y}})).$
(50)

It also holds for all $a_{\mathcal{P}_{y}}\neq\vec{y}$ and for any
$a_{-\mathcal{P}_{y}}\neq\hat{a}_{-\mathcal{P}_{y}}$ that

$W^{\alpha}(e(\mathcal{P}_{y},\mathcal{N}),(\vec{y}_{\mathcal{P}_{y}},a_{-\mathcal{P}_{y}}))\geq
W^{\alpha}(e(\mathcal{P}_{y},\mathcal{N}),(a_{\mathcal{P}_{y}},a_{-\mathcal{P}_{y}}))$
(51)

because any $y$-links garnered in the RHS above by changing
$\hat{a}_{-\mathcal{P}_{y}}$ to $a_{-\mathcal{P}_{y}}$ also contribute to the
LHS. In particular, the above holds for
$a_{-\mathcal{P}_{y}}=\hat{a}_{-\mathcal{P}_{y}}^{\prime}$. Lowering the gain
to $\alpha^{\prime}$ preserves the above inequality as well, as it de-values
$x$-links garnered on the RHS. ∎

A dual statement holds - agents playing $x$ in the SSS under $\alpha$ remain
so under a higher gain $\alpha^{\prime}>\alpha$.

######  Lemma 6.

Suppose $\alpha^{\prime}>\alpha$. Then for any $x$-partition $\mathcal{P}_{x}$
induced from $\alpha$, $\hat{a}_{i}^{\prime}=x$ for all
$i\in\mathcal{P}_{x}\backslash F$.

We omit the proof for brevity, as it is analogous to the proof of Lemma 5. We
are now ready to prove Theorem 2.

###### Proof of Theorem 2.

Consider any graph $G\in\mathcal{G}_{N}$ with fixed set $F$. Recall that
efficiency is one for $\alpha=\alpha_{\text{sys}}$. Thus, we first consider
$\alpha<\alpha_{\text{sys}}$. Observe that

$\displaystyle|e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k})|$ $\displaystyle\geq
W^{\alpha}(e(\mathcal{P}_{y},\mathcal{N}),(a_{\mathcal{P}_{y}}^{*},\hat{a}_{-\mathcal{P}_{y}}))$
(52)
$\displaystyle=W^{\alpha}(e(\mathcal{P}_{y},\mathcal{N}),(a_{\mathcal{P}_{y}}^{*},a_{-\mathcal{P}_{y}}^{*}))$

where the inequality is due to (CYE). The equality results from Lemma 6 \- the
agents ($\notin\mathcal{P}_{y}$) that neighbor any member of $\mathcal{P}_{y}$
remain playing $x$ in $a^{*}$. We then obtain

$\frac{|e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k})|}{W(e(\mathcal{P}_{y}^{k},\mathcal{N}),a^{*})}\geq\frac{1+\alpha}{1+\alpha_{\text{sys}}}.$
(53)

The inequality results since the expressions of the numerator and denominator
garner the same edges for welfare. It occurs with equality if and only if
$a_{i}^{*}=x$ $\forall i\in\mathcal{P}_{y}^{k}\backslash F$. Applying the
mediant inequality (34) to (49),
$J_{\text{f}}(\alpha,F;G)\geq\frac{1+\alpha}{1+\alpha_{\text{sys}}}$. The case
when $\alpha>\alpha_{\text{sys}}$ follows analogous arguments. From Lemma 5,
$|e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k})|=W^{\alpha}(e(\mathcal{P}_{y}^{k},\mathcal{P}_{y}^{k}),a^{*})$.
For $x$-partitions,

$\displaystyle\frac{(1\\!+\\!\alpha_{\text{sys}})|e(\mathcal{P}_{x}^{k},\mathcal{P}_{x}^{k})|}{W(e(\mathcal{P}_{x}^{k},\mathcal{N}),a^{*})}$
$\displaystyle\geq\frac{1\\!+\\!\alpha_{\text{sys}}}{1\\!+\\!\alpha}\frac{W^{\alpha}(e(\mathcal{P}_{x}^{k},\mathcal{N}),a^{*})}{W(e(\mathcal{P}_{x}^{k},\mathcal{N}),a^{*})}$
(54) $\displaystyle\geq\frac{1\\!+\\!\alpha_{\text{sys}}}{1\\!+\\!\alpha}$

where the first inequality is from (CXE) and the second occurs with equality
if $a_{i}^{*}=y$ $\forall i\in\mathcal{P}_{x}^{k}\backslash F$. From (34) and
(49), $J_{\text{f}}(\alpha,F;G)\geq\frac{1+\alpha_{\text{sys}}}{1+\alpha}$. ∎

We have just shown fundamental lower bounds on efficiency for any graph with
fixed agents. The bounds are tight as they can be achieved for any gain
$\alpha$ by arranging $N_{x}$ fixed $x$ and $N_{y}$ fixed $y$ leaf nodes that
influence a single unfixed agent in the center of a star graph. If
$\alpha<\alpha_{\text{sys}}$, choosing
$\frac{N_{x}}{N_{y}}=\frac{1}{1+\alpha}$ gives the minimal efficiency
$\frac{1+\alpha}{1+\alpha_{\text{sys}}}$. If $\alpha>\alpha_{\text{sys}}$,
choosing $\frac{N_{x}}{N_{y}}=\frac{1}{1+\alpha}$ gives the minimal efficiency
$\frac{1+\alpha_{\text{sys}}}{1+\alpha}$. Note that if $\alpha$ is rational,
one could choose finite integers $N_{y},N_{x}$ that achieve such ratios.
Recall Figure 2(b) for illustrative examples. However if it is irrational,
they must be taken arbitrarily large to better approximate the ratio.

##  VI Proof of Theorem 3: worst-case risks under randomized operator designs

Recall a randomized strategy consists of gains
$\bm{\alpha}=\\{\alpha_{i}\\}_{i=1}^{M}$ with distribution
$\bm{p}\in\Delta_{M}$. The gains are ordered
$\alpha_{\text{sys}}\leq\alpha_{1}<\cdots<\alpha_{M}$. To prove Theorem 3, we
outline a few technical Lemmas. The key insight is the expected efficiency of
any graph $G$ can be expressed in the form $\sum_{i=1}^{M}p_{i}s_{i}$, where
the coefficient $s_{i}$ is a mediant sum over local efficiencies of partitions
in $G$ when gain $\alpha_{i}$ is used. The following two mathematical facts
are the basis of this insight.

######  Fact 2.

Let $\nu_{i}<\frac{n_{i}}{d_{i}}\leq 1$ with $r_{i}\geq 0$ and $n_{i},d_{i}>0$
for all $i=1,\ldots,M$ . Then for all $\bm{p}\in\Delta_{M}$,

$\sum_{i=1}^{M}p_{i}s_{i}\geq
1+\min_{i=1,\ldots,M}\left\\{\left(\sum_{j=1}^{i}p_{j}\right)(\nu_{i}-1)\right\\}$
(55)

where
$s_{i}:=\frac{\sum_{j=1}^{i-1}d_{j}+\sum_{j=i}^{M}n_{j}}{\sum_{j=1}^{M}d_{j}},\quad
i=1,\ldots,M$.

We provide a proof in the Appendix. The following dual result follows
directly.

######  Fact 3.

For all $\bm{p}\in\Delta_{M}$,

$\sum_{i=1}^{M}p_{i}s_{i}^{\prime}\geq
1+\min_{i=1,\ldots,M}\left\\{\left(\sum_{j=i}^{M}p_{j}\right)(\nu_{i}-1)\right\\}$
(56)

where
$s_{i}^{\prime}:=\frac{\sum_{j=1}^{i}n_{j}+\sum_{j=i}^{M}d_{j}}{\sum_{j=1}^{M}d_{j}},\quad
i=1,\ldots,M$.

###### Proof.

The proof follows similarly to Fact 2, where the indices of the $s_{i}$
coefficients are reversed. ∎

We will show for any $(S,G)$ that
$\mathbb{E}_{\bm{\alpha},\bm{p}}[J_{\text{b}}|S,G]=1-\mathbb{E}_{\bm{\alpha},\bm{p}}[R_{\text{b}}|S,G]$
can be expressed in the form $\sum_{i=1}^{M}p_{i}s_{i}$ from the LHS of (55).
The lower bounds establish worst-case expected efficiencies - and hence risks.
The $\nu_{i}$ correspond to the worst-case deterministic efficiencies
$J_{\text{b}}^{*}(\alpha_{i})=1-R_{\text{b}}^{*}(\alpha_{i})$ of the $M$ gains
and $\frac{n_{i}}{d_{i}}$ to local efficiencies of selected partitions in the
graph. Fact 2 will be used to establish (22), and Fact 3 for (23) (Theorem 3).
We now identify a structural property required of worst-case graphs.

######  Lemma 7.

A worst-case graph, i.e. a member of
$\underset{G\in\mathcal{G}_{N},S\in\mathcal{T}(G)}{\operatorname{arg}\,\operatorname{min}}\;\mathbb{E}_{\bm{\alpha},\bm{p}}[J_{\text{\emph{b}}}|S,G]$,
has no active $x$-links in $\alpha_{1}$.

###### Proof.

Any active $x$-links in $\alpha_{1}$ remain so for all
$\\{\alpha_{i}\\}_{i=2}^{M}$. The efficiency corresponding to each gain can be
reduced in the following manner. Delete all such $x$-links and associated
agents. For each mis-coordinating link between an $x$ and $y$ agent that
existed, replace with a single link to a newly created isolated agent with an
$x$-imposter attached. This preserves the stochastically stable states of all
other nodes while reducing efficiency in each gain. ∎

Intuitively, a graph that has coordinating $x$ nodes in each gain
$\alpha_{1},\ldots,\alpha_{M}$ can be modified by removing these links,
resulting in a lower efficiency. We are now ready to prove (22) (Theorem 3).

###### Proof of (22) (Theorem 3).

Consider any graph $G=(\mathcal{N},\mathcal{E})\in\mathcal{G}_{N}$ and
$S\in\mathcal{T}(G)$. Let us denote the $M$ (worst-case) stochastically stable
states that correspond to each gain $\alpha_{i}$ with $\hat{a}^{i}$. Define
for each $k=1,\ldots,M$

$P^{k}=\\{n\in\mathcal{N}:\hat{a}_{n}^{i}=y\ \forall i\leq k,\
\hat{a}_{n}^{i}=x\ \forall i>k\\}$ (57)

as the set of nodes that play $y$ in the SSS in $\alpha_{1},\ldots,\alpha_{k}$
and play $x$ in $\alpha_{k+1},\ldots,\alpha_{M}$. Note that $P^{k}$ is
possibly composed of multiple $y$-partitions. Also note it is possible that
$P^{k}=\varnothing$ for all $k>\bar{m}$ for some
$\bar{m}\in\\{2,\ldots,M-1\\}$ \- that is, $\hat{a}^{i}=\vec{x}$ for all
$i>\bar{m}$. We first consider the case when $P^{k}\neq\varnothing$ for every
$k=1,\ldots,M$.

Let $Q^{k}:=\\{n\in\mathcal{N}:\hat{a}_{n}^{k}=y\\}=\bigcup_{i=k}^{M}P^{i}$.
Denote $P^{x}:=\\{n\in\mathcal{N}:\hat{a}_{n}^{1}=x\\}=(Q^{1})^{c}$ as the set
of nodes stable to $x$ for all $\alpha_{i}$. Consider the gain $\alpha_{i}$
with $i\leq k$. Then the local efficiency
$\frac{W(e(P^{k},\mathcal{N}),\hat{a}^{k})}{W(e(P^{k},\mathcal{N}),(a^{*}_{P^{k}},\hat{a}^{k}_{-P^{k}}))}$
of $P^{k}$ is

$\displaystyle\frac{|e(P^{k},Q^{k+1})|+|e(P^{k},P^{k})|}{(1\\!+\\!\alpha_{\text{sys}})(|e(P^{k}\\!,P^{k})|\\!+\\!|e(P^{k}\\!,P^{x})|\\!+\\!|e(P^{k}\\!,(Q^{k})^{c})|)}$
(58) $\displaystyle\quad\quad>J_{A}^{*}(\alpha_{i}).$

The inequality is due to Proposition 1. For gains $\alpha_{i}$ with $i>k$, the
local efficiency of $P^{k}$ is

$\frac{(1\\!+\\!\alpha_{\text{sys}})(|e(P^{k}\\!,P^{k})|\\!+\\!|e(P^{k}\\!,P^{x})|\\!+\\!|e(P^{k}\\!,(Q^{k})^{c})|)}{(1\\!+\\!\alpha_{\text{sys}})(|e(P^{k}\\!,P^{k})|\\!+\\!|e(P^{k}\\!,P^{x})|\\!+\\!|e(P^{k}\\!,(Q^{k})^{c})|)}=1.$
(59)

Hence, the overall system efficiency under gain $\alpha_{i}$ is the mediant
sum of the local efficiencies of the $P^{k}$. An application of Fact 2 gives
the result. The case when $P^{k}=\varnothing$ for
$k>\bar{m}\in\\{2,\ldots,M-1\\}$ also follows directly from Fact 2. From the
notation of Fact 2, $\frac{n_{k}}{d_{k}}=1$ for $k>\bar{m}$. ∎

The details for the proof of (22) (Theorem 3) follow analogous arguments
pertaining to focused attacks. Recall for a graph $G\in\mathcal{G}_{n}$ and
restricted action set $\mathcal{A}$, we denote $F=F_{x}\cup
F_{y}\subset\mathcal{N}$ as its set of fixed nodes. Additionally, we restrict
attention to gains $\alpha_{i}\geq\alpha_{\text{sys}}$, as these are not
strictly dominated in the risk curve. The following structural property holds
in a worst-case graph for focused risk.

######  Lemma 8.

A worst-case graph, i.e., a member of
$\underset{G\in\mathcal{G}_{N},F\in\mathcal{F}(G)}{\operatorname{arg}\,\operatorname{min}}\;\mathbb{E}_{\bm{\alpha},\bm{p}}[J_{\text{\emph{f}}}|F,G]$,
has no active $y$-links in $\alpha_{M}$. Additionally,
$a_{F^{c}}^{*}=\vec{y}$.

###### Proof.

A graph that has active $y$-links in $\alpha_{M}$ remain active for all
$\alpha_{1},\ldots,\alpha_{M-1}$. The efficiency corresponding to each gain
can be reduced by removing all such links and keeping the border nodes as
fixed $y$ agents. This preserves the stability properties of all other nodes.
The claim $a_{F^{c}}^{*}=\vec{y}$ follows from Lemma 5. ∎

We are now ready to prove (23) in Theorem 3.

###### Proof of (23) (Theorem 3).

Consider any graph $G=(\mathcal{N},\mathcal{E})\in\mathcal{G}_{N}$ and fixed
nodes $F\in\mathcal{F}(G)$. The $M$ stochastically stable states that
correspond to each gain $\alpha_{i}$ are denoted $\hat{a}^{i}$. Define for
each $k=1,\ldots,M$

$P^{k}=\\{n\in F^{c}:\hat{a}_{n}^{i}=x\ \forall i\geq k,\ \hat{a}_{n}^{i}=y\
\forall i<k\\}$ (60)

as the set of unfixed nodes that play $x$ in the SSS for
$\alpha_{k},\ldots,\alpha_{M}$ and play $y$ in
$\alpha_{1},\ldots,\alpha_{k-1}$ . Note that it is possible
$P^{k}=\varnothing$ for all $k<\bar{m}$ for some
$\bar{m}\in\\{2,\ldots,M-1\\}$. That is, $a^{k}_{F^{c}}=\vec{y}$ for
$k=1,\ldots,\bar{m}-1$. We first consider the case when $P^{k}\neq\varnothing$
for every $k=1,\ldots,M$.

Let $Q^{k}=\\{n\in F^{c}:\hat{a}_{n}^{k}=y\\}=\bigcup_{i=k}^{M}P^{i}$.
Consider the gain $\alpha_{i}$ with $i\geq k$. Then the local efficiency
$\frac{W(e(P^{k},\mathcal{N}),\hat{a}^{k})}{W(e(P^{k},\mathcal{N}),(a^{*}_{P^{k}},\hat{a}^{k}_{-P^{k}}))}$
of $P^{k}$ is

$\displaystyle\frac{(1+\alpha_{\text{sys}})(|e(P^{k},P^{k})|\\!+\\!|e(P^{k},(Q^{k-1})^{c})|\\!+\\!|e(P^{k},F_{x})|)}{|e(P^{k},P^{k})|+|e(P^{k},Q^{k})|+|e(P^{k},F_{y})|}$
(61) $\displaystyle\quad\quad>J_{\text{f}}^{*}(\alpha_{i}).$

Here, we use the convention $|e(P^{1},(Q^{0})^{c})|=0$. For gains $\alpha_{i}$
with $i<k$, the local efficiency of $P^{k}$ is

$\frac{|e(P^{k},P^{k})|+|e(P^{k},Q^{k})|+|e(P^{k},F_{y})|}{|e(P^{k},P^{k})|+|e(P^{k},Q^{k})|+|e(P^{k},F_{y})|}=1.$
(62)

Hence the overall system efficiency under $\alpha_{i}$ is the mediant sum of
the local efficiencies of the $P^{k}$. An application of Fact 3 gives the
result. The case when $P^{k}=\varnothing$ for $k>\bar{m}\in\\{2,\ldots,M-1\\}$
also follows directly from Fact 3. ∎

##  VII Summary

In this paper, we framed graphical coordination games as a distributed system
subject to two types of adversarial influences. The focus of our study
concerned the performance of a class of distributed algorithms against the
associated worst-case risks. We identified fundamental tradeoffs between
ensuring security against one type of risk and vulnerability to the other, and
vice versa. Furthermore, our analysis shows randomized algorithmic designs
significantly improves the available tradeoffs. Our work highlights the design
challenges a system operator faces in maintaining the efficiency of networked,
distributed systems.

Figure 4: An illustration of the constructive process (proof of Lemma 3) that
generates a member $(S^{\prime},G^{\prime})\in\mathbb{S}_{m}$ from any graph
$(S,G)$ with one $y$-partition, and $\alpha<1$. Here, the labels on each node
indicate the type of imposter influence. Green (blue) nodes play $x$ ($y$) in
the SSS. (Left) Start with an arbitrary graph-adversary pair $(S,G)$. (Center)
The partitions of $(S,G)$ are re-cast as star subgraphs with the same number
of edges. When there is more than one edge between the $y$ and an
$x$-partition, new nodes are created for the excess outgoing edges. This re-
casting preserves the original efficiency $J_{\text{b}}(\alpha,S;G)$. (Right)
The active $x$-links are converted into $y$-links by redirecting them to the
center of the $y$-partition. This results in a graph
$(S^{\prime},G^{\prime})\in\mathbb{S}_{m}$.

###### Proof of Lemma 3:.

This proof outlines a procedure to transform any $(S,G)$ into a star graph
with lower efficiency if $\alpha<1$. We split into two cases - either $(S,G)$
induces a single $y$-partition or more than one. First, assume $(S,G)$ induces
a single $y$-partition $\mathcal{P}_{y}$. An illustration of the constructive
process is shown in Figure 4.

Construct a star subgraph $\Gamma_{y}$ that has
$1+|e(\mathcal{P}_{y},\mathcal{P}_{y})|$ nodes, each having a $y$ imposter
attached. Call the center node $i_{y}$. Construct similar star configurations
$\Gamma_{x}^{k}$ for each $x$-partition $\mathcal{P}_{x}^{k}$. Call their
center nodes $i_{x}^{k}$. Connect $\Gamma_{y}$ to each $\Gamma_{x}^{k}$ with a
link between $i_{x}^{k}$ and $i_{y}$. If there are multiple edges between
$\mathcal{P}_{x}^{k}$ and $\mathcal{P}_{y}$
($|e(\mathcal{P}_{x}^{k},(\mathcal{P}_{x}^{k})^{c})|\geq 2$), create
$|e(\mathcal{P}_{x}^{k},(\mathcal{P}_{x}^{k})^{c})|-1$ new isolated nodes with
a single $x$ imposter attached, and connect each to $i_{y}$ with a single
link. At this point, $\Gamma_{y}$ and $\Gamma_{x}^{k}$ are stable $y$ and
$x$-partitions, and the isolated nodes are stable playing $x$. We have
obtained a graph of $N^{\prime}\geq N$ nodes with identical efficiency to
$(S,G)$ since the number and type of edges are preserved.

We can further reduce efficiency if there are active $x$ links, i.e. if
$|e(\Gamma_{x}^{k},\Gamma_{x}^{k})|\geq 1$ for at least one $\Gamma_{x}^{k}$.
If there are none, then the graph belongs to $\mathbb{S}_{N^{\prime}}$ and we
are done. Otherwise for each leaf node $j\in\mathcal{P}_{x}^{k}$, redirect the
edge $(j,i_{x}^{k})$ to $(j,i_{y})$, and replace $j$’s $x$ imposter with a $y$
imposter. Call $m_{x}$ the total number of such converted nodes. The resulting
graph-target pair $(S^{\prime},G^{\prime})$ belongs to
$\mathbb{S}_{N^{\prime}}$. We claim the resulting (larger) $y$-partition
$\Gamma_{y}^{\prime}$ is stable. For this claim to hold, (45) requires that

$2|e(\mathcal{P}_{y},\mathcal{P}_{y})|+2m_{x}+1\geq(1+\alpha)(|e(\mathcal{P}_{y},\mathcal{N})|+m_{x}).$
(63)

From the original $\mathcal{P}_{y}$, it holds that

$\displaystyle|e(\mathcal{P}_{y},\mathcal{P}_{y})|+|\mathcal{P}_{y}|\geq(1+\alpha)|e(\mathcal{P}_{y},\mathcal{N})|$
(64) $\displaystyle\Rightarrow
2|e(\mathcal{P}_{y},\mathcal{P}_{y})|+2m_{x}+1>(1+\alpha)(|e(\mathcal{P}_{y},\mathcal{N})|+m_{x})$

due to $|\mathcal{P}_{y}|\leq 1+|e(\mathcal{P}_{y},\mathcal{P}_{y})|$ and
$\alpha<1$. All $x$-partitions in $(S^{\prime},G^{\prime})$ , now just a
collection of single nodes connected to $i_{y}$ with an $x$-imposter, are
stable. The efficiency is less than the original because active $x$-links
increase efficiency more than active $y$-links do. Hence,

$J_{\text{b}}(\alpha,S;G)>J_{\text{b}}(\alpha,S^{\prime};G^{\prime}).$ (65)

Now, we consider the remaining case when $(S,G)$ induces $k_{y}>1$
$y$-partitions $\\{\mathcal{P}_{y}^{k}\\}_{k=1}^{k_{y}}$ and $k_{x}\geq 1$
$x$-partitions $\\{\mathcal{P}_{x}^{k}\\}_{k=1}^{k_{x}}$. Consider $k_{y}$
such star subgraphs $\\{\Gamma_{y}^{k}\\}_{k=1}^{k_{y}}$ with center nodes
$i_{y}^{k}$. Recast the $x$-partitions into similar star subgraphs
$\\{\Gamma_{x}^{k}\\}_{k=1}^{k_{x}}$ with center nodes $i_{x}^{k}$. We first
connect each $\Gamma_{x}^{k}$ to some $\Gamma_{y}^{j}$ with a single link
$(i_{x}^{k},i_{y}^{j})$ in any manner as long as a link between the original
$\mathcal{P}_{x}^{k}$ and $\mathcal{P}_{y}^{j}$ exists. For each excess
outgoing edge, we create an isolated node with an $x$-imposter attached. Each
isolated node is attached to a corresponding $i_{y}^{k}$ such that the
original number of outgoing edges for each $\mathcal{P}_{y}^{k}$ is satisfied.
At this point, there are $k^{\prime}\leq k_{y}$ connected components $G_{k}$
in the construction, and the efficiency of this construction is identical to
the original. Lastly, we apply the efficiency reduction procedure from before
for each $G_{k}$ to obtain
$(S_{k}^{\prime},G_{k}^{\prime})\in\mathbb{S}_{m_{k}}$. From (37) and (34), we
have

$\displaystyle J_{\text{b}}(\alpha,S;G)$
$\displaystyle>\frac{\sum_{k=1}^{k^{\prime}}|e(\Gamma_{y}^{k},\Gamma_{y}^{k})|}{(1+\alpha_{\text{sys}})\sum_{k=1}^{k^{\prime}}|e(\Gamma_{y}^{k},\mathcal{N})|}$
(66)
$\displaystyle\geq\min_{k=1,\ldots,k^{\prime}}J_{\text{b}}(\alpha,S_{k}^{\prime};G_{k}^{\prime}).$

∎

###### Proof of Lemma 2: Technical result for expected risks.

Let us define $f(\bm{p}):=\sum_{i=1}^{M}p_{i}s_{i}$ and
$f_{i}(\bm{p}):=\left(\sum_{j=1}^{k}p_{j}\right)(\nu_{k}-1)+1$. The set of
probability vectors such that
$k=\underset{i=1,\ldots,M}{\operatorname{arg}\,\operatorname{min}}\;f_{i}(\bm{p})$
can be written as the set

$\displaystyle V_{k}$
$\displaystyle:=\left\\{\bm{p}\in\Delta_{M}:f_{k}(\bm{p})\leq
f_{\ell}(\bm{p})\ \forall\ell\neq k\right\\}$ (67)
$\displaystyle=\bigcap_{\ell\neq
k}\left\\{\bm{p}\in\Delta_{M}:\frac{\sum_{j=1}^{k}p_{j}}{\sum_{j=1}^{\ell}p_{j}}\geq\frac{1-\nu_{\ell}}{1-\nu_{k}}\right\\}.$

Define $\lambda_{k}=\frac{\sum_{j=1}^{k}d_{j}}{\sum_{j=1}^{k+1}d_{j}}$ for
each $k=1,\ldots,M-1$. With some algebra, we can express each $s_{i}$ as

$\displaystyle
s_{i}=\left[\\!\sum_{j=1}^{M-i+1}\frac{n_{j}}{d_{j}}(1\\!-\\!\lambda_{j-1})\left(\prod_{k=j}^{M-1}\lambda_{k}\right)\\!\right]+\left(1\\!-\\!\\!\prod_{j=M-i+1}^{M-1}\lambda_{j}\right)$
(68)

Using the identities
$\sum_{k=1}^{M}(1\\!-\\!\lambda_{k-1})\left(\prod_{j=k}^{M-1}\lambda_{j}\right)=1$
and
$\sum_{k=1}^{\ell}(1\\!-\\!\lambda_{k-1})\left(\prod_{j=k}^{M-1}\lambda_{j}\right)=\prod_{j=\ell}^{M-1}\lambda_{j}$
for $\ell\\!=\\!1,\ldots,M-1$, we obtain (omitting the algebraic steps)

$\displaystyle f(\bm{p})$
$\displaystyle=\sum_{i=1}^{M}(1\\!-\\!\lambda_{i-1})\\!\\!\left(\prod_{j=i}^{M-1}\lambda_{j}\right)\\!\\!\left[\left(\frac{n_{i}}{d_{i}}-1\right)\\!\\!\left(\sum_{j=1}^{M-i+1}p_{j}\right)\\!+\\!1\right]$
(69)

Now, suppose $\bm{p}\in V_{k}$ for $k\in\\{1,\ldots,M\\}$. Using (67) and
$\nu_{i}\leq n_{i}/d_{i}\leq 1$, we then have

$\displaystyle f(\bm{p})$
$\displaystyle\geq\sum_{i=1}^{M}\lambda_{i-1}\left(\prod_{j=i}^{M-1}\lambda_{j}\right)f_{k}(\bm{p})=f_{k}(\bm{p}).$
(70)

∎

## References

  * [1] J. Cortes, S. Martinez, and F. Bullo, “Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions,” _IEEE Transactions on Automatic Control_ , vol. 51, no. 8, pp. 1289–1298, Aug 2006.
  * [2] M. Mesbahi and M. Egerstedt, _Graph theoretic methods in multiagent networks_. Princeton University Press, 2010, vol. 33.
  * [3] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” _Computer Networks_ , vol. 38, no. 4, pp. 393 – 422, 2002.
  * [4] H. P. Young, _Individual strategy and social structure: An evolutionary theory of institutions_. Princeton University Press, 2001.
  * [5] A. Montanari and A. Saberi, “The spread of innovations in social networks,” _Proceedings of the National Academy of Sciences_ , vol. 107, no. 47, pp. 20 196–20 201, 2010.
  * [6] S. A. West, S. P. Diggle, A. Buckling, A. Gardner, and A. S. Griffin, “The social lives of microbes,” _Annual Review of Ecology, Evolution, and Systematics_ , vol. 38, no. 1, pp. 53–77, 2007.
  * [7] M. Del Vicario, A. Bessi, F. Zollo, F. Petroni, A. Scala, G. Caldarelli, H. E. Stanley, and W. Quattrociocchi, “The spreading of misinformation online,” _Proceedings of the National Academy of Sciences_ , vol. 113, no. 3, pp. 554–559, 2016.
  * [8] Y. Mao, S. Bouloki, and E. Akyol, “Spread of information with confirmation bias in cyber-social networks,” _IEEE Transactions on Network Science and Engineering_ , 2018.
  * [9] S. Amin, A. A. Cárdenas, and S. S. Sastry, “Safe and secure networked control systems under denial-of-service attacks,” in _Hybrid Systems: Computation and Control_ , R. Majumdar and P. Tabuada, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 31–45.
  * [10] S. Amin, X. Litrico, S. S. Sastry, and A. M. Bayen, “Stealthy deception attacks on water scada systems,” in _Proceedings of the 13th ACM international conference on Hybrid systems: computation and control_. ACM, 2010, pp. 161–170.
  * [11] H. Fawzi, P. Tabuada, and S. Diggavi, “Secure state-estimation for dynamical systems under active adversaries,” in _2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2011, pp. 337–344.
  * [12] F. Pasqualetti, F. Dorfler, and F. Bullo, “Attack detection and identification in cyber-physical systems,” _IEEE Transactions on Automatic Control_ , vol. 58, no. 11, pp. 2715–2729, Nov 2013.
  * [13] S. Sundaram and B. Gharesifard, “Distributed optimization under adversarial nodes,” _IEEE Transactions on Automatic Control_ , 2018.
  * [14] V. Auletta, D. Ferraioli, F. Pasquale, and G. Persiano, “Metastability of logit dynamics for coordination games,” in _Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms_. Society for Industrial and Applied Mathematics, 2012, pp. 1006–1024.
  * [15] L. E. Blume, “The statistical mechanics of best-response strategy revision,” _Games and Economic Behavior_ , vol. 11, no. 2, pp. 111 – 145, 1995.
  * [16] J. R. Marden and J. S. Shamma, “Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation,” _Games and Economic Behavior_ , vol. 75, no. 2, pp. 788–808, 2012.
  * [17] T. Tatarenko, “Proving convergence of log-linear learning in potential games,” in _2014 American Control Conference_. IEEE, 2014, pp. 972–977.
  * [18] D. Acemoglu, A. Ozdaglar, and A. ParandehGheibi, “Spread of (mis) information in social networks,” _Games and Economic Behavior_ , vol. 70, no. 2, pp. 194–227, 2010.
  * [19] J. Ghaderi and R. Srikant, “Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate,” _Automatica_ , vol. 50, no. 12, pp. 3209–3215, 2014.
  * [20] H. P. Borowski and J. R. Marden, “Understanding the influence of adversaries in distributed systems,” in _2015 54th IEEE Conference on Decision and Control (CDC)_ , Dec 2015, pp. 2301–2306.
  * [21] P. N. Brown, H. Borowski, and J. R. Marden, “Security against impersonation attacks in distributed systems,” _IEEE Transactions on Control of Network Systems_ , pp. 1–1, 2018.
  * [22] B. Canty, P. N. Brown, M. Alizadeh, and J. R. Marden, “The impact of informed adversarial behavior in graphical coordination games,” in _2018 IEEE Conference on Decision and Control (CDC)_ , Dec 2018, pp. 1923–1928.
  * [23] H. P. Young, “The evolution of conventions,” _Econometrica: Journal of the Econometric Society_ , pp. 57–84, 1993.
  * [24] D. Foster and H. P. Young, “Stochastic evolutionary game dynamics,” _Theoretical population biology_ , vol. 38, no. 2, pp. 219–232, 1990.
  * [25] D. Monderer and L. S. Shapley, “Potential games,” _Games and economic behavior_ , vol. 14, no. 1, pp. 124–143, 1996.