# A Trimming Estimator for the Latent-Diffusion-Observed-Adoption Model

L.S. Sanna Stephan

(September 2023)

##  1 Introduction

Diffusion in networks has been vastly studied in biology and Computer Science.
Yet recently it has increasingly been acknowledged that also economic agents
exchange goods, services or assets in social networks and that it is highly
important and interesting to estimate at which rate they do so. A key
challenge here is that economic interaction in social networks is oftentimes
unobserved.
We can tackle such a situation assuming that economic events which we spot are
but a signal of the process that jointly determines an observed outcome and an
unobserved state variable. Yet, fitting such a model to the data is
challenging due to the high dimensionality: at each point in time, there
exists a system of equations relating all the unobserved individual state
variables to one another, and the dynamics of this system are governed by the
network. With social networks typically being dense and large, we thus have a
gigantic number of scenarios that could have given rise to the data at hand.
This is problematic in particular if the time horizon we wish to consider is
large.
Due to the nonlinear nature of network diffusion models, Maximum Likelihood
(ML) estimation would be the preferred estimation method. However, setting up
the log likelihood function is computationally infeasible for larger time
horizons. The gigantesque number of possible realizations of the latent
diffusion process that could have generated the observed adoption pattern
makes it impossible to establish the probability to observe the given data by
applying the law of total probability (i.e. by integrating out the latent
process). To ensure tractability one needs to either restrict the model time
horizon or to use a dimension reduction strategy. In this paper, I conduct a
Monte Carlo study in order to compare these two alternatives. This shows that
the “Trimming estimator”, derived in the present chapter, outperforms the
previously used estimator that restrict the number of rounds of network
interaction that can take place in most cases (precisely, whenever the sample
includes a sufficient number of villages for which trimming impacts no more
than one-third of the individuals that are eligible to be trimmed). The
“Trimming estimator” is thereafter applied to four real villages from the
Banerjee et al. (2013) study.
I propose a simple trimming rule that imposes restrictions on the number of
permissible results of the unobservable network interaction and compare it to
the estimate that results from restricting the time horizon modeled. Fast and
flexible, the algorithm can be used to estimate a class of network models that
comprises an observed outcome and an unobserved state variable. The strategy
is easily implemented and oftentimes succeeds in selecting the interaction
outcomes with the largest probability mass. I also investigate how features of
the network affect performance of the algorithm.
I demonstrate, that the MLE obtained from maximizing the approximate log
likelihood function quickly converges to the exact MLE as the trimming value
increases. I proceed by establishing the (approximate) log likelihood function
and finding its maximum by means of grid search. This entails certain
advantages. As a byproduct we obtain the log likelihood function which,
plotted over the grid, can provide us with additional insights (e.g. I can
detect local maxima, areas of weak identification or illustrate the covariance
of the parameters). Confidence sets can be constructed straightforwardly using
the Likelihood Ratio (LR) test and corner solutions can be dealt with.
The application considered stems from the seminal study Banerjee et al.
(2013), in which the authors investigate the diffusion of micro-finance in
Indian village networks. Linked agents repeatedly exchange new information,
the information status being unobserved. Upon being newly informed, they can
make an observable borrowing choice. We use eleven of the village networks
from this data set in our simulation study. Nonetheless, it is important to
emphasize that the applicability of our algorithm goes well beyond this
particular model. A model in which an observed outcome depends on an
unobserved status lends itself to various applications in economics. Instead
of information, one could model technology spill-over, where we observe the
adoption of new technologies, but for those that abstain from it we do not
know whether this is by deliberate choice or by lack of knowledge.
Alternatively, one can estimate a model in which the probability of (observed)
micro-business default depends on (unobserved) mutual lending among friends.
In recent years, the amount of data on (action taking place through) social
networks that is available has increased drastically, providing new exciting
research possibilities, but also serious challenges for econometricians. What
shies away many applied researchers from fully embracing this opportunity and
using MLE in settings where it provides clear advantages is often the lack of
tractable, easily implementable algorithms. While established software
packages exist for common estimation procedures, these typically work very
well for specific tasks, but lack the flexibility required by network models.
They are not fully efficient in terms of speed and provide little opportunity
to deal with large dimensionality of the data. Research into methodological
approaches facilitating ML estimation in such models thus has the potential to
be beneficial. In the current paper, I make a contribution to the this new
strand of research.
The paper is organized as follows: Section 2 provides an overview of the
model. In section 3 we highlight the challenges of ML estimation in this model
and introduce the basic trimming procedure. Section 4 outlines the Monte Carlo
study. Section 5 provides and analyses the Monte Carlo results. Section 6
contains the results from applying the trimming estimator to four real
villages using actual adoption data. Section 7 concludes. The Appendices
highlight how features of the network impact the algorithm’s performance and
the shape of the error curve.

##  2 The Model

In this and the following sections, we use the terminology of the concrete
application despite our algorithm being applicable to many research questions.
We dispose over a sample of villages, indexed by $v=1,...,V$.
$N_{v}$ individuals in village $v$ are linked in a network, represented by the
network adjacency matrix $G_{v}$. While villagers $i=1,...,N_{v}$ entertain
relationships among themselves, they are supposed not to interfere with agents
living in other villages. Consequently, to ease notation, in the following we
drop the subscript $v$ and we outline the model with an exemplary village.
The symmetric matrix $G$ comprises binary variables indicating the presence
(absence) of a link. If the entry in row $i$, column $j$ takes the value of
one (i.e. $g_{ij}=g_{ji}=1$), we denominate $i$ and $j$ as “neighbors” or
“friends”. An organization enters the community and starts providing a new
technology to its members. In period $t=0$, they advertise their innovation to
a subset of them (referred to as the “information injection points” or “IPs”)
and thereafter rely on word-of-mouth marketing.
In each subsequent period ($t=1,...,4$), two processes take place: first,
newly informed individuals face the choice of whether or not to adopt the
technology, second, informed individuals can instruct their neighbors about
the novel opportunity.
The process is modeled using the random matrices $Y$ and $S$, containing dummy
variables for respectively the participation and information statuses of each
of the villagers at each point in time. Using the first subscript for
individuals and the second subscript for time periods, thus $Y_{it}=1$
($S_{it}=1$) (i.e. the row $i$, column $t$ element of $Y$ ($S$) displays the
value one) implies that $i$ participates (is informed) in period $t$. The
distributions of the random matrices $Y$ and $S$ depend on the village network
($G$) and the information injection $s_{0}$).
For each village, we observe the network ($G$), the information initialization
$s_{0}$ and the individual participation decisions over time (i.e. one
realization of $Y$). The information statuses of all inhabitants but the IPs
are generally unobserved. In particular, there usually exist various
realizations of $S$ that are in accordance with the data at hand.
The following assumptions are made:

Assumption 1: Independence across villages
Villages can be treated as independent entities. In particular, there is no
link between any two agents that reside in different communities.

Assumption 2: Exogenous network
The network is exogenous and observed. Measurement error is negligible.

Assumption 3: Timing
Each period consists of two processes: First, newly informed individuals
decide upon participation, second, information is exchanged. This implies that
$Y$ is of dimension $N\times 4$ while $S$ is of dimension $N\times 3$: since
information is exchanged after the participation decisions, modeling the
fourth period’s information exchange is redundant.

Assumption 4: Information is a pre-condition for participation

Assumption 5: Participation is a one-time opportunity
Each period only newly informed individuals face the participation decision.
Having opted in (out), the respective individual will thereafter stay in the
set of participants (non-participants) forever.

Assumption 6: Distributional assumption
Conditional on being newly informed, the random variables $Y_{it}\hskip
4.26773pt\forall i=1,...,N;\hskip 4.26773ptt=1,...,4$ are i.i.d. and follow a
Bernoulli distribution. The probability to participate conditional on being
newly informed is $p$.

Assumption 7: Information is never forgotten
Individuals can only switch their information status once (from being
uninformed ($S_{i(t-1)}=0$) to being informed ($S_{it}=1$)). Any informed
individual remains potentially informing her neighbors every period.

Assumption 8: Information exchange
In each period, informed individuals may transmit the information to their
neighbors. On average, they do so with probability $q$. Transmitting is
independent across all links.
Let the random variable $I_{(ij)t}$ denote the indicator that shows that
individual $i$ has sent the information to individual $j$ in period $t$.
Conditional on $i$ being a sender, the variables $I_{(ij)t}\hskip
2.84544pt\forall i\neq j;t=1,...,3$ are i.i.d. and follow a Bernoulli
distribution with $E[I_{(ij)t}]=q$.

The aim is to estimate
(i) the individual’s probability to participate if informed ($p$) and
(ii) individual’s probability to share information with acquaintances ($q$)

##  3 Establishing the (approximate) Log Likelihood function

Using the notation introduced above,

$\ell(p,q)=Pr\big{(}Y_{1}=y_{1},...,Y_{T}=y_{T}|S_{0}=s_{0},G,p,q\big{)}$ (1)

is the probability to observe the actual data at hand, given the (nonrandom)
village network, the parameters and the information initiation and

$\mathcal{L}(p,q)=\log\hskip
2.84544pt\Big{(}Pr\big{(}Y_{1}=y_{1},...,Y_{T}=y_{T}|S_{0}=s_{0},G,p,q\big{)}\Big{)}$
(2)

is the village log likelihood function.
However, the probability to observe any particular outcome pattern depends on
the (unobserved) information propagation.111Note that knowing the probability
of (not) observing somebody as a participant depends on her chances to receive
the information which in turn depends on which of her neighbors are informed
In the following, we use “information scenario” to denote a unique sequence
$S_{1}=s_{1},...,S_{(T-1)}=s_{(T-1)}$. The set $\mathbb{S}$ comprises all
possible information scenarios. Then the log likelihood function is (by the
law of total probability)

$=\log\Bigg{(}\displaystyle\sum_{s\in\mathbb{S}}Pr\Big{(}Y_{1:T}=y_{1:T},S_{1:(T-1)}\in
s|S_{0}=s_{0},G,p,q\Big{)}\Bigg{)}$ (3)

The joint probability of the outcome matrix and the information status matrix
can, by iterated conditioning, conveniently be factorised into four time
period specific factors, which in turn are a product of $N$ individual
specific factors. Denoting by $l_{t}$ the likelihood up to and including
period $t$ and by $\Delta\ell_{t}$ the change in the likelihood function as we
move from period $t-1$ to period $t$, we can rewrite (1) as

$\ell=\underbrace{\underbrace{\underbrace{\displaystyle\sum_{\tau=1}^{\\#{\mathbb{S}}}\ell_{1}\times\Delta\ell_{2(\tau)}}_{\ell_{2}}\Delta\ell_{3(\tau)}}_{\ell_{3}}\Delta\ell_{4(\tau)}}_{\ell_{4}}\hskip
28.45274pt\Delta\ell_{t(\tau)}=\prod_{i=1}^{N}\Delta\ell_{it(\tau)}$ (4)

As we shall see, for any particular information scenario, the factors
appearing in (4) are straightforward to evaluate and thus the joint
probability of the outcome and that particular scenario are easily computed.
Applying the law of total probability then amounts to summing up these joint
probabilities over all possible information scenarios. The challenge stems
from the fact that the cardinality of $\mathbb{S}$ quickly becomes
prohibitively large.

Individual $i$’s contribution to the village log likelihood function depends
on any other individual only insofar as that $i$ may newly receive the
information from her. Let

$r_{it}=P(S_{it}=1|S_{i(t-1)}=0,S_{t-1}=s_{t-1},G,p,q)$ (5)

denote $i$’s probability to newly receive the information (from any of her
neighbors) in period $t$. Using $r_{i(t-1)}$, we can categorize villagers at
any point in time into four groups according to what they contribute to $\ell$
at this point in time (that is, according to $\Delta\ell_{it}$):

  * •

former participants: $\Delta\ell_{it}=1$
These individuals are certain to remain (informed) participants until the end
of the modeling horizon.

  * •

new participants: $\Delta\ell_{it}=r_{i(t-1)}p$
These individuals are observed to experience a switch in their outcome, which
(according to the modeling assumptions) must be preceded by a switch in their
information status.

  * •

non-participants out of reach $\Delta\ell_{it}=1$
These individuals are too far away from any IP to possibly have received the
information and thus certain to be uninformed.

  * •

potentially informed individuals (PIIs)
Sufficiently close to an IP to potentially receive the information, they yet
do not indicate (by participating) that they have done so. As a consequence,
while the likelihood contribution for the three groups above is unequivocal,
for the PIIs, three scenarios (each leading to a specific likelihood
contribution) are indistinguishable in terms of the empirical evidence that
they generate.

    * –

scenario A: newly informed PIIs $\Delta\ell_{it}=P(A_{it})=r_{i(t-1)}(1-p)$
This group has received the information in the last exchange and opts out this
period.

    * –

scenario B: uninformed PIIs  $\Delta\ell_{it}=P(B_{it})=(1-r_{i(t-1)})$
They entered last period’s information exchange uninformed and also did not
receive the information.

    * –

scenario C: previously informed PIIs  $\Delta\ell_{it}=P(C_{it})=1$
Since they obtained the information and opted out in a previous period they
will thus abstain from participation forever.

We can thus see that the PIIs are the origin of the dimensionality problem:
without them, there would be only one information status matrix that could
have generated the data. PIIs introduce a twofold challenge. First, their own
information status cannot be derived from the data and hence their own
contribution to the likelihood function is scenario specific. Second, whether
or not they enter any particular period informed impacts all their neighbours’
(and later on their neighbours’ neighbours’) information reception
probabilities, implying that these individuals’ likelihood contributions
become scenario specific as well. As the cardinality of $\mathbb{S}$ increases
exponentially in the number of PIIs, hence (2) cannot be computed.
Due to the interdependence described above, likelihood contributions being
scenario specific implies that $i^{\prime}s$ contribution depends on the
previous information statuses of all her neighbours as well as on her own
current status.
As claimed above, for any particular information scenario, the individual
likelihood contributions can be calculated straightforwardly: first, the
individual information reception probabilities $r_{it}$ are computed, then
these are plugged into the formulas above, where for PIIs we choose formula A,
B or C, depending on her own past and current status. Since $i$ is informed as
long as any of her neighbors sends the information, we can use the counter-
factual probability (nobody informs $i$) to calculate

$r_{it}=1-\prod_{j}\underbrace{(1-g_{ij}qs_{j(t-1)})}_{\mbox{
\footnotesize\begin{tabular}[]{c}if $j$ is an informed neighbor of $i$,\\\ she
does not send the information\end{tabular}}}$ (6)

From period two onward, different information status vectors from the last
period lead to different PIIs and different probabilities of any individual to
receive the information in the current period, thus $r_{it}$ needs to be
computed for each $S_{(t-1)}\in\mathbb{S}$.
The origin of the dimensionality problem will also be the point of attack for
our algorithm since a restriction of the number of PIIs directly translates
into a pronounced reduction of information scenarios.
For any PII who enters a time period uninformed, the scenarios A: “newly
informed and opted out” and B: “uninformed” are observationally equivalent.
The basic idea of our trimming procedure is to, for a certain number of PIIs,
restrict the log likelihood function to include only one of these two cases.
We illustrate the dimension reduction strategy using two toy villages. The
first village consists of six individuals one of which is the IP. Even in this
very small and rather sparse network, three rounds of information exchanges
result in 92 information propagation possibilities.

Figure 1: Village Graph 11 IP 2 3 4 5 6

Consider a slightly larger and denser network.

Figure 2: Village Graph 21 IP 2 3 4 5 6 7 8 9 10

What has changed from one graph to the other is a substantial increase in the
number of intermediate PIIs. A large number of PIIs implies that the number of
possible information propagation possibilities grows very large. What can
happen in any later information exchange always depends on what has happened
in previous ones. Consequently, for each information scenario, we would, in
each intermediate time period, need to store the information who has been
informed already in order to know who can be informed thereafter and to
calculate the scenario specific individual information reception probabilities
($r_{it}$). If we wanted to evaluate the exact log likelihood function that
would imply storing $2^{4}$ period one information status vectors, for each of
them computing and storing all possible period two information status vectors,
in order to finally know - for each realization of $S_{1:2}$ \- the final
(scenario specific) information reception probabilities of all agents. If the
network is large and dense, it is our inability to store so many intermediate
information status vectors and the time needed to process files that prevent
us from establishing the log likelihood function.
If we have not eight, but roughly sixty to a hundred intermediate PIIs, then
there would be not a billion or trillion, but a quintillion or nonillion of
possible realizations of $S_{1:2}$.
To tackle the problem, we apply a trimming strategy. We will only allow a
fixed number of $d$ PIIs to have two possible information status variables in
the next period. For all other PIIs, the next period’s information status will
be set to a default (either one, in which case we assume the agent to be
informed and opted out, or zero in which case we presume her to be
uninformed). In particular, the individual will be trimmed to whichever of the
two scenarios is more likely in the given period. If in each of the first two
exchanges, the maximal number of PIIs is set to a trimming value of $d$, then
we end up with a number of $s_{1:2}$ scenarios that cannot exceed $2^{2d}$.
Storing information scenarios is only necessary to calculate the probabilities
of what can follow. Since nothing follows after the third information
exchange, a large number of final PIIs is absolutely un-problematic and there
is no need to restrict the last wave of PIIs.
Accordingly, we need to select $d$ PIIs for which the two scenarios will be
considered. Recapitulating that each PII can, in each exchange in which she
can reached be either newly informed and uninterested or uninformed, we can
see that there exists a threshold $r_{it}$ such that both are equally likely.

$\underbrace{(1-p)r_{i}}_{\begin{subarray}{c}\mbox{probability of scenario
A:}\\\ \mbox{$i$ is informed and opts
out}\end{subarray}}=\underbrace{(1-r_{i})}_{\begin{subarray}{c}\mbox{probability
of scenario B:}\\\ \mbox{$i$ is uninformed}\end{subarray}}$ $\Rightarrow
2-\frac{1}{r_{i}}=p$ (7)

The simple trimming rule identifies agents that are the furthest away from
this threshold and trims their information status to either zero (if the
agent’s information reception probability falls below the threshold) or one
(if it exceeds the threshold). This is repeated until only $d$ PIIs are left
unrestricted. The basic idea of the proceeding is that if an agent is far away
from the threshold, the probability of one scenario will be large while the
other will be small and as such, neglecting the less likely scenario for these
agents is the optimal choice from the current perspective (i.e. not taking
into account what can happen thereafter) in the sense that the currently most
likely scenarios are chosen. It may be the case, however, that a trimming
choice reveals itself as sub-optimal in one of the following periods. Most
dramatically, imagine a period-3 participant that is two links away from the
nearest IP. The algorithm may set all neighbors of her neighbors to the
default status “uninformed” in the first information exchange, which obviously
has probability zero given that someone must have informed the period-3
participant. In the Appendix, we discuss under which circumstances such
erroneous choices occur and how they depend on the network topology.
We demonstrate the trimming with the second graph above. Assume we are at a
grid-point $p,q$ for which $2-\frac{1}{q}>p$ implying that scenario A is more
likely for any PII and that we pick a $d$ value of 2. All PIIs featuring the
same number of IP links in the first information exchange, the algorithm
arbitrarily picks individual 2 and 3 to be trimmed. With 2 and 3 being newly
informed and opting out, there are 4 scenarios resulting from the first
exchange. Depending on which scenario was realized, there are four or five
period-two PIIs. In any case, however, 6 and 7 will always be the ones with
the largest number of links to the information and hence the algorithm trims
them to scenario A. In the last exchange, there will be three or four PIIs. No
individual will have more links to the information than 10 and as such, she
will be subject to trimming. If there are four PIIs, then another PII to be
trimmed will be chosen from the remaining three ones.
Assume next that the grid-point is such that $2-\frac{1}{(1-(1-q)^{4})}<p$
implying that scenario B is more likely for any PIIs and that we again pick a
$d$ value of 2. This time, 2 and 3 will be trimmed to being uninformed in the
first exchange. As such, the second exchange features four to six PIIs. No PII
can have less links to the information than 2 and 3 and thus they will be
trimmed again and not receive the information. Whenever there are six PIIs,
two additional PIIs that have one link to the information will be trimmed. The
last exchange again trimms 2 and 3 and if necessary up to three other
PIIs.222Trimming an individual to zero implies that she temporarily looses her
right to receive the information or that the link is temporarily deactivated.
She can, however, enter the PIIs in the next period. Whether or not she will
be cut again depends on her and everybody else’s probability to receive the
information in that period.
For each link portfolio an agent can have, there exist a specific $pq$
relationship such that the two scenarios are equally likely. Figure 3
illustrates this with a link portfolio of one, two, three and four links.

Figure 3: Scenario Equivalence Thresholds for PIIs With 1 to 4 Informed
Neighbours1 $p=2-\frac{1}{q}$ 2 $p=2-\frac{1}{(2q-q^{2})}$ 3
$p=2-\frac{1}{(3q-3q^{2}+q^{3})}$ 4 $p=2-\frac{1}{(4q-6q^{2}+4q^{3}-q^{4})}$
$q$$p$

The trimming strategy works better when agents are furthest away from the
threshold rate. As a direct consequence, the best performance can be expected
whenever either $p$ or $q$ is small and the respective other large.
Worth mentioning, note that the number of scenarios considered is endogenous.
Each of the $2^{d}$ period-1 information status vectors entails a different
number of scenarios that are subsequently possible as the umber of agents in
reach of the information and the number of agents already informed vary. As a
consequence, each trimming choice induces a different number of scenarios
taken into account when establishing the log likelihood function. The rates at
which trimming occurs are endogenous too. If the aim is to always trim to a
certain number of PIIs, thus the lower and upper trimming rates vary on the
grid.

##  4 Monte Carlo Set-up

The aim of the study is to evaluate the performance of the simple trimming
technique as the trimming value ($d$) varies.

Table 1: Monte Carlo Parameters $N$ | size of the networks: 20
---|---
seed S | seed for drawing the IP
| ranging from 1 to 90
seed D | seeds for simulating the data
| ranging from 2 to 91
$p_{0}$ | participation rate used to simulate the data
$q_{0}$ | diffusion rate used to simulate the data
$V$ | sample size: 11
$R$ | number of replications: 90

We use eleven network adjacency matrices from Banerjee et al. (2013). These
were surveyed by asking villagers in India with whom they engage in regular
activities. We here use the union of the activity-specific networks, thus
assuming that any joint activity indicates the presence of a link. The
alternative would be to simulate the network data as well. However, this would
require us to specify a network formation model and to choose its parameters
and these choices would impact the study results.
The eleven villages are large and dense. In the Monte Carlo study, we need to
be able to evaluate the exact log likelihood function. To achieve
tractability, we pick a sub-matrix consisting of $N$ individuals. By the same
token, to limit the number of PIIs, only one individual will obtain the
information initially. This individual is randomly drawn from the $N$
villagers. The sub-matrix used in each replication is different.333The
algorithm starts at the element row seed S, column seed S situated on the
diagonal and reads out a square 20 times 20 matrix
Each repetition consists of simulation and estimation. While $N$, $p_{0}$,
$q_{0}$ and $V$ are held fixed, each repetition distinguishes itself by its
unique combination of the seeds used to initialize the random number
generators. We consider the settings: case 1: $p_{0}=0.5,q_{0}=0.5$, case 2:
$p_{0}=0.1,q_{0}=0.9$ and case 3: $p_{0}=0.9,q_{0}=0.1$ with $N=20$ and
$V=11$.

Simulation: The participation data is simulated according to the model
assumptions using parameters $p_{0}$ (participation probability) and $q_{0}$
(information transmission probability) and the network sub-matrices. Each
replication chooses a different sub-matrix out of the network matrix.
Following the random draw of the initially informed individual and the random
determination of her participation status, there are three rounds of
information diffusion and participation. Each round, for each individual
linked to the information, we draw a number from the uniform distribution in
the interval $[0,1]$ and specify that the information is passed on if the
number drawn is smaller or equal to $q_{0}$. Equivalently, for each newly
informed individual, the number drawn from the standard uniform distribution
needs to be smaller or equal to $p_{0}$ for her to participate.
This leads to a participation data matrix for each village, i.e. one sample.

Estimation: The log likelihood function is established as the sum over
information scenarios and each scenarios has a different number of potentially
informed individuals (PIIs). Our trimming strategy sets a maximum to this
number and sets PIIs exceeding this number to their more likely scenario in
the first two exchanges (trimming is computationally unnecessary in the last
exchange). In the simulation study, we wish to let the trimming value ($d$)
vary and evaluate the consequences. Therefore, for each village, we find the
maximal number of PIIs ($\bar{d}_{v}$). We then compute the approximate log
likelihood function for $d=0,...,\bar{d}_{v}-1$ (denoted $\mathcal{L}_{v,d}$)
and the correct log likelihood function, i.e. $d=\bar{d}_{v}$ which implies no
trimming (denoted $\mathcal{L}_{v,\bar{d}_{v}}$). Each time, the number of
PIIs is trimmed down to size $d$ in the first two information exchanges. Then
the approximate sample log likelihood function for each trimming value is
computed by aggregating all villages, i.e.

$\mathcal{L}_{d}=\sum_{v=1}^{V}\mathcal{L}_{v,max(d,\bar{d}_{v})}$

(i.e. if the trimming value exceeds the maximal number of PIIs in the village,
the village is not subject to trimming). Changes of the trimming value when it
is low hence impact practically all villages and in the villages practically
all scenarios but as the trimming value grows towards its maximum, only few
villages and scenarios are actually subject to trimming. Then the peak of the
log likelihood function for each $d$ is found by grid search and confidence
sets are established using the LR test. Each repetition hence delivers a
sequence of estimates $\hat{p}_{d},\hat{q}_{d}$ together with their confidence
sets for $d=0,...,max(\bar{d}_{v})$. We compare the estimates at different
trimming values with the estimates that result from applying ML to a shortened
time horizon of two periods.

##  5 Monte Carlo Results

For each case, the proceeding described above leads to ninety series of
estimates. Remembering that trimming takes place whenever the number of PIIs
exceed the desired trimming value, thus the lengths of this series is pinned
down by the largest number of PIIs in any village and the last estimate of
this series is the four-period MLE. Additionally, we dispose over the MLE that
results from restricting the time horizon to two periods (i.e. the “Two-period
Estimator” from chapter two).
In Figures 4-15, we plot the mean estimates and their empirical standard
errors, the estimated density and the histograms of the empirical probability
mass function.
For each case the first two plots depicts the mean estimate ($\bar{\hat{p}}$
and $\bar{\hat{q}}$) as a function of the trimming value, the mean being taken
over the 90 estimates (Figures 4, 8 and 12). The vertical bars have the length
of the empirical standard error in each direction, the latter being simply
computed as the square root of average squared deviation of the individual
estimate from the mean estimate.

$\left(\frac{1}{89}\sum_{r=1}^{90}(\hat{p}_{r}-\bar{\hat{p}})^{2}\right)^{1/2}\hskip
56.9055pt\left(\frac{1}{89}\sum_{r=1}^{90}(\hat{q}_{r}-\bar{\hat{q}})^{2}\right)^{1/2}$

The trimmed estimates converge to the MLE rather quickly. However, it needs to
be kept in mind that we have restricted the village sizes to twenty and as a
result, a substantial fraction of villages simply feature very few PIIs, in
particular when participation rates are not too small. Then, these villages
are already at the MLE, even for minor trimming values. The results are
nonetheless encouraging in the sense that trimming substantially increases
computational speed and does not hurt much (compared to the MLE) as long as
the sample includes enough villages for which no more than one third of the
PIIs are trimmed. The efficiency gains compared to the “Two-period Estimator”
are substantial, in particular for the diffusion rate.
Thereafter, for each case, we depict depict the kernel density estimates
together with the empirical quantiles (first and third)(Figures 5(b), 9(b) and
13(b)). The density of the “Two-period Estimator”, depicted in orange, is
substantially flatter and more often exhibit multiple local maxima.
The histograms in the third plot series (Figures 6(b), 10(b), 14(b) and 7, 11,
15) reconfirm that the “Two-period estimates” are much more dispersed,
especially for the diffusion rates. As the Trimming estimates converge, the
histograms for larger trimming values become indistinguishable from the MLE.

The following case-specific observations can be made.
Case 1:
The densities for “Trimming estimates” exhibit a distinct peak in the
probability mass function, which is not the case for the “Two-period
estimates”. Observe that for the latter, the estimated diffusion rate for a
substantial fraction of the sample is at 0.99. Also, the estimates are much
less dispersed for the “Trimming-Estimator” than the “Two-period Estimator”.
Case 2:
The gains from increasing the trimming value are made exclusively for the
diffusion rate estimates, while the participation rate estimates are very
similar.
The standard deviations are smaller and the log likelihood surfaces are more
peaked for small trimming values.
Case 3:
Both $p$ and $q$ are well identified whenever adoption rate is high (except
for the extreme case of $d=0$, which would imply trimming all PIIs).
Unsurprisingly, in this case also the performance difference as compared to
the “Two-Period estimator” is smallest.

Figure 4: Case 1: $p_{0}=0.5,q_{0}=0.5$ Estimates and Standard Deviations

Figure 5: Case 1: $p_{0}=0.5,q_{0}=0.5$,

(a) Estimated Densities $p$ for Different Trimming Values (black) and the Two-
period MLE (orange)

(b) Estimated Densities $q$ for Different Trimming Values (black) and the Two-
period MLE (orange)

Figure 6: Case 1: $p_{0}=0.5,q_{0}=0.5$ Histograms (Trimming Estimator)

(a) Histograms $p$

(b) Histograms $q$

Figure 7: Case 1: $p_{0}=0.5,q_{0}=0.5$ Histograms (Two-period MLE)

Figure 8: Case 2: $p_{0}=0.1,q_{0}=0.9$ Estimates and Standard Deviations

Figure 9: Case 2: $p_{0}=0.1,q_{0}=0.9$,

(a) Estimated Densities $p$ for Different Trimming Values (black) and the Two-
period MLE (orange)

(b) Estimated Densities $q$ for Different Trimming Values (black) and the Two-
period MLE (orange)

Figure 10: Case 2: $p_{0}=0.1,q_{0}=0.9$ Histograms (Trimming Estimator)

(a) Histograms $p$

(b) Histograms $q$

Figure 11: Case 2: $p_{0}=0.1,q_{0}=0.9$ Histograms (Two-period MLE)

Figure 12: Case 3: $p_{0}=0.9,q_{0}=0.1$ Estimates and Standard Deviations

Figure 13: Case 3: $p_{0}=0.9,q_{0}=0.1$,

(a) Estimated Densities $p$ for Different Trimming Values (black) and the Two-
period MLE (orange)

(b) Estimated Densities $q$ for Different Trimming Values (black) and the Two-
period MLE (orange)

Figure 14: Case 3: $p_{0}=0.9,q_{0}=0.1$ Histograms (Trimming Estimator)

(a) Histograms $p$

(b) Histograms $q$

Figure 15: Case 3: $p_{0}=0.9,q_{0}=0.1$ Histograms (Two-period MLE)

##  6 Real Data Application

This section presents the results of an application of the “Trimming-
estimator” to four selected real and full-size villages. This estimation was
run on the powerful Amazon-Web-Service server cluster and I am grateful that
funds have been made available for this estimation, which also provided me
with the opportunity to gain valuable experience with respect to the usage of
this server cluster.
The time horizon is set to 3, the chosen villages are 1, 12, 31 and 67. The
choice was guided by the fact that in particular these four villages exhibit a
steady increase in the observed real adoption rates, whereas for many other
villages there is a distinct jump. With jumps being potentially associated to
measurement error, I hope to have chosen the villages with the most
informative observed adoption patterns. These villages have, respectively,
182, 175, 153 and 193 inhabitants.
Due to the computational cost, it was infeasible to calculate the objective
function over the entire grid. However, this was also not necessary. Extensive
testing indicated that the convergence was relatively slow (approximately 0.01
when the trimming value increases by two for $q$ and practically nonexistent
for $p$). A relatively low trimming value of eighteen was chosen to define the
subgrid to be evaluated. The subgrid contains 48 point with the diffusion rate
varying from 0.58 to 0.73 and the adoption rate from 0.23 to 0.25. This range
was chosen according to a prognostic calculation such that the resulting grid
would cover approximately most of the five present confidence set of the final
largest feasible trimming value, which was 32.
For a trimming estimation with three time periods that starts from a trimming
value that is low compared to the total number of villagers, the computation
time roughly doubles when the trimming value is increased by one.
Parallelization was done over both villages and gridpoints. The final
computation times were 651.2 hours (village 1), 609.5 hours (village 12),
480.7 hours (village 31) and 751.8 hours (village 67).

Table 2: Sequence of Trimming Estimates | d=18 | d=28 | d=29 | d=30 | d=31 | d=32
---|---|---|---|---|---|---
$p$ | 0.24 | 0.25 | 0.25 | 0.25 | 0.25 | 0.25
$q$ | 0.73 | 0.68 | 0.68 | 0.67 | 0.67 | 0.66
5% conf. |  |  |  |  |  |
set $p$ | $[0.23,0.25]$ | $[0.23,0.25]$ | $[0.23,0.25]$ | $[0.23,0.25]$ | $[0.23,0.25]$ | $[0.23,0.25]$
5% conf. |  |  |  |  |  |
set $q$ | $[0.66,0.73]$ | $[0.61,0.73]$ | $[0.6,0.73]$ | $[0.6,0.73]$ | $[0.59,0.73]$ | $[0.59,0.73]$

The fact that the estimate is situated at the border of the grid is not
problematic given that testing indicated that convergence of $p$ was achieved
much faster than convergence of $q$ and as such, not much change can be
expected in the adoption parameter when the trimming value further increases.
The confidence sets are enlarging when the trimming value increases. This is
intuitive: the subgrid around the peak is situated in an area in which all
agents are trimmed to being “informed and opted out” (the small $p$, high $q$
area). A change in $q$ will thus have the same effect on all trimmed
individuals leading to a more pronounced peak, while in the full likelihood,
the impact of a change in $q$ would be different for different scenarios, thus
resulting overall in a flatter log likelihood function. This hints towards the
finding that indeed the trimming estimate may, in cases of relatively low
trimming values, lead to an over-pronounced peak such that it may be necessary
to adjust critical values accordingly. This same finding is also in the
contour and surface plots.
The “Two-period Estimate” estimate is outside the interval considered. Given
the test results, it is expected that the full MLE with three time periods
will converge to a value that is somewhere in between the trimming and the
“Two-period estimate”.
Estimation using only four villages is highly challenging as we can deduct
from the sizes of the “Two-period estimate”’s confidence sets. Note that when
testing on the basis of the “Two-period estimate”, the hypothesis that it
equals the trimming estimate cannot be rejected even at 30%.
Since practically all points in the sub-grid are in the 5% confidence set,
hence I compute the confidence sets for higher confidence values. As compared
to the “Two-period estimate”, the “Trimming estimate”’s confidence set is
extremely narrow. This is in line with the observation that the confidence
sets widen when the trimming value is increased.

Figure 16: Confidence Sets Based on the Two-Period estimate of Chapter 2
Figure 17: Confidence Sets Based on the Trimming Estimate

Figure 18: Likelihood Surface and Contour Based on the Trimming Estimate

Figure 19: Likelihood Surface and Contour Based on the Two-Period Estimate
from Chapter 2

Figure 20: Likelihood Surface and Contour Based around the peak on the Two-
Period Estimate from Chapter 2

##  7 Conclusion

The “Trimming estimator” provides an attractive alternative when exact MLE
estimation is infeasible. Substantial increases in computational speed can be
achieved whenever the sample comprises a sufficiently large fraction of
villages for which no more than one third of the PIIs are trimmed. The
efficiency gains are substantial, in particular for the diffusion rate
estimate. This is in particular the case when the adoption rate is low.

##  8 Appendix

###  8.1 Details on Establishing the (Approximate) Log-likelihood Function

  * •

In order to find an expression for the log likelihood function, we will first
establish the joint density of $Y$ and $S$ and then integrate out the
unobserved information-status vector. This is an application of the law of
total probability. Since $S$ is discrete, we establish the joint probability
of the outcome $Y$ and each information scenario that could have generated it
and then sum over information scenarios.

  * •

Conditional on $S_{0:t-1}$, the vector ${\bf Y_{t}}$ fulfills the strong
Markov property with respect to its own past values444That is
$Pr(Y_{t}=y_{t}|Y_{1:(t-1)}=y_{1:(t-1)},S_{0:t-1}=s_{0:t-1},G,p,q)=Pr(Y_{t}=y_{t}|Y_{(t-1)}=y_{(t-1)},S_{0:(t-1)}=s_{0:t-1},G,p,q)$
and the weak Markov property with respect to the information status vectors
555That is
$Pr(Y_{t}=y_{t}|Y_{(t-1)}=y_{(t-1)},S_{0:(t-1)}=s_{0:(t-1)},G,p,q)=Pr(Y_{t}=y_{t}|Y_{(t-1)}=y_{(t-1)},S_{(t-1)}=s_{(t-1)},S_{(t-2)}=s_{(t-2)},G,p,q)$:
first, we need to know whether or not the individual already enters the period
as a participant (thus we condition on $Y_{t-1}$) 666If $Y_{i(t-1)}=1$, the
individual participates forever, if $Y_{i(t-1)}=0$ and $Y_{it}=1$, she is a
new participant. Else, she is a non-participant.. For non-participants, the
three possible cases can only be distinguished on the basis of past values of
$S$. In particular, when establishing the probability of $Y_{t}$, we must know
whether or not a switch in the information status occurred during the last
information exchange (thus we condition on $S_{t-1}$ and $S_{t-2}$).

  * •

The individual outcome variables (i.e. the elements of ${\bf Y_{t}}$) are
independent of one another once we condition the outcome of individual $i$ on
her own individual (scalar) past outcome and her own individual (scalar) past
two information status variables777 Consequently, we must condition
$Y^{i}_{t}$ on $S^{i}_{t-1},S^{i}_{t-2}$ and on $Y^{i}_{t-1}$

  * •

The vector ${\bf S_{t}}$ fulfills the strong Markov property with respect to
past values (rows) of both the outcome and the information
status.888$Pr(S_{t}=s_{t}|Y_{1:t}=y_{1:t},S_{0:(t-1)}=s_{0:(t-1)},G,p,q)=Pr(S_{t}=s_{t}|Y_{t}=y_{t},S_{(t-1)}=s_{(t-1)},G,p,q)$
This is the case because we need to know whether the outcome signals us that
the individual must be informed (since she participates), whether she was
previously informed and opted out and what is her probability to be newly
informed

    * –

It is sufficient to condition on the previous (scalar) individual outcome

    * –

It is necessary to condition on the entire past information status vector:
$i^{\prime}s$ probability to be newly informed is a function of her neighbor’s
information status vectors 999Consequently, we must condition $S^{i}_{t}$ on
$Y_{t}^{i}$ and on $S_{t-1}$

These facts can be used to factorize the log likelihood function.
Recall that we denote a possible realization of the random $N\times T-1$
matrix $S$ as an “information scenario” and collect all possible such
scenarios in the set $\mathbb{S}$. Then $s\in\mathbb{S}$ an information (or,
equivalently, a sequence of information status vectors
$\\{S_{1}=s_{1},S_{2}=s_{2},...,S_{(T-1)}=s_{(T-1)}\\}$) that is permissible
given the data at hand).

step 1: we apply the law of total probability

$Pr\Big{(}Y_{1:T}=y_{1:T}|s_{0},G,p,q\Big{)}=Pr\Big{(}Y_{1}=y_{1},Y_{2}=y_{2},...,Y_{T}=y_{T}|S_{0}=s_{0},G,p,q\Big{)}=$
$=\displaystyle\sum_{s\in\mathbb{S}}Pr\Big{(}Y_{1:T}=y_{1:T},S_{1:(T-1)}\in
s|S_{0}=s_{0},G,p,q\Big{)}=$

step 2: only the past matters for current outcome variables, only the past and
the present matter for current state variables (assumption 3: timing)

${\footnotesize\begin{array}[]{c}Pr\big{(}Y_{1}=y_{1}|G,S_{0}=s_{0},p,q\big{)}\times\vspace{.1cm}\\\
\displaystyle\sum_{s\in\mathbb{S}}\Bigg{\\{}Pr\big{(}S_{1}=s_{1}\in
s|Y_{1}=y_{1},G,S_{0}=s_{0},p,q\big{)}Pr\big{(}Y_{2}=y_{2}|Y_{1}=y_{1},S_{1}=s_{1}\in
s,G,S_{0}=s_{0},p,q\big{)}\times\\\
\displaystyle\prod_{t=3}^{T}Pr\big{(}S_{(t-1)}=s_{(t-1)}\in
s|Y_{1:(t-1)}=y_{1:(t-1)},S_{1:(t-2)}=s_{1:(t-2)}\in
s,G,S_{0}=s_{0},p,q\big{)}\\\
Pr\big{(}Y_{t}=y_{t}|Y_{1:(t-1)}=y_{1:(t-1)},S_{1:(t-1)}=S_{1:(t-1)}\in
s,G,S_{0}=s_{0},p,q\big{)}\Bigg{\\}}=\end{array}}$

step 3: we apply the Markov properties

${\footnotesize\begin{array}[]{c}Pr\big{(}Y_{1}=y_{1}|G,S_{0}=s_{0},p,q\big{)}\times\vspace{.1cm}\\\
\displaystyle\sum_{s\in\mathbb{S}}\Bigg{\\{}Pr\big{(}S_{1}=s_{1}\in
s|Y_{1}=y_{1},G,S_{0}=s_{0},p,q\big{)}Pr\big{(}Y_{2}=y_{2}|Y_{1}=y_{1},S_{1}=s_{1}\in
s,G,S_{0}=s_{0},p,q\big{)}\times\\\
\displaystyle\prod_{t=3}^{T}Pr\big{(}S_{(t-1)}=s_{(t-1)}\in
s|Y_{(t-1)}=y_{(t-1)},S_{(t-2)}=s_{(t-2)}\in s,G,S_{0}=s_{0},p,q\big{)}\\\
Pr\big{(}Y_{t}=y_{t}|Y_{(t-1)}=y_{(t-1)},S_{(t-1)}=S_{(t-1)}\in
s,S_{(t-2)}=S_{(t-2)}\in s,G,S_{0}=s_{0},p,q\big{)}\Bigg{\\}}=\end{array}}$
$\displaystyle Pr\big{(}Y_{1}=y_{1}|G,S_{0}=s_{0},p,q\big{)}\times\hskip
199.16928pt$
$\displaystyle\displaystyle\sum_{s\in\mathbb{S}}\Bigg{\\{}\displaystyle\prod_{t=2}^{T}Pr\big{(}S_{(t-1)}=s_{(t-1)}\in
s|Y_{(t-1)}=y_{(t-1)},S_{(t-2)}=s_{(t-2)}\in s,G,S_{0}=s_{0},p,q\big{)}$
$\displaystyle Pr\big{(}Y_{t}=y_{t}|Y_{(t-1)}=y_{(t-1)},S_{(t-1)}=s_{(t-1)}\in
s,S_{(t-2)}=s_{(t-2)}\in s,G,S_{0}=s_{0},p,q\big{)}\Bigg{\\}}=$

step 4: we apply the conditional independence across individuals

$\displaystyle\hskip
85.35826pt\displaystyle\prod_{i=1}^{N}Pr\Big{(}Y_{i1}=y_{i1}|S_{i0}=s_{i0},G,p,q\Big{)}\times$
$\displaystyle\displaystyle\sum_{s\in\mathbb{S}}\Bigg{\\{}\displaystyle\prod_{t=2}^{T}\Bigg{[}\prod_{i=1}^{N}Pr\Big{(}S_{i(t-1)}=s_{i(t-1)}|Y_{i(t-1)}=y_{i(t-1)},S_{(t-2)}=s_{(t-2)}\in
s,S_{0}=s_{0},G,p,q\Big{)}\times$ $\displaystyle\hskip
64.01869ptPr\Big{(}Y_{it}=y_{it}|Y_{i(t-1)}=y_{i(t-1)},S_{i(t-2):(t-1)}=s_{i(t-2):(t-1)}\in
s,S_{0}=s_{0},G,p,q\Big{)}\Bigg{]}\Bigg{\\}}$

We have thus established that the likelihood arises as a sum over the product
of (scenario specific) probabilities.
If we number the feasible information scenarios in $\mathbb{S}$ we can rewrite
the likelihood function concisely as

$=\underbrace{\underbrace{\underbrace{\ell_{1}\times\displaystyle\sum_{\tau=1}^{\\#\mathbb{S}}\Delta\ell_{2(\tau)}}_{\begin{subarray}{c}\ell_{2}=\ell_{1}\times\\\
Pr(S_{1}|Y_{1},S_{0},G,p,q)\\\
Pr(Y_{2}|Y_{1},S_{1},S_{0},G,p,q)\end{subarray}}\Delta\ell_{3(\tau)}}_{\begin{subarray}{c}\ell_{3}=\ell_{2}\times\\\
Pr(S_{2}|Y_{2},S_{1},G,p,q)\\\
Pr(Y_{3}|Y_{2},S_{2},S_{1},G,p,q)\end{subarray}}\Delta\ell_{4(\tau)}}_{\begin{subarray}{c}\ell_{4}=\ell_{3}\times\\\
Pr(S_{3}|Y_{3},S_{2},G,p,q)\\\
Pr(Y_{4}|Y_{3},S_{3},S_{2},G,p,q)\end{subarray}}\hskip
28.45274pt\Delta\ell_{t(\tau)}=\prod_{i=1}^{N}\underbrace{\Delta\ell_{it(\tau)}}_{\begin{subarray}{c}P(Y_{it}=y_{it}|Y_{i(t-1)},S_{i(t-1)},S_{i(t-2)})\\\
P(S_{i(t-1)}|S_{(t-2)})\end{subarray}}$ (8)

Where the latter is the scenario-specific individual contribution to the
village log-likelihood function. From the above, we can see two features that
are crucial for the computations:

  1. 1.

The likelihood is established as a sum over scenarios and a product over time
periods and the summands can be computed individually (e.g. by different
routines). The order in which scenarios are evaluated has no importance, which
makes it possible for us to “outsource” scenarios, store them and process them
later. We can have multiple routines (in fact even multiple CPUs) to all add
to the same likelihood value for a point on the grid.

  2. 2.

The Markov property enables us to save intermediate results without bothering
about the whole path that lead to them. Also, once a sequence has reached the
end of the time horizon and added its contribution to the log likelihood
function, the respective state vectors are not needed any more and thus memory
can be freed to deal with previously saved vectors.

As stated above, in any given period, villagers can be categorized into
distinct groups:

  * •

former participant: ${\bf Y_{i(t-1)}=Y_{it}=1}$

  * •

new participant: ${\bf Y_{i(t-1)}=0,Y_{it}=1}$

  * •

non-participant out of reach of the information ${\bf Y_{it}=0,r_{i(t-1)}=0}$

  * •

potentially informed individuals (PIIs) ${\bf Y_{it}=0,r_{i(t-1)}>0}$

To obtain the individual and scenario specific likelihood contributions, we
can simply plug the individual and scenario specific outcome and information
status variables into the algorithm we wrote for this purpose.

Density of the outcome variable
For the first outcome, the information status is observed.

$P(Y_{i1}=y_{i1}|S_{i0}=s_{i0})=s_{i0}\big{(}y_{i1}p+(1-y_{i1})(1-p)\big{)}+(1-s_{i0})(1-y_{i1})$

For all subsequent outcomes, the information status is unobserved.

$P(Y_{it}=y_{it}|Y_{i(t-1)}=y_{i(t-1)},S_{i(t-1)}=s_{i(t-1)},S_{i(t-2)}=s_{i(t-2)},S_{0}=s_{0},G,p,q)=$

$\underbrace{y_{it-1}y_{it}}_{\mbox{ \footnotesize\it\shortstack{a previous
participant \\\ participates for sure}}}\hskip 2.84544pt+\hskip
2.84544pt\underbrace{(1-y_{i(t-1)})y_{it}}_{\mbox{ \footnotesize\it a new
participant
}}\Big{[}\underbrace{s_{i(t-1)}(1-s_{i(t-2)})}_{\mbox{\footnotesize\it\shortstack{must
have been \\\ newly
informed}}}\underbrace{p}_{\mbox{\footnotesize\it\shortstack{and \\\ opted in
}}}\Big{]}+$ $\underbrace{(1-y_{i(t-1)})(1-y_{it})}_{\mbox{ \footnotesize\it a
non participant}}\Bigg{[}\underbrace{s_{i(t-1)}(1-s_{i(t-2)})}_{\mbox{
\footnotesize\it\shortstack{may have been \\\ newly informed
}}}\underbrace{(1-p)}_{\mbox{ \footnotesize\it\shortstack{ and \\\ opted
out}}}+\underbrace{(1-s_{i(t-1)})(1-s_{i(t-2)})}_{\mbox{ \footnotesize\it may
be uninformed }}+$ $\underbrace{s^{i}_{t-2}}_{\mbox{
\footnotesize\it\shortstack{ or may have been informed \\\ (and opted out) in
a previous period }}}\Bigg{]}$
$=y_{i(t-1)}y_{it}+(1-y_{i(t-1)})y_{it}\Big{[}s_{i(t-1)}(1-s_{i(t-2)})p\Big{]}+\\\
(1-y_{i(t-1)})(1-y_{it})\Big{[}1-s_{i(t-1)}(1-s_{i(t-2)})p\Big{]}$

Observe that an individual that participated previously will always
participate for sure. Further, a switch in the outcome $y_{it}=1\cap
y_{i(t-1)}=0$ indicates that the individual must have been newly informed.
Finally, the likelihood to observe no switch is one minus the likelihood to
observe a switch.

Density of the information variable
Note that it follows directly from the timing assumption that the random
variable $S_{it}$ depends only on (all individuals’) past information status
and on the individual’s own past participation status.

$P(S_{it}=s_{it}|S_{t-1}=s_{t-1},Y_{it}=y_{it})=P(S_{it}=s_{it}|r_{it},S_{i(t-1)}=s_{i(t-1)},Y_{it}=y_{it})=$
$\underbrace{y_{it}s_{it}}_{\mbox{ \footnotesize\it\shortstack{a participant
\\\ must be\\\ informed}}}+\underbrace{(1-y_{it})}_{\mbox{
\footnotesize\it\shortstack{a non-\\\
participant}}}\Bigg{[}\underbrace{s_{it}(1-s_{i(t-1)})r_{it}}_{\mbox{
\footnotesize\it\shortstack{may have entered the \\\ period uninformed\\\ and
newly received\\\ the
information}}}+\underbrace{(1-s_{it})(1-s_{it-1})(1-r_{it})}_{\mbox{
\footnotesize\it\shortstack{may have entered the \\\ period uninformed\\\ and
not received\\\ the information}}}+$ $\underbrace{s_{it}s_{i(t-1)}}_{\mbox{
\footnotesize\it\shortstack{may have entered the period informed\\\ (i.e.
previously opted out)}}}\Big{]}$

The probability to observe the data is then the density of the outcome,
conditional on the information status, times the density of the information
status. Plugging in the concrete values of
$y_{it},y_{i(t-1)},s_{it},s_{i(t-1)}$ of the five groups above,
straightforwardly leads to the expressions from above.
Summing up, we can formulate the village log likelihood function in terms of
the observed data. Due to the fact that the individual information status is
unobserved, we need to make usage of the law of total probability. While for
the individual outcome, it is sufficient to condition on the past individual
participation and information variables, the density of the diffusion
variables can only be established by conditioning on the whole system of past
state variables for all individuals.
An information scenario consists of a sequence of information status vectors
that, together with the outcome vectors, can be plugged into our algorithm to
yield the scenario specific likelihood contribution. The difference in
establishing the full versus the approximate log likelihood function simply
amounts to restricting the number of such scenarios considered.

###  8.2 Performance of the Algorithm

To ease notation in the following we use $P(y_{t})$ to signify
$P(Y_{t}=y_{t})$ and $P(s_{t})$ to signify $P(S_{t}=s_{t})$. These are the
probabilities of a particular outcome pattern or information status,
respectively.
With three time periods and the information initiation being observed, we need
to model two information exchanges. We dispose over an algorithm that, given
one particular outcome (vector $S_{1}=s_{1}$) resulting from the first
information exchange can compute all possible outcomes of the second
information exchange and evaluate the log likelihood function for period $T=3$
accordingly. If there are $e_{1}$ Potentially-Informed-Individuals (PIIs) in
period one, the problem arises from the fact that there are $2^{e_{1}}$ such
realizations of the random vector $S_{1}$, running the program that many times
is prohibitively slow. The aim is thus to establish an approximate log
likelihood function that considers only a subset
$\mathbb{S}_{1,c}\subset\mathbb{S}_{1}$ and neglects the remaining scenarios.
The number of scenarios considered is $2^{d}$. The challenge is to pick the
set $\mathbb{S}_{1,c}$ such that the probability mass of all scenarios
associated with this period one information scenario is larger than for any
scenario considered ($s_{1,c}\in\mathbb{S}_{1,c}$) than for any scenario not
considered ($s_{1,nc}\notin\mathbb{S}_{1,c}$). Using
$\mathbb{S}_{2}(s_{1})\subset\mathbb{S}_{2}$ to denote the collection of all
period two information status vectors that can follow a specific information
status vector $s_{1}$ (i.e. $P(s_{1},s_{2}|y_{1:2},s_{0},G,\theta)>0$, we wish
all of our selected $s_{1,c}$ to satisfy

$\sum_{\begin{subarray}{c}s_{2}\in\\\
\mathbb{S}_{2}(s_{1,c})\end{subarray}}P\big{(}y,s_{1c},s_{2}|s_{0},\theta,G)\geq\sum_{\begin{subarray}{c}s_{2}\in\\\
\mathbb{S}_{2}(s_{1,nc})\end{subarray}}P\big{(}y,s_{1nc},s_{2}|s_{0},\theta,G)$
(9) $\forall s_{1,c}\in\mathbb{S}_{1,c},s_{1,nc}\notin\mathbb{S}_{1,c}$

To see why this is important consider

$\ell=\sum_{s_{1:2}\in\mathbb{S}}P\big{(}y_{1:3},s_{1:2}|s_{0},\theta,G)=\sum_{s_{1}\in\mathbb{S}_{1}}\sum_{\begin{subarray}{c}s_{2}\in\\\
\mathbb{S}_{2}(s_{1})\end{subarray}}P\big{(}y_{1:3},s_{1},s_{2}|s_{0},\theta,G)=$
$P\big{(}y_{1}|s_{0},\theta,G)\sum_{s_{1}\in\mathbb{S}_{1}}P\big{(}s_{1}|y_{1},s_{0},\theta,G)P\big{(}y_{2}|s_{1},y_{1},s_{0},\theta,G)\times$
(10) $\sum_{\begin{subarray}{c}s_{2}\in\\\
\mathbb{S}_{2}(s_{1})\end{subarray}}P\big{(}s_{2}|y_{1:2},s_{1},s_{0},\theta,G)P\big{(}y_{3}|y_{1:2},s_{2},s_{1},s_{0},\theta,G)=$
$\sum_{s_{1}\in\mathbb{S}_{1,c}}\sum_{\begin{subarray}{c}s_{2}\in\\\
\mathbb{S}_{2}(s_{1})\end{subarray}}P\big{(}y_{1:3},s_{1,},s_{2}|s_{0},\theta,G)+\sum_{s_{1}\in\mathbb{S}_{1,nc}}\sum_{\begin{subarray}{c}s_{2}\in\\\
\mathbb{S}(s_{1})\end{subarray}}P\big{(}y_{1:3}s_{1},s_{2}|s_{0},\theta,G)=\widehat{\ell}+\varepsilon$

Let $\underline{s}_{1,c}$ denote the information status vector in
$\mathbb{S}_{1,c}$ for which the LHS of (9) is minimal, then, if (9) holds, we
can quantify the approximation error as

$\varepsilon\leq 2^{e_{1}-d}\sum_{\begin{subarray}{c}s_{2}\in\\\
\mathbb{S}_{2}(\underline{s}_{1,c})\end{subarray}}P\big{(}Y_{1:3},\underline{s}_{1,c},s_{2}|s_{0},\theta,G)$

For participants, the information status is unequivocal. The dimensionality
problem arises from the potentially informed individuals (PIIs): sufficiently
close to have received the information, they do not (by participating)
indicate that they have done so. For PIIs, the scenario A: “informed and opted
out” and the scenario B: “uninformed” are observationally equivalent.
As we shall see, the algorithm can lead to choices violating (9) due to the
fact that it does not anticipate correctly the last part of (10) and as such,
the error bound property fails to hold for some areas of the grid.

###  8.3 Erroneous Choices

Consider the following example.
Define a sub-graph as consisting of a final agent $k\in e_{2}$ and the
collection of intermediate agents ($j=1,..,J\in e_{1}$) that are situated on
the indirect paths from $k$ to one or several IPs. Figure 21 depicts two
independent sub-graphs.

Figure 21: Miniature Village Networkip1 ip2 ip3 ip4ip5 6 7 8 9 1011 12 13 14

Assume that individuals 6, 7, 8, 9 are subject to trimming. If $A_{6}>B_{6}$
we will trim 6 to A. However, it can be that

$A_{6}\prod_{i=10}^{13}(A_{i}+B_{i})<(B_{6})(A_{6}+B_{6})$ (11)

(this is for instance the case for $p=0.5=q$). In this case, setting 6 to
scenario A turns out to be a sub-optimal choice.
By the same argument if $A_{7}<B_{7}$, it may be that

$(\prod_{i=7}^{9}A_{i})(A_{14}+B_{14})>\prod_{i=7}^{9}B_{i}(A_{i}+B_{i})$ (12)

(This is for instance the case for $p=0.4,q=0.6$).
The simple algorithm thus results in (11) and (12) violating (9). To evaluate
the performance of the algorithm, it is informative to understand when
applying it entails mistakes. We define a mistake as a choice that violates
such that there exists a different choice in the current period that
guarantees that a larger fraction of probability mass is covered in the final
period.
Note that $A_{i}+B_{i}=1-pr_{i}$ is decreasing in $r_{i}$. Consequently, if we
choose scenarios that imply that intermediate PIIs are informed, then these
should c.p. be the ones with the largest number of IP friends: they have a
high $A_{i}$ and a low $B_{i}(A_{i}+B_{i})$. Furthermore when an intermediate
agent is informed in the first exchange, she can inform her neighbours in the
second exchange. Say individual $i$ has $\omega_{i}$ neighbours, then having
$i$ informed in period one leads to
$A_{i}\prod_{j=1}^{\omega_{i}}(A_{j}+B_{j})$ as this decreases in
$\omega_{i}$, thus if we choose scenarios that imply that intermediate agents
are informed, these should c.p. be the ones with the smallest out-degree.
However, final agents are regularly linked to not one, but several
intermediate PIIs. To account for the the total impact a PII has on the final
agents, we need to consider her “ip-betweenness”. We define the latter as the
sum of the fractions of links between an ip and a final agent that pass by the
intermediate agent. A high ip-betweenness signifies that the intermediate
agent is linked to many final agents or that these final agents she is linked
with are linked to few other intermediate agents. An ip-betweenness smaller
than one indicates that the final agents she is linked to are also a
neighbours of many other intermediate agents.
There are two situation that may result in erroneous choices.

Mistake 1: betweenness exceeds the in degree and $\bf A_{i}>B_{i}$
For facilitate the exposition, we first assume that all final agents are
homogeneous and only linked to one intermediate agent and thereafter give a
formula that is valid in general. This case is the first example from the
above. Then we have

$\displaystyle A_{i}\left(\prod_{j}(A_{j}+B_{j})\right)$
$\displaystyle=B_{i}(A_{i}+B_{i})$ $\displaystyle\frac{A_{i}}{B_{i}}$
$\displaystyle=\frac{(A_{i}+B_{i})}{(1-pq)^{b}}$
$\displaystyle\vspace{.5cm}b\rightarrow\infty\hskip
21.33955pt\frac{A_{i}}{B_{i}}$
$\displaystyle<\underbrace{\frac{(A_{i}+B_{i})}{(1-pq)^{b}}}_{\rightarrow\infty}$

If we let $b$ go to infinity while holding the in degree constant, the
denominator of the second term goes to zero, implying that the second term
becomes larger than the first. This means that “$i$ is uninformed in the first
exchange” ultimately results in a larger probability mass then “$i$ is
informed in the first exchange” despite the fact that $A_{i}>B_{i}$ and as
such, the choice was incorrect.

Mistake 2: the in degree exceeds the betweenness and $\bf A_{i}<B_{i}$
For clarity, assume that intermediate agents are homogeneous and linked to one
final agent, i.e. they each have a share of $b<1$ of the paths from IPs to the
final agent that pass through them and as a consequence, there are $1/b$
intermediate agents. This is the situation in the second example above. Since
$B_{i}>A_{i}$, the algorithm trims the intermediate agents to B. This is the
optimal choice if

$\displaystyle\prod_{i}A_{i}(A_{j}+B_{j})$
$\displaystyle<\prod_{i}B_{i}(A_{i}+B_{i})$
$\displaystyle\Big{(}\frac{A_{i}}{B_{i}}\Big{)}^{1/b}$
$\displaystyle<\frac{\Big{(}A_{i}+B_{i}\Big{)}^{1/b}}{(A_{j}+B_{j})}$
$\displaystyle\vspace{.5cm}\frac{A_{i}}{B_{i}}$
$\displaystyle<\frac{(A_{i}+B_{i})}{(1-p(1-(1-q)^{1/b})^{b}}$

However, if the number of intermediate agents is increased, $b$ becomes very
small and as a consequence, the denominator of the RHS approaches one, such
that the RHS expression converges to $A_{i}+B_{i}<1$. If we are at a point on
the grid where the difference between $A_{i}$ and $B_{i}$ is small, the LHS is
close to one and thus exceeds the RHS, such that we conclude that the choice
has been erroneous, i.e.

$b\rightarrow 0\hskip 21.33955pt\underbrace{\frac{A_{i}}{B_{i}}}_{\approx
1}>\underbrace{\frac{(A_{i}+B_{i})}{(1-p(1-(1-q)^{1/b})^{b}}}_{\rightarrow
A_{i}+B_{i}<1}$

When $b$ is small, setting all intermediate agents to “informed” in the first
exchange implies a higher reception rate for the final agent, thus decreasing
$A_{j}+B_{j}$ and making this choice less attractive. However, $A_{j}+B_{j}$
decreases less than proportionally and as the number of intermediate agents
grows large, the further decrease becomes negligible. Setting all intermediate
agents to “uninformed” features a zero reception rate for the final agent but,
on the other hand, implies that we need to consider two scenarios in the next
period for each intermediate agent, which decreases the probability mass. When
$B_{i}>A_{i}$ induces us to set intermediate agents to “uninformed”, we
neglect this future impact, which may result in a sub-optimal choice.

The formulas above use the easier cases in which either final or intermediate
agents are homogeneous. More generally, however, intermediate agents can have
different link portfolios and sub-graphs can overlap. Now, there is no
straightforward relationship between $b$ and the number of agents in the sub-
graph, however, the two are still proportional. A lower b value implies that a
agent is liked to few, or densely connected final agents. A higher b value on
the other hand signifies that she is one of the few neighbours of a final
agent, or linked to a large number of them. Assume that there are $J+1$
intermediate agents who are linked to $K$ final agents. To focus on the last
intermediate agent, we assume that the equation holds strictly for the $J$
remaining ones, implying

$\displaystyle(\prod_{i=1}^{J}A_{i})\prod_{k=1}^{K}\big{[}A_{k(J)}+B_{k(J)}\big{]}$
$\displaystyle=\prod_{i=1}^{J}B_{i}(A_{i}+B_{i})$
$\displaystyle\prod_{i=1}^{J}\frac{A^{i}}{B^{i}}$
$\displaystyle=\frac{\prod_{i=1}^{J}(A_{i}+B_{i})}{\prod_{k=1}^{K}\big{[}A_{k(J)}+B_{k(J)}\big{]}}$

If we add the last agent, this becomes

$\prod_{i=1}^{J}\frac{A_{i}}{B_{i}}\frac{A_{l}}{B_{l}}=\frac{\prod_{i=1}^{J}(A_{i}+B_{i})}{\prod_{k=1}^{K}\big{[}A_{k(J)}+B_{k(J)}\big{]}}\frac{\prod_{k=1}^{K}\big{[}A_{k(J)}+B_{k(J)}\big{]}}{\prod_{k=1}^{K}\big{[}A_{k(J+1)}+B_{k(J+1)}\big{]}}(A_{l}+B_{l})$

The second term reflects the fact that now all final agents have one more
potential linking partners. We cancel out the equality to obtain

$\frac{A_{l}}{B_{l}}=\frac{\prod_{k=1}^{K}\big{[}A_{k(J)}+B_{k(J)}\big{]}}{\prod_{k=1}^{K}\big{[}A_{k(J+1)}+B_{k(J+1)}\big{]}}(A_{l}+B_{l})$

Further, in the first term on the RHS, we can cancel out all agents that are
not linked to agent $l$ and note that the remaining $\tilde{K}$ ones gain one
additional link when $l$ is added

$\frac{A_{l}}{B_{l}}=\frac{\prod_{k=1}^{\tilde{K}}\big{[}1-p(1-(1-q)^{x^{k}}\big{]}}{\prod_{k=1}^{\tilde{K}}\big{[}1-p(1-(1-q)^{x^{k}+1}\big{]}}(A_{l}+B_{l})$

The equality may fail to hold. If $x^{k}$ is small, then $l$ is the only or
one of the few neighbours for many final agents and the first term on the RHS
is larger than one. If there are many such final agents $\tilde{K}$ is large
thus counteracting the multiplication by $A_{l}+B_{l}$ ad the entire RHS
exceeds one. Then $l$ has a substantial impact on many final agents ad despite
the fact that $A_{l}>B_{l}$, the optimal choice is to trim her to $B_{l}$.

$\tilde{K}\rightarrow K,\hskip 14.22636ptx^{k}\rightarrow 0,\hskip
14.22636pt\frac{A_{l}}{B_{l}}<\frac{(A_{l}+B_{l})}{(1-pq)^{\tilde{K}}}$

which implies committing error one.
If on the other hand $x_{k}$ is large and/or $\tilde{K}$ is small, then the
first term on the RHS is close to one. Agent $l$ has a negligible impact on
the others and the condition becomes

$\tilde{K}\rightarrow 0,\hskip 14.22636ptx^{k}\rightarrow\infty,\hskip
14.22636pt\frac{A_{l}}{B_{l}}>A_{l}+B_{l}$

If $B_{l}>A_{l}$ and the difference is sufficiently small, we end up
committing error two.

###  8.4 The Error Function

We have seen above that, by the law of total probability, the likelihood
function arises as a sum, the summands being the (joint) probability of the
data and each (unobserved) information status matrix that could have generated
it. We have also seen that in dense Networks with low participation rates, the
total number of possible information scenarios (and thus the number of
summands of the log likelihood function) easily explodes. We have proposed to
tackle this problem by neglecting highly unlikely scenarios. Consequently, our
method leads to an approximation error. We now quantify the approximation
error, analyze the systematic pattern it exhibits and outlay how this pattern
can be used for identifying the maximum of the village Log-likelihood
function.
As before, we let $\mathbb{S}$ denote the set of all possible sequences of
information status vectors $S_{1},...,S_{T-1}$ that are conform with the
observed outcome matrix $Y_{(1:T)}$. If $s$ stands for a particular sequence
in this set then the log likelihood function of village $v$ is given by

$\displaystyle\mathcal{L}_{v}=\log\Bigg{(}\displaystyle\sum_{s\in\mathbb{S}_{v}}Pr(Y_{(1:T),v}=y_{(1:T),v},s|s_{0,v},G_{v},p,q)\Bigg{)}$

We have also noted that the curse of dimensionality arises from the typically
large size of “potentially informed individuals” (PIIs): with two possible
information statuses, each additional non-participant that comes in reach of
the information in period 1 (respectively, 2, 3) can potentially quadruple
(respectively, triple, double) the possible realizations of the random matrix
$S$.We need to reduce the number of sumamnds of the log likelihood function
and we achieve this reduction by limiting the set of PIIs for which both
scenarios (“informed and opted out” and “uninformed”) are considered. For each
point on the grid, our algorithm can foresee the ordering of information
scenarios according to their probabilities to occur even without having to
actually compute (and store) these probabilities. Having established the
ordering of scenarios in $\mathbb{S}$, we can select as many scenarios as our
storage and computing capacities allow, knowing we selected the most likely
ones. As a consequence, whenever a specific information scenario is highly
unlikely, it will be neglected and the PIIs involved in this unlikely scenario
will be pushed to their more likely default value.
Since out of the set $\mathbb{S}_{v}$ we are only considering a limited number
of elements. Partitioning $\mathbb{S}=\mathbb{S}_{c,v}\cup\mathbb{S}_{nc,v}$
(where the subscript c (nc) stands for the considered (not considered)
scenarios such that $\mathbb{S}_{c,v}\cap\mathbb{S}_{nc,v}=\emptyset$). We can
write

$\displaystyle\mathcal{L}_{v}=\log\Bigg{(}\displaystyle\sum_{s\in\mathbb{S}_{c,v}}$
$\displaystyle Pr(Y_{(1:T),v}=y_{(1:T),v},s|s_{0,v},G_{v},p,q)+$
$\displaystyle\displaystyle\sum_{s\in\mathbb{S}_{nc,v}}Pr(Y_{(1:T),v}=y_{(1:T),v},s|s_{0,v},G_{v},p,q)\Bigg{)}$

In the following, $\hat{\ell}$ ($\hat{\mathcal{L}}$) denotes the approximate
(log) likelihood function.

$\mathcal{L}_{v}=\log\bigg{(}\widehat{\ell_{v}}+\ell_{v}-\widehat{\ell_{v}}\bigg{)}=\log\Bigg{(}\widehat{\ell_{v}}\Bigg{[}1+\frac{\ell_{v}-\widehat{\ell_{v}}}{\widehat{\ell_{v}}}\Bigg{]}\Bigg{)}=\log\big{(}\widehat{\ell_{v}}\big{)}+\log\Bigg{(}1+\frac{\ell_{v}-\widehat{\ell_{v}}}{\widehat{\ell_{v}}}\Bigg{)}=$
$\mathcal{L}_{v}=\widehat{\mathcal{L}_{v}}+\varepsilon_{v}$ (13)

Therefore, we have the sample Log-likelihood function

$\mathcal{L}=\log\Big{(}\prod_{v}\ell_{v}\Big{)}=\sum_{v}\log(\ell_{v})=\sum_{v}\mathcal{L}_{v}=\sum_{v}\widehat{\mathcal{L}}_{v}+\sum_{v}\varepsilon_{v}=\widehat{\mathcal{L}}+\varepsilon$

The error function is always piece-wise linear in the trimming value.
Furthermore, it is close to being convex if the algorithm does not commit too
many errors on average. Convexity of the error function is useful because it
enables us to get an estimate of the maximal error by interpolation. Knowing
that at $e^{1}=d$ the error is zero, we can use the slope
$\Delta\varepsilon_{1}$ to trace back the maximal error level: as the error
function is concave, the actual error curve will thus under our interpolated
one and hence we obtain a conservative estimate.

The error function is piecewise linear in $d$. It can be convex, concave or
change curvature over the range of $d=1,...,e^{1}$. However, as long as the
algorithm makes no large mistakes on average, it is close to being convex.

###### Proof.

Define $\mathbb{S}_{c,d}$ as the set of scenarios considered if $d$ agents are
not trimmed. Then define
$P(s_{d})=\sum_{s\in\mathbb{S}_{c,d}}-\sum_{s\in\mathbb{S}_{c,d-1}}$ as the
additional scenarios considered when the $d^{th}$ agent is not trimmed. Since
$\mathcal{L}=\varepsilon_{d}=\widehat{\mathcal{L}}_{d}$ thus the change in the
error is

$\Delta\varepsilon_{d}=\widehat{\mathcal{L}}_{d-1}-\widehat{\mathcal{L}}_{d1}=\log\bigg{(}\sum_{x=1}^{d-1}P(s_{x})\bigg{)}-\log\bigg{(}\sum_{x=1}^{d}P(s_{x})\bigg{)}=$
$\log\bigg{(}\sum_{x=1}^{d-1}P(s_{x})\bigg{)}-\log\bigg{(}\sum_{x=1}^{d-1}P(s_{x})+P(s_{d})\bigg{)}=$
$\log\bigg{(}\sum_{x=1}^{d-1}P(s_{x})\bigg{)}-\log\bigg{(}\sum_{x=1}^{d-1}P(s_{x})\bigg{(}1+\frac{P(s_{d})}{\sum_{x=1}^{d-1}P(s_{x})}\bigg{)}=$
$\log\bigg{(}\sum_{x=1}^{d-1}P(s_{x})\bigg{)}-\log\bigg{(}\sum_{x=1}^{d-1}P(s_{x})\bigg{)}-\log\bigg{(}1+\frac{P(s_{d})}{\sum_{x=1}^{d-1}P(s_{x})}\bigg{)}=$
$-\log\bigg{(}1+\frac{P(s_{d})}{\sum_{x=1}^{d-1}P(s_{x})}\bigg{)}$

The error function always slopes downwards. The slope exceeds one if
$\frac{P(s_{d})}{\sum_{x=1}^{d-1}P(s_{x})}>1$ that is the sum of all new
scenarios is more likely than the sum of all scenarios considered so far, in
which case the error curve exhibits a kink. A necessary and sufficient
condition for convexity is

$-\log\bigg{(}\frac{P(s_{d-1})}{\sum_{x=1}^{d-2}P(s_{x})}\bigg{)}<-\log\bigg{(}\frac{P(s_{d})}{\sum_{x=1}^{d-1}P(s_{x})}\bigg{)}$
$\frac{P(s_{d-1})}{\sum_{x=1}^{d-2}P(s_{x})}>\frac{P(s_{d})}{\sum_{x=1}^{d-1}P(s_{x})}\hskip
14.22636pt\forall d$

∎

In the numerator are the new scenarios that arise when $d$ is not trimmed.
These are thus the scenarios in which she is set to the smaller of the two
choices $A$ or $B$, whereas in the denominator are the same scenarios with PII
$d$ being trimmed to her threshold. As such, if the choice is correct, then
the slope of the error function is indeed decreases in absolute value and as
such, convexity holds. Importantly, it is not necessary for convexity that the
algorithm commits no error. Any choice to trim to a threshold can be evaluate
conditioning on the scenarios all other agents and as such, a choice is rarely
erroneous in all of these cases. Convexity holds as long as the fraction of
the total probability mass of the non-treshhold scenarios over the total
probabilities of the treshold scenarios is smaller than one and keeps
decreasing. The error function is close to being convex as long as the
algorithm does not commit too many errors on average.

##  9 Bibliography

## References

  * Andrews (1994) Andrews, D. W. (1994).  Empirical process methods in econometrics.  In R. F. Engle and D. McFadden (Eds.), Handbook of Econometrics, Volume 4, Chapter 37, pp. 2247 – 2294. Elsevier.
  * Anselin (2001) Anselin, L. (2001).  Spatial econometrics.  A companion to theoretical econometrics 310330, 111–222.
  * Anselin and Bera (1998) Anselin, L. and A. K. Bera (1998).  Introduction to spatial econometrics.  Handbook of applied economic statistics 237, 111–222.
  * Bandiera and Rasul (2006) Bandiera, O. and I. Rasul (2006).  Social Networks and Technology Adoption in Northern Mozambique.  The Economic Journal 116 (514), 869–902.
  * Banerjee et al. (2013) Banerjee, A., A. Chandrasekhar, E. Duflo, and M. Jackson (2013, Science 26 July).  The diffusion of microfinance.  Vol. 341 (Issue 6144).
  * Bhagat et al. (2012) Bhagat, S., A. Goyal, and L. Lakshmanan (2012).  Maximizing Product Adoption in Social Networks.  Proceedings of the fifth ACM international conference on Web search and data mining 5, pp.603–612.
  * Bickel et al. (2011) Bickel, P. J., A. Chen, and E. Levina (2011, 10).  The method of moments and degree distributions for network models.  Ann. Statist. 39(5), 2280–2301.
  * Centola (2015) Centola, D. (2015).  The Social Origins of Networks and Diffusion.  American Journal of Sociology 120(5), 1295–1338.
  * Christakis and Fowler (2007) Christakis, N. A. and J. H. Fowler (2007).  The Spread of Obesity in a Large Social Network over 32 Years.  The New England Journal of Medecine 357(4), pp.370–379.
  * Coleman et al. (1966) Coleman, J., E. Katz, and H. Menzel (1966).  Medical Innovation: A Diffusion Study.  Bobbs-Merrill Co.
  * Conley and Udry (2010) Conley, T. G. and C. R. Udry (2010).  Learning about a New Technology: Pineapple in Ghana.  The American Economic Review 100(1), 35–69.
  * Cowan (2005) Cowan, R. (2005).  Network models of innovation and knowledge diffusion.  In Clusters, Networks and Innovation, OUP E-Books, pp. 29–53. Oxford University Press New York.
  * Craig et al. (2020) Craig, B. R., T. Phelan, J.-P. Siedlarek, and J. Steinberg (2020).  Improving epidemic modeling with networks.  Economic Commentary 2020-23, 111–222.
  * de Paula (2020) de Paula, A. (2020).  Econometric models of network formation.  Annual Review of Economics 12(1), 775–799.
  * Durlauf and Ioannides (2010) Durlauf, S. N. and Y. M. Ioannides (2010).  Social interactions.  Annual Review of Economics 2(1), 451–478.
  * Hansen and Lee (2019) Hansen, B. E. and S. Lee (2019).  Asymptotic theory for clustered samples.  Journal of econometrics 210(2), 268–290.
  * Hansen (2001) Hansen, L. P. (2001).  Generalized method of moments estimation: A time series perspective.  In N. J. Smelser and P. B. Baltes (Eds.), International Encyclopedia of Social and Behavioral Sciences, pp. 9743–9751. Elsevier.
  * Hethcote (2000) Hethcote, H. W. (2000).  The Mathematics of Infectious Diseases.  Society for Industrial and Applied Mathematics (SIAM) Review 42(4), pp.599––653.
  * Jackson et al. (2012) Jackson, M., T. Rodriguez-Barraquer, and X. Tan (August 2012).  Social capital and social quilts: Network patterns of favor exchanges.  American Economic Review Vol. 102, No 5, pp.1857–97.
  * Jackson (2004) Jackson, M. O. (2004).  A survey of models of network formation: Stability and efficiency.  In G. Demange and M. Wooders (Eds.), Group Formation in Economics; Networks, Clubs and Coalitions, Chapter 1, pp. 11–57. Cambridge University Press.
  * Jackson and Yariv (2005) Jackson, M. O. and L. Yariv (2005).  Diffusion on social networks.  In Economie Publique. Citeseer.
  * Karaivanov (2020) Karaivanov, A. (2020).  A social network model of covid-19.
  * Katungi et al. (2008) Katungi, E., S. Edmeades, and M. Smale (2008).  Gender, Social Capital and Information Exchange in Rural Uganda.  Journal of International Development 20, 35–52.
  * Krisztin et al. (2020) Krisztin, T., P. Piribauer, and M. Woegerer (2020).  The spatial econometrics of the coronavirus pandemic.  Letters in Spatial and Resource Sciences 13(2), (accessible online).
  * Liu and fei Lee (2010) Liu, X. and L. fei Lee (2010).  Gmm estimation of social interaction models with centrality.  Journal of Econometrics 159(1), 99 – 115.
  * Newey and McFadden (1994) Newey, W. K. and D. McFadden (1994).  Chapter 36 large sample estimation and hypothesis testing.  In R. F. Engle and D. McFadden (Eds.), Handbook of Econometrics, Volume 4, Chapter 36, pp. 2111 – 2245. Elsevier.
  * Neyman and Pearson (1933) Neyman, J. and E. Pearson (1933).  IX. On the problem of the most efficient tests of statistical hypotheses.  Phil. Trans. R. Soc. Lond. 231(694-706), 289––337.
  * Ryan and Gross (1950) Ryan, B. and N. Gross (1950).  Acceptance and diffusion of hybrid corn seed in two Iowa communities.  Research Bulletin (Iowa Agriculture and Home Economics Experiment Station) Vol. 29 : No. 372, Article 1.
  * Singh et al. (2019) Singh, S. S., K. Singh, A. Kumar, H. K. Shakya, and B. Biswas (2019).  A survey on information diffusion models in social networks.  In A. K. Luhach, D. Singh, P.-A. Hsiung, K. B. G. Hawari, P. Lingras, and P. K. Singh (Eds.), Advanced Informatics for Computing Research, Singapore, pp. 426–439. Springer Singapore.
  * Snijders (2017) Snijders, T. A. (2017).  Stochastic actor-oriented models for network dynamics.  Annual Review of Statistics and Its Application 4(1), 343–363.
  * Su and Yang (2011) Su, L. and Z. Yang (2011).  Instrumental variable quantile estimation of spatial autoregressive models.  Research Collection School Of Economics. Singapore Management University https://ink.library.smu.edu.sg/soe_research/1074, 1–35.
  * Todoa et al. (2011) Todoa, Y., D. M. Yadateb, P. Matousc, and R. Takahashid (2011).  Effects of Geography and Social Networks on Diffusion and Adoption of Agricultural Technology: Evidence from Rural Ethiopia.  Center for the Study of African Economics (CSAE) $25^{t}h$ Anniversary Conference, 111–222.
  * Valente (1996) Valente, T. W. (1996).  Social network thresholds in the diffusion of innovations.  Social networks 18(1), 69–89.
  * Valente (2005) Valente, T. W. (2005).  Network models and methods for studying the diffusion of innovations.  Models and methods in social network analysis 28, 98.
  * Wooldridge (1994) Wooldridge, J. (1994).  Estimation and inference for dependent processes.  In R. F. Engle and D. McFadden (Eds.), Handbook of Econometrics, Volume 4, Chapter 45, pp. 2639 – 2738. Elsevier.