- Source: DeGroot learning
DeGroot learning refers to a rule-of-thumb type of social learning process. The idea was stated in its general form by the American statistician Morris H. DeGroot; antecedents were articulated by John R. P. French and Frank Harary. The model has been used in physics, computer science and most widely in the theory of social networks.
Setup and the learning process
Take a society of
n
{\displaystyle n}
agents where everybody has an opinion on a subject, represented by a vector of probabilities
p
(
0
)
=
(
p
1
(
0
)
,
…
,
p
n
(
0
)
)
{\displaystyle p(0)=(p_{1}(0),\dots ,p_{n}(0))}
. Agents obtain no new information based on which they can update their opinions but they communicate with other agents. Links between agents (who knows whom) and the weight they put on each other's opinions is represented by a trust matrix
T
{\displaystyle T}
where
T
i
j
{\displaystyle T_{ij}}
is the weight that agent
i
{\displaystyle i}
puts on agent
j
{\displaystyle j}
's opinion. The trust matrix is thus in a one-to-one relationship with a weighted, directed graph where there is an edge between
i
{\displaystyle i}
and
j
{\displaystyle j}
if and only if
T
i
j
>
0
{\displaystyle T_{ij}>0}
. The trust matrix is stochastic, its rows consists of nonnegative real numbers, with each row summing to 1.
Formally, the beliefs are updated in each period as
p
(
t
)
=
T
p
(
t
−
1
)
{\displaystyle p(t)=Tp(t-1)}
so the
t
{\displaystyle t}
th period opinions are related to the initial opinions by
p
(
t
)
=
T
t
p
(
0
)
{\displaystyle p(t)=T^{t}p(0)}
Convergence of beliefs and consensus
An important question is whether beliefs converge to a limit and to each other in the long run.
As the trust matrix is stochastic, standard results in Markov chain theory can be used to state conditions under which the limit
p
(
∞
)
=
lim
t
→
∞
p
(
t
)
=
lim
t
→
∞
T
t
p
(
0
)
{\displaystyle p(\infty )=\lim _{t\to \infty }p(t)=\lim _{t\to \infty }T^{t}p(0)}
exists for any initial beliefs
p
(
0
)
∈
[
0
,
1
]
n
{\displaystyle p(0)\in [0,1]^{n}}
. The following cases are treated in Golub and Jackson
(2010).
= Strongly connected case
=If the social network graph (represented by the trust matrix) is strongly connected, convergence of beliefs is equivalent to each of the following properties:
the graph represented by
T
{\displaystyle T}
is aperiodic
there is a unique left eigenvector
s
{\displaystyle s}
of
T
{\displaystyle T}
corresponding to eigenvalue 1 whose entries sum to 1 such that, for every
p
∈
[
0
,
1
]
n
{\displaystyle p\in [0,1]^{n}}
,
(
lim
t
→
∞
T
t
p
)
i
=
s
⋅
p
{\displaystyle \left(\lim _{t\to \infty }T^{t}p\right)_{i}=s\cdot p}
for every
i
∈
{
1
,
…
,
n
}
{\displaystyle i\in \{1,\dots ,n\}}
where
⋅
{\displaystyle \cdot }
denotes the dot product.
The equivalence between the last two is a direct consequence from Perron–Frobenius theorem.
= General case
=It is not necessary to have a strongly connected social network to have convergent beliefs, however,
the equality of limiting beliefs does not hold in general.
We say that a group of agents
C
⊆
{
1
,
…
,
n
}
{\displaystyle C\subseteq \{1,\dots ,n\}}
is closed if for any
i
∈
C
{\displaystyle i\in C}
,
T
i
j
>
0
{\displaystyle T_{ij}>0}
only if
j
∈
C
{\displaystyle j\in C}
. Beliefs are convergent if and only if every set of nodes (representing individuals) that is strongly connected and closed is also aperiodic.
= Consensus
=A group
C
{\displaystyle C}
of individuals is said to reach a consensus if
p
i
(
∞
)
=
p
j
(
∞
)
{\displaystyle p_{i}(\infty )=p_{j}(\infty )}
for any
i
,
j
∈
C
{\displaystyle i,j\in C}
. This means that, as a result of the learning process, in the limit they have the same belief on the subject.
With a strongly connected and aperiodic network the whole group reaches a consensus.
In general, any strongly connected and closed group
C
{\displaystyle C}
of individuals reaches a consensus for every initial vector of beliefs if and only if it is aperiodic. If, for example, there are two groups satisfying these assumptions, they reach a consensus inside the groups but there is not necessarily a consensus at the society level.
Social influence
Take a strongly connected and aperiodic social network. In this case, the common limiting belief is determined by the initial beliefs through
p
(
∞
)
=
s
⋅
p
(
0
)
{\displaystyle p(\infty )=s\cdot p(0)}
where
s
{\displaystyle s}
is the unique unit length left eigenvector of
T
{\displaystyle T}
corresponding to the eigenvalue 1. The vector
s
{\displaystyle s}
shows the weights that agents put on each other's initial beliefs in the consensus limit. Thus, the higher is
s
i
{\displaystyle s_{i}}
, the more influence individual
i
{\displaystyle i}
has on the consensus belief.
The eigenvector property
s
=
s
T
{\displaystyle s=sT}
implies that
s
i
=
∑
j
=
1
n
T
j
i
s
j
{\displaystyle s_{i}=\sum _{j=1}^{n}T_{ji}s_{j}}
This means that the influence of
i
{\displaystyle i}
is a weighted average of those agents' influence
s
j
{\displaystyle s_{j}}
who pay attention to
i
{\displaystyle i}
, with weights of their level of trust. Hence influential agents are characterized by being trusted by other individuals with high influence.
Examples
These examples appear in Jackson (2008).
= Convergence of beliefs
=Consider a three-individual society with the following trust matrix:
T
=
(
0
1
/
2
1
/
2
1
0
0
0
1
0
)
{\displaystyle T={\begin{pmatrix}0&1/2&1/2\\1&0&0\\0&1&0\\\end{pmatrix}}}
Hence the first person weights the beliefs of the other two with equally, while
the second listens only to the first, the third only to the second individual.
For this social trust structure, the limit exists and equals
lim
t
→
∞
T
t
p
(
0
)
=
(
lim
t
→
∞
T
t
)
p
(
0
)
=
(
2
/
5
2
/
5
1
/
5
2
/
5
2
/
5
1
/
5
2
/
5
2
/
5
1
/
5
)
p
(
0
)
{\displaystyle \lim _{t\to \infty }T^{t}p(0)=\left(\lim _{t\to \infty }T^{t}\right)p(0)={\begin{pmatrix}2/5&2/5&1/5\\2/5&2/5&1/5\\2/5&2/5&1/5\\\end{pmatrix}}p(0)}
so the influence vector is
s
=
(
2
/
5
,
2
/
5
,
1
/
5
)
{\displaystyle s=\left(2/5,2/5,1/5\right)}
and the consensus belief is
2
/
5
p
1
(
0
)
+
2
/
5
p
2
(
0
)
+
1
/
5
p
3
(
0
)
{\displaystyle 2/5p_{1}(0)+2/5p_{2}(0)+1/5p_{3}(0)}
. In words, independently of the initial beliefs,
individuals reach a consensus where the initial belief of the first and the second person has twice as
high influence than the third one's.
= Non-convergent beliefs
=If we change the previous example such that the third person also listens exclusively to the first
one, we have the following trust matrix:
T
=
(
0
1
/
2
1
/
2
1
0
0
1
0
0
)
{\displaystyle T={\begin{pmatrix}0&1/2&1/2\\1&0&0\\1&0&0\\\end{pmatrix}}}
In this case for any
k
≥
1
{\displaystyle k\geq 1}
we have
T
2
k
−
1
=
(
0
1
/
2
1
/
2
1
0
0
1
0
0
)
{\displaystyle T^{2k-1}={\begin{pmatrix}0&1/2&1/2\\1&0&0\\1&0&0\\\end{pmatrix}}}
and
T
2
k
=
(
1
0
0
0
1
/
2
1
/
2
0
1
/
2
1
/
2
)
{\displaystyle T^{2k}={\begin{pmatrix}1&0&0\\0&1/2&1/2\\0&1/2&1/2\\\end{pmatrix}}}
so
lim
t
→
∞
T
t
{\displaystyle \lim _{t\to \infty }T^{t}}
does not exist and
beliefs do not converge in the limit. Intuitively, 1 is updating based on 2 and 3's beliefs while
2 and 3 update solely based on 1's belief so they interchange their beliefs in each period.
Asymptotic properties in large societies: wisdom
It is possible to examine the outcome of the DeGroot learning process in large societies,
that is, in the
n
→
∞
{\displaystyle n\to \infty }
limit.
Let the subject on which people have opinions be a "true state"
μ
∈
[
0
,
1
]
{\displaystyle \mu \in [0,1]}
. Assume that individuals
have independent noisy signals
p
i
(
0
)
(
n
)
{\displaystyle p_{i}^{(0)}(n)}
of
μ
{\displaystyle \mu }
(now superscript refers to time, the argument to the size of the society).
Assume that for all
n
{\displaystyle n}
the trust matrix
T
(
n
)
{\displaystyle T(n)}
is such that the
limiting beliefs
p
i
(
∞
)
(
n
)
{\displaystyle p_{i}^{(\infty )}(n)}
exists independently from the initial beliefs.
Then the sequence of societies
(
T
(
n
)
)
n
=
1
∞
{\displaystyle \left(T(n)\right)_{n=1}^{\infty }}
is called wise if
max
i
≤
n
|
p
i
(
∞
)
−
μ
|
→
p
0
{\displaystyle \max _{i\leq n}|p_{i}^{(\infty )}-\mu |{\xrightarrow {\ p\ }}0}
where
→
p
{\displaystyle {\xrightarrow {\ p\ }}}
denotes convergence in probability.
This means that if the society grows without bound, over time they will have a common and accurate
belief on the uncertain subject.
A necessary and sufficient condition for wisdom
can be given with the help of influence vectors. A sequence of societies is wise if and only
if
lim
n
→
∞
max
i
≤
n
s
i
(
n
)
=
0
{\displaystyle \lim _{n\to \infty }\max _{i\leq n}s_{i}(n)=0}
that is, the society is wise precisely when even the most influential individual's influence vanishes in the
large society limit. For further characterization and examples see Golub and Jackson (2010).
References
Kata Kunci Pencarian:
- Perang total
- DeGroot learning
- Mathematical models of social learning
- Perron–Frobenius theorem
- Eigenvector centrality
- Long march through the institutions
- Bayesian inference
- Frank Harary
- Maury Gallagher
- Larry A. Wasserman
- Mean squared error