The formalism of choice for this paper is binary aggregation \cite{grandi13lifting}. A binary aggregation structure (BA structure) is a tuple \(\mathcal{A}=\left\langle N,{\bf P}\right\rangle\) where:
\(N=\left\{1,\dots,n\right\}\) is a finite set individuals s.t. \(|N|=n\in\mathbb{N}\);
\({\bf P}=\left\{p_{1},\dots,p_{m}\right\}\) is a finite set of issues (\(|{\bf P}|=m\in\mathbb{N}\)), each represented by a propositional atom.
We denote with \(\mathcal{L}\) the propositional language constructed by closing \({\bf P}\) under a functionally complete set of Boolean connectives (e.g., \(\left\{\neg,\wedge\right\}\)). An opinion \(O:{\bf P}\to\{0,1\}\) is an assignment of truth values to the set of issues \({\bf P}\). Thus, \(O(p)=0\) (respectively, \(O(p)=1\)) indicates that opinion \(O\) rejects (respectively, accepts) the issue \(p\). Syntactically, the two opinions correspond to the truth of the literals \(p\) or \(\neg p\). For \(p\in{\bf P}\) we write \(\pm p\) to denote one element from \(\left\{p,\neg p\right\}\). An opinion profile \({\bf O}=(O_{1},\dots,O_{n})\) records the opinion, on the given set of issues, of every individual in \(N\). Given a profile \({\bf O}\) the \(i^{\mathit{th}}\) projection \(O_{i}\) denotes the opinion of agent \(i\) in profile \({\bf O}\). We also denote by \({\bf O}(p)=\{i\in N\mid O_{i}(p)=1\}\) the set of agents accepting issue \(p\) in profile \({\bf O}\).
In \cite{Degroot_1974}, DeGroot proposes a simple model of step by step opinion change under social influence. The model combines two types of matrices. Assuming a group of \(n\) agents, a first \(n\times n\) matrix represents the weighted influence network (who influences whom and how much), and a second \(n\times m\) matrix represents the probability assigned by each agent to each of the \(m\) different alternatives. Both the agents’ opinion and the influence weights are taken within \([0,1]\) and are (row) stochastic (each row sums up to \(1\)). Given an opinion and an influence matrix, the opinion of each agent in the next time step is obtained through linear averaging.
In this paper we focus on the Boolean extreme of a DeGroot process. Opinions are defined over a BA structure, and hence are taken to be binary. Similarly, we take influence to be modeled by the binary case of an influence matrix. Influence is of an “all-or-nothing” type and each agent is therefore taken to be influenced by exactly one agent, possibly itself. The graph induced by such a binary influence matrix (called influence graph) is therefore a structure \(G=\left\langle N,R\right\rangle\) where \(R\subseteq N^{2}\) is a binary relation where \(iRj\) is taken here to denote that “\(i\) is influenced by \(j\)”. Such relation is serial (\(\forall i\in N,\exists j\in N:iRj\)) and functional (\(\forall i,j,k\in N\) if \(iRj\) and \(iRk\) then \(j=k\)). So each agent \(i\) has exactly one successor (influencer or ‘guru’), possibly itself, which we denote \(R(i)\).
An influence profile \({\bf G}=(G_{1},\dots,G_{m})\) records how each agent is influenced by each other agent, with respect to each issue \(p\in{\bf P}\). Given a profile \({\bf G}\) the i\({}^{\mathit{th}}\) projection \(G_{i}\) denotes the influence graph for issue \(p_{i}\).
So let us define the type of dynamics the paper focuses upon:
Now fix an opinion profile \({\bf O}\) and an 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\), \(p\in{\bf P}\), \(O_{i}^{n+1}(p):=O^{n}_{R_{p}(i)}(p)\).
We call processes defined by the above dynamics Boolean DeGroot processes (BDPs).
It should be clear that the above dynamics is the extreme case of linear averaging applied on binary opinions and binary influence.
BDPs are also limit cases of processes that have recently been proposed in the multi-agent systems literature as propositional opinion diffusion processes \cite{Grandi:2015:POD:2772879.2773278}, i.e., cases where 1) the aggregation rule is the unanimity rule (an agent adopts an opinion if and only if all her influencers agree on it), and 2) each agent has exactly one influencer. We will come back to the link with propositional opinion diffusion in some more detail later in Section \ref{sec:coloring}.