# Robust Naive Learning in Social Networks

Gideon Amir 111Department of Mathematics, Bar Ilan University, Israel. Email:
<EMAIL_ADDRESS>Itai Arieli222Faculty of Industrial Engineering and
Management, Technion. Email<EMAIL_ADDRESS>Galit Ashkenazi-
Golan333School of Mathematical Sciences, Tel-Aviv University. Email:
<EMAIL_ADDRESS>Ron Peretz444Department of Economics, Bar Ilan
University, Israel. Email<EMAIL_ADDRESS>
###### Abstract

We study a model of opinion exchange in social networks where a state of the
world is realized and every agent receives a zero-mean noisy signal of the
realized state. It is known from Golub and Jackson [12] that under the DeGroot
[5] dynamics agents reach a consensus which is close to the state of the world
when the network is large. The DeGroot dynamics, however, is highly non-robust
and the presence of a single ‘bot’ that does not adhere to the updating rule,
can sway the public consensus to any other value. We introduce a variant of
the DeGroot dynamics which we call _ $\varepsilon$-DeGroot_. The
$\varepsilon$-DeGroot dynamics approximates the standard DeGroot dynamics and
like the DeGroot dynamics it is Markovian and stationary. We show that in
contrast to the standard DeGroot dynamics, the $\varepsilon$-DeGroot dynamics
is highly robust both to the presence of bots and to certain types of
misspecifications.

##  1 Introduction

Social networks play a very important role as a conduit of information.
Individuals repeatedly interact with their peers and adjust the choices they
make by responding to their observed behavior. One explanation of such
adaptive behavior is informational effects; i.e., individuals infer the
underlying information that gives rise to the observed behavior and based on
this _social learning_ change their own behavior (See, e.g., [2], [10], [1]).
Making fully rational inferences about the private information of _all_ agents
given the observed-behavior, however, is known to be conceptually and
computationally complex.555See, e.g., [13]. In practice, agents are often
unaware of the structure of the network. This unawareness prevents the agents
from tracing the information path in an environment of repeated interaction.

In order to overcome the complexity of rational decision making, an
alternative approach has been developed. The underling assumption of the
alternative approach is that individuals follow a particular heuristics when
revising their opinion. The most prominent such approach is the one proposed
by DeGroot [5] and brought into the economics literature by DeMarzo et al.
[6]. For a related work that studies belief exchange in networks see [15].

The DeGroot framework comprises a social network which is represented by a
(finite) graph. The agents of the graph represent agents who are in direct
relations with their neighbors in the graph. The true state of the world is
represented by a real number $\mu$. At each time period $t\geq 0$ each agent
$i$ obtains a subjective opinion regarding the state of the world
$A_{i,t}\in\mathbb{R}$. A common assumption is that the initial opinions
$A_{i,0}=\mu+\varepsilon_{i}$, where the $\\{\varepsilon_{i}\\}_{i\in V}$ are
i.i.d. with expectation zero. As time progresses, the agents simultaneously
revise their opinions while relying only on the opinions of their neighbors.
The DeGroot updating rule asserts that an agent updates her opinion to be
equal to the average of the opinions of her neighbors.

An important property of the DeGroot updating procedure, as established both
by DeGroot [5] and by Demarzo et al. [6] is that in the long run agents reach
consensus. That is, when the entire population uses the DeGroot heuristics,
agents’ opinions converge to the same value. Moreover, this value is a
weighted average of the initial opinions at time zero. The weights, called the
_measure of centrality_ , are given by the stationary distribution of the
random walk over the underlying network graph.

When the graph is large, one can infer $\mu$ from the initial opinions
$\\{A_{i,0}\\}_{i\in V}$, but no single agent can make such an inference by
herself, since she observes her own opinion and the opinions of her neighbors
only. However, Golub and Jackson [12] demonstrated the following striking
property of the DeGroot dynamics, which they termed _naive learning_. Despite
the simplicity of the DeGroot rule, when the graph is large and no agent is
too central, the agents’ opinions converge to a consensual opinion which is
close to the true state of the world with high probability. This means that
under a mild assumption regarding the network the DeGroot heuristics enables
every agent to trace back the state of the world with high probability by
eliciting the so called _wisdom of the crowd_.

A weakness of the classic DeGroot dynamics as a tool to aggregate private
information is its sensitivity to minor deviations (see Section 2.1). The
source of such deviations may be either malicious agents, who have an
incentive to change the public opinion, or agents who suffer from behavioral
biases. For example, suppose one of the agents does not follow the updating
rule, while all others do. Specifically, say that one of the agents is a
‘bot’; it starts with a certain opinion and never changes it. Running the
DeGroot dynamics with such a bot results in everyone adopting the opinion of
the bot in any finite connected graph (see Lemma 2.2). Another possible
modification of the model is distorted monitoring — the agents do not observe
the exact opinions of their neighbors, but rather a small modification of it.
Say, everyone sees $x+\delta$ when the true opinion is $x$. Then, even if
$\delta$ is very small (yet positive), the resulting limiting opinions of all
of the agents will be $\infty$ regardless of the state of the world.

The core research question we address in this paper is the following: does
there exist a simple boundedly rational heuristics that enables naive learning
which is immune to the above mentioned deviations? We provide a positive
answer to this question in a setting with either a large or a countably
infinite graph of bounded degree.

We introduce a parameterized family of heuristics $\varepsilon$-_DeGroot_
which approximate the DeGroot heuristics as the parameter $\varepsilon>0$ goes
to zero. According to the $\varepsilon$-_DeGroot_ updating rule, whenever an
agent has a revision opportunity and the current average of the opinions of
her neighbors is $y$ (which is the DeGroot updating value), she updates her
current opinion $x$ by projecting it on the interval
$[y-\varepsilon,y+\varepsilon]$. That is, she either does not change her
opinion, if $|x-y|\leq\varepsilon$, or changes it to the closest point to $x$
in $\\{y-\varepsilon,y+\varepsilon\\}$ otherwise.

Our main results show that the $\varepsilon$-DeGroot dynamics leads to
approximate learning while being immune to minor deviations. Specifically, we
say that an agent achieves _$(\delta,\rho)$ -learning_ if her opinion
eventually lies within $\delta$ of the true state of the world with
probability at least $1-\rho$. A dynamics on an infinite graph $G$ satisfies
$(\delta,\rho)$-learning if all but a finite set of agents satisfy
$(\delta,\rho)$-learning.

Our first main result, Theorem 3.1, loosely says that if the graph $G$ is
infinite with a bounded degree and a moderate growth rate666The specific
assumptions on the growth of the graph are detailed in Section 3., then for
every $\delta,\rho>0$ there exists an $\varepsilon>0$ such that the
$\varepsilon$-DeGroot dynamics satisfies $(\delta,\rho)$-learning.
Furthermore, $(\delta,\rho)$-learning continues to hold in the presence of
finitely many bots and when the agents are $0.9\varepsilon$-distorted.

Our second main result, Theorem 3.2, is a generalization of the first main
result to families of graphs. Theorem 3.2 can be viewed as an analogue of the
result of Golub and Jackson [12] who refer to growing families of finite
graphs.

Thus by a slight modification of the standard DeGroot heuristics we offer a
highly robust learning procedure. Not only is the $\varepsilon$-DeGroot
heuristics immune to bots, but it also achieves approximate naive learning
when the agents suffer some bias or systematic errors in deriving their
opinions.

A series of recent papers analyzes the implications of Bayesian agents having
misspecified beliefs about the environment in a social learning model. Bohren
and Hauser [4] provide a general framework of misspecified beliefs and how
they impact social learning outcomes. Frick, Iijima, and Iishi [8] provide
conditions under which learning outcomes are not robust to minimal
misspecifications.777See also Frick, Iijima, and Iishi [9]. Our analysis here
complements the above literature by providing a robust variant of the leading
non-Bayesian social learning rule in a way that is immune to biases which can
arise as misspecifications.

##  2 Model and Preliminaries

We consider a model of opinion exchange in networks similar to that of DeGroot
[5]. A connected graph $G=(V,E)$ (which is either finite or countably
infinite) is given. Each agent $i\in V$ is represented by a vertex in the
graph. Time is discrete. At time $t=0$ a state of the word $\mu\in\mathbb{R}$
is realized according to an unknown distribution $\psi\in\Delta(\mathbb{R})$.
Thereafter, each agent $i$ observes $A_{i,0}=\mu+x_{i}$ where
$\\{x_{i}\\}_{i\in V}$ is a collection of a zero mean bounded (by a constant
$|x_{i}|\leq K$) i.i.d. random variables. For every agent $i$ we let $N_{i}$
be the neighbors of agent $i$ and let $n_{i}=|N_{i}|$. Furthermore, let
$A_{i,t}\in\mathbb{R}$ be the opinion of agent $i$ at time $t\geq 0$. We
assume that there is a parameter $d>0$ such that $n_{i}\leq d$, for all $i\in
V$.

At each time $t>0$ each agent $i$ updates her opinion by the rule

$A_{i,t}=\frac{1}{n_{i}}\sum_{j\in N_{i}}A_{j,t-1}:=\mathrm{Average_{j\in
N_{i}}(A_{j,t-1})}.$

We first provide an analogue of the “naive wisdom of crowds” result of Golub
and Jackson [12] for infinite graphs (see proof in the appendix).

######  Theorem 2.1.

Let $G$ be a connected infinite graph of bounded degree. For every agent $i\in
V$ it holds that $\lim_{t\rightarrow\infty}A_{i,t}=\mu$ almost surely.

Golub and Jackson consider a growing sequence of networks with the _vanishing
influence_ property, i.e., the largest coordinate of the stationary-measure of
the Markov chain induced by the network approaches zero as the network grows.
The assumption of bounded degree applied to a growing sequence of networks
implies the vanishing influence property. Therefore, Theorem 2.1 can be viewed
as an analogue of Golub and Jackson’s result for infinite graphs.

There is, however, a difference between finite graphs and infinite graphs.
When the graph is finite the convergence of $A_{i,t}$ as $t\to\infty$ is
guaranteed888Strictly speaking, it is guaranteed that the limits
$\lim_{t=0}^{\infty}A_{i,2t}$ and $\lim_{t=0}^{\infty}A_{i,2t+1}$ exist, and
if in addition the graph is not bipartite then the two limits are equal. for
every value of the initial opinions $\\{A_{i,0}\\}_{i\in V}$. For infinite
graphs, there may be initial values under which $A_{i,t}$ oscillates as
$t\to\infty$. A simple consequence of Theorem 2.1 is that the set of such
initial values has zero probability under our assumptions on the distribution
of the initial opinions.

###  2.1 The Fragility of the DeGroot Dynamics

In this section we demonstrate the known fact that in finite networks the
DeGroot model and the wisdom of the crowd result by Golub and Jackson [12] are
highly fragile to the presence of “bots” or “biased” agent. We call an agent a
‘bot’ if it sets its opinion to be constant $A_{i,t}\equiv c$ over time $t$.

######  Lemma 2.2.

Consider a connected finite graph $G=(V,E)$ and a unique bot $i_{0}\in V$ that
sets its opinion to be constant $c$. Then for every agent $i\in V$ it holds
that $\lim_{t\rightarrow\infty}A_{i,t}=c$ almost surely999For completeness, we
provide the proof of this standard result in the appendix..

Thus, in order to achieve the wisdom of the crowd in the standard DeGroot
model, all agents have to comply with the dynamics; even a single bot is
sufficient to dramatically swing the consensus according to its opinion.

Another form of fragility in learning dynamics is that of agents who suffer
from a bias in aggregating others’ opinion. Consider an updating heuristic
$g_{i,t}:\mathbb{R}^{(m+1)(t-1)}\rightarrow\mathbb{R}$, for some agent $i\in
V$ of degree $m=|N_{i}|$ at time period $t>0$. That is, according to the
heuristic $g=\\{g_{i,t}\\}$, agent $i$ is supposed to update her opinion
through

$A_{i,t}=g_{i,t}((A_{j,<t})_{j\in N_{i}\cup\\{i\\}}).$

We say that $i$ suffers from _$\beta$ -distorted monitoring_ (_$\beta$
-monitoring_, for short) with respect to $g$ if at every time period $t>0$

$A_{i,t}=g_{i,t}((A^{\prime}_{j,<t})_{j\in N_{i}\cup\\{i\\}}),$

for some $(A^{\prime}_{j,<t})_{j\in N_{i}\cup\\{i\\}}$, such that for every
$0\leq s<t$,

$|A^{\prime}_{j,s}-A_{j,s}|\leq\begin{cases}\beta&j\in N_{i},\\\
0&j=i.\end{cases}$

Thus, agent $i$ updates her opinion in accordance to $g$ but may perceive some
of the opinions of her neighbors differently than they actually are. For
example, she may add the value $\beta$ to the opinions of her neighbors, or,
vice versa, subtract $\beta$ from the opinions of all of her neighbors. This
special case of $\beta$-monitoring is called _$\beta$ -bias_.

One can easily show that no matter how small $\beta>0$ is, a single agent who
suffers from $\beta$-distorted monitoring with respect to the DeGroot updating
rule is sufficient to sway the public opinion away from the DeGroot consensus
to any other point.

##  3 Main Results

Our main goal is to introduce a robust version of the DeGroot dynamics. We
next introduce a parameter-dependent family of heuristics which we call the
$\varepsilon$-DeGroot dynamics. Consider a time period $t>0$ and an agent $i$
and let $y=\mathrm{Average_{j\in N_{i}}(A_{j,t-1})}$. Under
$\varepsilon$-DeGroot each agent updates her opinion as follows:101010Note
that the opinion of an agent at time $t$ depends on her opinion at time $t-2$
rather than $t-1$. The reason for taking this approach is technical. A natural
question is whether one could rely on $t-1$ as well.

$\displaystyle
A_{i,t}=\left\\{\begin{array}[]{llc}A_{i,t-2}&|A_{i,t-2}-y|\leq\varepsilon,\\\
y+\varepsilon&A_{i,t-2}>y+\varepsilon,\\\
y-\varepsilon&A_{i,t-2}<y-\varepsilon.\end{array}\right.$ (4)

Where, $A_{i,-1}$ is defined arbitrarily. In words: under the
$\varepsilon$-DeGroot heuristics an agent reverts to her previous opinion
whenever the distance between the previous opinion and the avaregae of the
current opinions of her neighbors, $y=\mathrm{Average_{j\in
N_{i}}(A_{j,t-1})}$, is at most $\varepsilon$. If, on the other hand, $y$ is
more than $\varepsilon$ away from the agent’s previous opinion, then the agent
sets her new opinion as the projection of her previous opinion on the interval
$[y-\varepsilon,y+\varepsilon]$.

The $\varepsilon$-DeGroot dynamics is similar to the standard DeGroot dynamics
in the following respects. Firstly, by definition, it holds that when an agent
$i$ updates her opinion at time $t$, $|A_{i,t}-\mathrm{Average_{j\in
N_{i}}(A_{j,t-1})}|\leq\varepsilon.$ Thus, the updated opinion of every agent
lies within a distance of at most $\varepsilon$ of the value it would have
under the standard DeGroot updating rule. Secondly, similarly to the DeGroot
updating rule, the $\varepsilon$-DeGroot updating rule is also stationary and
Markovian. Namely, when an agent updates her opinion, she bases her new
opinion only on the current opinion vector of her neighbors, and not on the
past opinions or the calendar time.

To obtain our main results we make an assumption on the growth rate of the
underlying network. To formulate this assumption we need the following
definitions. We say that a graph $G=(V,E)$ is _majorized by_ a function
$f\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$, if for every $i\in V$ and every
$r\in\mathbb{N}$ the ball of radius $r$ around $i$, $B(i,r)\subset V$,
satisfies $|B(i,r)|\leq f(r)$. We say that $f$ has a _stretched exponential_
growth rate if there exist $\alpha>0$ and $r_{0}>0$, such that
$f(r)>\exp(r^{\alpha})$, for all $r\geq r_{0}$. We say that $f$ has a
_stretched sub-exponential_ growth rate if for all $\alpha>0$, there exists
$r_{0}>0$, such that $f(r)<\exp(r^{\alpha})$, for all $r\geq r_{0}$. We say
that a graph has a stretched sub-exponential growth rate if it is majorized by
a stretched sub-exponential function.

######  Definition 3.0.1.

Consider a dynamics $A_{i,t}$ on a graph $G=(V,E)$. We say that $i\in V$
satisfies $(\delta,\rho)$-_learning_ if

$\Pr(\mu-\delta\leq\liminf_{t\rightarrow\infty}A_{i,t}\leq\limsup_{t\rightarrow\infty}A_{i,t}\leq\mu+\delta)\geq
1-\rho.$

We say that the dynamics satisfies $(\delta,\rho)$-_learning_ on $G$ if all
but a finite set of agents satisfy $(\delta,\rho)$-learning.

We can now state our first main result.

######  Theorem 3.1.

Let $G$ be an infinite connected graph of bounded degree and stretched sub-
exponential growth rate. For every $\delta,\rho>0$, there exists
$\varepsilon>0$ such that the $\varepsilon$-DeGroot dynamics satisfies
$(\delta,\rho)$-learning on $G$.

Furthermore, $(\delta,\rho)$-learning on $G$ continues to hold even in the
presence of finitely many bots and when all other agents suffer from
$0.9\varepsilon$-distorted monitoring.

We next take the approach of Golub and Jackson and define learning on a family
of graphs. As before, say that a family of graphs $\mathcal{G}$ is majorized
by a function $f\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$ if every graph
$G\in\mathcal{G}$ is majorized by $f$. We say that $\mathcal{G}$ has a
stretched sub-exponential growth rate, if $\mathcal{G}$ is majorized by a
stretched sub-exponential function. In addition, we say that the family
$\mathcal{G}$ has a bounded degree if there exists $d>0$ such that the degree
of any agent in any graph $G\in\mathcal{G}$ is at most $d$.

######  Definition 3.1.1.

Consider a family of graphs $\mathcal{G}$. Suppose we have a family of
dynamics, one on each graph $G\in\mathcal{G}.$ We say that the family of
dynamics satisfies $(\delta,\rho)$-_learning_ on $\mathcal{G}$ if there exists
a number $n$ such that for every $G\in\mathcal{G}$ all but $n$ agents satisfy
$(\delta,\rho)$-learning.

We are now ready to state our second main theorem which generalizes our first
main result by regarding families of graphs.

######  Theorem 3.2.

Let $\mathcal{G}$ be a family of connected graphs of bounded degree and
stretched sub-exponential growth rate. For every $\delta,\rho>0$, there exists
$\varepsilon>0$ such that the $\varepsilon$-DeGroot dynamics satisfies
$(\delta,\rho)$-learning on $\mathcal{G}$.

Furthermore, $(\delta,\rho)$-learning on $\mathcal{G}$ continues to hold even
in the presence of a bounded number of bots and when all other agents suffer
from $0.9\varepsilon$-distorted monitoring.

##  4 Proof Techniques

Beyond the results themselves, our paper also offers a novel technical
contribution. In this section we outline the technical contribution.

Formally, Theorem 3.1 is a special case of Theorem 3.2 where the family of
graphs consists of a single graph. However, in order to establish Theorems 3.1
and 3.2 we prove Theorem 4.1 which implies them both. We believe that Theorem
4.1 is of independent interest; it asserts that the influence of any bot is
limited to a certain radius around it. Outside that radius, approximate
learning is satisfied.

######  Theorem 4.1.

Let $f\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$ be a stretched sub-exponential
function, $d>0$, and $\delta,\rho>0$. There exist $\varepsilon>0$ and $R>0$
such that the $\varepsilon$-DeGroot dynamics on any connected graph $G$ that
is majorized by $f$, has a degree at most $d$, and a radius at least $R$
satisfies the following:

  1. (i)

every agent $i$ such that $B(i,R)$ does not include a bot satisfies
$(\delta,\rho)$-learning.

  2. (ii)

$(\delta,\rho)$-learning continues to hold even when all agents suffer from
$0.9\varepsilon$-distorted monitoring.

Theorems 3.1 and 3.2 readily follow from Theorem 4.1. We next outline the
proof of Theorem 4.1. The proof is divided into three steps which are
explained next.

###  4.1 Step 1: Convergence of opinions

The first step in the proof of Theorem 4.1 is to establish that the opinions
converge. Our proof of the convergence of opinions relies on a property of the
$\varepsilon$-DeGroot dynamics which we call _robustness_. Recall that the
$\varepsilon$-DeGroot updating rule sets the opinion of a revising agent $i$
at time $t$ to be the projection of $A_{i,t-2}$ on the interval
$I_{t}:=[\mathrm{Average}_{j\in
N_{i}}(A_{j,t-1})-\varepsilon,\mathrm{Average}_{j\in
N_{i}}(A_{j,t-1})+\varepsilon]$. It follows that for any $v\in I_{t}$, we have
$|A_{i,t}-v|\leq|A_{i,t-2}-v|$, or equivalently,
$0\leq(A_{i,t-2}-v)^{2}-(A_{i,t}-v)^{2}$. Furthermore, a simple investigation
of the function $f(x)=(x-v)^{2}$ shows that, setting
$\gamma:=|v-\mathrm{Average}_{j\in N_{i}}(A_{j,t-1})|$ and
$\eta:=2(\varepsilon-\gamma)$, we have

$\eta|A_{i,t}-A_{i,t-2}|\leq\left(A_{i,t-2}-v\right)^{2}-\left(A_{i,t}-v\right)^{2}.$

This motivates the following definition that will play a key role in bounding
the variation of an agent’s opinion over time.

######  Definition 4.1.1.

Let $\gamma,\eta>0$. We say that a dynamics $A_{i,t}$ on a graph $G=(V,E)$ is
_$(\gamma,\eta)$ -robust_ if

$\displaystyle\forall v\in[\mathrm{Average}_{j\in
N_{i}}(A_{j,t-1})-\gamma,\mathrm{Average}_{j\in N_{i}}(A_{j,t-1})+\gamma],$
$\displaystyle\eta|A_{i,t}-A_{i,t-2}|\leq\left(A_{i,t-2}-v\right)^{2}-\left(A_{i,t}-v\right)^{2},$

for every $i\in V$ and $t>0$.

We say that a dynamics is _robust_ , if it is $(\gamma,\eta)$-robust, for some
$\gamma,\eta>0$.

Surprisingly, robustness facilitates a useful sufficient condition for the
convergence of dynamics on graphs of moderate growth rate. The above argument
shows that the $\varepsilon$-DeGroot dynamics is
$(\gamma,2(\varepsilon-\gamma))$-robust, for any $\gamma\in(0,\varepsilon)$.
Another example of a robust dynamics is the majority dynamics (studied, e.g.,
in [17, 11]). The classic DeGroot dynamics is an example of a _non-robust_
dynamics, and indeed, there are initial opinions given which the DeGroot
dynamics diverges (even on slowly growing graphs such as the infinite line
$\mathbb{Z}$).

In order to rigorously state our condition, we first need to fix some
terminology. Let $G=(V,E)$ be a connected graph. We say that $G$ has a sub-
exponential growth rate if for some (every) $i\in V$,
$\lim_{r\to\infty}\frac{\log(|B(i,r)|)}{r}=0$. We say that $A_{i,t}$ is
bounded, if there exists $K>0$ such that $|A_{i,t}|<K$, for every $i\in V$ and
$t\geq 0$. We say that $\\{A_{i,t}\\}_{i\in V,t\in\mathbb{R}_{+}}$
_alternately converges_ if both limits $\lim_{t\to\infty}A_{i,2t}$ and
$\lim_{t\to\infty}A_{i,2t+1}$ exist, for every $i\in V$.

We are now ready to state the sufficient condition for alternate
convergence.111111Note that Proposition 4.1 does not assume stretched sub-
exponential growth rate, but rather just sub-exponential.

######  Proposition 4.1.

Any bounded robust dynamics on a graph of sub-exponential growth rate
alternately converges.

Note that the notion of robustness is of local nature; it refers to any
updating instance separately. Therefore, an updating rule that induces a
$(\gamma,\eta)$-robust dynamics will continue to do so even in the presence of
bots, since never changing one’s opinion is $(\gamma,\eta)$-robust. Dealing
with distorted monitoring requires further considerations that will be
subsequently explained in Section 4.3.

The proof of Proposition 4.1 is established using tools that have been
developed by Ginosar and Holzman [11] and Tamuz and Tessler [17]. For every
agent $i$ we construct a Lyaponov function $L_{i}(t)$ which is a function of
$(A_{j,t+\iota})_{j\in V,\iota=0,1}$ the opinions at times $t$ and $t+1$. The
function $L_{i}(t)$ has the following properties: (i)
$L_{i}(t)\in\mathbb{R}_{+}$, (ii) whenever at least one agent changes her
opinion the function decreases, (iii) every time the opinion of agent $i$
changes by $x$ the function $L_{i}(t)$ decreases by at least $\eta x$
(specifically, $L_{i}(t-1)-L_{i}(t)\geq\eta|A_{i,t-1}-A_{i,t+1}|$). This shows
in particular that the variation of $A_{i,2t+\iota}$ (as a function of $t$) is
finite, and therefore, $A_{i,2t+\iota}$ converges as $t\to\infty$.

###  4.2 Step 2: Approximate learning

The second part of the proof of Theorem 4.1 shows that approximate learning
occurs. Namely, the limiting opinion of any agent who is sufficiently far from
any bot is close to the true state of the world, $\mu$, with probability close
to one. As in the first part of the proof, dealing with distorted monitoring
is deferred to Section 4.3.

In addition to robustness, the following two properties of the
$\varepsilon$-DeGroot dynamics will play a significant role in the proof:
_monotonicity_ and _$\varepsilon$ -averaging_.

######  Definition 4.1.2.

We say that an updating rule is _monotonic_ if whenever an agent $i$ receives
a revision opportunity at time $t$, the updated opinion $A_{i,t}$ is a
monotonic function of $i$’s private history $(A_{j,s})_{j\in
N_{i}\cup\\{i\\},s<t}.$

######  Definition 4.1.3.

We say that a dynamics is $\varepsilon$-_averaging_ if whenever an agent $i$
receives a revision opportunity at time $t$, the updated opinion $A_{i,t}$
satisfies $|A_{i,t}-\mathrm{Average}(A_{j,t-1})_{j\in N_{i}}|\leq\varepsilon.$

We draw the outline of the proof. Fix a agent $i$ and consider the dynamics of
$A_{i,t}$ induced by the $\varepsilon$-DeGroot updating rule. The analysis is
divided into two stages. Up to some time $T$ (that has to be carefully
determined) and from time $T$ onward.

Up to time $T$, we compare $A_{i,t}$ to the standard DeGroot dynamics
$B_{i,t}$. The two dynamics are coupled via sharing the same initial opinions.
On the one hand, monotonicity and $\varepsilon$-averaging guarantee that
$|A_{i,T+\iota}-B_{i,T+\iota}|$ is small with probability close to one (as
long as $T$ is not too large, for $\iota=0,1$). On the other hand, analysis of
the DeGroot dynamics shows that $B_{i,T+\iota}$ is close to $\mu$ with
probability close to one (as long as $T$ is large enough). By carefully
choosing $T$, we guarantee that both hands hold, and thus, $A_{i,T+\iota}$ is
close to $\mu$ with probability close to one.

It remains to verify that from time $t=T$ onward $A_{i,t}$ does not change
much. To this end, we slightly modify $A_{T+\iota}=(A_{j,T+{\iota}})_{j\in V}$
upwards and downwards to obtain $A^{\prime}_{T+\iota}\leq A_{T+\iota}\leq
A^{\prime\prime}_{T+\iota}$ such that
$|A^{\prime}_{i,T+\iota}-A^{\prime\prime}_{i,T+\iota}|$ is small with
probability close to one. In addition, $A^{\prime}_{T+\iota}$ and
$A^{\prime\prime}_{T+\iota}$ are defined so that the respective Lyapunov
functions $L_{i}^{\prime}(T)$ and $L_{i}^{\prime\prime}(T)$ are small with
probability close to one. At times $t>T$, we define $A^{\prime}_{t}$ and
$A^{\prime\prime}_{t}$ by assuming the $\varepsilon$-DeGroot updating rule.
The monotonicity property implies that $A^{\prime}_{i,t}\leq A_{i,t}\leq
A^{\prime\prime}_{i,t}$, for any $t\geq T$; therefore the limits

$\displaystyle Z_{i}$
$\displaystyle=\lim_{t\to\infty}(A_{i,2t+\iota})_{\iota=0,1},$ $\displaystyle
Z^{\prime}_{i}$
$\displaystyle=\lim_{t\to\infty}(A^{\prime}_{i,2t+\iota})_{\iota=0,1},\text{
and}$ $\displaystyle Z^{\prime\prime}_{i}$
$\displaystyle=\lim_{t\to\infty}(A^{\prime\prime}_{i,2t+\iota})_{\iota=0,1}$

satisfy $Z_{i}^{\prime}\leq Z_{i}\leq Z_{i}^{\prime\prime}$ (the existence of
the limits is guaranteed by Proposition 4.1). The same argument as in the
proof of Proposition 4.1 implies that the variations of
$A^{\prime}_{i,2t+\iota}$ and $A^{\prime\prime}_{i,2t+\iota}$ are proportional
to the respective values of the Lyapunov functions $L_{i}^{\prime}(T)$ and
$L_{i}^{\prime\prime}(T)$. Consequently, $Z^{\prime}_{i}$ and
$Z^{\prime\prime}_{i}$ are close to $(A^{\prime}_{i,T+\iota})_{\iota=0,1}$ and
$(A^{\prime\prime}_{i,T+\iota})_{\iota=0,1}$ respectively. Since
$(A_{i,T+\iota})_{\iota=0,1}$ is close to $(\mu,\mu)$ with probability close
to one, so are $(A^{\prime}_{i,T+\iota})_{\iota=0,1}$ and
$(A^{\prime\prime}_{i,T+\iota})_{\iota=0,1}$, and hence $Z^{\prime}_{i}$ and
$Z^{\prime\prime}_{i}$ are close to $(\mu,\mu)$; therefore so is $Z_{i}$, as
desired.

###  4.3 Step 3: Distorted monitoring

We next show that our results continue to hold even in the presence of
$\beta$-distorted monitoring (where $\beta=0.9\varepsilon$). The above proof
of the special case of Theorem 4.1 where $\beta=0$ (without distortion) relies
on the three key properties of the $\varepsilon$-DeGroot dynamics: (i)
monotonicity, (ii) approximate averaging, (iii) robustness. In fact, any
updating rule that satisfies these properties induces approximate learning
(the formal statement appears in Theorem 5.2).

Unfortunately, while the $\varepsilon$-DeGroot updating rule with
$\beta$-distorted monitoring still satisfies (ii) and (iii), it no longer
satisfies (i). Therefore, our proof does not apply to it directly. In order to
overcome this difficulty, we consider two special cases of $\beta$-distorted
monitoring that do preserve monotonicity. These special cases are the two
extremes of distorted monitoring: the positive and the negative $\beta$-biased
monitoring. Under the positive $\beta$-biased monitoring agents overestimate
the opinions of their neighbors, namely, they perceive them as $\beta$ higher
than their actual value. Similarly, negative $\beta$-biased agents
underestimate the opinions of their neighbors by $\beta$.

Let $A_{i,t}$ be an $\varepsilon$-DeGroot dynamics with $\beta$-distorted
monitoring on a graph that satisfies the conditions of Theorem 4.1. We couple
$A_{i,t}$ with the negative and the positive $\beta$-biased dynamics,
$A^{-}_{i,t}$ and $A^{+}_{i,t}$, by sharing the same initial values. By the
monotonicity property, we have $A^{-}_{i,t}\leq A_{i,t}\leq A^{+}_{i,t}$, for
every agent $i$ and time $t\geq 0$. Since $A^{-}_{i,t}$ and $A^{+}_{i,t}$
satisfy (i)-(iii) they both satisfy approximate learning, and therefore, so
does $A_{i,t}$.

###  4.4 Generalization

As mentioned above, our proof is more general than the statement of Theorems
3.1, 3.2, and 4.1. We identify general conditions under which approximate
learning is satisfied. Namely, any updating rule that satisfies monotonicity,
approximate averaging, and robustness induces approximate learning.

An example of a different dynamics that fits into our framework is a
discretized version of the DeGroot dynamics which we call _granular DeGroot_.
Let $W$ be a finite set of real numbers. The _$W$ -granular DeGroot_ dynamics
is defined as follows. At time $0$, $A_{i,0}\in W$, for all $i\in V$. At time
$t>0$, we define $A_{i,t}$ to be the nearest element to
$\mathrm{Average}_{j\in N_{i}}(A_{j,t-1})$ in $W$. In case of a tie between
two alternatives, the one which is closer to $A_{i,t-2}$ is chosen (where
$A_{i,-1}\in W$ is defined arbitrarily). The reason for choosing this tie-
breaking rule is that it satisfies both monotonicity and robustness.

##  5 A general framework

In this section we present a general framework within which our main results
hold. The general framework encompasses any updating rule that satisfies the
three properties (i) monotonicity, (ii) $\varepsilon$-averaging, and (iii)
$(\gamma,\eta)$-robustness. Such an updating rule is called
_$(\varepsilon,\gamma,\eta)$ -robust_.

We first provide a concentrated list of notations and other conventions that
will be used in the statement of the general results, and subsequently during
their proofs.

###  5.1 List of notations

  * •

The social network is a connected graph denoted by $G=(V,E)$.

  * •

The neighbours of agent $i$ is the set $N_{i}$ and $(i):=\\{i\\}\cup N_{i}$.

  * •

The opinion of agent $i\in V$ at time $t\geq 0$ is denoted $A_{i,t}$.

  * •

By conditioning on the state of the world $\mu$ and re-scaling the opinions,
we assume w.l.o.g. that $A_{i,t}\in[0,1]$, for all $i\in V$ and $t\geq 0$.
Unless otherwise specified, we assume that $\\{A_{i,0}\\}_{i\in V}$ are i.i.d.
with expectation $\mu$.

  * •

The set of all possible histories is denoted $\mathcal{H}$. Formally,
$\mathcal{H}$ is defined as the set of all functions $A\colon
V\times\mathbb{Z}_{+}\to[0,1]$.

  * •

Each agent $i$ sees only $i$’s own opinion and those of $i$’s neighbours. For
a history $A\in\mathcal{H}$ and agent $i$ and time $t>0$, the restriction of
$A$ to $(i)\times\\{0,\ldots,t-1\\}$ is denoted $A_{(i),<t}$. The set of all
_private histories of agent $i$ up to time $t$_ is denoted
$\mathcal{H}_{(i),<t}:=\\{A_{(i),<t}:A\in\mathcal{H}\\}$.

  * •

At time $t>0$ each agent $i$ updates her opinion according to an _updating
function_ $g_{i,t}\colon\mathcal{H}_{(i),<t}\to[0,1]$. Namely,
$A_{i,t}=g_{i,t}(A_{(i),<t})$. An _updating rule_ is a scheme of updating
functions $\\{g_{i,t}\\}_{i\in V,t>0}$.

  * •

We consider two specific updating rules defined next.

    * –

The $\varepsilon$-DeGroot updating rule is defined as follows. Suppose
$A_{i,t-2}=x$ and $\mathrm{Average}_{j\in N_{i}}(A_{j,t-1})=y$ (where
$A_{i,-1}$ is defined arbitrarily). Then,

$A_{i,t}=g_{\varepsilon}(x,y):=\left\\{\begin{array}[]{llc}x&|x-y|\leq\varepsilon\\\
y+\varepsilon&x>y+\varepsilon\\\
y-\varepsilon&x<y-\varepsilon\end{array}\right.$

    * –

The $0$-DeGroot updating rule is also called the _DeGroot_ updating rule and
it is denoted by $g_{D}$. Explicitly,
$g_{D}\colon\mathcal{H}_{(i),<t}\to[0,1]$ is defined by

$g_{D}(A_{i,<t}):=\mathrm{Average_{j\in N_{i}}(A_{j,t-1})}.$

  * •

Let $W$ be a finite subset of $[0,1]$. The $W$-granular DeGroot ($W$-DeGroot
for short) updating function of agent $i$ at time $t>0$ is defined by first
projecting the values of $\\{A_{j,t-1}\\}_{j\in N_{i}}$ on $W$, then taking
their average, and then projecting the result on $W$. Formally, define the
projection function $\pi\colon W\times[0,1]\to W$ by setting $\pi(w,x)$ to be
the closest element to $x$ in $W$, where ties between two alternatives are
broken in favor of the one which is closer to $w$. The $W$-granular DeGroot
updating rule is defined by

$A_{i,t}=\pi(A_{i,t-2},\mathrm{Average}_{j\in N_{i}}(\pi(0,A_{j,t-1}))),$

where $A_{i,-1}$ is defined arbitrarily.

The choice of $0$ in the inner projection is arbitrary. In fact, $0$ could
have been replaced by any constant, or more generally, any monotonic function
of $A_{(i),<t}$.

###  5.2 Generalized results

######  Definition 5.0.1.

Let $\varepsilon,\gamma,\eta>0$. An updating rule $\\{g_{i,t}\\}_{i\in V,t>0}$
is _$(\varepsilon,\gamma,\eta)$ -robust_ if the following conditions are
satisfied for every $i\in V$ and $t>0$.

  1. (A1)

_Monotonicity._ For any
$A_{(i),<t},A_{(i),<t}^{\prime}\in\mathcal{H}_{(i),<t}$ such that $\forall
j,\leavevmode\nobreak\ \forall s<t,\leavevmode\nobreak\ A_{j,s}\leq
A^{\prime}_{j,s}$,

$g_{i,t}(A_{(i),<t})\leq g_{i,t}(A^{\prime}_{(i),<t}).$

  2. (A2)

_Approximate averaging_. For every $A_{(i),<t}\in\mathcal{H}_{(i),<t}$,

$|g_{i,t}(A_{(i),<t})-g_{D}(A_{(i),<t})|\leq\varepsilon.$

  3. (A3)

_Robustness_. $\forall A_{(i),<t}\in\mathcal{H}_{(i),<t}$, let

$\displaystyle g_{D}$ $\displaystyle=g_{D}(A_{(i),<t}),$ $\displaystyle
g_{i,t}$ $\displaystyle=g_{i,t}(A_{(i),<t}).$

The third condition states that $\forall v\in[g_{D}-\gamma,g_{D}+\gamma]$,

$\eta|g_{i,t}-A_{i,t-2}|\leq\left(A_{i,t-2}-v\right)^{2}-\left(g_{i,t}-v\right)^{2}.$

A dynamics induced by an $(\varepsilon,\gamma,\eta)$-robust updating rule is
called an _$(\varepsilon,\gamma,\eta)$ -robust dynamics_.

Note that, assuming undistorted monitoring, an updating rule that satisfies
(A2) induces an $\varepsilon$-averaging dynamics, and an updating rule that
satisfies (A3) induces a $(\gamma,\eta)$-robust dynamics. Also, note that
Condition (A3) does not impose any condition on the initial opinions
$\\{A_{i,0}\\}_{i\in V}$. Furthermore, the predicate of Condition (A3) is
defined on any history in $\mathcal{H}$, not just those induced by some
updating rule. We need to consider inconsistent histories due to the
definitions of distorted monitoring. Also, note that Conditions (A2) and (A3)
can only be satisfied if $\gamma\leq\varepsilon$.

######  Definition 5.0.2.

For $i\in V$, we define $Z_{i}\in[0,1]\times[0,1]$ as long as the following
limit exists,

$Z_{i}:=(\lim_{t\to\infty}A_{i,2t+\iota})_{\iota=0,1}.$

The following theorem says that $Z_{i}$ is well defined under Condition (A3).

######  Theorem 5.1.

Let $G=(V,E)$ be a graph of sub-exponential growth rate. For any updating rule
$g=\\{g_{i,t}\\}_{i\in V,t>0}$ that satisfies Condition (A3) w.r.t. some
$\gamma,\eta>0$, and any $\beta\in[0,\gamma)$ , the $\\{Z_{i}\\}_{i\in V}$
induced by $g$ with $\beta$-distorted monitoring, and possibly with bots, are
well defined given any initial values $\\{A_{i,0}\\}_{i\in V}$.

The next theorem sets conditions under which $Z_{i}$ is close to $(\mu,\mu)$
with probability close to one.

######  Theorem 5.2.

For any $d,\varepsilon,\gamma,\eta,\delta>0$, $\beta\in[0,\gamma)$ and
stretched sub-exponential function $f\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$,
there exist positive numbers $R=R(\varepsilon,\gamma,\eta,d,\delta,f,\beta)$,
$\rho=\rho(\varepsilon,\gamma,\eta,d,\delta,f,\beta)$, such that any
$(\varepsilon,\gamma,\eta)$-robust dynamics on a bounded $d$-degree graph
$G=(V,E)$ majorized by $f$, $\beta$-monitoring, and either with or without
bots satisfies the following property:

If the radius of $G$ is at least $R$ and the distribution of the initial
opinions $A_{0}$ is i.i.d. with expectation $\mu$, then for every $i\in V$
which is at least $R$ away from any bot (if there are bots),

$\Pr(\|Z_{i}-(\mu,\mu)\|>\delta)\leq\rho.$

Furthermore, for fixed $d$, $\delta$ and $f$, and any $K,k>1$,

$\sup_{\begin{subarray}{c}\eta,\gamma,\beta\,:\\\
\eta,(\gamma-\beta)\geq\varepsilon^{K}\end{subarray}}\rho(\varepsilon,\gamma,\eta,d,\delta,f,\beta)\xrightarrow[\varepsilon\to
0^{+}]{}0.$

The proofs of Theorems 5.1 and 5.2 are given in the next two sections.

##  6 Proof of Theorem 5.1

Theorem 5.1 is purely combinatorial. There is no probability involved. The
results hold for any initial opinions $A_{i,0}$, and Condition (A3) can be
assumed with respect to any $\gamma\in(0,1)$ and $\eta>0$. The mathematical
argumentation follows a path paved by Durrett & Steif [7] and by Holzman &
Ginosar [11] and Tamuz & Tessler [17] who worked on the majority dynamics.
According to the majority dynamics an agent updates its binary opinion to
match the majority of the opinions of its neighbours. Since the majority
dynamics is a $\\{0,1\\}$-granular DeGroot dynamics, it satisfies Condition
(A3). Therefore, Theorem 5.1 generalizes the convergence results of the above
mentioned papers.

The proof of Theorem 5.1 follows from the conjunction of Proposition 4.1 and
the following lemma.

######  Lemma 6.1.

Let $g$ be an updating rule that satisfies Condition (A3) w.r.t.
$\gamma,\eta>0$ and let $\beta\in[0,\gamma)$. Then, the dynamics induced by
$g$ with $\beta$-monitoring and either with or without bots is
$(\gamma-\beta,\eta)$-robust.

###### Proof of Lemma 6.1.

Let $g$ be an updating rule that satisfies Condition (A3) w.r.t.
$\eta,\gamma>0$, and let $\beta\in[0,\gamma)$. We may assume w.l.o.g. that
there are no bots. Indeed, if there are bots, say $i_{0}\in V$ is a bot, we
can modify $g_{i_{0},t}$ so that $g_{i_{0},t}(A_{(i_{0}),<t}):=A_{i_{0},0}$,
for all $t\geq-1$ and assume that $i_{0}$ is no longer a bot. The modified
updating rule is $(\gamma,\eta)$-robust while inducing the same dynamics as if
$i_{0}$ were a bot.

Define a predicate

$\mathcal{P}(x,y,v)\quad\Leftrightarrow\quad\eta|y-x|\leq(y-v)^{2}-(x-v)^{2}.$

Let $A\in\mathcal{H}$ be the history induced by $g$ with $\beta$-monitoring.
Let $i\in V$ and $t>0$ be arbitrary. Denote $g_{D}:=g_{D}(A_{(i),<t})$. We
have to show that

$\displaystyle\begin{split}&\mathcal{P}(A_{i,t},A_{i,t-2},v),\\\ &\forall
v\in[g_{D}-(\gamma-\beta),g_{D}+(\gamma-\beta)].\end{split}$ (5)

Let $A^{\prime}_{(i),<t}$ be the $\beta$-distorted version of $A_{(i),<t}$
such that $A_{i,t}=g_{i,t}(A^{\prime}_{(i),<t})$. Denote
$g^{\prime}_{D}:=g_{D}(A^{\prime}_{(i),<t})$. Since
$A^{\prime}_{i,t-2}=A_{i,t-2}$,

$\mathcal{P}(A_{i,t},A_{i,t-2},v)\quad\Leftrightarrow\quad\mathcal{P}(g(A^{\prime}_{(i),<t}),A^{\prime}_{i,t-2},v),$

which holds for every $v\in[g^{\prime}_{D}-\gamma,g^{\prime}_{D}+\gamma]$,
since $g$ satisfies Condition (A3) w.r.t. $\eta$ and $\gamma$.

Since $|g^{\prime}_{D}-g_{D}|\leq\beta$,

$[g_{D}-(\gamma-\beta),g_{D}+(\gamma-\beta)]\subset[g^{\prime}_{D}-\gamma,g^{\prime}_{D}+\gamma],$

which implies (5). ∎

The main tool utilized in the proof of Proposition 4.1 is a Lyapunov function
defined in the next couple of paragraphs. For a graph $G=(V,E)$, an agent
$i\in V$ and an edge $e\in E$ we denote $d(i,e)$ the distance between $i$ and
$e$ in the graph. For $r\in(0,1)$ we define:

$M_{i}(r)=\sum_{e\in E}r^{d(i,e)}.$

The following lemma relates the growth rate of $G$ to the growth rate of
$M_{i}(r)$ as a function of $1/(1-r)$.

######  Lemma 6.2.

If a connected graph $G=(V,E)$ has a sub-exponential growth rate then
$M_{i}(r)<\infty$, for every $r\in(0,1)$ and $i\in V$. Furthermore, for any
stretched sub-exponential function $f\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$
there exists a stretched sub-exponential function
$g\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$, such that for any graph $G=(V,E)$
that is majorized by $f$, it holds that $\sup_{i\in V}M_{i}(r)\leq
g(1/(1-r))$, for every $r\in(0,1)$.

###### Proof.

Let $i\in V$ and $f\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$ a non-decreasing
function such that $|B(i,\cdot)|\leq f(\cdot)$. We think of $f$ as a sub-
exponential function in the first part of the lemma and a stretched sub-
exponential function in the second part of the lemma. Let $r\in(0,1)$ and
$k(r)=\lceil 1/(1-r)\rceil$. Since $r^{k(r)}\leq 1/e$, we have

$M_{i}(r)=\sum_{e\in E}r^{d(i,e)}\\\
<d|B(i,k(r))|+\frac{1}{e}d|B(i,2k(r))|+\ldots+\frac{1}{e^{n-1}}d|B(i,nk(r))|+\ldots\\\
\leq de\left(\sum_{n=1}^{\infty}\frac{f(kn)}{e^{n}}\right).$ (6)

If $f$ is sub-exponential, then $f(kn)<e^{\frac{1}{2}n}$, for every $n$ large
enough. Therefore, the tail of the series on the right-hand side of (6) is
dominated by a convergent geometric series, and therefore, $M_{i}(r)<\infty$.
This proves the first part of the lemma.

In order to prove the second part of the lemma it is sufficient to prove that
the right-hand side of (6) is a stretched sub-exponential function of $k$,
assuming that $f$ is stretched sub-exponential. Namely, it is sufficient to
show that

$\sum_{n=1}^{\infty}\frac{f(kn)}{e^{n}}$

is a stretched sub-exponential function of $k$, whenever $f$ is a non-
decreasing stretched sub-exponential function. In deed, since $f$ is non-
decreasing and

$kn\leq\frac{k^{2}+n^{2}}{2}\leq\max\\{k^{2},n^{2}\\},$

we have

$f(kn)\leq f(\max\\{k^{2},n^{2}\\})\leq f(k^{2})+f(n^{2}).$

Hence,

$\sum_{n=1}^{\infty}\frac{f(kn)}{e^{n}}\leq
f(k^{2})\sum_{n=1}^{\infty}\frac{1}{e^{n}}+\sum_{n=1}^{\infty}\frac{f(n^{2})}{e^{n}}.$

This completes the proof of the second part of the lemma since the function
$f(k^{2})$ is stretched sub-exponential being a composition of a polynomial
and a stretched sub-exponential function, and
$\sum_{n=1}^{\infty}\frac{f(n^{2})}{e^{n}}$ is a finite constant since
$f(n^{2})$ is sub-exponential in $n$. ∎

For every edge $(j,k)\in E$ denote $w(j,k):=r^{d(i,(j,k))}$. Following Tamuz
and Tessler [17], given a history $A\in\mathcal{H}$ and $r\in(0,1)$, we define
a Lyapunov function.

######  Definition 6.2.1.

$\displaystyle L_{i,r}(t)$ $\displaystyle:=\sum_{(j,k)\in
E}w(j,k)\left(A_{j,t+1}-A_{k,t}\right)^{2}$ $\displaystyle=\sum_{j\in
V}\sum_{k\in N_{j}}w(j,k)\left(A_{j,t+1}-A_{k,t}\right)^{2}$
$\displaystyle=\sum_{j\in V}\sum_{k\in
N_{j}}w(j,k)\left(A_{j,t}-A_{k,t+1}\right)^{2}.$

Note that every edge $e=(j,k)$ appears twice in the summation: once as $(j,k)$
and the second time as $(k,j)$. Therefore,

$0\leq L_{i,r}(t)\leq 2M_{i}(r).$

For readability, we sometimes suppress $i$ and $r$ and write
$L(t):=L_{i,r}(t)$.

We define

$J^{+}_{j}(t):=\sum_{k\in N_{j}}w(j,k)\left(A_{j,t+1}-A_{k,t}\right)^{2}$

$J^{-}_{j}(t):=\sum_{k\in N_{j}}w(j,k)\left(A_{j,t-1}-A_{k,t}\right)^{2}$

By considering the last two equivalent formulations of Definition 6.2.1, we
have

$L_{i,r}(t)=\sum_{j\in V}J^{+}_{j}(t)=\sum_{j\in V}J^{-}_{j}(t+1).$

It follows that

$L_{i,r}(t)-L_{i,r}(t-1)=\sum_{j\in V}\left(J^{+}_{j}(t)-J^{-}_{j}(t)\right).$
(7)

######  Lemma 6.3.

For every graph $G=(V,E)$, agent $i\in V$, $\gamma\in(0,1)$,
$r\in[1-\gamma,1)$, $\eta>0$, and every $(\gamma,\eta)$-robust
$A\in\mathcal{H}$,

$J^{+}_{j}(t)-J^{-}_{j}(t)\leq 0,$

for all $j\in V$ and $t>0$.

###### Proof.

Fix $j\in V$ and $t>0$. Let $f(x):=\sum_{k\in
N_{j}}w(i,(j,k))\left(x-A_{k,t}\right)^{2}$. The function $f(x)$ is a second-
degree polynomial, whose minimum is attained at $v=\sum_{k\in
N_{j}}q(k)A_{k,t}$ where $q(k):=\tfrac{w(i,(j,k))}{\sum_{\ell\in
N_{j}}w(i,(j,\ell))}.$ Therefore, $f(x)=C_{1}(x-v)^{2}+C_{2}$, for some
$C_{1}>0$ and $C_{2}\in\mathbb{R}$. Let $g_{D}:=\mathrm{Average}_{k\in
N_{j}}(A_{k,t})$. Assumption (A3) implies that if $|g_{D}-v|<\gamma$, then,
$(A_{j,t+1}-v)^{2}-(A_{j,t-1}-v)^{2}\leq 0$. Therefore, since
$J^{+}_{j}(t)-J^{-}_{j}(t)=f(A_{j,t+1})-f(A_{j,t-1})$, it remains to prove
that $|g_{D}-v|<\gamma$.

Let the uniform measure $u\in\Delta(N_{j})$ be
$u(k):=\frac{1}{deg(j)},\leavevmode\nobreak\ \forall k\in N_{j}$. Let
$a(k):=A_{k,t}\leavevmode\nobreak\ \forall k\in N_{j}$. Note that
$g_{D}=\langle u,a\rangle$ and $v=\langle q,a\rangle$.

We show that $||u-q||_{TV}\leq\gamma$. Recall that

$||u-q||_{TV}=\max_{f\colon N_{j}\to[0,1]}\int
f\,\mathrm{d}(u-q)=\sum_{\begin{subarray}{c}k\in N_{j}:\\\
u(k)>q(k)\end{subarray}}[u(k)-q(k)].$

There exists $D$, such that for every $k\in N_{j}$, we have
$d(i,(j,k))\in\\{D,D+1\\}$. Let

$\alpha:={|\\{k\in N_{j}:d(i,(j,k))=D+1\\}|}/{|N_{j}|}.$

Then

$q(k)=\begin{cases}\frac{1}{(1-\alpha(1-r))deg(j)}&\text{if $d(i,(j,k))=D$,
}\\\ \frac{r}{(1-\alpha(1-r))deg(j)}&\text{if $d(i,(j,k))=D+1$. }\end{cases}$

Then, by the second definition of the total variation distance,

$||u-q||_{TV}=\sum_{k\in
N_{j}:d(i,(j,k))=D+1}[u(k)-q(k)]=(1-r)\frac{\alpha(1-\alpha)}{1-\alpha(1-r)}\leq(1-r)\leq\gamma.$

By the first definition of the total variation distance,

$|v-g_{D}|=|\langle u-q,a\rangle|\leq||u-q||_{TV}\leq\gamma.$

∎

Note that in the above proof if $r\geq\frac{1}{2}$, it holds that
$||u-q||_{TV}\leq\tfrac{\gamma}{2}$, since

$(1-r)\frac{\alpha(1-\alpha)}{1-\alpha(1-r)}\leq(1-r)\frac{\alpha(1-\frac{\alpha}{2})^{2}}{1-\frac{\alpha}{2}}\leq\frac{(1-r)}{2}\leq\frac{\gamma}{2}.$

Equation (7) and Lemma 6.3 imply the following corollary.

######  Corollary 6.3.1.

For every graph $G=(V,E)$, agent $i\in V$, $\gamma\in(0,1)$,
$r\in[1-\gamma,1)$, $\eta>0$, and $(\gamma,\eta)$-robust $A\in\mathcal{H}$,
the Lyapunov function $L_{i,r}(t)$ is non-increasing in $t$.

We are now ready to prove Proposition 4.1. We actually prove a slightly
stronger implication than the existence of the designated limit of
$(A_{i,2t+\iota})_{\iota=0,1}$. We prove that the variations of
$A_{i,2t+\iota}$ are finite. The following definition captures the sum of the
two variations.

######  Definition 6.3.1.

For $b\geq a\geq 0$, $A\in\mathcal{H}$, and $i\in V$, we define

$V_{a}^{b}[A_{i,t}]:=\sum_{a<t<b}|A_{i,t+1}-A_{i,t-1}|.$

Note that if $V_{a}^{\infty}[A_{i,t}]<\infty$, for some $a\geq 0$, then
Proposition 4.1 holds.

######  Lemma 6.4.

For any $\gamma\in(0,1)$, $\eta>0$, $(\gamma,\eta)$-robust $A\in\mathcal{H}$,

$V_{a}^{b}[A_{i,t}]\leq\eta^{-1}\left(L_{i,1-\gamma}(a)-L_{i,1-\gamma}(b-1)\right),$

for any $b>a\geq 0$.

Note that Lemmata 6.2 and 6.4 imply Proposition 4.1, since
$L_{i,1-\gamma}(t)<M_{i}(1-\gamma)<\infty$, for any $t>0$, and therefore,
$V_{0}^{\infty}[A_{i,t}]<\eta^{-1}M_{i}(1-\gamma)<\infty$.

###### Proof of Lemma 6.4.

Fix $a<t<b$. Let $g_{D}=\mathrm{Average}_{j\in N_{i}}A_{j,t}$. Let
$f(x)=\sum_{j\in N_{i}}(x-A_{j,t})^{2}=deg(i)(x-g_{D})^{2}+C$, for some
$C\in\mathbb{R}$. Since $J^{+}_{i}(t)=f(A_{i,t+1})$ and
$J^{-}_{i}(t)=f(A_{i,t-1})$, we have

$\left(A_{i,t-1}-g_{D}\right)^{2}-\left(A_{i,t^{+}}-g_{D}\right)^{2}=\frac{1}{deg(i)}\left(J^{-}_{i}(t)-J^{+}_{i}(t)\right).$

By Condition (A3) applied with $v=g_{D}$,

$|A_{i,t+1}-A_{i,t-1}|\leq\eta^{-1}\left(J^{-}_{i}(t)-J^{+}_{i}(t)\right).$

By Lemma 6.3 and Equation (7),

$J^{-}_{i}(t)-J^{+}_{i}(t)\leq\sum_{j\in
V}\left(J^{-}_{j}(t)-J+_{j}(t)\right)=L_{i,1-\gamma}(t-1)-L_{i,1-\gamma}(t).$

Since $L_{i,1-\gamma}(t)$ is a non-increasing, by Corollary 6.3.1, summing
over all $a<t<b$ we get

$V_{a}^{b}[A_{i,t}]\leq\eta^{-1}\sum_{a<t<b}\left(L_{i,1-\gamma}(t-1)-L_{i,1-\gamma}(t)\right)=\eta^{-1}\left(L_{i,1-\gamma}(a)-L_{i,1-\gamma}(b-1)\right).$

∎

##  7 Proof of Theorem 5.2

In this section we prove Theorem 5.2. Namely, we provide conditions under
which the limiting opinion of an agent is close to the expected initial
opinion with probability close to one. The event considered in Theorem 5.2 is
the union of two pairs of symmetric events

$\\{\|Z_{i}-(\mu,\mu)\|>\delta\\}=\bigcup_{\iota=0,1}\left(\\{\lim_{t\to\infty}A_{i,2t+\iota}<\mu-\delta\\}\cup\\{\lim_{t\to\infty}A_{i,2t+\iota}>\mu+\delta\\}\right).$

In our proof we consider one of the four events. Similar proofs apply to the
other three. Theorem 5.2 follows immediately from the following lemma.

######  Lemma 7.1.

Under the conditions, notations, and quantification of Theorem 5.2,

$\Pr(\lim_{t\to\infty}A_{i,2t}<\mu-\delta)<\frac{\rho}{4}.$

The proof of Lemma 7.1 is divided into four sections. In Section 7.1, we
provide a few preliminary facts regarding the standard DeGroot dynamics. In
Sections 7.2 and 7.3, we prove Lemma 7.1 under the assumption of undistorted
monitoring ($\beta=0$). In Section 7.4 we extend the proof to the general
case.

###  7.1 Analysis of the DeGroot dynamics

Let $B_{i,t}$ be the (standard) DeGroot dynamics with i.i.d. initial opinions
with expectation $\mu$. We analyze the speed in which $B_{i,t}$ converges to
$\mu$. We consider the voters model $V_{i,t}$ defined as follows.

$V_{i,0}:=B_{i,0},\quad\forall i\in V.$

At each time period $t>0$, $V_{i,t}$ is chosen randomly by

$\Pr(V_{i,t}=V_{j,t-1})=\frac{1}{|N_{i}|},\quad\forall j\in N_{i},$

where $\\{V_{i,t}\\}_{i\in V}$, are independent conditional on
$\mathcal{H}_{<t}$.

By induction on $t$, one has that $B_{i,t}=E[V_{i,t}|\mathcal{H}_{0}]$. Let
$(R_{t})_{t=0}^{\infty}$ be a standard random walk on $G$ originating in $i$.
Conditional on $\mathcal{H}_{0}$, the distribution of $V_{i,t}$ is identical
to the distribution of $V_{R_{t},0}$ (again, by induction on $t$). Let
$p_{t}=\max\\{\Pr(R_{t}=j):j\in V\\}$. The next lemma shows that

$p_{t}=\mathcal{O}\left(\frac{d}{\sqrt{t}}\right).$ (8)

######  Lemma 7.2.

There exists a global constant $C$, such that for any $t>0$ and $j\in V$ whose
eccentricity is at least $t$ (in particular if $G$ is infinite and connected
then the eccentricity of any vertex is infinite),

$\Pr(R_{t}=j)\leq\frac{deg(j)\cdot C}{\sqrt{t}}.$

###### Proof.

Our proof is based on the method of evolving sets [16]. A different approach
in a slightly different setting can be found in [3].

We prove that the probability that $R_{t}=j$ can be bounded from above by the
probability that a random walk on the integers, beginning at initial state
$deg(j)$, does not hit 0 during the first $t$ periods.

We describe a random walk by a sequence of i.i.d. random functions
$g_{1},g_{2},...$, where $g_{i}:V\rightarrow V$ maps each vertex to a random
neighbour of that vertex using a uniform distribution and independently of the
other vertices.

The random walk $\\{R_{t}\\}_{t=0}^{\infty}$ originating at $R_{0}=i$ is
realized as

$R_{t}=g_{t}\circ g_{t-1}\circ...\circ g_{1}(i).$

Thus, the event $\\{R_{t}=j\\}$ can be expressed as

$\left\\{R_{t}=j\right\\}=\left\\{i\in\left(g_{t}\circ...\circ
g_{1}\right)^{-1}(j)\right\\}=\left\\{i\in g_{1}^{-1}\circ
g_{2}^{-1}\circ...\circ g_{t}^{-1}(j)\right\\}.$

Therefore,

$\Pr(R_{t}=j)\leq\Pr(g_{1}^{-1}\circ g_{2}^{-1}\circ...\circ
g_{t}^{-1}(j)\neq\emptyset).$

For every finite set of vertices $A\subset V$, define $|A|=\sum_{a\in
A}deg(a)$. Since $g_{1},\ldots,g_{t}$ are i.i.d. we get

$\Pr(R_{t}=j)\leq\Pr(|g_{1}^{-1}\circ...\circ
g_{t}^{-1}(j)|>0)=\Pr(|g_{t}^{-1}\circ...\circ g_{1}^{-1}(j)|>0).$

Define a sequence of random sets of vertices $A_{0},A_{1},\ldots\subset V$
recursively by121212The random sets $A_{0},A_{1},\ldots$ are known as
“evolving sets” due to [16].

$A_{0}=\left\\{j\right\\},\leavevmode\nobreak\ A_{k+1}=g_{k+1}^{-1}(A_{k}).$

Define $X_{k}=|A_{k}|$. We have

$E\left[X_{k}|A_{k-1}\right]=\sum_{v\in V}deg(v)\cdot\frac{\\#(N_{v}\cap
A_{k-1})}{deg(v)}=\sum_{v\in V}\\#(N_{v}\cap A_{k-1})=\sum_{a\in
A_{k-1}}deg(a)=|A_{k-1}|.$

Namely, $X_{k}$ is a non-negative Martingale taking integer values, and

$\Pr\left(R_{t}=j\right)\leq\Pr(A_{t}\neq\emptyset)=\Pr\left(X_{1},...,X_{t}>0\right).$

Let $S_{0},S_{1},\ldots$ be a standard symmetric random walk on $\mathbb{Z}$
originating at $S_{0}=deg(j)$. We construct stopping times
$t_{1}<t_{2}<\cdots$ such that for every $n\in\mathbb{N}$

$(X_{1},...,X_{n})\sim(S_{t_{1}},S_{t_{2}},...,S_{t_{n}})$

conditional on the event $\\{X_{n}>0\\}=\\{X_{1},\ldots,X_{n}>0\\}$.

Let $t_{0}=0$. For $k>0$, conditioning on $A_{k-1}$ we construct
$\hat{t}_{k}=t_{k}-t_{k-1}$. Let us represent the martingale increment
$X_{k}-X_{k-1}$ as a sum of independent random variables. Let

$Y_{v}^{k}:=deg(v)\left(\mathbf{1}_{\left(g_{k}(v)\in
A_{k-1}\right)}-\Pr\left(g_{k}(v)\in A_{k-1}\right)\right).$

Then,

$X_{k}-X_{k-1}=\sum_{v\in V}Y_{v}^{k}.$

In the above sum, for all but a finite set of vertices, we have
$Y_{v}^{k}\equiv 0$, and for the rest of the vertices,
$\left\\{Y_{v}^{k}\right\\}_{v}$ are independent, take 2 integer values,
$a_{v}<0<b_{v}$, and $E[Y_{v}^{k}]=0$.

As long as $A_{k-1}$ is non-trivial ($A_{k-1}\neq\emptyset$ and $A_{k-1}\neq
V$), there is at least one vertex $v$ such that $Y_{v}^{k}$ is non-trivial
($Y_{v}^{k}\not\equiv 0$). Each non-trivial $Y_{v}^{k}$ can be implemented by
a stopping time of a symmetric random walk over the integers, that begins at 0
and stops when it gets to one of the two values, $a_{v}$ or $b_{v}$. The sum
$\sum_{v\in V}Y^{k}_{v}$ can be implemented by concatenating such stopping
times obtaining a stopping time which is how we define $\hat{t}_{k}$. Since
not all of the $Y_{v}^{k}$’s are trivial, we have that $\hat{t}_{k}>0$. If
$A_{k-1}=\emptyset$ then define $\hat{t}_{k}=1$. Thus,

$t_{k}=\hat{t}_{1}+\hat{t}_{2}+...+\hat{t}_{k}\geq k.$

Given that $S_{t_{k-1}}>0$, we have $|A_{k-1}|=X_{k-1}=S_{t_{k-1}}$, and
therefore, $A_{k-1}\neq\emptyset$. It follows that $S_{t_{k}}=X_{k}\geq 0$. If
in addition $X_{k}=0$, then $|A_{k}|=\emptyset$ and it must be that all of the
non-trivial $\\{Y_{v}^{k}\\}_{v}$ are negative. In this case
$S_{t_{k-1}+1},\ldots,S_{t_{k}-1}>0$. It follows that

$\Pr\left\\{S_{t_{1}},S_{t_{2}},...,S_{t_{k}}>0\right\\}=\Pr\left\\{S_{0},...,S_{t_{k}}>0\right\\}\leq\Pr\left(S_{0},...,S_{k}>0\right).$

By the reflection principle of symmetric random walks on the integers,

$\Pr\left(S_{0},...,S_{k}>0|S_{0}\right)=\Pr(-S_{0}<S_{k}-S_{0}\leq
S_{0})\leq|S_{0}|\Pr(S_{k}-S_{0}\in\\{0,1\\}).$

By Sterling’s formula $\Pr(S_{k}-S_{0}\in\\{0,1\\})\sim\frac{1}{\sqrt{2\pi
k}}$. The proof of the lemma is concluded by letting $k=t$ and $S_{0}=deg(j)$.
∎

Since $B_{i,t}=\sum_{j\in V}\Pr(R_{t}=j)B_{j,0}$, by Hoeffding’s Inequality
[14], we have

$\Pr(B_{i,t}<\mu-\delta)\leq\exp\left(\frac{-\delta^{2}}{2\sum_{j\in
V}P^{2}(R_{t}=j)}\right)\leq\exp\left(\frac{-\delta^{2}}{2p_{t}}\right).$

By (8), we obtain the following corollary.

######  Corollary 7.2.1.

Let $G$ be a connected graph of degree at most $d$ and radius at least $t$.
Let $B_{i,t}$ be the standard DeGroot dynamics on $G$ with
$\\{B_{i,0}\in[0,1]\\}_{i\in V}$ i.i.d. and $E[B_{i,0}]=\mu$. Then,

$\Pr\left(B_{i,t}<\mu-\frac{\delta}{3}\right)\leq\exp\left(\frac{-C_{0}\delta^{2}\sqrt{t}}{d}\right),$

for all $i\in V$ and some universal constant $C_{0}>0$.

Let $n=\left\lfloor\frac{\delta}{3\varepsilon}-1\right\rfloor$. It follows
that

$\Pr\left(B_{i,n}<\mu-\frac{\delta}{3}\right)\leq\exp\left(-C_{1}\left(\frac{\delta^{2.5}}{d\sqrt{\varepsilon}}\right)\right),$

for some universal $C_{1}>0$. Define

$\rho_{1}=\rho_{1}(d,\varepsilon,\delta):=\exp\left(-C_{1}\left(\frac{\delta^{2.5}}{d\sqrt{\varepsilon}}\right)\right).$

###  7.2 Up to time n

Let $G=(V,E)$ be a graph that satisfies the conditions of Theorem 5.2. Let
$g=\\{g_{i,t}\\}_{i\in V,t\geq 0}$ be an $(\varepsilon,\gamma,\eta)$-robust
updating rule that induces the history $A\in\mathcal{H}$ with undistorted
monitoring.

Let $R_{1}=n$. We will prove Lemma 7.1 with some $R>R_{1}$ . Therefore, until
time $n$, agent $i$ is not influenced by any bot. We couple $A_{j,t}$ with a
DeGroot dynamics $B_{j,t}$ by setting $A_{j,0}=B_{j,0}$, for all $j\in V$. By
Assumptions (A1) and (A2), and by induction on $t$, for any $t\leq n+1$,

$A_{i,t}\geq B_{i,t}-t\varepsilon\geq B_{i,t}-(n+1)\varepsilon\geq
B_{i,t}-\frac{\delta}{3}.$

It follows that

$\Pr\left(A_{i,n}<\mu-\tfrac{2}{3}\delta\right),\Pr\left(A_{i,n+1}<\mu-\tfrac{2}{3}\delta\right)\leq\rho_{1},$
(9)

for any $i$ which is at least $R_{1}$ away from any bot.

###  7.3 From time n onward

For every $j\in V$ and $t\leq n+1$, define

$A^{\prime}_{j,t}=\begin{cases}\mu-\frac{2}{3}\delta&A_{j,t}\geq\mu-\frac{2}{3}\delta,\\\
0&A_{j,t}<\mu-\frac{2}{3}\delta.\end{cases}$

For $t>n+1$, define $A^{\prime}_{j,t}=g_{j,t}(A^{\prime}_{(j),<t})$.

By Theorem 5.1, the limits $z_{i}:=\lim_{t\to\infty}A_{i,2t}$ and
$z^{\prime}_{i}:=\lim_{t\to\infty}A^{\prime}_{i,2t}$ exist. By Condition (A1),
since $A^{\prime}_{\leq n}\leq A_{\leq n}$, we have $A^{\prime}_{t}\leq
A_{t}$, for $t>n$, as well. Therefore, $z^{\prime}_{i}\leq z_{i}$. It follows
that

$\Pr(z_{i}<\mu-\delta)\leq\Pr(z^{\prime}_{i}<\mu-\delta)\leq\\\
\leq\Pr\left(A^{\prime}_{i,n}<\mu-\tfrac{2}{3}\delta\right)+\Pr\left(|z^{\prime}_{i}-A^{\prime}_{i,n}|>\tfrac{1}{3}\delta\right)\leq\\\
\leq\rho_{1}+\Pr\left(V_{n}^{\infty}[A^{\prime}_{i,t}]>\tfrac{1}{3}\delta\right).$

Let $L^{\prime}(t)=L^{\prime}_{i,1-\gamma}(t)$ be the Lyapunov function
defined w.r.t. the history $A^{\prime}$. By Lemma 6.4 and Markov’s Inequality,

$P\left(V_{n}^{\infty}[A^{\prime}_{i,t}]>\tfrac{1}{3}\delta\right)\leq
P\left(L^{\prime}(n)>\tfrac{\eta\delta}{3}\right)\leq\tfrac{3}{\eta\delta}\mathbb{E}[L^{\prime}(n)].$

Summing up, we get

$\Pr(Z_{i}<\mu-\delta)\leq\rho_{1}+\tfrac{3}{\eta\delta}\mathbb{E}[L^{\prime}(n)].$
(10)

It remains to bound $\mathbb{E}[L^{\prime}(n)]$ from above. Let $D_{i}\geq
R\geq R_{1}$ be the distance between $i$ and the nearest bot (if there are no
bots, then $D_{i}=\infty$). By (9),

$\mathbb{E}[L^{\prime}(n)]=\sum_{(j,k)\in
E}(1-\gamma)^{d(i,(j,k))}\mathbb{E}\left[(A^{\prime}_{j,n}-A^{\prime}_{k,n+1})^{2}\right]\leq\\\
\leq\sum_{(j,k)\in
E}(1-\gamma)^{d(i,(j,k))}\left(\Pr(A_{j,n}<\mu-\tfrac{2}{3}\delta)+\Pr(A_{k,n+1}<\mu-\tfrac{2}{3}\delta)\right)\\\
\leq 4\rho_{1}M_{i}(1-\gamma)+d(1-\gamma)^{D_{i}-R_{1}}f(R_{1})\\\ \leq
4\rho_{1}M_{i}(1-\gamma)+d(1-\gamma)^{R-R_{1}}f(R_{1}).$

We get that Lemma 7.1 holds for any pair $\rho,R>0$ that satisfy the relation

$\frac{\rho}{4}=\rho_{1}+\tfrac{3}{\eta\delta}\left(4\rho_{1}M_{i}(1-\gamma)+d(1-\gamma)^{R-R_{1}}f(R_{1})\right).$

If we fix $\delta$, $d$, and $f$, and suppose $\eta^{-1}+\gamma^{-1}\leq
poly(\varepsilon^{-1})$, then we can take

$R=\gamma^{-1.00001},$

and have $\rho\to 0$, as $\varepsilon\to 0$.

This concludes the proof of Lemma 7.1 for the case $\beta=0$.

###  7.4 Distorted monitoring

We turn now to prove Lemma 7.1 for any $\beta\in[0,\gamma)$. For any
$A\in\mathcal{H}$, define $A^{\beta}$, by

$A_{i,t}^{\beta}=\max\\{0,A_{i,t}-\beta\\},\quad\forall i\in V\ \forall t\geq
0.$

For an updating rule $g$, define $g^{\beta}$ by

$g_{i,t}^{\beta}(A_{(i),<t})=g_{i,t}\left(A^{\beta}_{(i),<t}\right).$

By Lemma 6.1, if $g$ is $(\varepsilon,\eta,\gamma)$-robust, then $g^{\beta}$
is $(\varepsilon+\beta,\eta,\gamma-\beta)$-robust. Let $A$ be a dynamics
induced by $g$ with $\beta$-distorted monitoring, and let $A^{\prime}$ be the
dynamics induced by $g^{\beta}$ with the same initial opinions and with
undistorted monitoring. Let
$z^{\prime}_{i}=\lim_{t\to\infty}A^{\prime}_{i,2t}$ and
$z_{i}=\lim_{t\to\infty}A_{i,2t}$. By induction on $t$, Condition (A1) implies
that $A^{\prime}_{i,t}\leq A_{i,t}$, for all $i\in V$ and $t>0$. Therefore,
$z^{\prime}_{i}\leq z_{i}$, for all $i\in V$. By Lemma 7.1, for the case
$\beta=0$,

$\Pr(z_{i}<\mu-\delta)\leq\Pr(z^{\prime}_{i}<\mu-\delta)\leq\tfrac{1}{4}\rho(d,\varepsilon+\beta,\eta,\gamma-\beta,\delta,f,0),$

for any $i$ which is at least
$R(d,\varepsilon+\beta,\eta,\gamma-\beta,\delta,f,0)$ away from any bot.
Therefore, letting

$\displaystyle R(d,\varepsilon,\eta,\gamma,\delta,f,\beta)$
$\displaystyle=R(d,\varepsilon+\beta,\eta,\gamma-\beta,\delta,f,0),$
$\displaystyle\rho(d,\varepsilon,\eta,\gamma,\delta,f,\beta)$
$\displaystyle=\rho(d,\varepsilon+\beta,\eta,\gamma-\beta,\delta,f,0)$

provides the requirements of Lemma 7.1.

This concludes the proof of Lemma 7.1 and therefore, Theorem 5.2, as well.

##  8 Robust dynamics

In this section we show that the $\varepsilon$-DeGroot and the $W$-granular
DeGroot dynamics are robust.

###  8.1 Robustness of approximate DeGroot

The $\varepsilon$-DeGroot updating function for agent $i$ at time $t$,
$g_{i,t}\colon\mathcal{H}_{(i),<t}\to[0,1]$, is defined as follows. Let
$A_{(i),<t}\in\mathcal{H}_{(i),<t}$ and
$g_{D}:=g_{D}(A_{(i),<t})=\mathrm{Average}_{j\in N_{i}}(A_{j,t-1})$. Then,

$g_{i,t}(A_{(i),<t}):=\left\\{\begin{array}[]{llc}A_{i,t-2}&|A_{i,t-2}-g_{D}|\leq\varepsilon,\\\
g_{D}+\varepsilon&A_{i,t-2}>g_{D}+\varepsilon,\\\
g_{D}-\varepsilon&A_{i,t-2}<g_{D}-\varepsilon.\end{array}\right.$

######  Lemma 8.1.

The $\varepsilon$-DeGroot updating function is
$(\varepsilon,\gamma,2(\varepsilon-\gamma))$-robust, for any
$\varepsilon>\gamma>0$ .

###### Proof.

We show that the $\varepsilon$-DeGroot updating function satisfies (A1), (A2)
and (A3).

The $\varepsilon$-DeGroot updating function is monotonic (satisfies (A1))
because it can be presented as the following composition of monotone
functions:

$g_{i,t}(A_{(i),<t})=\min\left\\{\max\left\\{d_{D}-\varepsilon,A_{i,t-2}\right\\},g_{D}+\varepsilon\right\\}.$

The $\varepsilon$-DeGroot updating function satisfies (A2) because each one of
the three cases detailed in the definition satisfies (A2).

Lastly, let $\varepsilon>\gamma>0$ and $\eta=2(\varepsilon-\gamma)$. We show
that condition (A3) is satisfied in each one of the cases of the definition.
In the case that $|A_{i,t-2}-g_{D}|\leq\varepsilon$, (A3) is satisfied
trivially. The other two cases are symmetric. We consider the case
$A_{i,t-2}>g_{D}+\varepsilon$. Let $v\in[g_{D}-\gamma,g_{D}+\gamma]$. Define
$x:=A_{i,t-2}-v$ and $y:=g_{D}+\varepsilon-v$. Condition (A3) spells as

$\eta(x-y)\leq x^{2}-y^{2}.$

Since $x>y$, the above is equivalent to $\eta\leq x+y$. Indeed,

$x+y\geq 2y=2\left(g_{D}+\varepsilon-v\right)\geq
2\left(g_{D}+\varepsilon-(g_{D}+\gamma)\right)=\eta.$

∎

Theorem 5.2 and Lemma 8.1 conclude the proof of Theorem 4.1.

###  8.2 Robustness of Granular DeGroot

Let $W$ be a finite subset of $[0,1]$. Recall the definition of the
$W$-granular DeGroot updating rule. The projection function $\pi\colon
W\times[0,1]\to W$ is defined by setting $\pi(w,x)$ to be the closest element
to $x$ in $W$, where ties between two alternatives are broken in favor of the
one which is closer to $w$. The $W$-granular DeGroot updating function
$g_{i,t}$ is defined by

$g_{i,t}(A_{(i),<t}):=\pi(A_{i,t-2},\mathrm{Average}_{j\in
N_{i}}(\pi(0,A_{j,t-1}))),$

where $A_{i,-1}\in W$ is defined arbitrarily. Note that $g_{i,t}$ is defined
only as long as $A_{i,t-2}\in W$.

Strictly speaking, the $W$-DeGroot updating rule is not robust, therefore, it
does not fit into our framework per-se. However, the histories consistent with
the $W$-DeGroot updating rule do satisfy robustness. The only reason for
demanding robustness w.r.t. to inconsistent histories in the first place, is
to guarantee immunity to distorted monitoring. The way we defined the
$W$-DeGroot updating function already corrects for distorted monitoring via
the projecting the observed opinions on $W$. Therefore, the following lemma
implies that the $W$-DeGroot updating rule satisfies the premises of Theorems
5.1 and 5.2.

######  Lemma 8.2.

For any finite $W\subset[0,1]$ there exist $\varepsilon,\gamma,\eta>0$ such
that for every $i\in V$ and $t>0$, the $W$-granular DeGroot updating function
$g_{i,t}$ satisfies Conditions (A1), (A2), as long as $A_{i,t-2}\in W$, and
(A3) if in addition $A_{j,t-1}\in W$ for every $j\in N_{i}$.

###### Proof.

For $x\in[0,1]$ and $r>0$, let $B(x,r):=[x-r,x+r]\cap[0,1]$. Define

$\varepsilon=\varepsilon(W):=\inf\left\\{r>0:\cup_{w\in
W}B(w,r)=[0,1]\right\\},\quad\text{and}$
$\rho=\rho(W):=\sup\left\\{r>0:B(w,r)\cap
B(w^{\prime},r)=\emptyset,\leavevmode\nobreak\ \forall w,w^{\prime}\in
W,\leavevmode\nobreak\ w\neq w^{\prime}\right\\}.$

We show that there exist $\gamma=\gamma(W)>0$, and $\eta=\eta(W)>0$, such that
$g_{i,t}$ is

  1. (i)

monotonic in its domain,

  2. (ii)

$2\varepsilon$-averaging,

  3. (iii)

$(\gamma,\eta)$-robust as long as $A_{N_{i},t-1}\in W^{N_{i}}$,

for every $i\in V$, and $t>0$.

Condition (i) holds, since $g_{i,t}$ is defined as a composition of monotone
functions. Condition (ii) holds since the projection $\pi(w,x)$ is within
$\varepsilon$ from $x$ for every $w,x$. Therefore, $\mathrm{Average}_{j\in
N_{i}}(\pi(0,A_{j,t-1}))$ is within $\varepsilon$ from
$g_{D}=\mathrm{Average}_{j\in N_{i}}(A_{j,t-1})$. The projection of the
average changes the result by at most an additional $\varepsilon$.

It remains to verify Condition (iii). Recall that the degree of the underlying
graph is denoted by $d$. Let

$W^{d}:=W\cup\frac{W+W}{2}\cup\frac{W+W+W}{3}\cup\cdots\cup\frac{W+W+\cdots+W}{d},$

the set of all possible values for $g_{D}$. We show that Condition (iii) holds
w.r.t. $\gamma=\eta=\rho(W^{d}\cup W^{2})$.

Since we assume that $A_{N_{i},t-1}\in W^{N_{i}}$, we have
$g_{i,t}=g_{i,t}(A_{(i),<t})=\pi(A_{i,t-2},g_{D})$. Let $v\in
B(g_{D},\gamma)$. Defining $x:=A_{i,t-2}-v$ and $y:=g_{i,t}-v$, Condition
(iii) spells as

$\eta|x-y|\leq x^{2}-y^{2}.$

We first claim that either $x=y$, or $|x|-|y|\geq\eta$. To see that, note that
since $g_{i,t}$ is a closest point to $g_{D}$ in $W$ and $A_{i,t-2}\in W$, we
must have either $x=y$, or

$\displaystyle A_{i,t-2}$ $\displaystyle<$
$\displaystyle\frac{A_{i,t-2}+g_{i,t}}{2}$ $\displaystyle<$ $\displaystyle
g_{D},g_{i,t},$ or $\displaystyle A_{i,t-2}$ $\displaystyle>$
$\displaystyle\frac{A_{i,t-2}+g_{i,t}}{2}$ $\displaystyle>$ $\displaystyle
g_{D},g_{i,t}.$

Since all these points are in $W^{d}\cup W^{2}$, they are either equal or
$2\eta$ away one from the next one. The claim follows, since
$|v-g_{D}|\leq\gamma=\eta$.

Now, if $x=y$, Condition (iii) holds trivially. Otherwise, $|x|-|y|\geq\eta$,
and then

$\eta|x-y|\leq\eta(|x|+|y|)\leq(|x|-|y|)(|x|+|y|)=x^{2}-y^{2}.$

∎

## Acknowledgements

We would like to thank Ori Gurel-Gurevich for useful conversations regarding
evolving sets.

## Appendix

###### Proof of Theorem 2.1.

Let $G=(V,E)$ be an infinite connected graph of bounded degree. And let
$B_{i,t}$ be a standard DeGroot dynamics on $G$ with bounded i.i.d. initial
opinions with expectation $\mu$. By scaling we may assume w.l.o.g. that
$B_{i,t}\in[0,1]$. By applying Corollary 7.2.1 to both $B_{i,t}$ and
$1-B_{i,t}$, we get

$\sum_{t=1}^{\infty}\Pr(|B_{i,t}-\mu|>\delta)<\infty,$

for every $i\in V$ and $\delta>0$. By Borel-Cantelli Lemma, we get that
$B_{i,t}$ converges to $\mu$ almost surely, for every $i\in V$. ∎

###### Proof of Lemma 2.2.

Let $G=(V,E)$ be a finite connected graph. And let $B_{i,t}$ be a standard
DeGroot dynamics on $G$ where for all node $i\neq i_{0}$ the variables
$(B_{i,0})_{i\in V,i\neq i_{0}}$ are any initial opinions all agents but agent
$i_{0}$ apply the DeGroot dynamic and $B_{i_{0},t}=c$ is constant at any time.

Let $R_{i,t}$ be a standard random walk started at node $i$ such that node
$i_{0}$ is an absorbing state. That is, when the random walk enters $i_{0}$ it
stays there and never exists. By induction on $t$, for any $i\in V$ one has
that $B_{i,t}=\sum_{j\in V}P(R_{i,t}=j)B_{j,0}$. Since the $G$ is a connected
and finite graph it follows that $\lim_{t\to\infty}P(R_{i,t}=i_{0})=1$ for
every $i\in V$. Therefore $\lim_{t\to\infty}B_{i,t}=B_{i_{0},0}$ for every
node $i$. ∎

## References

  * [1] D Acemoglu, M A Dahleh, I Lobel, and A Ozdaglar.  Bayesian learning in social networks.  Review of Economic Studies, 78:1–34, 2010.
  * [2] Robert J Aumann.  Agreeing to disagree.  The annals of statistics, pages 1236–1239, 1976.
  * [3] Martin T Barlow.  Random walks and heat kernels on graphs.  Bull. Amer. Math. Soc, 56:705–711, 2019.
  * [4] J Aislinn Bohren and Daniel N Hauser.  Social learning with model misspecification: A framework and a characterization.  Technical report, Working Paper, 2020.
  * [5] Morris H DeGroot.  Reaching a consensus.  Journal of the American Statistical Association, 69(345):118–121, 1974.
  * [6] Peter M DeMarzo, Dimitri Vayanos, and Jeffrey Zwiebel.  Persuasion bias, social influence, and unidimensional opinions.  The Quarterly journal of economics, 118(3):909–968, 2003.
  * [7] Richard Durrett and Jeffrey E. Steif.  Fixation results for threshold voter systems.  The Annals of Probability, 21(1):232–247, 1993.
  * [8] Mira Frick, Ryota Iijima, and Yuhta Ishii.  Misinterpreting others and the fragility of social learning.  Econometrica, 88(6):2281–2328, 2020.
  * [9] Mira Frick, Ryota Iijima, and Yuhta Ishii.  Stability and robustness in misspecified learning models.  Technical report, Cowles Foundation Discussion Paper, 2020.
  * [10] John D Geanakoplos and Heraklis M Polemarchakis.  We can’t disagree forever.  Journal of Economic theory, 28(1):192–200, 1982.
  * [11] Yuval Ginosar and Ron Holzman.  The majority action on infinite graphs: strings and puppets.  Discrete Mathematics, 215(1-3):59–71, 2000.
  * [12] Benjamin Golub and Matthew O Jackson.  Naive learning in social networks and the wisdom of crowds.  American Economic Journal: Microeconomics, 2(1):112–49, 2010.
  * [13] Jan Hkazla, Ali Jadbabaie, Elchanan Mossel, and M Amin Rahimian.  Reasoning in bayesian opinion exchange networks is pspace-hard.  In Conference on Learning Theory, pages 1614–1648. PMLR, 2019.
  * [14] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association, 58(301):13–30, 1963.
  * [15] Ali Jadbabaie, Pooya Molavi, Alvaro Sandroni, and Alireza Tahbaz-Salehi.  Non-bayesian social learning.  Games and Economic Behavior, 76(1):210–225, 2012.
  * [16] Ben Morris and Yuval Peres.  Evolving sets, mixing and heat kernel bounds.  Probability Theory and Related Fields, 133(2):245–266, 2005.
  * [17] Omer Tamuz and Ran J Tessler.  Majority dynamics and the retention of information.  Israel Journal of Mathematics, 206(1):483–507, 2015.