authorea.com/102071

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.

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.

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.

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

## Share on Social Media