Boolean DeGroot Processes, Fixpoint Logics and Liquid Democracy

This paper studies opinion diffusion in cases where each agent holds binary opinions and follows a unique influencer. This type of opinion diffusion, which we name ‘Boolean DeGroot process’, lies at the intersection of two more general frameworks for opinion diffusion: the seminal stochastic model proposed by DeGroot, and the more recent approach, stemming from the literature on judgment aggregation, of Propositional Opinion Diffusion. The paper provides three contributions. First, it establishes conditions for convergence of opinions in Boolean DeGroot processes and in a simple generalization of them. Second, it shows how these conditions can be captured by modal fixpoint logics, thereby enabling a rich toolbox for the study of opinion formation. Third, it applies the convergence results to gain a novel insight into a problematic aspect of the collective decision-making system known as ‘liquid democracy’.


The paper focuses on a specific class of opinion diffusion processes in which opinions are binary, and agents are influenced by exactly one influencer, possibly themselves, of which they copy the opinion. This is an extremely simple model of opinion diffusion on networks, and it is of interest for two reasons. First, it corresponds to a class of processes which lies at the interface of two classes of diffusion processes that have remained so far unrelated: the stochastic opinion diffusion model known as DeGroot’s (Degroot 1974), and the more recent propositional opinion diffusion model due to (Grandi 2015). The processes we study—called here Boolean DeGroot processes—are the \(\left\{0,1\right\}\) limit case of the DeGroot stochastic processes and, at the same time, the limit case of propositional opinion diffusion processes where each agent has access to the opinion of exactly one neighbor (cf. Figure \ref{figure:intersection}). Second, it provides an abstract model with which to analyze some aspects the popular, and currently much discussed, aggregation system called liquid democracy (Behrens 2014). We will see that Boolean DeGroot processes offer a novel and natural angle on the issue of delegation cycles in liquid democracy.

Contributions of the paper

The paper studies the convergence of Boolean DeGroot processes, characterizing them with necessary and sufficient conditions. In doing so the paper uses standard graph-theoretic tools as well as techniques from modal fixpoint logics, thereby establishing a fruitful interface between such logics and qualitative models of opinion diffusion. The results we obtain on the characterization of convergence are then applied to provide novel insights into liquid democracy, which remains a rather underexplored system in the social-choice literature.

Outline of the paper

Section \ref{sec:preliminaries} introduces the paper’s notation and the key definition of Boolean DeGroot process. Section \ref{sec:convergence} studies necessary and sufficient conditions for those processes to converge. Section \ref{sec:logic} shows how off-the-shelf fixpoint logics (specifically the modal \(\mu\)-calculus) can be used to specify the properties of such processes formally. Section \ref{sec:coloring} elaborates further on the link of our work with the propositional opinion diffusion model. It studies convergence conditions for a simple generalization of Boolean DeGroot processes, where several influencers are allowed and opinions change under unanimity of the influencers. Section \ref{sec:liquid} shows how Boolean DeGroot processes relate to liquid democracy, contributing some novel insights into the understanding of delegation cycles. Section \ref{sec:conclusions} concludes the paper and sketches some on-going lines of research.

\label{figure:intersection}BDPs lie in the intersection of DeGroot processes and propositional opinion diffusion processes.

Binary aggregation and DeGroot processes


Binary aggregation

The formalism of choice for this paper is binary aggregation (Grandi 2013). 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}\).

Binary aggregation and binary influence

In (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}\).

De Groot processes in binary aggregation

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