DeGroot learning

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 ${\displaystyle T}$ is aperiodic
• there is a unique left eigenvector ${\displaystyle s}$ of ${\displaystyle T}$ corresponding to eigenvalue 1 whose entries sum to 1 such that, for every ${\displaystyle p\in [0,1]^{n}}$, ${\displaystyle \left(\lim _{t\to \infty }T^{t}p\right)_{i}=s\cdot p}$ for every ${\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.

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 ${\displaystyle C\subseteq \{1,\dots ,n\}}$ is closed if for any ${\displaystyle i\in C}$, ${\displaystyle T_{ij}>0}$ only if ${\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.

A group ${\displaystyle C}$ of individuals is said to reach a consensus if ${\displaystyle p_{i}(\infty )=p_{j}(\infty )}$ for any ${\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 ${\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.

A society with convergent beliefs

Consider a three-individual society with the following trust matrix:

${\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

${\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 ${\displaystyle s=\left(2/5,2/5,1/5\right)}$ and the consensus belief is ${\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.

A society with 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:

${\displaystyle T={\begin{pmatrix}0&1/2&1/2\\1&0&0\\1&0&0\\\end{pmatrix}}}$

In this case for any ${\displaystyle k\geq 1}$ we have

${\displaystyle T^{2k-1}={\begin{pmatrix}0&1/2&1/2\\1&0&0\\1&0&0\\\end{pmatrix}}}$

and

${\displaystyle T^{2k}={\begin{pmatrix}1&0&0\\0&1/2&1/2\\0&1/2&1/2\\\end{pmatrix}}}$

so ${\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.