In the above, we have worked at the intersection of two models of opinion diffusion, the DeGroot model, and the propositional opinion diffusion model. However, there is more to say about how the two frameworks relate.
Let us take a brief detour towards a generalisation of BDPs corresponding to the case of propositional opinion diffusion with the unanimity rule, where agents can have several influencers and change their opinions only if all their influencers disagree with them. This means that we relax the functionality constraint on influence graphs. We will show how the two frameworks meet again: some non-stabilizing opinion cases under the unanimity rule correspond to a special class among the ‘semi-Boolean’ cases of DeGroot processes where opinions are still binary but influence does not need to be.
We define the dynamics of opinions under the unanimity rule in the obvious way:
Fix an opinion profile \({\bf O}\) and a (serial but non-necessarily functional) influence profile \({\bf G}\). Consider the stream \({\bf O}^{0},{\bf O}^{1},\ldots,{\bf O}^{n},\ldots\) of opinion profiles recursively defined as follows:
Base: \({\bf O}_{0}:={\bf O}\)
Step: for all \(i\in N\) and all \(p\in{\bf P}\):
\begin{align} {\bf O}_{i}^{n+1}(p) & =\left\{\begin{array}{ll}O_{i}^{n}(p)&\mbox{if for some $j,k\in R_{p}(i)$,$O_{j}^{n}(p)\neq O_{k}^{n}(p)$ }\\ O_{j}^{n}(p)&\mbox{otherwise, where $j\in R_{p}(i)$ }\end{array}\right.\\ \end{align}We call processes defined by the above dynamics Unanimity Processes (UPs).
We give a sufficient condition for non-convergence of UPs:
Let \(G\) be a (serial and non-necessarily functional) influence profile and \({\bf O}\) be an opinion profile, such that, for some \(p\in{\bf P}\), for all \(i,j\in C\), where \(C\) is a connected component of \(G_{p}\): if \(i\in R_{p}(j)\), then \(O_{i}(p)\neq O_{j}(p)\). Then \({\bf O}\) does not converge in UP.
Let \(G\) be a (serial and non-necessarily functional) influence profile, and \({\bf O}\) be an opinion profile, such that, for some \(p\in{\bf P}\), for all \(i,j\in C\) with \(C\) a connected component of \(G_{p}\): if \(i\in R_{p}(j)\), then \(O_{i}(p)\neq O_{j}(p)\). Then, by definition of UPs, for all \(i\in C\), \(O^{1}_{i}(p)\neq O_{i}(p)\), and by repeating the same argument, for all \(n\in\mathbb{N}\), \(O^{n+1}_{i}(p)\neq O^{n}_{i}(p)\). ∎
Intuitively, the above condition for non-convergence corresponds to a situation of global maximal disagreement: all agents (of a connected component) disagree with all their influencers. Recall that a graph is properly \(k\)-colored if each node is assigned exactly one among \(k\) colors and no node has a successor of the same color, and consider the two possible opinions on issue \(p\) as colors. The above result can be reformulated in terms of proper \(2\) colorings, as follows: if for some \(p\in{\bf P}\), \({\bf O}\) properly colors \(G_{p}\), then \({\bf O}\) does not converge. In such a case, all agents will change their opinion on \(p\) at every step, entering an oscillation of size \(2\). So the maximal state of disagreement is the maximally unstable case of the dynamics. Note that this limit case of opinion distribution is yet another special case of DeGroot processes, another example within the intersection between the two frameworks of propositional opinion diffusion and DeGroot.
The possibility of such a distribution of opinions on \(p\) relies on the influence graph \(G_{p}\) being \(2\)-colorable, which is again a requirement about the lengths of its cycles: it is \(2\)-colorable if and only if it contains no cycle of odd length. However, non \(2\)-colorability is not a sufficient condition for convergence of UPs in general: a simple cycle of three agents, for instance, is not \(2\)-colorable but does not guarantee convergence either (as illustrated above with the convergence conditions for BDPs). Nevertheless, there is a class of influence profiles for which being \(2\)-colorable is a necessary condition of non-convergence of UPs, the symmetric ones:
Let \({\bf G}\) be a symmetric (serial and non-necessarily functional) influence profile and \({\bf O}\) be an opinion profile. The following are equivalent:
\({\bf O}\) converges in UP on \({\bf G}\).
For all \(p\in{\bf P}\), for all connected component \(C\) of \(G_{p}\), there are \(i,j\in C\), such that \(i\in R_{p}(j)\), and \(O_{i}(p)=O_{j}(p)\).
\(2)\Rightarrow 1)\) Assume that for any \(p\in{\bf P}\), for any connected component \(C\) of \(G_{p}\), there exist \(i,j\in C\), such that \(R_{p}(j)\) and \(O_{i}(p)=O_{j}(p)\). By definition of UP, this implies that \(O_{i}(p)\) is stable, and that all agents with distance \(\leq k\) will be stable after at most \(k\) steps. \(1)\Rightarrow 2)\) This follows from Lemma \ref{lemma:suff.UP}. ∎
This means that opinions on a given \(p\) will converge if and only if two agents influencing each other on \(p\) already agree on it. We can therefore, as we did for BDPs, characterize the class of influence profiles for which all (symmetric) opinion profiles converge in UPs:
Let \({\bf G}\) be a symmetric (serial and non-necessarily functional) influence profile. The following are equivalent:
All opinion profiles \({\bf O}\), converge in UPs on \({\bf G}\).
For all \(p\in{\bf P}\), and all connected components of \(C\subseteq G_{p}\), \(C\) is not \(2\)-colorable (contains cycle(s) of odd length).
\(2)\Rightarrow 1)\) Let \(p\in{\bf P}\) and \(C\) be connected component of \(G_{p}\) with diameter \(k\). Let \(C\) contain a cycle of length \(c\), with \(c\) odd. Let \({\bf O}\) be an arbitrary opinion profile. Since \(c\) is odd, there exist \(i,j\in S\) such that \(j\in R_{p}(i)\) and \(O_{i}(p)=O_{j}(p).\) By definition of UP, this implies that \(O_{i}(p)\) is stable, and that all agents with distance \(\leq k\) will be stable after at most \(k\) steps. Hence, \({\bf O}\) converges. \(1)\Rightarrow 2)\) This follows from Lemma \ref{lemma:symm.opinionUP}. ∎
Note that, while the basic modal language cannot capture graph \(2\)-colorability, it can capture non \(2\)-colorability, and therefore capture the class of symmetric (serial and non-necessarily functional) influence profiles which guarantee convergence of UPs. We leave the detail out for space reason.
We have shown that, for UPs in general, convergence (in a connected component) is not guaranteed if it contains no odd cycles, and that symmetric UPs guarantee convergence as soon as they contain some odd cycle. However, containing an odd cycle is a very “easy” requirement for a real-life influence network to meet (it corresponds to a non-zero clustering coefficient). By contrast, recall that BDPs guarantee convergence (on any opinion profile) only when they contain only cycles of size \(1\), which is a rather implausible requirement to be satisfied on real influence networks.