Network Structure and Naive Sequential Learning
Krishna Dasaratha Kevin He




Network Structure and Naive Sequential LearningWe thank Daron Acemoglu, J. Aislinn Bohren, Jetlir Duraj, Ben Enke,
Erik Eyster, Drew Fudenberg, Ben Golub, David Laibson, Jonathan Libgober,
Margaret Meyer, Pooya Molavi, Xiaosheng Mu, Matthew Rabin, Ran Spiegler,
Tomasz Strzalecki, Alireza Tahbaz-Salehi, Omer Tamuz, Linh T. T,
Muhamet Yildiz, and three anonymous referees for useful comments.
    Krishna DasarathaHarvard University. Email: 
Kevin HeCalifornia Institute of Technology and University of Pennsylvania.
Email: 
    

First version:     January 17, 2017This version:     February 29, 2020
========================================================================================================================================================================================================================================================================================================================================================================================================



We study a sequential-learning model featuring a network
of naive agents with Gaussian information structures. Agents apply
a heuristic rule to aggregate predecessors' actions. They weigh these
actions according the strengths of their social connections to different
predecessors. We show this rule arises endogenously when agents wrongly
believe others act solely on private information and thus neglect
redundancies among observations. We provide a simple linear formula
expressing agents' actions in terms of network paths and use this
formula to characterize the set of networks where naive agents eventually
learn correctly. This characterization implies that, on all networks
where later agents observe more than one neighbor, there exist disproportionately
influential early agents who can cause herding on incorrect actions.
Going beyond existing social-learning results, we compute the probability
of such mislearning exactly. This allows us to compare likelihoods
of incorrect herding, and hence expected welfare losses, across network
structures. The probability of mislearning increases when link densities
are higher and when networks are more integrated. In partially segregated
networks, divergent early signals can lead to persistent disagreement
between groups.


empty


=10000





§ INTRODUCTION


Consider an environment with a sequence of agents facing the same
decision problem in turn, where each agent considers both her private
information and the behavior of those who came before her in reaching
a decision. When consumers choose between rival products, for instance,
their decisions are often informed by the choices of early customers.
When doctors decide on a treatment for their patients, they consult
best practices established by other clinicians who came before them.
Additionally, when a new theory or rumor is introduced into a society,
individuals are swayed by the discussions and opinions of those who
have already taken a clear stance on the new idea.

A key feature of these examples is that agents observe only the behavior
of a certain subset of their predecessors. For example, a consumer
may know about her friends' recent purchases, but not the product
choices of anyone outside her social circle. In general, each sequential
social-learning problem has an observation network that determines
which predecessors are observable to each agent. Observation networks
associated with different learning problems may vary in density, extent
of segregation, and other structural properties. Hence, our central
research question: how does the structure of the observation network
affect the probability of correct social learning in the long run?

To answer this question, our model must capture key behavioral patterns
in how individuals process social information in these learning settings.
Empirical research on social learning suggests that humans often exhibit
inferential naivet, failing to understand that their
predecessors' actions reflect a combination of private information
and the inference those predecessors have drawn from the behavior
of still others (e.g., <cit.>).
Returning to the examples, a consumer may mistake a herd on a product
for evidence that everyone has positive private information about
the product's quality. In an online community, a few early opinion-makers
can make a rumor go viral, due to people not thinking through how
the vast majority of a viral story's proponents are just following
the herd and possess no private information about the rumor's veracity.

The present study examines the effect of the observation network
on the extent of learning, in a setting where players suffer from
inferential naivet. We analyze the theoretical implications
of a tractable log-linear learning rule that aggregates observations
in a manner related to the DeGroot heuristic. Agents who fail to account
for correlations in their observations (as in )
choose actions according to this log-linear rule. We also introduce
weighted networks and a weighted version of log-linear behavior,
where agents place different weights on different neighbors' actions.
We show that such decision weights arise when agents additionally
misperceive the precisions of predecessors' signals according to the
strengths of their links to said predecessors.

When combined with a Gaussian informational environment, our weighted
log-linear learning rule lets us compute naive agents' exact probability
of taking the correct action (“learning accuracy”) on arbitrary
weighted networks. In contrast, the existing literature on social
learning has focused on whether long-run learning outcome exhibits
certain properties (e.g., convergence to dogmatic beliefs in the wrong
state) with positive probability, but not on how these probabilities
vary across environments. In settings where learning is imperfect
(i.e., society does not almost surely learn the correct state in the
long run), we obtain a richer characterization of the learning outcome
and compute comparative statics of learning accuracy with respect
to network structures.

Under our weighted log-linear learning rule, actions take a simple
form: given a continuous action space and a binary state space, we
can express each agent's action as a log-linear function of her predecessors'
private signal realizations with coefficients depending on the weighted
network structure. We exploit this expression to develop a necessary
and sufficient condition for society to learn completely: no agent
has too much “influence.” Imperfect learning is the leading case:
some agent in the network must have disproportionate influence whenever
all but finitely many people observe more than one neighbor. Since
this condition applies to a very broad class of networks, our analysis
focuses on comparing differentially inefficient learning outcomes
across networks. The detailed comparative statics we obtain from this
approach are crucial: imperfect learning implies a wide range of welfare
losses on different networks.

Introducing naivet generates predictions matching empirical observations
in several domains where the rational model's implications are unclear
or counterfactual. We prove that increasing network density leads
to more inaccurate social-learning outcomes in the long run. This
prediction is supported by the experimental results in our companion
paper <cit.>, where we find human subjects'
accuracy gain from social learning is twice as large on sparse networks
compared to dense networks. As another example, disagreement among
different communities is common in practice. In the domain of product
adoption, respective subcommunities frequently insist upon the superiority
of their preferred products. We prove that if agents' actions only
coarsely reflect their beliefs and society is partially segregated,
then two social subgroups can disagree forever.[Segregation is extensively documented in social networks (see 
for a survey).] Because of the limited information conveyed by actions, disagreement
can persist even when agents observe the actions of unboundedly many
individuals from another group. This presents a sharp contrast with
Bayesian social-learning models (and other leading learning models
such as DeGroot learning), where asymptotic agreement is a robust
prediction.



 §.§ Related Literature




  §.§.§ Effect of Network Structure on Learning


Much of the literature on how network structure matters for learning
outcomes has focused on networked agents repeatedly guessing a state
while learning from the same set of neighbors each period (e.g., <cit.>).

The leading behavioral model here is the DeGroot heuristic, which
forms a belief in each period by averaging the beliefs of neighbors
in the previous period. A key prediction of DeGroot learning is that
society converges to a long-run consensus <cit.>,
which will be correct in large networks as long as the network is
not too unbalanced <cit.>. Much of the analysis focuses
on how network structure (e.g., homophily) matters for the speed of
convergence to correct consensus beliefs <cit.>.
We find that in a sequential setting, natural changes in network structure
matter for asymptotic accuracy, not only for speed of learning. Changing
network density, which has no effect on DeGroot learning in large
networks, can substantially alter the probability that a society learns
correctly. One intuition for this difference is that DeGroot agents
assign weights adding up to 1 to their neighbors, but agents in our
setting have increasing out-degrees with increasing network density
and therefore can overweight their social information. Homophily also
matters for this probability and even for whether consensus is ever
reached.

While DeGroot proposes the averaging rule as an ad hoc heuristic,
several recent papers have developed behavioral microfoundations for
learning in the repeated-interaction setting <cit.>.
These models closely resemble ours at the level of individual behavior,
but their predictions about society's long-run beliefs are more in
line with DeGroot. As such, changes in network structure again have
a limited scope for affecting learning outcomes in this literature.



  §.§.§ Sequential Social Learning


We consider the same environment as the extensive literature on sequential
social learning beginning with <cit.> and <cit.>.
<cit.> and <cit.> characterize
network features that lead to correct asymptotic learning for Bayesians
who move sequentially. By providing a thorough understanding of rational
learning in sequential settings, this literature provides a valuable
benchmark as we study naive learning. We find that among network structures
where Bayesian agents learn asymptotically, there is large variation
in the probability of mislearning for naive agents.

Several authors look at sequential behavioral learning on a particular
network structure, usually the complete network <cit.>.
We characterize several ways in which the choice of network structure
matters for the distribution of long-run outcomes. <cit.>
exhibit a general class of social-learning rules, which includes the
weighted log-linear rule we study for certain values of the weights,
where mislearning occurs with positive probability. We go beyond this
general result by deriving expressions for the exact probabilities
of mislearning on different networks, whose associated welfare losses
cannot be compared using the binary classification of <cit.>.



§ MODEL




 §.§ Sequential Social Learning on a Weighted Network


There are two possible states of the world, ω∈{0,1}, both
equally likely. There is an infinite sequence of agents indexed by
i∈ℕ. Agents move in order, each acting once.

On her turn, agent i observes a private signal s_i∈ℝ.
Private signals (s_i) are Gaussian and independent and identically
distributed(i.i.d.) given the state. When ω=1, we have s_i∼𝒩(1,σ^2)
for some conditional variance σ^2>0. When ω=0, we
have s_i∼𝒩(-1,σ^2).

In addition to her private signal, agent i also observes the actions
of previous agents. Then, i chooses an action a_i∈[0,1].
In our microfoundation for Definition <ref>, agent
i chooses a_i to maximize the expectation of 

    u_i(a_i,ω)-(a_i-ω)^2

given her belief about ω, which we describe later. So her
chosen action corresponds to the probability she assigns to the event
{ω=1}.

We find it convenient to work with the following change of variables.

We have s̃_iln(ℙ[ω=1|s_i]/ℙ[ω=0|s_i])
and ã_iln(a_i/1-a_i)

In words, s̃_i is the log-likelihood ratio of the events
{ω=1} and {ω=0} given signal s_i, while it
is easy to show that ã_i is the log-likelihood ratio
of {ω=1} and {ω=0} corresponding to action a_i.
That is to say, if a_i is optimal given i's beliefs, then
ã_i is the log-likelihood ratio of {ω=1} and
{ω=0} according to i's beliefs. Note that the transformations
from s_i to s̃_i and from a_i to ã_i
are bijective, so no information is lost when we relabel variables.

Agents are linked to all of their predecessors on a weighted network,
with a lower-triangular adjacency matrix M where all diagonal entries
are equal to 0. For i>j, the weight of the link from i to j
is given by M_i,j∈[0,1]. The weights of the edges determine
the relative importance agents place on others' actions in forming
their beliefs. In Section <ref>, we derive comparative
statics with respect to the network structure. Because studying continuous
changes in the network is more tractable than discrete changes, we
consider a model that allows interior network weights.

Throughout, we study naive agents who choose actions equal
to a weighted sum of their observations according to the following
log-linear updating rule.

 Agents use the weighted log-linear rule
if each agent i plays 

    ã_i=s̃_i+∑_j<iM_i,jã_j.


In words, each agent i's log action is a weighted sum of her predecessors'
log actions and her own log signal. The network M exogenously determines
the relative influences of different predecessors' behavior on i's
play, with j's influence proportional to the strength of i's
social connection to her. By contrast, a society of rational agents
would put endogenous weights on others' actions that are not simply
proportional to strengths of the network links between them. For example,
if agents only observe the actions of linked neighbors, rational agents
would play the unique perfect Bayesian equilibrium of the social-learning
game, in which case some equilibrium decision weights may be negative.[We omit the proof that actions are log linear at the perfect Bayesian
equilibrium. This can be shown by induction, and the key step is a
calculation similar to Lemma <ref>.]

The formula in Definition <ref>
resembles the DeGroot updating rule. A key distinction is that we
allow for agents to have any out-degree, while the DeGroot heuristic
requires all agents' weights sum to 1. In an unweighted network, any
agent with multiple observations has an out-degree greater than 1.
This distinction is not just a normalization, but is, in fact, the
source of redundancy under naive inference.




 §.§ Microfoundation for Weighted
Log-Linear Rule


In this subsection, we provide a psychological microfoundation for
the weighted log-linear rule from Definition <ref>.
We first show that on unweighted networks (i.e., when each
M_i,j is either 0 or 1), this rule follows from a primitive assumption
about agents' inference.

A growing body of recent evidence in psychology and economics shows
that people learning from peers are often not fully correct in their
treatment of social structure <cit.>.
Instead of calculating the optimal Bayesian behavior that fully takes
into account all they know about the network and signal structure,
agents often apply heuristic simplifications to their environment.
When networks are complicated and/or uncertain, determining Bayesian
behavior can be intractable <cit.> and these
heuristic learning rules become especially prevalent <cit.>.
Motivated by this observation, we consider the following behavioral
assumption.

Each agent wrongly believes that each predecessor
chooses an action to maximize her expected payoff based only on her
private signal, and not on her observation of other agents.

This inferential mistake can be equivalently described as agent i
misperceiving M_j,k=0 for all k<j<i. Under this interpretation,
i acts as if her neighbors do not take into account their own predecessors'
actions.

In the sequential-learning literature, Assumption <ref>
was first studied on the complete network by <cit.>,
who coined the term “best-response trailing naive inference” (BRTNI)
to describe this behavior. The laboratory games in <cit.>
and <cit.> find evidence for this behavioral
assumption.

Agents who make this inferential mistake use the log-linear rule on
unweighted networks, providing a psychological microfoundation for
the behavior we study.

On an unweighted network where agents
observe only the actions of linked predecessors, Assumption <ref>
implies agents use the weighted log-linear rule.

Due to the inferential mistake, agent i wrongly infers that j's
log action equals her log signal. (This inference is possible since
the continuum action set is rich enough to exactly reveal beliefs
of predecessors.) The action a_i is the product of the relevant
likelihoods because an agent satisfying Assumption <ref>
thinks her observations are based on independent information, and
therefore ã_i is the sum of the corresponding log-likelihood
ratios.

Inference under Assumption <ref> is cognitively simple
in that it does not rely on agents' knowledge about the network (beyond
their own neighborhoods) or even knowledge about the order in which
their predecessors moved. Our model therefore applies even to complex
environments with random arrival of agents. In such environments,
Assumption <ref> may be more realistic than assuming
full knowledge about the observation structure and move order.

Next we give a microfoundation for the same behavior on weighted networks.
We provide an interpretation of network weights that formalizes the
idea that agents place more trust in neighbors with whom their connections
are stronger: we suppose that agents underestimate the precision of
others' private signals in a way that depends on M_i,j.

 Given network weight M_i,j∈[0,1],
agent i believes j's private signal has conditional variance
σ^2/M_i,j given the state.

<cit.>'s meta-analysis of sequential social-learning
experiments finds that laboratory subjects underuse social information
relative to their own private signals. Our Assumption <ref>
is consistent with this evidence, but also allows for different degrees
of underuse for different predecessors. Weaker network connections
formally correspond to predecessors whose signals are believed to
be less informative about the state or less relevant. Conversely,
if we know that i acts as if j's signal has conditional variance
V_i,j≥σ^2, then we can construct a weighted network
with weights M_i,j=σ^2/V_i,j.

The next result shows the combination of the inferential mistake about
others' social information and the underestimation of others' signal
precisions (Assumptions <ref> and <ref>)
provides a microfoundation for the weighted log-linear rule.

Agents who satisfy Assumptions <ref>
and <ref> use the weighted log-linear rule.

By a property of the Gaussian distribution, a log-transformed Gaussian
variable is also Gaussian, which is the key to showing the above lemma.



 §.§ Complete Learning and Mislearning


We define what it means for society to learn completely in terms of
convergence of actions.

Society learns completely
if (a_n) converges to ω in probability.

Since a_n reflects agent n's belief in {ω=1} in
our microfoundation of weighted log-linear inference, this definition
also describes a property about the convergence of beliefs.[In general, we treat a_n as the belief of a naive agent who plays
ã_n.] In a setting where society learns completely, agent n becomes
very likely to believe strongly in the true state of the world as
n grows large.

One failure of complete learning is when society becomes fully convinced
of the wrong state of the world with positive probability, an event
we call mislearning.

Society mislearns when lim_n→∞a_n=0 but ω=1
or when lim_n→∞a_n=1 but ω=0.


 Mislearning is not the only obstacle
to complete learning. Consider a network where, for i≥3, we have
M_i,1=M_i,2=1 and M_i,j=0 for all j1,2. Clearly
this society neither learns completely nor mislearns with positive
probability. Instead, agents' beliefs almost surely do not converge.




§ SOCIAL INFLUENCE AND LEARNING


In this section, we develop a necessary and sufficient condition on
the network for society to mislearn. We argue that this condition
is satisfied by a large class of networks of economic relevance.



 §.§ Path-Counting Interpretation
of Actions


We now show that with naive agents, actions have a simple (log-)linear
expression in terms of paths in the network. Unlike the expression
in Definition <ref>, this next result expresses actions
in terms of only signal realizations and the network structure, making
no reference to predecessors' actions.

Let M[n] refer to the n× n upper-left submatrix of M.

Consider any weighted network M. For
each n, the actions of the first n agents are determined by

    ([ ã_1;   ⋮; ã_n ])=(I-M[n])^-1·([ s̃_1;    ⋮; s̃_n ]).

 So, ã_i is a linear combination of (s̃_j)_j=1^i,
with coefficients given by the number of weighted paths from i
to j in the network with adjacency matrix M.

From a combinatorial perspective, the formula says that the influence
of j's signal on i's action depends on the number of weighted
paths from i to j. In unweighted networks where all entries
in M are 1 or 0, this is just the number of paths. In general,
“weighted paths” means the path passing through agents i_0,...,i_K
is counted with weight ∏_k=0^K-1M_i_k,i_k+1.

Our Proposition <ref> resembles a formula for
agents' actions in <cit.>. In a setting of repeated
interaction with a fixed set of neighbors instead of sequential social
learning, <cit.> also find that the influence
of i's private information on j's period t posterior belief
depends on the number of length-t paths from i to j in the
network.



 §.§ Condition for Complete Learning


We now use the representation result of Proposition <ref>
to study which networks lead to mislearning by naive agents.

We define below a notion of network influence for the sequential social-learning
environment, which plays a central role in determining whether society
learns completely in the long run.

Let b_i,j(I-M[i])_i,j^-1 be the number of weighted
paths from i to j in network M.

Because of Proposition <ref>, these path counts
are important to our analysis.

For n>i, the influence of i on n is 𝕀(i→ n) b_n,i/∑_j=1^nb_n,j.

That is to say, the influence of i on n is the fraction of paths
from n that end at i.

A different definition of influence appears in <cit.>,
who study DeGroot learning in a network where agents act simultaneously
each period. For them, the influence of an agent i is determined
by the unit left eigenvector of the belief-updating matrix, which
is proportional to i's degree in an undirected network with symmetric
weights. Both definitions are related to the proportion of walks terminating
at an agent, but because of the asymmetry between earlier and later
agents in the sequential setting, the distribution of walks tends
to be more unbalanced.

For Proposition <ref> only, we consider
networks that satisfy the following connectedness condition.

Network M satisfies the connectedness condition if there
is an integer N and constant C>0 such that for all i>N, there
exists j<N with b_i,j≥ C.

Intuitively, this says that all sufficiently late agents are indirectly
influenced by some early agent. An unweighted network satisfies the
connectedness condition if and only if there are only finitely many
agents who have no neighbors. If such a network violates the connectedness
condition, then clearly the infinitely many agents without neighbors
will prevent society from learning completely. All weighted networks
studied in Section <ref> also satisfy the connectedness
condition.

Consider any weighted network
satisfying the connectedness condition. Society learns completely
if and only if lim_n→∞𝕀(i→ n)=0 for all i.

Proposition <ref> says that beliefs
always converge to the truth if and only if no agent has undue influence
in the network. This is a recurring insight in research on social
learning on networks, beginning with the “royal family” example
and related results in <cit.>. Other examples where
excessive influence hinders social learning in networks include <cit.>,
<cit.>, and <cit.>. The
main contribution of Proposition <ref>
is to identify the relevant measure of influence in our sequential-learning
setting with naive agents. In our setting, unlike on large unordered
networks as in <cit.>, the ordering of agents creates
an asymmetry that prevents society from learning completely on most
natural networks. Early movers influence many successors, an asymmetry
unique to the sequential-learning setting. For instance, the results
of <cit.> imply that when agents move simultaneously
and every agent weights every other agent equally, society converges
to complete learning as the size of the network grows. But as we show
in Section <ref>, society does not learn completely
in the uniform weighted network where each agent is connected to every
predecessor with the same weight.

The idea behind the proof is that if there were some i and ϵ>0
such that 𝕀(i→ n)>ϵ for infinitely many n,
then i exerts at least ϵ influence on all these future
players. Since s̃_i is unbounded, there is a rare but
positive probability event where i gets such a strong but wrong
private signal so that any future player who puts ϵ weight
on s̃_i and (1-ϵ) weight on other signals would
come to believe in the wrong state of the world with high probability.
But this would mean infinitely many players have a high probability
of believing in the wrong state of the world, so society fails to
learn completely. To gain an intuition for the converse, first observe
that ã_n=b⃗_n_1∑_i=1^n𝕀(i→ n)s̃_i.
In the event that ω=1, the mean of ã_n converges
to infinity with n. So, provided the variance of ã_n
is small relative to its mean, ã_n will converge to infinity
in probability and society will learn completely. Since the log signals
(s̃_i) are i.i.d., the variance of ã_n
is small relative to its mean precisely when all of the weights 𝕀(i→ n)
in the summand are small; this is guaranteed by the condition on influence
lim_n→∞𝕀(i→ n)=0.

We now argue, both analytically and through an example, that the condition
for complete learning in Proposition <ref>
is violated by a large class of weighted networks. The out-degree
of an agent i is ∑_j<iM_i,j, interpreted as the total
number of neighbors who directly affect i's play. We first show
that on any network where all but finitely many agents have out-degree
at least 1+ϵ for some ϵ>0, complete learning fails.

Suppose there exists ϵ>0 so
that ∑_j<iM_i,j≥1+ϵ for all except finitely many
agents i. Then society does not learn completely.

The proof establishes that such a network satisfies the connectedness
condition, but the influence of at least one of the early agents does
not converge to 0, so complete learning fails by Proposition <ref>.
The intuition is that if an influential later agent has an out-degree
greater than 1, then the earlier agents whose action indirectly affects
her must have even more influence. We construct a correspondence between
weighted paths ending at early agents and weighted paths ending at
later agents.

The condition in Proposition <ref> is satisfied
by all of the weighted networks studied in Section <ref>,
which all feature mislearning with positive probability. The network
in Remark <ref> also satisfies the condition
in Proposition <ref> and almost surely leads
to nonconvergence of beliefs.

As an additional example, consider a network where network weights
decay exponentially in distance, so M_i,j=δ^i-j for some
δ≥0. When the rate of decay is strictly above the threshold
of 1/2, late enough agents have out-degree bounded away
from 1, so society does not learn completely by Proposition <ref>.
When the rate of decay is strictly below the same threshold, we can
show the connectedness condition fails and agents' beliefs do not
converge to ω due to lack of information. At the threshold
value of δ=1/2, private signals of all predecessors
are given equal weight, so the law of large numbers implies complete
learning. This highlights the fragility of complete learning in our
model.

Suppose M_i,j=δ^i-j for some δ≥0.
Society learns completely if and only if δ=1/2.

Details of the arguments are provided in the Appendix.



§ PROBABILITY OF MISLEARNING AND NETWORK STRUCTURE


In this section, we compare the probability of mislearning in networks
where complete learning fails by Proposition <ref>.
To do so, we first derive a formula for the probability of mislearning
as a function of the observation network. Then, applying this expression
to several canonical network structures, we compute comparative statics
of this probability with respect to network parameters.

The first network structure we consider assigns the same weight to
each link. Next, we study a homophilic network structure with agents
split into two groups, allowing different weights on links within
groups and between groups.



 §.§ Probability of Mislearning


Due to the Gaussian signal structure, we can give explicit expressions
for the distributions of agent actions in each period. We show that
the probability that agent n is correct about the state is related
to the ratio of ℓ_1 norm to ℓ_2 norm of the vector
of weighted path counts to n's predecessors, b⃗_n(b_n,1,...,b_n,n).
The ratio b⃗_n_1/b⃗_n_2 can be viewed
as a measure of distributional equality for the vector of weights
b⃗_n.[In fact, the ratio of ℓ_1 to ℓ_2 norm has been used
in the applied mathematics literature as a measure of normalized sparsity.] Indeed, among positive n-dimensional vectors b⃗_n with
b⃗_n_1=1, the ℓ_1/ℓ_2 ratio is minimized
by the vector b⃗_n=(1,0,...,0) and maximized by the vector
b⃗_n=(1/n,1/n,...,1/n).

We can express in terms of the network structure the ex ante probability
that agent n puts more confidence in the state being ω=1
when this is, in fact, true. This gives the key result that later
lets us compare the probabilities of mislearning on different networks.

 On any network, the probability that agent
n thinks the correct state is more likely than the incorrect one
is 

    ℙ[ã_n>0|ω=1]=Φ(1/σ·∥b⃗_n∥_1/∥b⃗_n∥_2),

where Φ is the standard Gaussian distribution function.

As ∥b⃗_n∥_1/∥b⃗_n∥_2
increases, the probability of agent n playing higher actions in
state ω=1 also increases. In other words, the agent is more
likely to be correct about the state when the vector of path counts
is more evenly distributed. This should make intuitive sense as she
is more likely to be correct when her action is the average of many
independent signals with roughly equal weights, and less likely to
be correct when her action puts disproportionally heavy weights on
a few signals.

The proof of Proposition <ref> first expresses
ã_n=∑_i=1^nb_n,is̃_i using Proposition
<ref> and then observes that (s_i) are distributed
i.i.d. 𝒩(1,σ^2) conditional on ω=1.
This means (s̃_i) are also conditionally i.i.d. Gaussian
random variables, since the proof of Lemma <ref> establishes
that s̃_i=2s_i/σ^2. As a sum of conditionally
i.i.d. Gaussian random variables, the action ã_n is
itself Gaussian. The result follows from calculating the mean and
variance of this sum.

For the remainder of this section, we study specific weighted networks
where the ratio b⃗_n_1/b⃗_n_2 can be
expressed in terms of interpretable network parameters. Our basic
technique is to count paths on a given network using an appropriate
recurrence relation, and then to apply Proposition <ref>.
This allows us to relate network parameters to the probability distribution
over learning outcomes.



 §.§ Uniform Weights


The simplest network we consider assigns the same weight q∈[0,1]
to each feasible link. By varying the value of q, we can ask how
link density affects the probability of mislearning, which we now
define.

Consider the q-uniform weighted network.
When 0<q≤1, almost surely agents' actions a_n converge to
0 or 1. The probability that society mislearns is 

    Φ(-1/σ·√(q+2/q)).

This probability is strictly increasing in q.

The first statement of the proposition tells us that agents eventually
agree on the state of the world, and that these beliefs are arbitrarily
strong after some time. These consensus beliefs need not be correct,
however. The probability of society converging to incorrect beliefs
is nonzero for all positive q, and increases in q. When the
observational network is more densely connected, society is more likely
to be wrong, as in Figure <ref>.



When the observation network is sparse (i.e., q is low), early
agents' actions convey a large amount of independent information because
they do not influence each other too much. This facilitates later
agents' learning. For high q, early agents' actions are highly
correlated, so later naive agents cannot recover the true state as
easily. A related intuition compares agents' beliefs about network
structure to the actual network: as q grows, agents' beliefs about
the network weights chosen by their neighbors differ more and more
from the true weights. For small q, however, underweighting of
social information partially mitigates the error due to Assumption
<ref>. To complement this theoretical result, in
a companion paper we conduct a sequential-learning experiment to evaluate
a related comparative static <cit.>. In
line with the intuition above, we find that human subjects indeed
exhibit lower long-run accuracy in the learning game when the density
of the observation network increases.

The proof relies on the recurrence relation b_n,i=(1+q)b_n-1,i.
To see that this recurrence holds, let Ψ[n→ i] be
the set of all paths from n to i and let Ψ[(n-1)→ i]
be the set of all paths from n-1 to i. For each ψ∈Ψ[(n-1)→ i]
passing through agents (n-1),j_1,j_2,...,i, we associate two
paths ψ^',ψ^”∈Ψ[n→ i], with ψ^'
passing through n,j_1,j_2,...i and ψ^” passing through
n,(n-1),j_1,j_2,...,i. This association exhaustively enumerates
all paths in Ψ[n→ i] as we consider all ψ∈Ψ[(n-1)→ i].
Path ψ^' has the same weight as ψ since they have the
same length, while path ψ^” has q fraction of the weight
of ψ since it is longer by 1. This shows that the weight of
all paths in Ψ[n→ i] is equal to 1+q times the
weight of all paths in Ψ[(n-1)→ i]; hence, b_n,i=(1+q)b_n-1,i.

The case q=1 is studied in <cit.>, who use a
slightly different signal structure. In their setting, <cit.>
show that agents' beliefs converge to 0 or 1 almost surely and
derive a nonzero lower bound on the probability of converging to the
incorrect belief. By contrast, our result gives the exact probability
of converging to the wrong belief for any 0<q≤1, under a Gaussian
signal structure.

There is a discontinuity at q=0. As q
approaches 0, the probability of society eventually learning correctly
approaches 1. But when q=0, each agent uses only her own private
signal, so there is no social learning. This nonconvergence of actions
means that society never learns correctly. 



While we have focused on long-run learning accuracy, there is a trade-off
between the speed of convergence and asymptotic accuracy for naive
agents. The next proposition illustrates an extreme form of this trade-off.
Start with a uniform-weights network with any link weight 0<q^*≤1.
Sufficiently sparse uniform-weights networks will have worse accuracy
than the q^*-uniform network for arbitrarily many early agents
due to a lack of information aggregation. However, as implied by Proposition
<ref>, late enough agents will have higher accuracy
on these very sparse networks than on the q^*-uniform network.

For any 0<q^*≤1 and N∈ℕ,
there exists some q̅∈(0,q^*) so that ℙ[ã_n>0|ω=1]
is strictly larger on the q^*-uniform weights network than the
q-uniform weights network for all 2≤ n≤ N and q∈(0,q̅).




 §.§ Two Groups


We next consider a network with two groups and different weights for
links within groups and between groups. By varying the link weights,
we will consider how homophily (i.e., segregation in communication)
changes learning outcomes.

Odd-numbered agents are in one group and even-numbered agents are
in a second group. Each feasible within-group link has weight q_s
(s for same) and each feasible between-group link has weight q_d
(d for different), so that for i>j, the link M_i,j=q_s
if i≡ j (mod 2) and M_i,j=q_d otherwise. Figure
<ref> illustrates the first four agents
in a two-group network.



We denote the probability of mislearning with weights q_s and
q_d as ξ(q_s,q_d).

Consider the two-groups network with within-group
link weight q_s and across-group link weight q_d. When 0≤ q_s≤1
and 0<q_d≤1, almost surely agents' actions a_n converge
to 0 or 1. The partial derivatives of the mislearning probability
ξ(q_s,q_d) satisfy 

    ∂ξ/∂ q_d>∂ξ/∂ q_s>0,

 i.e., the probability is increasing in q_s and q_d, but
increasing q_d has a larger effect than increasing q_s.

The first statement again says that agents eventually agree on the
state and eventually have arbitrarily strong beliefs. The fact that
ξ is increasing in q_s and q_d is another example of
higher link density implying more mislearning. The comparison ∂ξ/∂ q_d>∂ξ/∂ q_s
tells us that more integrated (i.e., less homophilic) networks are
more likely to herd on the wrong state of the world.

Convergence of beliefs is more subtle with two groups, as we might
imagine the two homophilic groups holding different beliefs asymptotically.
This does not happen because agents have continuous actions that allow
them to precisely convey the strength of their beliefs. As such, eventually
one group will develop sufficiently strong beliefs to convince the
other given any arbitrarily weak connection q_d>0 between groups.
(In Section <ref>, however, we show that disagreement
between two homophilic groups is possible with a coarser action space.)

To see that convergence must occur, observe that the belief of a later
agent n depends mostly on the number of paths from that agent to
early agents (and those agents' signal realizations). When n is
large, most paths from agent n to an early agent pass between the
two groups many times. So the number of paths does not depend substantially
on agent n's group. Put another way, when q_s≫ q_d>0 and
n is large, agent n has many more length-1 paths to her own
group than to the other group, but roughly the same total number of
paths across all lengths to both groups. Therefore, agent n's belief
does not depend substantially on whether n is in the odd group
or the even group.[Each path transitions between the two groups, and eventually the probability
of ending in a given group is approximately independent of the starting
group. This is analogous to a Markov chain approaching its stationary
distribution.]

<cit.>'s homophily index equals (q_s-q_d)/(q_s+q_d)
for this weighted network. To explore how homophily affects mislearning
probability while holding fixed the average degree of each agent,
we consider the total derivative d/dΔξ(q_s+Δ,q_d-Δ).
To interpret, we are considering the marginal effect on mislearning
of a Δ increase to all the within-group link weights, coupled
with a Δ decrease to all the between-groups link weights.
These two perturbations, applied simultaneously, leave each agent
with roughly the same total degree and increases the homophily index
by (2Δ)/(q_s+q_d). Using the chain rule and Proposition
<ref>,

    d/dΔξ(q_s+Δ,q_d-Δ)=∂ξ/∂ q_s-∂ξ/∂ q_d<0,

which means increasing the homophily index of the society and fixing
average degrees always decreases the probability of mislearning. Note
that this result holds regardless of whether society is currently
homophilic (q_s>q_d) or heterophilic (q_s<q_d).

An important insight from the literature about social learning on
networks is that beliefs converge more slowly on more segregated networks
<cit.>. In our model, faster convergence of beliefs
tends to imply a higher probability of incorrect beliefs. When beliefs
converge quickly, agents are putting far too much weight on early
movers, while when beliefs converge more slowly agents wait for more
independent information. Since agents eventually agree, segregation
helps society form strong beliefs more gradually.



§ DISAGREEMENT


In Section <ref>, we saw that even on partially
segregated networks, agents eventually reach a consensus on the state
of the world. This agreement relies crucially on the richness of the
action space available to agents, which allows agents to communicate
the strength of their beliefs. In this section, we modify our model
so that the action space is binary and show that the two groups can
disagree forever about the state of the world even when the number
of connections across the groups is unbounded.

The contrasting results for the binary-actions model versus the continuum-actions
model echo a similar contrast in the rational-herding literature,
where society herds on the wrong action with positive probability
when actions coarsely reflect beliefs <cit.>,
but almost surely converges to the correct action when the action
set is rich enough <cit.>. Interestingly, while
the rational-herding literature finds that an unboundedly informative
signal structure prevents herding on the wrong action even when actions
coarsely reflect beliefs <cit.>, we will show
below that even with Gaussian signals two groups may disagree with
positive probability.

Suppose that the state of the world and the signal structure are the
same as in Section <ref>, but agents now choose binary
actions a_i∈{ 0,1}. Agents still maximize the
expectation of u_i(a_i,ω)-(a_i-ω)^2
given their beliefs about ω, under the psychological errors
given by Assumptions <ref> and <ref>.
This utility function now implies that an agent chooses the action
corresponding to the state of world she believes is more likely. Agents
live on the two-groups network from Section <ref>:
for i>j, the link M_i,j=q_s if i≡ j (mod 2)
and M_i,j=q_d otherwise. We assume q_s>q_d>0, so that
agents have stronger connections with predecessors from their own
groups.

 Consider the two-groups network. Suppose
q_s>q_d>0 and agents play binary actions. Then there is a positive
probability that all odd-numbered agents choose action 0 while
all even-numbered agents choose action 1.

Persistent disagreement is sustained even though agent n has approximately
nq_d/2 weighted links to agents from the other group (when n
is large) taking opposite actions.

Our result extends to two groups of unequal sizes as long as for all
later agents, the total number of weighted links to their own group
is larger than the total number of weighted links to the other group.

We also get the same result on a random-network analog of the two-groups
model, where edges are unweighted and q_s is the probability
of link formation within groups while q_d is the probability
of link formation between groups. Agents observe only the actions
of the predecessors to whom they are linked and wrongly believe all
observed actions derive from private signals.[Details of the statement and a proof are available in a previous draft
at <https://arxiv.org/pdf/1703.02105v5.pdf>.] By contrast, with rational agents, Theorem 2 of <cit.>
implies the groups almost surely agree asymptotically on this random
network.

This result adds a new mechanism to the literature on disagreement
in connected societies <cit.>.
<cit.> also study disagreement in a binary sequential-learning
setting with behavioral agents, but their results concern disagreement
on a complete network among agents with different types of behavioral
biases. By contrast, our Proposition <ref> says
that when all agents use the same naive heuristic, they can still
disagree by virtue of belonging to two different homophilic social
groups, even when there are many connections between those groups.



§ CONCLUSION


In this paper, we have explored the influence of network structures
on learning outcomes when agents move sequentially and use a log-linear
learning rule due to inferential naivet. We have compared long-run
welfare across networks by deriving the exact probabilities of mislearning
on arbitrary networks.

We have studied the simplest possible social-learning environment
to focus on the effect of network structure, but several extensions
are straightforward. Analogs of our general results hold for finite
state spaces with more than two elements, where we can define a log-likelihood
ratio for each pair of states. We can also make the order of moves
random and unknown, in which case naive behavior conditional on a
given turn order is the same as when that order is certain.

We prove our comparative statics results for weighted networks as
they are analytically more tractable than random graphs. For each
weighted network with weights in [0,1], there corresponds an analogous
(unweighted) random graph model where the i→ j link exists with
probability M_i,j. In numerical simulations, all comparative
statics results proved for weighted networks in Section <ref>
continue to hold in the analogous random network models. The major
obstacle to extending our proofs is that because our networks are
directed and acyclic, the relevant adjacency matrices have no nonzero
eigenvalues. As a consequence, most techniques from spectral random
graph theory do not apply (but perhaps other methods would).





Appendix





§ PROOFS





 §.§ Proof of Lemma <ref>


The log-likelihood ratio of state ω=1 and state ω=0
conditional on the signal realizations of i's linked predecessors
is:


    ln(ℙ[ω=1|s_i,(s_j)_j:M_i,j=1]/ℙ[ω=0|s_i,(s_j)_j:M_i,j=1])     =    ln(ℙ[s_i,(s_j)_j:M_i,j=1|ω=1]/ℙ[s_i,(s_j)_j:M_i,j=1|ω=0]) (two states equally likely)
        =    ln(ℙ[s_i|ω=1]/ℙ[s_i|ω=0]·∏_j:M_i,j=1ℙ[s_j|ω=1]/ℙ[s_j|ω=0]) (by independence)
        =    ln(ℙ[ω=1|s_i]/ℙ[ω=0|s_i])+∑_j:M_i,j=1ln(ℙ[ω=1|s_j]/ℙ[ω=0|s_j])
        =    s̃_i+∑_j:M_i,j=1s̃_j
        =    s̃_i+∑_j<iM_i,js̃_j


Due to Assumption <ref>, i thinks each predecessor
j must have received signal s_j such that s̃_j=ã_j.
When i observes only the play of linked predecessors, her log-likelihood
ratio of state ω=1 and state ω=0 given her social
observations and private signal is therefore s̃_i+∑_j<iM_i,jã_j.
She maximizes her expected payoff by choosing an action a_i corresponding
to her belief in state ω=1, which implies that ã_i
is equal to this log-likelihood ratio.




 §.§ Proof of Lemma <ref>

We first establish an auxiliary lemma.

 We have s̃_i=2s_i/σ^2.


The log-likelihood ratio is 

    ln(ℙ[ω=1|s_i]/ℙ[ω=0|s_i])     =ln(ℙ[s_i|ω=1]/ℙ[s_i|ω=0])=ln(exp(-(s_i-1)^2/2σ^2)/exp(-(s_i+1)^2/2σ^2))
        =-(s_i^2-2s_i+1)+(s_i^2+2s_i+1)/2σ^2=2s_i/σ^2.


We now turn to the proof of Lemma <ref>.

Due to Assumptions <ref>, i thinks that j will
choose a_j such that ã_j=2s_j/σ^2 by the
result just established, since j thinks the conditional variance
of her signal is σ^2. But, since i believes j's signal
has conditional variance σ^2/M_i,j by Assumption <ref>,
in i's view 

    ln(ℙ[ω=1|s_j]/ℙ[ω=0|s_j])=2s_j/σ^2/M_i,j=M_i,jã_j,

again applying the result above.

Omitting analogous algebraic arguments as in the proof of Lemma <ref>,

    ln(ℙ[ω=1|s_i,(s_j)_j<i]/ℙ[ω=0|s_i,(s_j)_j<i])     =ln(ℙ[ω=1|s_i]/ℙ[ω=0|s_i])+∑_j<iln(ℙ[ω=1|s_j]/ℙ[ω=0|s_j])
        =s̃_i+∑_j<iM_i,jã_j.

So s̃_i+∑_j<iM_i,jã_j is i's log-likelihood
ratio of state ω=1 and state ω=0 given her social
observations and private signal.




 §.§ Proof of Proposition <ref>


By weighted log-linear inference, for each i we have ã_i=s̃_i+∑_j∈ N_iM_i,jã_j.
In vector notation, we therefore have 

    ([ ã_1;   ⋮; ã_n ])=([ s̃_1;    ⋮; s̃_n ])+M[n]·([ ã_1;   ⋮; ã_n ])


Algebra then yields the desired expression. Note that (I-M[n])
is invertible because M[n] is lower triangular with all diagonal
entries equal to 0.

To see the path-counting interpretation, write (I-M[n])^-1=∑_k=0^∞M[n]^k.
Here, (M[n]^k)_i,j counts the number of weighted paths of length
k from i to j.




 §.§ Proof of Proposition <ref>


Without loss of generality, assume ω=1. (The case of ω=0
is exactly analogous and is omitted.) Note that a_n converges
in probability to 1 if and only if ã_n converges in probability
to ∞.

First suppose that lim_n→∞𝕀(j→ n)≠0
for some j. Then there exists ϵ>0 such that 𝕀(j→ n)>ϵ
for infinitely many n. For each such n, the probability that
agent n chooses an action with ã_n<0 is equal to the
probability that ∑_i=1^n𝕀(i→ n)s̃_i
is negative.

Because s is Gaussian, s̃ has finite variance, so we
can find positive constants C and δ independent of n
such that ∑_i≠ j𝕀(i→ n)s̃_i<C with
probability at least δ (for example, by applying Markov's
inequality to |s̃_i|). Then agent n will be wrong if
s̃_j<-C/ϵ, which is a positive probability event
since s̃ is unbounded. So the probability that an agent
n such that 𝕀(j→ n)>ϵ chooses ã_n<0
is bounded from below by a positive constant.

For the converse, suppose that lim_n→∞𝕀(i→ n)=0
for all i. By the independence of the log signals s̃_i,
the log action ã_n=∑_i=1^n𝕀(i→ n)s̃_i
is a random variable with mean b⃗_n_1 and standard
deviation b⃗_n_2σ when ω=1. We now use
the connectedness condition to show that b⃗_n_1/b⃗_n_2→∞.

Find N and C≤1 as in the connectedness condition. For each
ϵ>0, we can choose M_ϵ such that 𝕀(i→ n)<ϵ
whenever i<N and n>M_ϵ by the hypothesis lim_n→∞𝕀(i→ n)=0
applied to the finitely many members i<N. But now for any j≥ N
and any n>max(j,M_ϵ), concatenating a path from j
to n with a path from i to j gives a path from i to n
whose weight is the product of the weights of the two subpaths. This
shows b_n,i≥ b_j,i· b_n,j, which implies 𝕀(i→ n)≥𝕀(j→ n)· b_j,i.
We have 𝕀(j→ n)≤min_i<N𝕀(i→ n)/b_j,i,
where b_j,i≥ C for at least one i<N by the connectedness
condition. This shows for any j∈ℕ and for n>M_ϵ,
that we get 𝕀(j→ n)≤ϵ/C.

We have for all n>M_ϵ, 

    b⃗_n_2/b⃗_n_1≤max_j√(b⃗_n_1· b_n,j)/b⃗_n_1=max_j<n√(𝕀(j→ n))<√(ϵ/C).


Because ϵ>0 is arbitrary, b⃗_n_1/b⃗_n_2
converges to infinity.

Let some K>0 be given. We now show that ℙ[ã_n<K|ω=1]→0,
hence proving that ã_n converges to ∞ in probability.
We compute 

    z_n:=𝔼[ã_n|ω=1]-K/Std[ã_n|ω=1]=b⃗_n_1·2/σ^2/b⃗_n_2·2/σ-K/b⃗_n_2·2/σ.


Since b⃗_n_1/b⃗_n_2→∞, the first
term converges to infinity. By the connectedness condition, b⃗_n_2≥ C
for all large enough n, so the second term is bounded. This implies
z_n→∞. By Chebyshev's inequality, ℙ[ã_n<K|ω=1]≤ z_n^-2.
This shows ℙ[ã_n<K|ω=1]→0.

We note that this shows convergence in probability, but does not characterize
the joint distribution of actions, so these methods do not guarantee
almost sure convergence (without further structure on the networks
as in Section <ref>).




 §.§ Proof of Proposition <ref>


By the hypothesis of the proposition, there exists some ϵ>0
and N∈ℕ so that for all i>N, ∑_j<iM_i,j≥1+ϵ.
Modify the network to set all links originating from any of the first
N agents to have weight 0, that is, M_i,j=0 for all i,j≤ N.

We prove by induction that ∑_j≤ Nb_i,j≥1+ϵ for
all i≥ N+1 on the modified network. Consider agent N+1. Since
∑_j<N+1M_N+1,j≥1+ϵ and all of (N+1)'s out-degree
comes from links to agents in position N or earlier, ∑_j≤ Nb_N+1,j≥1+ϵ.
By induction, suppose ∑_j≤ Nb_N+k,j≥1+ϵ holds
for all 1≤ k≤ K. A lower bound on ∑_j≤ Nb_N+K+1,j
is 

    ∑_j≤ NM_N+K+1,j+∑_N+1≤ i≤ N+KM_N+K+1,i·(∑_j^'≤ Nb_i,j')    ≥∑_j≤ NM_N+K+1,j+∑_N+1≤ i≤ N+KM_N+K+1,i·(1+ϵ)
       ≥∑_j≤ N+KM_N+K+1,j
       ≥1+ϵ,

where in the first inequality we used the inductive hypothesis and
in the last inequality we used the fact that N+K+1 has an out-degree
of at least 1+ϵ. This establishes ∑_j≤ Nb_N+K+1,j≥1+ϵ
and so by induction, ∑_j≤ Nb_N+k,j≥1+ϵ for all
k≥1.

This result holds a fortiori on the original network with higher link
weights. By the pigeonhole principle, the original network satisfies
the connectedness condition with C=1/N(1+ϵ).

Now return to the modified network (so M refers to the possibly
modified network weights). We develop some notation for the rest of
the proof and establish an intermediary lemma. For j<i, let Ψ[i→ j]
be the set of all paths from i to j. Let Ψ̂[i→[N]]
be the set of paths from i to some agent k≤ N, such that the
path contains no links between two different agents among the first
N. Let Ψ̂[i→[N]| j] be the subset of such paths
that pass through j.

For a path ψ passing through agents i_1,i_2,...,i_L,
let W(ψ):=∏_ℓ=1^L-1M_i_ℓ+1,i_ℓ denote
its weight and let D(ψ):=∏_ℓ=1^L-1(∑_j<i_ℓM_i_ℓ,j)
denote the product of out-degrees of all agents on the path except
the last one.

 For n>N, ∑_ψ∈Ψ̂[n→[N]]W(ψ)/D(ψ)=1.


We prove by induction on n. For n=N+1, the set Ψ̂[n→[N]]
is the set of N paths each consisting of a link from N+1 to
some agent j≤ N. Each ψ∈Ψ̂[n→[N]] therefore
has D(ψ)=∑_j<N+1M_N+1,j, and the path terminating at
j has W(ψ)=M_N+1,j. So the claim holds for n=N+1. By
induction suppose it holds for all n≤ N+K for some K≥1.
For n=N+K+1, partition Ψ̂[n→[N]] into K+1 groups.
For 1≤ k≤ K, each path ψ∈Ψ(k) in the kth group
consists of the link n→(N+k) concatenated in front of a path
ψ^'∈Ψ̂[(N+k)→[N]], so ψ=((n,N+k),ψ^').
The final (K+1)th group consists of paths where n links directly
to an agent among the first N. We have: 

    ∑_ψ∈Ψ̂[n→[N]]W(ψ)/D(ψ)    =∑_k=1^K(∑_ψ^'∈Ψ̂[(N+k)→[N]]W((n,N+k),ψ^')/D((n,N+k),ψ'))+∑_j=1^NM_n,j/∑_h<nM_n,h
        =∑_k=1^K(∑_ψ^'∈Ψ̂[(N+k)→[N]]M_n,N+k· W(ψ^')/∑_h<nM_n,h· D(ψ'))+∑_j=1^NM_n,j/∑_h<nM_n,h
        =∑_k=1^K(M_n,N+k/∑_h<nM_n,h·1)+∑_j=1^NM_n,j/∑_h<nM_n,h (by inductive hypothesis)
        =∑_h<nM_n,h/∑_h<nM_n,h=1.


So by induction, this claim holds for all n>N.

We now return to the proof of Proposition <ref>.
For N<i<n, 

    b_n,i    =∑_ψ∈Ψ[n→ i]W(ψ)=∑_ψ∈Ψ[n→ i][W(ψ)·(∑_ψ̂∈Ψ̂[i→[N]]W(ψ̂)/D(ψ̂))],

 where the second equality follows because Lemma <ref>
implies the term in the inner parentheses is 1. For a path ψ
passing through i, let ψ[i] denote the subpath starting with
i. So the above says 

    b_n,i=∑_ψ∈Ψ̂[n→[N]| i]W(ψ)/D(ψ[i]).

 Summing across i, we may re-index the sum by paths in Ψ̂[n→[N]].
To be more precise, for ψ∈Ψ̂[n→[N]], write A(ψ)⊆{N+1,...,n-1}
to be the set of agents that ψ passes through. For each j∈ A(ψ),
we have ψ∈Ψ̂[n→[N]| j], so it contributes W(ψ)/D(ψ[j])
to the overall sum, 

    ∑_i=N+1^n-1b_n,i    =∑_i=N+1^n-1∑_ψ∈Ψ̂[n→[N]| i]W(ψ)/D(ψ[i])
        =∑_ψ∈Ψ̂[n→[N]]∑_j∈ A(ψ)W(ψ)/D(ψ[j])
       ≤∑_ψ∈Ψ̂[n→[N]]W(ψ)·∑_j∈ A(ψ)1/(1+ϵ)^|ψ[j]|-1
       ≤∑_ψ∈Ψ̂[n→[N]]W(ψ)·1/ϵ

 where |ψ[j]| denotes the number of agents in the subpath ψ[j].
On the third line, we used the fact that all agents on ψ except
the last one must have out-degree at least 1+ϵ, so D(ψ[j])≥(1+ϵ)^|ψ[j]|-1.
The result ∑_i=N+1^n-1b_n,i≤∑_ψ∈Ψ̂[n→[N]]W(ψ)·1/ϵ
also holds for the original network, since we have not modified the
subnetwork among agents N+1,...,n.

We also have ∑_i=1^Nb_n,i=∑_ψ∈Ψ̂[n→[N]]W(ψ).
On the original network, we have higher link weights among the first
N agents, so we in fact have 

    ∑_i=1^Nb_n,i≥∑_ψ∈Ψ̂[n→[N]]W(ψ).

So, on the original network, 

    ∑_i=1^N𝕀(i→ n)≥1/1+1/ϵ.

This inequality holds for every n, so it cannot be the case that
lim_n→∞𝕀(i→ n)=0 for all 1≤ i≤ N.




 §.§ Proof of Example <ref>


The coefficients b_i,n satisfy the recurrence relation b_n,i=2δ b_n-1,i
whenever n-i>1.

When δ=1/2, from the recurrence relation, all predecessors'
signals are given equal weight, so by the law of large numbers, actions
converge to ω almost surely.

When δ>1/2, ∑_k=0^∞δ^k>1, so
∑_j<iM_i,j is bounded above 1 for n large enough. So
by Proposition <ref>, society does not learn
correctly.

The final case is δ<1/2. We show that ℙ[a_n≤1/2|ω=1]
is bounded away from 0 for all n≥1, so (a_n) cannot converge
in probability to ω.

Without loss of generality, normalize to σ=1. From the recurrence
relation for the coefficients b_n,i, it is easy to check that
ã_n=2δã_n-1+s̃_n-δs̃_n-1
for each n. Evidently b_i+1,i=δ, so from recursion, b_n,i=(2δ)^n-i-1δ
for i≤ n-1, b_n,n=1. So, ã_n=s̃_n+δ∑_j=0^n-2(2δ)^j·s̃_n-1-j,
meaning 

    ã_n|(ω=1)∼𝒩(1+δ1-(2δ)^n-1/1-2δ,1+δ^21-(4δ^2)^n-1/1-4δ^2).

So 

    ℙ[ã_n≤0|ω=1]≥Φ(-1-δ/1-2δ)

 for all n, which implies for all n, 

    ℙ[a_n≤1/2|ω=1]≥Φ(-1-δ/1-2δ).





 §.§ Proof of Proposition <ref>


We first state and prove a lemma that gives the ex ante distribution
of agent n's log action.

When ω=1, the log action of agent
n on any weighted network is distributed as 

    ã_n∼𝒩(2/σ^2b⃗_n_1,4/σ^2b⃗_n_2^2).



By Proposition <ref>, ã_n=∑_i=1^nb_n,is̃_i.
This is equal to ∑_i=1^n2b_n,is_i/σ^2 according
to Lemma <ref>. Conditional on ω=1, (s_i)
are i.i.d. 𝒩(1,σ^2) random variables, so 

    ∑_i=1^n2b_n,i/σ^2s_i∼𝒩(2/σ^2∑_i=1^nb_n,i,4/σ^2∑_i=1^nb_n,i^2)=𝒩(2/σ^2b⃗_n_1,4/σ^2b⃗_n_2^2).


Now we give the proof of Proposition <ref>.

By Lemma <ref>, ã_n|(ω=1)∼𝒩(2/σ^2b⃗_n_1,4/σ^2b⃗_n_2^2).
So using properties of the Gaussian distribution, 

    ℙ[ã_n>0|ω=1]=Φ(2/σ^2b⃗_n_1/2/σb⃗_n_2)=Φ(1/σ·b⃗_n_1/b⃗_n_2).






 §.§ Proof of Proposition <ref>


The numbers of paths from various agents to agent i satisfy the
recurrence relation b_n,i=(1+q)b_n-1,i when n-i>1. By a
simple computation, we find that 

    ã_n=∑_i=1^n-1q(1+q)^n-i-1s̃_i+s̃_n.

Since s̃_i are independent Gaussian random variables,
our argument uses the fact that for n large, ã_n has
the same sign as another Gaussian random variable, whose mean and
variance we can compute.

We first show that ã_n converges to -∞ or ∞
almost surely. Consider the random variable 

    X_n(s⃗):=1/2∑_i=1^n-1(1+q)^-is̃_i,

where s⃗:=(s_i)_i=1^∞ is the profile of private
signal realizations. By a standard result, X_n(s⃗) converges
almost surely to a random variable Y(s⃗) such that the conditional
distribution of Y in each state of the world is Gaussian. For each
n, ã_n(s⃗)=2q(1+q)^n-1· X_n(s⃗)+s̃_n.
Since ∑_n=1^∞ℙ[s̃_n>n]<∞, by
the Borel–Cantelli lemma, ℙ[s̃_n>n infinitely often]=0.
So almost surely, lim_n→∞ã_n(s⃗)=lim_n→∞2q(1+q)^n-1· Y(s⃗)+s̃_n∈{-∞,∞}.
This in turn shows that a_n converges to 0 or 1 almost surely.

Now we show ℙ[a_n→0|ω=1]=Φ(-σ^-1√((q+2)/q)),
which is the same probability as ℙ[ã_n→-∞|ω=1].
The random variable Y(s⃗) that X_n(s⃗) converges
to a.s. has the distribution 𝒩(1/(σ^2q),1/(σ^2q(q+2)))
when ω=1, and ã_n has the same sign as X_n(s⃗)
with probability converging to 1 for n large. The distribution
𝒩(1/(σ^2q),1/(σ^2q(q+2))) assigns Φ(-σ^-1√((q+2)/q))
probability to the positive region. The symmetric argument holds for
ω=0.





 §.§ Proof of Proposition <ref>


First, we derive a closed-form expression for the probability that
the nth agent thinks the correct state is more likely in the uniform
weights network, conditional on ω=1.

 In the q-uniform weights network,

    ℙ[ã_n>0|ω=1]=Φ(1/σ·(1+q)^n-1·√((2+q))/√(2+q(1+q)^2n-2)).

This probability is strictly increasing in n when 0<q≤1.


From the proof of Proposition <ref>, we have

    ã_n=∑_i=1^n-1q(1+q)^n-i-1s̃_i+s̃_n

 where the different s̃_i's are conditionally independent
given ω=1, with s̃_i|(ω=1)∼𝒩(2/σ^2,4/σ^2)
from Lemma <ref>. Thus, the sum ã_n is
conditionally Gaussian with a mean of 

    2/σ^2·[1+∑_i=1^n-1q(1+q)^n-i-1]     =2/σ^2·[1+q·(1+q)^n-1-1/(1+q)-1]
        =2/σ^2·(1+q)^n-1

 and a variance of 

    4/σ^2·[1+∑_i=1^n-1q^2(1+q)^2n-2i-2]     =4/σ^2·[1+q^2·(1+q)^2n-2-1/(1+q)^2-1]
        =4/σ^2·2+(1+q)^2n-2q/2+q.

 Thus, 0 is 

    2/σ^2·(1+q)^n-1/√(4/σ^2·2+(1+q)^2n-2q/2+q)=1/σ·(1+q)^n-1·√((2+q))/√(2+q(1+q)^2n-2)

 standard deviations below the mean in the distribution of ã_n|(ω=1),
so 

    ℙ[ã_n>0|ω=1]=Φ(1/σ·(1+q)^n-1·√((2+q))/√(2+q(1+q)^2n-2)).

 To see that this expression is strictly increasing, let n≥1.
Then, 

    ℙ[ã_n+1>0|ω=1]     =Φ(1/σ·(1+q)·(1+q)^n-1·√((2+q))/√(2+(1+q)^2· q(1+q)^2n-2))
        >Φ(1/σ·(1+q)·(1+q)^n-1·√((2+q))/√((1+q)^2·2+(1+q)^2· q(1+q)^2n-2))
        =Φ(1/σ·(1+q)^n-1·√((2+q))/√(2+q(1+q)^2n-2))
        =ℙ[ã_n>0|ω=1]

 as desired.

Now we give the proof of Proposition <ref>.

Let ℙ[ã_2>0|ω=1] on the q^*-uniform
weights network be denoted by p. Lemma <ref>
implies ℙ[ã_n>0|ω=1] is strictly increasing
in n on the q^*-uniform weights network, so p>
and, furthermore, ℙ[ã_n>0|ω=1]≥ p
for all n≥2 on the same network.

The function 

    q    ↦   Φ(1/σ·(1+q)^N-1·√((2+q))/√(2+q(1+q)^2N-2))

 is continuous and equals Φ(1/σ) when q=0. So we may
find a small enough q̅∈(0,q^*) so that whenever 0<q<q̅,

    Φ(1/σ·(1+q)^N-1·√((2+q))/√(2+q(1+q)^2N-2))<p.

From the monotonicity result of Lemma <ref>,
this also implies 

    Φ(1/σ·(1+q)^n-1·√((2+q))/√(2+q(1+q)^2n-2))<p

 for all 2≤ n≤ N.




 §.§ Proof of Proposition <ref>


Suppose we have two groups, and agents observe predecessors in the
same group with weight q_s and predecessors in the other group
with weight q_d. Then the coefficients b_n,i satisfy the
recurrence relation 

    b_n,i=q_db_n-1,i+(1+q_s)b_n-2,i

when n-i>2. Since the network is translation invariant, b_n,i
only depends on n-i. By a standard algebraic fact, there exist
constants c_+,c_-,ζ_+,ζ_- (only depending on n-i)
so that 

    b_n,i=c_+ζ_+^n-i+c_-ζ_-^n-i,

where ζ_± are the solutions to the polynomial x^2-q_dx-(1+q_s)=0
and c_+,c_- are constants that we can determine from b_2,1
and b_3,1. We compute 

    ζ_±=q_d±√(4q_s+q_d+4)/2,

 where ζ_+>1 and ζ_-<0. By arguments analogous to
those in the proof of Proposition <ref>, we
may again establish that a_n converges to 0 or 1 almost surely.
We now analyze the probability of mislearning.

Since ζ_+>|ζ_-|, the exponential term with base ζ_+
dominates as n grows large. This shows c_+>0, since b_n,i
counts the number of weighted paths in a network so it must be a positive
number. This also shows that ℙ[ã_n<0|ω=1]→ℙ[∑_i=0^∞(ζ_+)^-is̃_i<0|ω=1]
as n→∞. Conditional on ω=1, the sum ∑_i=0^∞(ζ_+)^-is̃_i
has the distribution 

    𝒩(2/σ^2(ζ_+-1),4/σ^2(ζ_+-1)(ζ_++1)),

so it is easy to show that the probability assigned to the negative
region is increasing in ζ_+.

Having shown that the probability of mislearning is monotonically
increasing in ζ_+, we can take comparative statics: 

    ∂ζ_+/∂ q_d=q_d/2√(4q_s+q_d+4)+1/2 and ∂ζ_+/∂ q_s=1/√(4q_s+q_d+4).

It is easy to see that ∂ζ_+/∂ q_d>∂ζ_+/∂ q_s>0
for all q_s≥0 and q_d>0.





 §.§ Proof of Proposition <ref>


Define κ_q to be a naive agent i's log-likelihood ratio
of state ω=1 versus state ω=0 upon observing one neighbor
j who picks action 1 with weight q. Then we have:

    κ_qln(ℙ[ω=1|s_j≥0]/ℙ[ω=0|s_j<0])>0,

where ℙ is taken under i's beliefs about the conditional
distributions of s_j under Assumption <ref>,
that is s_j|(ω=1)∼𝒩(1,σ^2/q) and
s_j|(ω=0)∼𝒩(-1,σ^2/q). In particular,
this log likelihood κ_q is decreasing in q and so κ_q_s-κ_q_d>0
for q_s>q_d.

By symmetry of the Gaussian distribution, the log-likelihood ratio
after observing one neighbor who chooses action 0 with weight q
is -κ_q.

Suppose after 2n agents have moved, the actions taken so far involve
every odd-numbered agent playing 1and every even-numbered agent playing
0. Then agent 2n+1 has a log-likelihood ratio of n(κ_q_s-κ_q_d)
from her social observations. The probability that private signal
s_2n+1 is so strongly in favor of ω=0 as to make 2n+1
play 0 is 

    ϵ_nℙ[s_i∈ℝ:ln(ℙ[ω=1|s_i]/ℙ[ω=0|s_i])<-n(κ_q_s-κ_q_d)|ω=1]

For the Gaussian distribution, ln(ℙ[ω=1|s_i]/ℙ[ω=0|s_i])=2s_i/σ^2,
so 

    ∑_n=1^∞ϵ_n=∑_n=1^∞Φ(-σ^2/2n(κ_q_s-κ_q_d);1,σ^2)<∞

because the Gaussian distribution function tends to 0 faster than
geometrically. This shows that there is apositive probability that
every odd-numbered agent plays 1.

By an analogous argument, there is also a positive probability that
every even-numbered agent plays 0. In that argument we would use the
fact that 

    ∑_n=1^∞[1-Φ(σ^2/2n(κ_q_s-κ_q_d);1,σ^2)]<∞.


ecta


