\documentclass{article}
\usepackage{fullpage}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage{xcolor}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage[natbibapa]{apacite}
\usepackage{eso-pic}
\AddToShipoutPictureBG{\AtPageLowerLeft{\includegraphics[scale=0.7]{powered-by-Authorea-watermark.png}}}
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\iflatexml
\documentclass{article}
\fi
% \usepackage[affil-it]{authblk} % Not (yet) supported by LaTeXML.
\usepackage{graphicx}
%\usepackage[space]{grffile}
% \usepackage{latexsym} % Not (yet) supported by LaTeXML.
% \usepackage{textcomp} % Not (yet) supported by LaTeXML.
\usepackage{longtable}
\usepackage{multirow,booktabs}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{natbib}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=false,pdfborder={0 0 0}}
\newif\iflatexml\latexmlfalse
\usepackage[utf8]{inputenc}
% \usepackage[ngerman,english]{babel} % Not (yet) supported by LaTeXML.
% \usepackage{stmaryrd} % Not (yet) supported by LaTeXML.
% \usepackage{enumitem} % Not (yet) supported by LaTeXML.
\usepackage[normalem]{ulem}
\usepackage{tikz}
% \usepackage{centernot} % Not (yet) supported by LaTeXML.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{comment}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\newtheorem{theorem}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{contact}{Contact}
\
\renewcommand{\L}{\mathcal{L}}
\renewcommand{\L}{\mathcal{L}}
\newcommand{\N}{N}
\newcommand{\T}{\mathcal T}
\newcommand{\I}{\mathcal I}
\newcommand{\Model}{\mathcal{M}}
\renewcommand{\S}{\mathcal{A}}
\newcommand{\G}{{\bf G}}
\newcommand{\Atoms}{{\bf P}}
\newcommand{\C}{{\bf C}}
\renewcommand{\O}{{\bf O}}
\newcommand{\tuple}[1]{\left\langle #1 \right\rangle}
\newcommand{\set}[1]{\left\{ #1 \right\}}
%%%%%% LOGIC STUFF
%\newcommand{\Val}{V}
\renewcommand{\phi}{\varphi}
\newcommand{\Frame}{\mathcal{F}}
\newcommand{\true}[1]{\lVert #1 \rVert}
\newcommand{\K}{\mathsf{K}}
\newcommand{\lequiv}{\leftrightarrow}
\newcommand{\limp}{\rightarrow}
%\newcommand{\lbox}{\square}
%\newcommand{\ldia}{\lozenge}
\newcommand{\ldia}[1]{\left\langle #1 \right\rangle}
\newcommand{\lbox}[1]{\left[ #1 \right]}
\newcommand{\Stb}{\mathsf{stb}}
%%%%%% META SYNTAX
\newcommand{\IF}{\mbox{ \textsc{if} }}
\newcommand{\THEN}{\mbox{ \textsc{then} }}
\newcommand{\IMPLIES}{\mbox{ \textsc{implies} }}
\newcommand{\OR}{\mbox{ \textsc{or} }}
\newcommand{\AND}{\mbox{ \textsc{and} }}
\newcommand{\IFF}{\Longleftrightarrow}
\newcommand{\ST}{\mbox{ \textsc{s.t.} }}
\newcommand{\FOR}{\mbox{ \textsc{for} }}
\newcommand{\N}{N}
\newcommand{\T}{\mathcal T}
\newcommand{\I}{\mathcal I}
\newcommand{\Model}{\mathcal{M}}
\renewcommand{\S}{\mathcal{A}}
\newcommand{\G}{{\bf G}}
\newcommand{\Atoms}{{\bf P}}
\newcommand{\C}{{\bf C}}
\newcommand{\D}{\mathcal{O}}
\newcommand{\AB}{\mathcal{O}^\ast}
\newcommand{\maj}{\mathsf{maj}}
\newcommand{\pv}{\mathsf{pv}}
\renewcommand{\O}{{\bf O}}
\newcommand{\tuple}{\left\langle #1 \right\rangle}
\newcommand{\0}{{\bf 0}}
\newcommand{\1}{{\bf 1}}
\newcommand{\set}{\left\{ #1 \right\}}
\renewcommand{\phi}{\varphi}
\newcommand{\Frame}{\mathcal{F}}
\newcommand{\true}[1]{\lVert #1 \rVert}
\newcommand{\K}{\mathsf{K}}
\newcommand{\lequiv}{\leftrightarrow}
\newcommand{\limp}{\rightarrow}
\newcommand{\ldia}[1]{\left\langle #1 \right\rangle}
\newcommand{\lbox}[1]{\left[ #1 \right]}
\newcommand{\Stb}{\mathsf{stb}}
\newcommand{\IF}{\mbox{ \textsc{if} }}
\newcommand{\THEN}{\mbox{ \textsc{then} }}
\newcommand{\IMPLIES}{\mbox{ \textsc{implies} }}
\newcommand{\OR}{\mbox{ \textsc{or} }}
\newcommand{\AND}{\mbox{ \textsc{and} }}
\newcommand{\IFF}{\Longleftrightarrow}
\newcommand{\ST}{\mbox{ \textsc{s.t.} }}
\newcommand{\FOR}{\mbox{ \textsc{for} }}
\RequirePackage{url}
\pagestyle{empty}
\sloppy
\setlength{\textwidth}{5.5in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.35in}
\setlength{\evensidemargin}{0.0in}
\setlength{\topmargin}{0in}
\renewenvironment{abstract}{\begin{center}\small\textbf{Abstract}\\[8pt]
\begin{minipage}
{.85\textwidth}}{\end{minipage}
}
\newenvironment{contact}{\begin{center}\begin{tabular}{@{}l}}{\end{tabular}\hfill\mbox{}\end{center}}
\newcommand{\email}[1]{Email:~\url{#1}}
\begin{document}
\title{From Proxy Voting to DeGroot Processes}
\author[ ]{ZoĆ© Christoff}
\author[ ]{Davide Grossi}
\affil[ ]{}
\vspace{-1em}
\date{}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\selectlanguage{english}
\begin{abstract}
[[[THIS IS STILL THE OLD ABSTRACT!]]] 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'.%
\end{abstract}%
\maketitle
\section{Introduction}
\section{Preliminaries}
\subsection{Binary Aggregation}
The formalism of choice for this paper is binary aggregation \cite{grandi13lifting}.
A binary aggregation structure (\emph{BA structure}) is a tuple $\S = \tuple{\N,\Atoms,\gamma}$ where:
\begin{itemize}
%[noitemsep]
\item $\N = \set{1,\dots,n}$ is a finite set individuals s.t. $|\N|= n \in \mathbb{N}$;
\item $\Atoms = \set{p_1,\dots,p_m}$ is a finite set of issues ($|\Atoms|= m \in \mathbb{N}$), each represented by a propositional atom;
\item $\gamma \in \L$ is an (integrity) constraint, where $\L$ is the propositional language constructed by closing $\Atoms$ under a functionally complete set of Boolean connectives (e.g., $\set{\neg, \wedge}$)
\end{itemize}
An {\em opinion} $O: \Atoms \to \set{\0,\1}$ is an assignment of truth values to the set of issues $\Atoms$, and the set of all opinions is denoted by $\D$. The opinion of an agent $i$ is said to be ``consistent" whenever $O_i \models \gamma$, that is, $i$'s opinion satisfies the integrity constraint. The set of all consistent opinions is denoted $\D_c = \set{O \in \D \mid O \models \gamma}$.
Thus, $O(p)=\0$ (respectively, \mbox{$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 \Atoms$ we write $\pm p$ to denote one element from $\set{p, \neg p}$. An \emph{opinion profile} $\O=(O_1,\dots,O_{n})$ records the opinion, on the given set of issues, of every individual in $\N$. Given a profile $\O$ the $i^{\mathit{th}}$ projection $\O_i$ denotes the opinion of agent $i$ in profile $\O$.
We also denote by $\O(p)= \set{i \in \N \mid O_{i}(p)= \1}$ the set of agents accepting issue $p$ in profile $\O$ and by $\O(p^-)= \set{i \in \N \mid O_{i}(p)= \0}$.
Given a BA structure $\S$, an aggregation rule (or {\em aggregator}) for $\S$ is a function $F:\D_{c}^\N \to \D$, mapping every profile of consistent opinions to one collective opinion in $\D$.
$F(\O)(p)$ denotes the outcome of the aggregation on issue $p$. A benchmark aggregator is \emph{issue-by-issue strict majority rule} ($\maj$), which accepts an issue if and only if the majority of the population accepts it: $\maj(\O)(p)= \1$ if and only if $|\O(p)| \geq \frac{|\N|+1}{2}$.
%Note for Zoe: the rule is biased if |N| is even: if exactly half of the population all give 0 to p and 1 to q, \lnot p is "accepted" (i.e $\maj(\O)(p)=\0)$, but $q$ is not ($\maj(\O)(q)=\0)$.
It is well-known that aggregation by majority does not preserve consistency. The standard example is provided by the discursive dilemma, represented by the BA structure $\tuple{\set{1,2,3},\set{p,q,r},r \lequiv p \land q}$. The profile consisting of $O_1 \models p \land q \land r$, $O_2 \models p \land \neg q \land \neq r$, $O_3 \models \neg p \land q \land \neg r$, returns an inconsistent majority opinion $\maj(\O) \models p \land q \land \neg r$.
\subsection{Binary Aggregation with Abstention}
Allowing abstention in the framework of binary aggregation amounts to considering incomplete opinions. An {\em incomplete opinion} is a partial function $O: \Atoms \nrightarrow \set{\0,\1}$ from $\Atoms$ to $\set{\0, \1}$. We say that the incomplete opinion of an agent $i$ is consistent if formulas in $\set{p \in \Atoms \mid O_i(p) \in \set{\0, \1}} \cup \gamma$ are satisfiable (that is, the integrity constraint is consistent with $i$'s opinion on the issues she does not abstain about). We will sometimes use $\ast$ to denote the indetermined value. The set of incomplete opinions is denoted $\AB$ and the set of incomplete consistent opinions $\AB_c$. Profiles of incomplete opinions are defined in the obvious way.
Given a BA structure $\S$, an aggregator over profiles with abstentions for $\S$ is a function $F:\AB_{c}^\N \to \mathcal{O}$, mapping every profile of consistent incomplete opinions to one collective opinion in $\mathcal{O}$.
Again, a benchmark aggregator is \emph{issue-by-issue strict majority rule} ($\maj_\ast$), which accepts an issue if and only if the majority of the population expressing a definite opinion accepts it: $\maj_\ast(\O)(p)= \1$ if and only if $|\O(p)| \geq \frac{|\set{i \in \N \mid O_i(p) \in \set{\0, \1}}|+1}{2}$.
\subsection{On the Structural Complexity of $\gamma$}
\cite{Grandi_2013}
\subsection{Axiomatic properties}
We start by recalling well-known properties of aggregators from the judgment aggregation with abstention literature.
\begin{definition}
An aggregator over profiles with abstention $F$ is said to be:
\begin{description}
\item[unanymous] iff for all $p\in \Atoms$, for all profiles $\O$: if for all $i\in \N, O_i(p) = \1$, then $F(\O)(p)= \1$, and if for all $i\in \N, O_i(p)=\0$, then $F(\O)(p)=\0$.
\item[anonymous] iff for any bijection $\mu: \N\rightarrow\N$, $F(\O)=F(\O^\mu)$, where $\O^\mu = \tuple{O_{\mu(1)}, \ldots, O_{\mu(n)}}$. I.e., permuting opinions among individuals does not affect the output of the aggregator.
\item[$p$-dictatorial] iff there exists $i \in \N$ (the {\em $p$-dictator}) s.t. for any profile $\O$, if $O_i(p) = \1$, then $F(\O)(p)= \1$ and if $O_i(p)=\0$, then $F(\O)(p)=\0$. I.e., there exists an agent whose opinion determines the group's opinion on $p$, whenever he does not abstain. If $F$ is $p$-dictatorial, with the same dictator on all issues $p \in \Atoms$, then it is called {\bf dictatorial}.
\item[$p$-oligarchic] iff there exists $S \subseteq \N$ (the {\em $p$-oligarchs}) s.t. $S\neq\emptyset$ and for any profile $\O$, if for all $i\in S$, $O_i(p)=\1$, then $F(\O)(p) = \1$ and if for all $i\in S$, $O_i(p)=\0$, then $F(\O)(p) = \0$. I.e., there exists a group of agents whose opinion always determines the group's opinion on $p$, when they do not abstain. If $F$ is $p$-oligarchic, with the same oligarchs on all issues $p \in \Atoms$, then it is called {\bf oligarchic}.
\item[monotonic] iff, for all $p\in \Atoms$ and all $i\in\N$: for any profiles $\O, \O'$, if $\O =_{-i} \O'$ and $O_i(p)\neq 1$ and $O'_i(p)=1$, then: if $F(\O)(p)=1$, then $F(\O')(p)=1$.
\item[independent] iff, for all $p\in \Atoms$, for any profiles $\O, \O'$: if for all $i\in \N, O_i(p) = O'_i(p)$, then $F(\O)(p)=F(\O')(p)$.
\item[neutral] iff, for all $p,q \in \Atoms$, for any profile $\O$: if for all $i\in\N$, $O_i(p)=O_i(q)$, then $F(\O)(p)=F(\O)(q)$.
\item[systematic] iff it is neutral and independent.
\item[unbiased] iff for all $p \in \Atoms$, for any profiles $\O, \O'$: if for all $i\in\N$, $O_i(p)= 1$ iff $O'_i(p)=0$, then $F(\O)(p)=1$ iff $F(\O')(p)=0$.
\item[$\gamma$-rational] iff for any profile $\O$, $F(\O) \models \gamma$. I.e., if the aggregator preserves the constraint $\gamma$.
If it preserves $\gamma$ for all constraints $\gamma$, then the aggregator is {\bf rational}.
\end{description}
\end{definition}
Anonymity implies non oligarchy (except for the case where the set of oligarchs is the whole set $N$) and thus non-dictatorship.
The rule $\maj_\ast$ is unanymous, anonymous, monotonic, systematic, but it is not rational and not unbiased.
\section{Binary Aggregation with Proxy}
\subsection{Binary Opinions with Delegation}
In binary aggregation with proxy, agents either express an acceptance/rejection opinion or \emph{delegate} such opinion to a different agent. In this setup an opinion $O: \Atoms \to \set{\0,\1} \cup \N$ is an assignment of either a truth value or another agent to each issue in $\Atoms$, such that: (a) $O_i(p) \neq i$ (that is, self-delegation is not an expressible opinion); (b) and the set of formulas in \eqref{eq:ir} is satisfiable. The latter is a requirement we discuss in detail below, capturing a strong form of individual rationality in proxy aggregation.
We call functions of the above kind {\em proxy opinions} to distinguish them from standard (binary) opinions, and we denote by $\mathcal{P}$ the set of all proxy opinions.
\subsection{Aggregation of Proxy Opinions}
Each profile $\O$ of proxy opinions ({\em proxy profile} in short) induces a delegation graph $G^\O = \langle \N, \set{R_p}_{p \in \I}\rangle$ where for $i, j \in \N$ $iR^p j$ iff $\O_i(p) = j$ (``$i$ delegates to $j$ on issue $p$''). Each $R^p$ is a binary relation which is irreflexive and deterministic ($\forall i,j,k \in \N$ if $i R j$ and $i R k$ then $j = k$).
The weight of an agent $i$ w.r.t. $p$ in a delegation graph $G^\O$ is given by its indegree with respect to $R^*_p$ (i.e., the transitive reflexive closure of $R_p$):
$w^\O_i(p) = |\set{j \in \N \mid j R^*_p i}|$. For all $p \in \I$, we also define the function $g_p: \N \rightarrow \wp(\N)$ such that $g_p(i) = \set{j \in \N \mid j R^*_p i \AND \nexists k: jR_p k}$. The function associates to each agent $i$ (for a given issue $p$), the (singleton consisting of the) last agent reachable from $i$ via a path of delegation on issue $p$, when it exists (and $\emptyset$ otherwise). Slightly abusing notation we will use $g_p(i)$ to denote an agent, that is, the {\em guru} of $i$ over $p$ when $g_p(i) \neq \emptyset$. If $g_p(i) = \set{i}$ we call $i$ a {\em guru} for $p$.
Given a BA structure $\S$, a proxy aggregator for $\S$ maps every profile of proxy opinions to one opinion in $\D$. As above, $F(\O)(p)$ denotes the outcome of the aggregation on issue $p$.
The standard form of proxy voting can be modeled by following proxy aggregator based on issuewise majority:
\begin{align}
\pv_{\maj}(\O)(p) = 1 & \IFF \sum_{i \in \O(p)} w^\O_i(p) \geq \frac{|\N|+1}{2} \label{eq:proxymaj}
\end{align}
That is, an issue is accepted by proxy majority in profile $\O$ if and only if the sum of the weights of the agents who accept $p$ in $\O$ exceeds the majority quota. Just like majority, proxy majority is not collectively consistent. In general, given an (anonymous and independent) aggregator $F$, its proxy variant can be defined as in \eqref{eq:proxymajast} for $\maj$.
Remark that the notation introduced above allows us to define the majority rule in a simpler way:
\begin{align}
\pv_{\maj}(\O)(p) = 1 & \IFF |\{i \in \N | O_{g_i}(p)=\1 \}| \geq \frac{|\N |+1}{2} \label{eq:proxymajsimple}
\end{align}
The proxy version of the majority rule with abstention $\maj_\ast$ is defined similarly:
\begin{align}
\pv_{\maj_\ast}(\O)(p) = 1 & \IFF \sum_{i \in \O(p)} w^\O_i(p) \geq \frac{\sum_{i \in \O(p)} w^\O_i(p)+ \sum_{i \in \O(p^-)} w^\O_i(p)+1}{2} \label{eq:proxymajast}
\end{align}
%$\maj_\ast(\O)(p)= \1$ if and only if $|\O(p)| \geq \frac{|\set{i \in \N \mid O_i(p) \in \set{\0, \1}}|+1}{2}$.
Again, this definition can be rewritten in a simpler form:
\begin{align}
\pv_{\maj_\ast}(\O)(p) = 1 & \IFF |\{i \in \N | O_{g_i}(p)=1 \}| \geq \frac{|\{i \in \N | g_i(p)\neq\emptyset\}|+1}{2} \label{eq:proxymajastsimple} \end{align}
%note for Zoe: Davide mentioned that there the anonymous rules are exactly the quota rules (there is some result no this somewhere)
\subsection{Individual Rationality}
Individual rationality is a more debatable requirement than in classical aggregation. The individual rationality of a proxy opinion $O_i$ amounts to the satisfiability of the following set of formulas:
\begin{align}
\set{\gamma} \cup \set{p \in \I \mid O_i(p) = \1 \mbox{ or } O_{g_p(i)}(p) = \1} \cup \set{\neg p \in \I \mid O_i(p) = \0 \mbox{ or } O_{g_p(i)}(p) = \0} \label{eq:ir}
\end{align}
That is, the integrity constraint $\gamma$ is consistent with $i$'s opinion on the issues she does not delegate on, and the opinions of her gurus (if they exist). In what follows we assume for now that this formulation of individual rationality to hold (we will relax this assumption later on).
\section{An Analysis of Proxy Voting}
\subsection{Axiomatic properties}
We start by defining proxy variants of well-known properties of aggregators from the judgment aggregation literature. Let us first, however, introduce some auxiliary notation and terminology.
HERE IS THE NEW (``SLIGHTLY LESS AD HOC") DEFINITION:
We define a notion of permutation relative to connected components of a delegation graph, i.e only agents between which a path exists are permuted.
\begin{definition}[connectedness preserving permutation]
Given a proxy profile $\O$ and an issue $p\in P$, a \emph{connectedness preserving permutation} is a bijection $\mu: \N\rightarrow\N$, such that, for all $i\in\N$, $iR^*_{p}\mu(i)$ or $\mu(i)R^*_pi$.
\end{definition}
\begin{definition}[permutation OLD DEFINITION]
OLD (SUPER AD HOC) DEFINITION: Given a bijection $\mu: \N\rightarrow\N$, and a proxy profile $\O$, we denote with $\O^\mu = \tuple{O^\mu_1, \ldots, O^\mu_n}$ the permutation of $\O$ where:
$
O^\mu_i(p) = \left\{
\begin{array}{ll}
\O_{i}(p) & \mbox{if $i$ is a guru for $p$ in $\O$} \\
\mu(j) & \mbox{if $iR_pj$ in $\O$}
\end{array}
\right.
$
THIS TYPE OF PERMUTATION KEEPS THE NETWORKS ISOMORPHIC (AND WITH THE SAME OPINION FOR THE CORRESPONDING GURUS). WE WANT SOMETHING MORE GENERAL: THERE SHOULD BE ANOTHER TYPE OF TRANSFORMATION OF OUR PROFILE WHICH ONLY PRESERVES THE NUMBER OF AGENTS WHO ADD WEIGHT TO OPINION 1 AND WHO ADD WEIGHT TO OPINION ZERO. THAT IS, WE ONLY NEED TO PRESERVE THE CARDINALITIES OF THE SETS OF ALL AGENTS WITH GURUS WITH OPINION $\0$ AND WITH OPINION $\1$. THAT WOULD DEFINE THE SET OF PROXY PROFILES WHICH TRANSLATE TO THE SAME NON-PROXY PROFILE WITH ABSTENTION. BUT THEN IT IS NOT JUST A SIMPLE "PERMUTATION" ANYMORE.
\begin{definition}
A proxy aggregator $\pv$ is said to be:
\begin{description}
\item[unanymous] iff for all $p\in \Atoms$, for all proxy profile $\O$: if for all $i\in \N, O_{g_p(i)}(p) = \1$, then $\pv(\O)(p)=\1$ and if for all $i\in \N, O_{g_p(i)}(p)= \0$, then $\pv(\O)(p)=\0$. I.e., when all gurus agree, their opinion becomes the group's opinion.
%\item[unanymous bis] iff for all $p\in \Atoms$, for all proxy profiles $\O$: if for all $i\in \N, O_i(p) = \1$, then $\pv(\O)(p)= \1$ and if for all $i\in \N, O_i(p) \neq \1$, then $\pv(\O)(p)\neq \1$.
\item[anonymous] iff for any bijection $\mu: \N\rightarrow\N$, $\pv(\O)=\pv(\O^\mu)$. I.e., permuting proxy opinions among individuals does not affect the output of the aggregator.\footnote{It is worth observing that the permutation of a proxy profile cannot simply be defined by `reshuffling' the individual proxy opinions in the profile. If $i$ delegates to $j$, and the permutation $\mu$ is such that $i \mapsto k$ and $j \mapsto \ell$ (with $i \neq j \neq k \neq \ell$), then $k$'s opinion in the permuted profile should be a delegation to $\ell$ rather than to $j$.THAT'S NOT ENOUGH}
\item[$p$-dictatorial] iff there exists $i \in \N$ (the {\em $p$-dictator}) s.t. for any proxy profile $\O$, if $g_p(i) \neq \emptyset$ then $\pv(\O)(p) = \O_{g_p(i)}$. I.e., there exists an agent whose guru's opinion always determines the group's opinion on $p$. If the aggregator is $p$-dictatorial, with the same dictator on all issues $p \in \I$, then it is called {\bf dictatorial}.
%\item[$p$-dictatorial bis] iff there exists $i \in \N$ (the {\em $p$-dictator}) s.t. for any proxy profile $\O$, $\pv(\O)(p) = \O_i(p)$. I.e., there exists an agent whose opinion always determines the group's opinion on $p$. If the aggregator is $p$-dictatorial, with the same dictator on all issues $p \in \I$, then it is called {\bf dictatorial}.
\item[$p$-oligarchic] iff there exists $S \subseteq \N$ (the {\em $p$-oligarchs}) s.t. $S\neq\emptyset$ and for any proxy profile $\O$: if, for all $i\in S$, $O_{g_p(i)}=\1$, then $\pv(\O)(p) = \1$ and if, for all $i\in S$, $O_{g_p(i)}=\0$, then $\pv(\O)(p) = \0$. I.e., there exists a group of agents whose gurus' opinion always determines the group's opinion on $p$. If the aggregator is $p$-oligarchic, with the same oligarchs on all issues $p \in \Atoms$, then it is called {\bf oligarchic}.
%\item[$p$-oligarchic bis] iff there exists $S \subseteq \N$ (the {\em $p$-oligarchs}) s.t. $S\neq\emptyset$ and for any proxy profile $\O$, $\pv(\O)(p) = \1$ if and only if, for all $i\in S$, $O_i(p)=\1$. I.e., there exists a group of agents whose opinion always determines the group's opinion on $p$. If the aggregator is $p$-oligarchic, with the same oligarchs on all issues $p \in \I$, then it is called {\bf oligarchic}.
\item[monotonic] iff, for all $p\in \Atoms$ and all $i\in\N$: for any proxy profiles $\O, \O'$, if $\O =_{-i} \O'$ and $O_i(p)\neq 1$ and $O'_i(p)=1$, then: if $\pv(\O)(p)=1$, then $\pv(\O')(p)=1$.
%\item[monotonic bis?] iff, for all $p\in \Atoms$ and all $i\in\N$: for any proxy profiles $\O, \O'$, if $\O =_{-i} \O'$ and $O_i(p)\neq 1$ and $O'_i(p)=1$, then: if $\pv(\O)(p)=1$, then $\pv(\O')(p)=1$.
\item[independent] iff, for all $p\in \Atoms$, for any proxy profiles $\O, \O'$: if for all $i\in \N, O_{g_p(i)}(p) = O'_{g'_p(i)}(p)$, then $\pv(\O)(p)=\pv(\O')(p)$.
%\item[independent bis] iff, for all $p\in \Atoms$, for any proxy profiles $\O, \O'$: if for all $i\in \N, O_i(p) = O'_i(p)$, then $\pv(\O)(p)=\pv(\O')(p)$.
\item[neutral] iff, for all $p,q \in \Atoms$, for any proxy profile $\O$: if for all $i\in\N$, $O_{g_p(i)}(p)=O_{g_q(i)}(q)$, then $\pv(\O)(p)=\pv(\O)(q)$.
%\item[neutral bis] iff, for all $p,q \in \Atoms$, for any proxy profile $\O$: if for all $i\in\N$, $O_i(p)=O_i(q)$, then $\pv(\O)(p)=\pv(\O)(q)$.
\item[systematic] iff it is neutral and independent.
\item[unbiased] iff for all $p \in \Atoms$, for any proxy profiles $\O, \O'$: if for all $i\in\N$, $O_{g_p(i)}(p)= \1$ iff $O'_{g_p(i)}(p)\neq\1$, then $\pv(\O)(p)=\1$ iff $\pv(\O')(p)\neq\1$.
%\item[unbiased bis] iff for all $p \in \Atoms$, for any proxy profiles $\O, \O'$: if for all $i\in\N$, $O_i(p)= 1$ iff $O'_i(p)\neq \1$, then $\pv(\O)(p)=\1$ iff $\pv(\O')(p)\neq \1$.
\item[$\gamma$-rational] iff for any proxy profile $\O$, $\pv(\O) \models \gamma$. I.e., if the aggregator preserves the constraint $\gamma$. If an agreggator is $\gamma$-rational for all $\gamma$, then it is called {\bf rational}.
\end{description}
\end{definition}
It is worth briefly commenting on the above definitions. Like in the classic case, anonymity implies non-dictatorship. A weaker form of dictatorship would require the opinion of the dictator to become the collective opinion only in those cases in which the dictator herself is a guru. This would be the case when one agent is a guru for more than half of the population.
\subsection{Proxy Majority}
Proxy majority is unanimous, anonymous\footnote{Note that this is the case in a very weak sense: we defined the permutations in a way which makes this work.}, monotonic, systematic, not rational (but $\gamma$-rational when $\gamma$ is simple), and biased (unless $|\N|$ is odd).
We provide a variant of May's characterization theorem \cite{May_1952} of majority voting for proxy majority.
\begin{theorem}[Conjecture]
Let $\S$ be a BA structure where $\gamma$ is simple and $|\N|$ is odd. A proxy aggregator $\pv$ is the proxy majority if and only if it is $\gamma$-rational, monotonic, anonymous and unbiased.
\end{theorem}
\begin{proof}
\ldots
\end{proof}
\subsection{Proxy Voting as Binary Aggregation with Abstentions}
Each proxy opinion profiles can be mapped into a binary opinion profile with abstention:
\begin{definition}[standard translation $t$]
The standard translation function from proxy opinions to incomplete opinions
$t:\mathcal{P} \to \AB $, given by:
$t(O_i(p))= O_{g_p(i)}$ if $ g_p(i) \neq \emptyset $, and $t(O_i(p))$ is undefined otherwise.
By extension, we will denote by $t({\bf P})$ the incomplete opinions profile resulting of translating the opinions from a proxy profile ${\bf P}$.
\end{definition}
\begin{theorem}[Conjecture]
Let ${\bf P}$ be a proxy profile, $\O$ an opinion profile, $O$ an opinion, and $t$ the standard translation from a proxy profile to an opinion profile:
\begin{tikzpicture}
\node(P) at (0,0) {${\bf P}$};
\node(O)at (1,0) {$\O$};
\node(F) at (0, -1) {$O$};
\draw[->] (P) -- node[below]{$t$} (O);
\draw[->] (P) -- node[left]{$\pv_F$} (F);
\draw[->] (O) -- node[right]{$F$} (F);
\end{tikzpicture}
\end{theorem}
%WE WANT TO FIRST SHOW THAT IT WORKS FOR DICTATORSHIP, MAJORITY RULE, QUOTA RULES.
\begin{theorem}[The case of the majority rule]
${\bf P}$ be a proxy profile, and $t$ the above defined standard translation from a proxy profile to an opinion profile.
Then, $\pv_{\maj_\ast}({\bf P})=\maj_\ast(t({\bf P}))$.
\end{theorem}
\begin{proof}
Let $p\in\P$ be arbitrary.
\begin{align*}
\pv_{\maj_\ast}({\bf P})(p)=1 & iff \\
|\{i \in \N | O_{g_p(i)}(p)=1\}| \geq \frac{|\{i \in \N | g_p(i)\neq\emptyset\}|+1}{2} & iff \\
|\{i \in \N | t(O_i(p))=1 \}| \geq \frac{|\set{i \in \N \mid t(O_i(p)) \in \set{\0, \1}}|+1}{2} & iff \\
\maj_\ast(t({\bf P}))(p)=1
\end{align*}
\end{proof}
\subsection{Properties on Network-Invariant Profiles}
Let us assume that we restrict the set of possible proxy profiles to the ones with the same delegation structures (with respect to each issue). In that case, proxy majority becomes $p$-oligarchic---the oligarchs being the set of gurus such that more than half of the voters is related to any of them via $R^*_p$. Proxy majority would be oligarchic only if there existed a unique group of agents such that, for each opinion profile, \emph{for any issue $p$}, they were "p-oligarchs", which is not the case.
%(and the rule becomes dictatorial whenever there is only one such agent).
However, if we restrict even more our set of possible opinion profiles to the ones with a unique fixed network (i.e., the same network for all issues), then proxy majority becomes oligarchic.
\ldots
\section{To-do-list}
\subsubsection{Oligarchy}
An aggregator is said to be \emph{oligarchic} if there exists a non-empty set of agents (the oligarchs) such that, for any opinion profile, an issue is collectively accepted if and only if it is accepted by all the oligarchs. Majority proxy voting is not oligarchic in general.
\subsubsection{isomorphic networks}
Going towards the opposite direction, if we restrict our set of possible opinion profiles to the ones with isomorphic network structures (OR TO STRUCTURES WHICH ARE SIMILAR IN THE SENSE OF THE ABOVE AD HOC CONDITION), then we obtain a \emph{random issuewise oligarchy}. To make majority proxy voting properly oligarchic would require to add a stronger constraint to the set of opinion profiles: there is a unique set of agents such that for all opinion profiles, those agents are followed by more than half the population with respect to \emph{all} issues.
\subsubsection{Standard impossibility results}
The above defined opinion profiles can be mapped into a (non-proxy) opinion profile with abstention, as follows: For any proxy opinion profile, any agent and any issue $p$, if the agent is related via $R^*_p$ to an agent with opinion $0$ or $1$, then this agent is assigned opinion $0$ (respectively $1$) on issue $p$, otherwise this agent is abstaining on $p$.
Therefore, standard impossibility results for aggregation with abstention apply: every aggregation function that is independent and unanimous must be weakly oligarchic.
\subsection{Truth-tracking Behavior}
Condorcet's Jury Theorem shows that, for individuals whose probability of choosing the right alternative (among 2) is above 0.5, the probability of correct collective decision under the majority rule is (higher than the individual one and) approaches 1 as the size of the group increases.
When considering proxy voting, if we assume that all agents have the same probability of choosing correctly, then they would be better off without any delegation, as delegating reduces the number of impactful decision makers.
To make delegation truth-tracking, one thus needs to assume that when agents choose to delegate, they do so rather wisely too: they have more chances to delegate to someone who chooses more accurately than themselves than not (i.e, there is a probability above 0,5 that their delegate has a higher probability of making the right choice than theirs).
\subsection{Cycles}
The literature on proxy voting typically ignores cycles, for instance by discarding (considering as abstention) the votes of any part of the population containing a cycle, as defined above. This means that large parts of the population might not have a say. We will show below that there might exist better ways to deal with cycles.
\section{Diffusion-Based Aggregation}
Proxy voting can also be considered from a different perspective.
Imagine a population where, for each issue $p$, each agent copies the $0,1$ opinion of a unique ``guru''. Imagine that this population does so repeatedly until all groups of agents who are not related to a cycle of maximal gurus stabilize their opinions. Aggregating the opinions of this population , the collective output of a vote
The collective output of agents who either express a $0,1$ opinion or delegate to another agent is in a sense (for instance under any usual quota rule) the same as the output obtained from a vote where each individual has to express a $0,1$ opinion but gets there by copying the opinion of some unique ``guru'' (possibly themselves). The corresponding ``copying'' iterative deliberation process is a limit case of DeGroot influence in social networks, where the network structure (who copies who) is serial and functional.
\section{BELOW THIS POINT IS ONLY THE OLD MATERIAL Introduction}
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 \cite{Degroot_1974}, and the more recent propositional opinion diffusion model due to \cite{Grandi:2015:POD:2772879.2773278}. The processes we study---called here Boolean DeGroot processes---are the $\set{0,1}$ 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 \cite{liquid_feedback}. We will see that Boolean DeGroot processes offer a novel and natural angle on the issue of delegation cycles in liquid democracy.
\paragraph{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.
\paragraph{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.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/BDPs1/BDPs1}
\caption{{{BDPs lie in the intersection of DeGroot processes and propositional opinion diffusion processes.\label{figure:intersection}%
}%
}}
\end{center}
\end{figure}
\section{Binary aggregation and DeGroot processes} \label{sec:preliminaries}
\subsection{Binary aggregation}
The formalism of choice for this paper is binary aggregation \cite{grandi13lifting}.
A binary aggregation structure (\emph{BA structure}) is a tuple $\S = \tuple{\N,\Atoms}$ where:
\begin{itemize}
%[noitemsep]
\item $\N = \set{1,\dots,n}$ is a finite set individuals s.t. $|\N|= n \in \mathbb{N}$;
\item $\Atoms = \set{p_1,\dots,p_m}$ is a finite set of issues ($|\Atoms|= m \in \mathbb{N}$), each represented by a propositional atom.
\end{itemize}
We denote with $\L$ the propositional language constructed by closing $\Atoms$ under a functionally complete set of Boolean connectives (e.g., $\set{\neg, \wedge}$).
An {\em opinion} $O: \Atoms \to \{0,1\}$ is an assignment of truth values to the set of issues $\Atoms$.
Thus, $O(p)=0$ (respectively, \mbox{$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 \Atoms$ we write $\pm p$ to denote one element from $\set{p, \neg p}$. An \emph{opinion profile} $\O=(O_1,\dots,O_n)$ records the opinion, on the given set of issues, of every individual in $\N$. Given a profile $\O$ the $i^{\mathit{th}}$ projection $O_i$ denotes the opinion of agent $i$ in profile $\O$.
We also denote by $\O(p)=\{i \in \N \mid O_{i}(p)=1\}$ the set of agents accepting issue $p$ in profile $\O$.
\subsection{Binary aggregation and binary influence}
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 \emph{influence graph}) is therefore a structure $G = \tuple{\N, R}$ where $R \subseteq \N^2$ is a binary relation where $i R j$ is taken here to denote that ``$i$ is influenced by $j$''. Such relation is serial ($\forall i\in \N, \exists j \in \N: i R j$) and functional ($\forall i,j,k \in \N$ if $i R j$ and $i R k$ then $j = k$). So each agent $i$ has exactly one successor (influencer or `guru'), possibly itself, which we denote $R(i)$.
An \emph{influence profile} $\G=(G_1,\dots,G_m)$ records how each agent is influenced by each other agent, with respect to each issue $p \in \Atoms$. Given a profile $\G$ the i$^{\mathit{th}}$ projection $G_i$ denotes the influence graph for issue $p_i$.
\subsection{De Groot processes in binary aggregation}
So let us define the type of dynamics the paper focuses upon:
\begin{definition}
[BDP] \label{def:BDP}
Now fix an opinion profile $\O$ and an influence profile $\G$. Consider the stream $\O^0, \O^1, \ldots, \O^n, \ldots$ of opinion profiles recursively defined as follows:
\begin{itemize}[noitemsep]
\item Base: $\O_0 := \O$
\item Step: for all $i \in \N$, $p\in \Atoms$, $O_i^{n+1}(p) := O^{n}_{R_p(i)}(p)$.
\end{itemize}
We call processes defined by the above dynamics \emph{Boolean DeGroot processes} (BDPs).
\end{definition}
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 \emph{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}.
\section{Convergence} \label{sec:convergence}
When do the opinions of a group of individuals influencing each other stabilize? Conditions have been given, in the literature, for the general paradigms of which BDPs are limit cases. This section introduces the necessary graph-theoretic notions and briefly recalls those results before giving a characterization of convergence for BDPs.
\subsection{Graph-theoretic preliminaries}
We start with some preliminary graph-theoretic remarks.
Let us first recall some vocabulary.
Let $G = \tuple{\N, R}$ be a graph and $R^{*}$ be the transitive and symmetric closure of $R$.
A \emph{path} is a sequence of nodes $\tuple{i_1,\dots, i_k}$, such that, for all $l\in\{1,\dots,k\}$, $i_lRi_{l+1}$.
The \emph{distance} between two nodes $i,j$ is the length of the shortest path $\tuple{i,\dots, j}$ between them.
The \emph{diameter} of a graph is the maximal distance between any two nodes related by a path.
A \emph{cycle} is a path of length $k$ such that $i_1=i_k$.
A set of nodes $S\subseteq \N$ is said to be:
\begin{itemize}
\item[]\emph{a cycle in $G$} if all elements in $S$ are in one cycle of length $|S|$,
\item[]\emph{connected} if for any $i , j \in S$: $i R^{*}j$,
\item[] \emph{strongly connected} if for any $i,j \in S$: there is a path $\tuple{i,\dots, j}$,
\item[]\emph{closed} if for any $i\in S$, $j \notin S$, it is not the case that $iRj$,
\item[] a \emph{connected component} if for any $i,j \in \N$: $iR^{*}j$ if and only if $i,j\in S$,
\item[] \emph{aperiodic} if the greatest common divisor of the lengths of its cycles is $1$.
\end{itemize}
Note that the class of graphs BDPs rely on (finite, serial and functional) present a special shape:
\begin{fact}
\label{fact:uniquecycle}
Let $G$ be an influence graph and $C$ be a connected component of $G$.
Then $C$ contains exactly one cycle, and the set of nodes in the cycle is closed.
\end{fact}
\begin{proof}
Assume that $C$ does not contain any cycle. Since $\N$ is finite and since no path can repeat any node, any path in $C$ is finite too. Let $i$ be the last element of (one of) the longest path(s) in $C$. Then $i$ does not have any successor, which contradicts seriality. So $C$ contains at least one cycle.
Let $S$ be the set of nodes of a cycle in $C$. Assume that $S$ is not closed: for some $i\in S$ and $j\notin S$, $iRj$. Since $S$ is a cycle, there is also some $k\in S$, such that $iRk$, which contradicts functionality. Therefore, the nodes of any cycle in $C$ forms a closed set.
Now assume that $C$ contains more than one cycle. Since the nodes of each cycle forms a closed set, there is no path connecting any node inside a cycle to any node in any other cycle, which contradicts connectedness. So $C$ contains a unique cycle, whose nodes form a closed set.
\end{proof}
Intuitively, influence graphs of BDPs then look like sets of confluent chains aiming together towards common cycles.
\subsection{Convergence of BDPs}
For the general case of DeGroot processes, an influence structure guarantees that any distribution of opinions will converge if and only if ``every set of nodes that is strongly connected and closed is aperiodic" \cite[p.233]{jackson08social}.
In the propositional opinion diffusion setting, sufficient conditions for stabilization have been given by \cite[Th. 2]{Grandi:2015:POD:2772879.2773278}: on influence structures containing cycles of size at most one (i.e, only self-loops), for agents using an aggregation function satisfying (ballot-)monotonicity and unanimity\footnote{Notice that the rule underpinning BDP, that is the `guru-copying' rule on serial and functional graphs, trivially satisfies those constraints.}, opinions will always converge in at most at most $k+1$ steps, where $k$ is the diameter of the graph.\footnote{A second sufficient condition for convergence is given by \cite{Grandi:2015:POD:2772879.2773278}: when agents use the unanimity aggregation rule, on irreflexive graphs with only vertex-disjoint cycles, such that for each cycle there exists an agent who has at least two influencers, opinions converge after at most $\N$ steps. Note that no BDP satisfies this second condition.}
Our results will show how BDPs are an interesting limit case of both DeGroot and propositional opinion diffusion processes.
\subsubsection{Terminology}
Let us now turn to convergence for the limit case of BDPs. We start with some terminology.
We say that the stream of opinion profiles $\O^0, \O^1, \ldots, \O^n, \ldots$ {\em converges} if
there exists $n \in \mathbb{N}$ such that for all $m\in \mathbb{N}$, if $m\geq n$, then $\O^m = \O^n$.
We will also say that a stream of opinion profiles converges {\em for issue} $p$ if
there exists $n \in \mathbb{N}$ such that, for all $m\in \mathbb{N}$, if $m\geq n$, then $\O^m (p) = \O^n(p)$.
Given a stream of opinion profiles starting at $\O$ we say that agent $i \in \N$ stabilizes in that stream for issue $p$ if there exists $n \in \mathbb{N}$ such that $O^n_i(p) = O^{m}_i(p)$ for any $m > n$. So a BDP on influence graph $\G$ starting with the opinion profile $\O$ is said to converge if the stream $\O^0, \O^1, \ldots, \O^n, \ldots$ generated according to Definition \ref{def:BDP} where $\O = \O^0$ converges. Similarly, A BDP is said to converge for issue $p$ if its stream converges for $p$, and an agent $i$ in the BDP is said to stabilize for $p$ if it stabilizes for $p$ in the stream generated by the BDP.
\subsubsection{Two results}
It must be intuitively clear that non-convergence in a BDP is linked to the existence of cycles in the influence graphs. However, from the above observation
(Fact~\ref{fact:uniquecycle}), we know that nodes in a cycle cannot have any influencers outside this cycle, and hence that cycles (including self-loops) can only occur at the ``tail'' of the influence graph.
Hence, if the opinions in the (unique) cycle do not converge, which can only happen in a cycle of length $\geq 2$, the opinions of the whole population in the same connected component will not converge. The above implies that for any influence graphs with a cycle of length $\geq 2$, there exists a distribution of opinions which loops.
This brings us back to convergence result for general (not necessarily Boolean) DeGroot processes. Indeed, for functional and serial influence graphs, a closed connected component is aperiodic if and only if its cycle is of length $1$.
\begin{fact}
\label{fact:influence}
Let $\G$ be an influence profile. Then the following are equivalent:
\begin{enumerate}
\item The BDP converges for any opinion profile $\O$ on $\G$.
\item For all $p\in \Atoms$, $G_{p}$ contains no cycle of length $\geq 2$.
\item For all $p\in \Atoms $, all closed connected components of $G_{p}$ are aperiodic.
\end{enumerate}
\end{fact}
\begin{proof}
\fbox{$2) \Rightarrow 1)$}
Let $p\in\Atoms$ and assume that $G_p$ contains no cycle of length $\geq 2$ and has diameter $k$. Let $C_p$ be a connected component of $G_p$. By Fact \ref{fact:uniquecycle}, $C_p$ contains a unique cycle, which, by assumption, is of length $1$. Hence, $C_p$ is aperiodic. Let $i$ be the node in the cycle. The opinion of $i$ will spread to all nodes in $C_p$ after at most $k$ steps. Therefore, all BDPs on $G$ will converge after at most $l$ steps, where $l$ is the maximum within the set of diameters of $G_p$ for all $p\in\Atoms$.
\fbox{$1) \Rightarrow 3)$} We proceed by contraposition.
Assume that for some $p\in\Atoms$, a connected component $C_p$ of $G_p$ contains a cycle of length $k\geq 2$. By \ref{fact:uniquecycle}, this cycle is unique, and therefore the greatest common divisor of the cycles lengths of $C_p$ is $k$, so $C_p$ is not aperiodic.
Let $S$ be the set of nodes in the cycle.
Let $\O$ be such that for some $i,j\in S$ with distance $d$ from $i$ to $j$, $O_i(p)\neq O_j(p)$. Then $\O_i(p)$ will not converge, but enter a loop of size $k$: for all $x\in\mathbb{N}$, $O^{x\times k}_i(p) \neq O^{(x\times k)+d}_i(p)$. Hence, $\O$ does not converge.
\fbox{$3) \Rightarrow 2)$} Trivial.
\end{proof}
It is worth noticing that one direction (namely from $3$ to $1$) of the above result is actually a corollary of both the convergence result for DeGroot processes stated at the beginning of this section (cf. \cite{jackson08social}), and of a known convergence result for propositional opinion diffusion \cite[Th. 2]{Grandi:2015:POD:2772879.2773278}, also stated earlier.
\medskip
The above gives a characterization of the class of influence profiles on which \emph{all} opinion streams converge. But we can aim at a more general result, characterizing the class of pairs of opinion and influence profiles which lead to convergence:
\begin{theorem}
\label{theorem:opinion}
Let $\G$ be an influence profile and $\O$ be an opinion profile. Then the following statements are equivalent:
\begin{enumerate}
\item The BDP converges for $\O$ on $\G$.
\item For all $p\in \Atoms$, there is no set of agents $S\subseteq\N$ such that: $S$ is a cycle in $G_{p}$ and there are two agents $i,j\in S$ such that $O_i(p)\neq O_j(p)$.
\end{enumerate}
\end{theorem}
\begin{proof}
\fbox{$1) \Rightarrow 2)$} We proceed by contraposition.
Let $p\in\Atoms$, $S\subseteq\N$ be a cycle in $G_p$, $i,j\in S$, and $O_i(p)\neq O_j(p)$. Let $k$ be the length of the cycle and $d$ be the distance from $i$ to $j$. Then $O_i(p)$ will enter a loop of size $k$: for all $x\in\mathbb{N}$, $O^{x\times k}_i(p)\neq O^{(x\times k)+d}_i(p)$.
\fbox{$2) \Rightarrow 1)$}
Assume $S\subseteq\N$ be such that $S$ is a cycle in $G_p$, and for all $i,j\in S$, $O_i(p)=O_j(p)$. Then, for all $j\in S$, and all $x\in\mathbb{N}$, $O^{x}_j(p)=O_i(p)$ and for all $f\in\N\notin S$ with distance $d$ from $f$ to $i$, for all $x\in\mathbb{N}$, such that $x\geq d$, $O^{x}_f(p)=O_i(p)$.
\end{proof}
This trivially implies that the class of opinion profiles which guarantees convergence for {\em any} influence profile, is the one where everybody agrees on everything already. Note that the only stable distributions of opinions are the ones where, in each connected component in $G$, all members have the same opinion, i.e, on BDPs, converging and reaching a consensus (within each connected component) are equivalent, unlike in the stochastic case. Moreover, for an influence profile where influence graphs have at most diameter $d$ and the smallest cycle in components with diameter $d$ is of length $c$, it is easy to see that if a consensus is reached, it will be reached in at most $d-c$ steps, which is at most $n-1$.
\medskip
Finally observe that Theorem \ref{theorem:opinion} subsumes Fact \ref{fact:influence}. If $G_p$ contains only cycles of length $1$ (second statement in Fact \ref{fact:influence}) then, trivially, no two agents in a cycle can disagree (second statement in Theorem \ref{theorem:opinion}).
\section{Fixpoint Logics for Boolean DeGroot processes} \label{sec:logic}
In this section we show how a well-established logic for formal verification can be readily used to specify and reason about properties of BDPs, and in particular their convergence. The logic is the so-called $\mu$-calculus. This points to a so-far unexplored interface between fixpoint logics and models of opinion dynamics---like the DeGroot model and propositional opinion diffusion. The section moves some first steps in that direction along the lines of another recent work \cite{JvBoscillations}, where the $mu$-calculus, and extensions thereof, have been applied to the study of dynamical systems.
\subsection{Influence graphs as Kripke models}
We treat influence graphs as Kripke (multi-relational) models \cite{Seligmanetal:synthese,Christoff_2015}.%Christoff_2013,Christoff_2015,ZoePhD
\begin{definition}
We call an {\em influence model} a tuple $\Model = \tuple{\N, \G, \O}$ where $\G=(G_{p_1},\dots,G_{p_m})$ is an influence profile, and $\O: \Atoms \longrightarrow 2^\N$ is an opinion profile over $\Atoms$, that is, a valuation function.
\end{definition}
One can therefore easily interpret a modal language over influence models, where modalities are interpreted on the accessibility relations in $\G$. That is, to each graph $G_p$ we associate modalities $\lbox{p}$ and $\ldia{p}$. We will give the details below, but let us immediately note that the class of (possibly infinite) influence graphs would then be characterized by the following properties, for any $p \in \Atoms$:
\begin{align}
\lbox{p} \phi \limp \ldia{p} \phi & & \mbox{(seriality)} \\
\ldia{p} \phi \limp \lbox{p} \phi & & \mbox{(functionality)}
\end{align}
More precisely, for any influence profile $\G=(G_{p_1},\dots,G_{p_m})$, formula $\lbox{p_i} \phi \limp \ldia{p_i} \phi$ (respectively, $\ldia{p_i} \phi \limp \lbox{p_i} \phi$) is valid in such graph---that is, true in any pointed influence model built on such graph---if and only if each $G_{p_i}$ consists of a serial (respectively, functional) relation.\footnote{These are known results from modal correspondence theory (cf. \cite{Blackburn_2001}).} Put otherwise, on serial and functional graphs the modal box and diamond are equivalent.
\subsection{Modal $\mu$-calculus}
\[
\L^\mu: \phi ::= p \mid \bot \mid \neg \phi \mid \phi \land \phi \mid \ldia{p} \phi \mid \mu p. \phi(p)
\]
The language of the $\mu$-calculus expands the basic modal language with a least fixpoint operator $\mu$. Here is the BNF of the language:
where $p$ ranges over $\Atoms$ and $\phi(p)$ indicates that $p$ occurs free in $\phi$ (i.e., it is not bounded by fixpoint operators) and under an even number of negations.\footnote{This syntactic restriction guarantees that every formula $\phi(p)$ defines a set transformation which preserves $\subseteq$, which in turn guarantees the existence of least and greatest fixpoints by the Knaster-Tarski fixpoint theorem (cf. \cite{Stirling_2001}).} In general, the notation $\phi(\psi)$ stands for $\psi$ occurs in $\phi$. The usual definitions for Boolean and modal operators apply. Intuitively, $\mu p. \phi(p)$ denotes the smallest formula $p$ such that $p \lequiv \phi(p)$. The greatest fixpoint operator $\nu$ can be defined from $\mu$ as follows: $\nu p. \phi(p) := \neg \mu p. \neg \phi( \neg p)$.
We interpret $\L^\mu$ on influence models as follows:
\begin{definition}
Let $\phi \in \L^\mu$. The satisfaction of $\phi$ by a pointed influence model $(\Model, i)$ is inductively defined as follows:
\begin{align*}
\Model, i \not\models \bot & \\
\Model, i \models p \ & \IFF i \in \O(p), \mbox{ for } p \in {\bf P} \\
\Model, i \models \neg \phi & \IFF i \not\in \true{\phi}_\Model \\
\Model, i \models \phi_1 \wedge \phi_2 & \IFF i \in \true{\phi_1}_\Model \cap \true{\phi_2}_\Model \\
\Model, i \models \ldia{p} \phi & \IFF i \in \{ j \mid \exists k: j G_p k \ \& \ k \in \true{\phi}_\Model \} \\
\Model, i \models \mu p. \phi(p) & \IFF i \in \bigcap \{ X \in 2^\N \mid \true{\phi}_{\Model[p:=X]} \subseteq X \}
\end{align*}
where $\true{\phi}_{\Model[p:=X]}$ denotes the truth-set of $\phi$ once $\O(p)$ is set to be $X$. As usual, we say that: $\phi$ is valid in a model $\Model$ iff it is satisfied in all points of $\Model$, i.e., $\Model \models \phi$; $\phi$ is valid in a class of models iff it is valid in all the models in the class.
\end{definition}
We list some relevant known results about $\K^{\mu}$. The logic has a sound and (weakly) complete axiom system \cite{Walukiewicz_2000}. The satisfiability problem of $\K^{\mu}$ is decidable \cite{Streett_1984}. The complexity of the model-checking problem for $\K^{\mu}$ is known to be in NP $\cap$ co-NP \cite{Gr_del_1999}. It is known that the model-checking problem for a formula of size $m$ and alternation depth $d$ on a system of size $n$ can be solved by the natural fixpoint-approximation algorithm with (time) complexity of $O((m \cdot n)^{d+1})$ \cite{Emerson96}, where the alternation depth of a formula of $\L^\mu$ is the maximum number of $\mu/\nu$ alternations in a chain of nested fixpoint subformulas.\footnote{The reader is referred to, e.g. \cite{Emerson_2001}, for the precise definition.} Finally, the $\mu$-calculus is known to be invariant for bisimulation (cf. \cite{Blackburn_2001}). It actually corresponds to the bisimulation-invariant fragment of monadic second-order logic \cite{Janin_1996}.
\subsection{On the logic of convergence in BDPs}
Each stream of opinion profiles $\O^0, \O^1, \ldots, \O^n, \ldots$ corresponds to a stream of influence models $\Model^0, \Model^1, \ldots, \Model^n, \ldots$.
From the point of view of an influence model $\Model = \tuple{\N, \G, \O}$ the BDP dynamics of Definition \ref{def:BDP} can therefore be recast in terms of updates of the valuation function $\O$ as follows:
\begin{itemize}
[noitemsep]
\item Base: $\O^0 := \O$
\item Step: $\O^{n+1}(p) := \true{\lbox{p}p}_{\Model^n}$.
\end{itemize}
That is, the interpretation of $p$ at step $n+1$ is the interpretation of $\lbox{p}p$ at step $n$. Equivalently, the interpretation of $\neg p$ at step $n+1$ is the interpretation of $\lbox{p}\neg p$ at step $n$.
\begin{lemma}
\label{lemma:stable}
Let $\Model = \tuple{\N, \G, \O}$ be an influence model. The two following statements are equivalent:
\begin{enumerate}
\item $i \in \N$ is stable for $p$;
\item The pointed model $(\Model, i)$ satisfies:\footnote{Notice that $\pm p$ is used as a variable ranging over $\set{p, \neg p}$. Technically the above formula is to be read as a scheme for $\nu x. p \land \lbox{p} x$ and $\nu x. \pm \neg p \land \lbox{p} x$.}
\begin{align}
\Stb(p) := \nu x. \pm p \land \lbox{p} x
\end{align}
\end{enumerate}
\end{lemma}
\begin{proof}
First of all observe that, by the semantics of the $\mu$-calculus, formula $\Stb(p)$ denotes the largest fixpoint of function $\pm p \land \lbox{p}(\cdot)$, that is, formula $\lbox{p^*} \pm p$ where $\lbox{p^*}$ is the modal box interpreted over the reflexive and transitive closure of $G_p$.
\fbox{$1) \Rightarrow 2)$} Assume that $i$ is stable for $p$ and suppose towards a contradiction that $\Model, i \not\models \Stb(p)$. By what said above, it follows that there exists a $j$ such that $\O_i (p) \neq \O_j(p)$ which is connected by a finite $G_p$ path to $i$. By the functionality of influence models and the dynamics of Definition \ref{def:BDP} then at some stage $n$ in the stream of opinion profiles it should hold that $\O^n_i(p) = \O_j(p)$, against the assumption that $i$ be stable for $p$.
\fbox{$2) \Rightarrow 1)$} Assume $\Model, i \models \Stb(p)$. By what said above, this implies that there exists no $j$ such that $\O_i (p) \neq \O_j(p)$ which is connected by a finite $G_p$ path to $i$. It follows that in the stream generated by the BDP dynamics $i$ cannot change its opinion, and hence it is stable.
\end{proof}
\begin{theorem}
\label{theorem:mu}
Let $\Model = \tuple{\N, \G, \O}$ be an influence model. The two following statements are equivalent:
\begin{enumerate}
\item $i \in \N$ stabilizes for issue $p \in \Atoms$;
\item The pointed model $(\Model, i)$ satisfies:
\begin{align}
\mu x. \Stb(p) \vee \lbox{p} x
\end{align}
\end{enumerate}
\end{theorem}
\begin{proof}
First of all observe that, by the semantics of the $\mu$-calculus $\mu x. \Stb(p) \vee \lbox{p} x$ denotes the smallest fixpoint of equation $x \lequiv \Stb(p) \vee \lbox{p} x$. By the Knaster-Tarski theorem and the fact that influence models are finite, we can compute such fixpoint as $\bigcup_{0 \leq n < \omega} \true{\Stb(p)^n}$ where $\true{\Stb(p)^0} = \true{\Stb(p) \vee \lbox{p} \bot}$ (notice that $\lbox{p} \bot \lequiv \bot$ on influence models) and $\true{\Stb(p)^{n+1}} = \true{\Stb(p) \vee \lbox{p}\Stb(p)^n}$. So, by Lemma \ref{lemma:stable} $i$ belongs to $\true{\mu x. \Stb(p) \vee \lbox{p} x}$ either $i$ is stable for issue $p$ or has access in a finite number of steps to a an agent who is stable for $p$.
\fbox{$1) \Rightarrow 2)$} Assume that $i$ stabilizes for issue $p \in \Atoms$. So there exists a stage $n$ in the stream of profiles generated through Definition \ref{def:BDP} at which $\O_i^n(p) = \O_i^{m}(p)$ for all $m > n$. By Lemma \ref{lemma:stable}, $\tuple{\N, \G, \O^n}, i \models \Stb(p)$. It follows that $i$ is connected through a finite $G_p$-path to an agent $j$ such that $\Model, j \models \Stb(p)$. By what established above we thus have that $\Model, i \models \mu x. \Stb(p) \vee \lbox{p} x$.
\fbox{$2) \Rightarrow 1)$} Assume $\Model, i \models \mu x. \Stb(p) \vee \lbox{p} x$. It follows that $i$ is connected through a finite $G_p$-path to an agent $j$ such that $\Model, j \models \Stb(p)$. By Lemma \ref{lemma:stable} $j$ is therefore stable and therefore $i$ will stabilize for $p$.
\end{proof}
So the formula that expresses the stabilization of the agents' opinions on one issue is $\mu x. \left(\nu y. \pm p \land \lbox{p} y \right) \vee \lbox{p} x$.
Informally, the theorem states that in a BDP an agent reaches a stable opinion if and only if it has an indirect influencer (linked by an influence path) whose all direct and indirect influencer have the same opinion. Notice that such formula has alternation depth $0$. So an off-the-shelf model-checking algorithm for the $\mu$-calculus can check stabilization in time $O(m \cdot n)$ with $n$ being the size of the model and $m$ the size of the formula.
Now confront this with the earlier Theorem \ref{theorem:mu}. Since the convergence of the BDP is equivalent to the stabilization of all agents on all issues $p$ (either on $p$ or $\neg p$), we have the following corollary:
\begin{corollary}
The BDP for an opinion profile $\O$ based on influence graph $\G$ converges if and only if
\begin{align}
\tuple{\N, \G, \O}, i \models U \left(\bigwedge_{p \in \Atoms} \mu x. \Stb(p) \vee \lbox{p} x \right)
\end{align}
for any agent $i \in \N$, where $U$ denotes the universal modality (cf. \cite{Blackburn_2001}).
\end{corollary}
So we end up with a natural formalization of the property of convergence for a BDP.
\section{Unanimity and $2$-colorability}\label{sec:coloring}
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:
\begin{definition}
[UP]
Fix an opinion profile $\O$ and a (serial but non-necessarily functional) influence profile $\G$. Consider the stream $\O^0, \O^1, \ldots, \O^n, \ldots$ of opinion profiles recursively defined as follows:
\begin{itemize}[noitemsep]
\item Base: $\O_0 := \O$
%\item Step: for all $i \in \N$, $j\in \{1,...,m\}$, $\O_i^{n+1}(p_j)$ is given by:
%\begin{itemize}
%\item $\O_i^{n+1}(p_j)=\O_i^{n}(p_j)$ if for some $j,k\in R_j(i)$,$\O_j^{n}(p_j)\neq \O_k^{n}(p_j)$, and
%\item $\O_i^{n+1}(p_j)\neq \O_i^{n}(p_j)$ otherwise.
%\end{itemize}
%I AM NOT CONVINCED BY THE ABOVE STEP. MAYBE THIS (I ALSO SIMPLIFY NOTATION):
\item Step: for all $i \in \N$ and all $p \in \Atoms$:
%\begin{itemize}
\begin{align}
\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}
%\end{itemize}
\end{itemize}
We call processes defined by the above dynamics \emph{Unanimity Processes} (UPs).
\end{definition}
We give a sufficient condition for non-convergence of UPs:
\begin{lemma}
\label{lemma:suff.UP}
Let $G$ be a (serial and non-necessarily functional) influence profile and $\O$ be an opinion profile, such that, for some $p\in \Atoms $, 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 $\O$ does not converge in UP.
\end{lemma}
\begin{proof}
Let $G$ be a (serial and non-necessarily functional) influence profile, and $\O$ be an opinion profile, such that, for some $p\in \Atoms $, 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)$.
\end{proof}
Intuitively, the above condition for non-convergence corresponds to a situation of global maximal disagreement: \emph{all} agents (of a connected component) disagree with \emph{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\Atoms$, $\O$ properly colors $G_p$, then $\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 \emph{symmetric} ones:
\begin{lemma}
\label{lemma:symm.opinionUP}
Let $\G$ be a symmetric (serial and non-necessarily functional) influence profile and $\O$ be an opinion profile. The following are equivalent:
\begin{enumerate}[noitemsep]
\item $\O$ converges in UP on $\G$.
\item For all $p\in\Atoms $, 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)$.
\end{enumerate}
\end{lemma}
\begin{proof}
\fbox{$2) \Rightarrow 1)$} Assume that for any $p\in\Atoms$, 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. \fbox{$1) \Rightarrow 2)$} This follows from Lemma~\ref{lemma:suff.UP}.
\end{proof}
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:
\begin{theorem}
\label{thm:symm.influenceUP}
Let $\G$ be a symmetric (serial and non-necessarily functional) influence profile. The following are equivalent:
\begin{enumerate}[noitemsep]
\item All opinion profiles $\O$, converge in UPs on $\G$.
\item For all $p\in\Atoms$, and all connected components of $C \subseteq G_p$, $C$ is not $2$-colorable (contains cycle(s) of odd length).
\end{enumerate}
\end{theorem}
\begin{proof}
\fbox{$2) \Rightarrow 1)$} Let $p\in\Atoms$ and $C$ be connected component of $G_p$ with diameter $k$. Let $C$ contain a cycle of length $c$, with $c$ odd. Let $\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, $\O$ converges. \fbox{$1) \Rightarrow 2)$} This follows from Lemma~\ref{lemma:symm.opinionUP}.
\end{proof}
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 {\em 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.
\section{BDPs on logically interdependent issues}
\subsection{Preliminaries}
We consider now binary aggregation structures with constraints \cite{Grandi_2013}: $\S = \tuple{\N,\Atoms, \C}$ where $\C \subseteq \L$ is a finite set of propositional formulas over $\Atoms$. Intuitively, such formulas make explicit the logical interdependencies among the issues in $\Atoms$.
\begin{example}
The binary aggregation structure (with constraints) of the discoursive paradox is:
$\N = \set{1,2,3}$, $\Atoms = \set{p, q, r}$ and $\C= \set{p \lequiv (q \land r)}$
\end{example}
Given a BA structure with constraints, an {\em opinion} $O: \Atoms \to \{0,1\}$ is now an assignment of truth values to the set of issues $\Atoms$ which satisfies $\C$. That is, individual opinions are assumed to satisfy the constraints of the BA structure. As above, an \emph{opinion profile} $\O=(O_1,\dots,O_n)$ records the opinion, on the given set of issues, of every individual in $\N$.
\subsection{DeGroot processes in binary aggregation with constraints}
BDPs on aggregation structures with constraints may lead individuals to update with logically inconsistent opinions.
The following processes are simple adaptations of BDPs where agents update their opinions only if the opinions of their gurus, on the respective issues, are consistent with the constraints.
\begin{definition}
Fix an opinion profile $\O$, an influence profile $\G$, and a set of constraints $\C$. Consider the stream $\O^0, \O^1, \ldots, \O^n, \ldots$ of opinion profiles recursively defined as follows:
\begin{itemize}%[noitemsep]
\item Base: $\O_0 := \O$
\item Step: for all $i \in \N$, $p\in \Atoms$, $O_i^{n+1}(p) :=
\left\{
\begin{array}{ll}
O^{n}_{R_p(i)}(p) & \mbox{if } \bigwedge_{p \in \Atoms} O^{n}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C} \mbox{ is consistent} \\
O_i^{n}(p) & \mbox{otherwise}
\end{array}
\right.
$.
\end{itemize}
We call processes defined by the above dynamics \emph{resistant} BDPs.
\end{definition}
Resistant BDPs converge in some cases in which BDPs do not. There are cases in which there is disagreement in the cycles but the process still converges, because of the safeguard built in the dynamics.
Consider the following example. Let $\C=\{p\leftrightarrow \neg q\}$ and let $\O$ and $\G$ be as illustrated by the figure below:\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Resistant/default-figure}
\caption{{{Example of a resistant BDP with constraint $p\leftrightarrow \neg q$%
}%
}}
\end{center}
\end{figure}
This example shows that direction $1)\Rightarrow 2)$ of Theorem \ref{theorem:opinion} does not hold for resistant BDPs:
Some resistant BDPs stabilize even when there is disagreement within a cycle.
Intuitively, resistant BDPs with disagreements in cycles which stabilize do so because their cycles are not "synchronized". In the above example, given the constraint $p\leftrightarrow\neg q$, the only way to get stabilization starting from a situation respecting the constraint is to have a cycle of influence for $q$ which goes in \emph{the opposite direction} from the one from $p$, all other cases would amount to violate the constraint.
Beyond this simple example, we want to find out what happens with more complex constraints and what are the conditions for resistant BDPs to converge. Let us first show that direction $2)\Rightarrow 1)$ of Theorem \ref{theorem:opinion} still holds for resistant BDPs, that is, resistant BDPs without disagreement in their cycles always converge:
\begin{theorem}
\label{theorem:resistantsufficient}
Let $\G$ be an influence profile, $\O$ be an opinion profile, and $\C$ a set of constraints. Then the following holds:
\begin{enumerate}
\item[] If for all $p\in \Atoms$, for all $S\subseteq\N$ such that $S$ is a cycle in $G_{p}$, and all $i,j\in S$: $O_i(p)=O_j(p)$, then
\item[] the resistant BDP for $\O$, $\G$ and $\C$ converges in at most $k$ steps, where $k\leq max\{diam(G_p)|p\in P\}$.
\end{enumerate}
\end{theorem}
\begin{proof}
Assume that for all $p\in \Atoms$, for all $S\subseteq\N$ such that $S$ is a cycle in $G_{p}$, for all $i,j\in S$: $O_i(p)=O_j(p)$.
%Consider an arbitrary $p\in \Atoms$, and
Consider an arbitrary $i\in \N$.
%Let $k$ be the distance from $i$ to $l$, where $l$ is the closest agent in a cycle $S\subseteq\N$ of $G_p$.
Let $k_i(p)$ be the distance from $i$ to the closest agent in a cycle of $G_p$, and let $k_i$ denote $max \{k_i(p)|p\in P\}$. We show that for any $k_i\in\mathbb{N}$, $O^{k_i}_ i$ is stable.
\begin{itemize}
\item If $k_i=0$: $i$ is its only infuencer, therefore $O^0_{i}$ is stable.
\item If $k_i=n+1$: Assume that for all agents $j$ such that $k_j=n$, $O^{k_j}_ j$ is stable. This implies that all influencers of $i$ are stable. We need to consider the following cases:
\begin{enumerate}
\item If $\bigwedge_{p \in \Atoms} O^{m}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C}$ is not consistent, then it will never be: $O^{n}_i$ is stable.
\item If $\bigwedge_{p \in \Atoms} O^{m}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C}$ is consistent,
then $O^{n+1}_i$ is stable.
\end{enumerate}
\end{itemize}
\end{proof}
\begin{comment}
%%%%%THIS IS THE OLD PROOF (WITHOUT BOUND)
\begin{proof}
Assume that for all $p\in \Atoms$, for all $S\subseteq\N$ such that $S$ is a cycle in $G_{p}$, for all $i,j\in S$: $O_i(p)=O_j(p)$.
Consider an arbitrary $p\in \Atoms$, and an arbitrary $i\in \N$. Let $k$ be the distance from $i$ to $l$, where $l$ is the closest agent in a cycle $S\subseteq\N$ of $G_p$. We show that for any such $k\in\mathbb{N}$, there exists an $n \in \mathbb{N}$, such that $O^{n}_ i(p)$ is stable.
\begin{itemize}
\item If $k=0$: $i\in S$, hence $O_{i}(p)$ is stable.
\item if $k=n+1$: Assume that for agent $j$ at distance $n$ from $l$,
for some $m \in \mathbb{N}$, $O^{m}_ j(p)$ is stable. We need to consider the following cases:
\begin{enumerate}
\item If $\bigwedge_{p \in \Atoms} O^{m}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C}$ is consistent,
then $O^{m+1}_i(p)=O^m_j(p)$, and $O^{m+1}_i(p)$ is stable.
\item If $\bigwedge_{p \in \Atoms} O^{m}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C}$ is not consistent, then:
\begin{enumerate}
\item if $O^{m}_i(p)=O^m_j(p)$, then $O^{m}_i(p)$ is stable.
\item if $O^{m}_i(p) \neq O^m_j(p)$, then:
%$\O^{m+1}_i(p) = \O^{m}_i(p)$: $i$ does not change his opinion at stage $m+1$ but this does not guarantee that this won't change later on:
\begin{enumerate}
\item If there is a $t\in\mathbb{N}$ such that $\bigwedge_{p \in \Atoms} O^{m+t}_{R_p(i)}(p) \wedge \bigwedge_{\varphi \in \C}$ is consistent, then $O^{m+t+1}_i(p) = O^{m}_j(p)$, and $O^{m+t+1}_i(p)$ is stable.
\item If there is no such $t$, then $i$'s opinion on $p$ will never change: $O^{m}_i(p)$ is stable.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{itemize}
\end{proof}
\end{comment}
Can we say more about resistant BDPs? What are the necessary conditions for their stabilization? What opinions are reachable? And, in particular, when is a consensus reached?
\subsection{Other influence policies}
We can consider other types of influence policies than the one of resistant BDPs. For instance, agents may be allowed to "pass through" an inconsistent state at some point, in which case we can wonder under which conditions they can still converge to a consistent state.
We can also consider an undeterministic policy, where an agent confronted with inconsistent opinions from her influencers keeps one of the closest consistent opinions set, instead of not being influenced at all.
\section{Liquid democracy: a BDP perspective} \label{sec:liquid}
In this section we give a glimpse of how BDPs interface with the collective decision-making system known as liquid democracy, and provide an interesting angle on one of its most discussed issues: delegation cycles.
\subsection{Liquid democracy}
The natural interpretation of BDPs is in terms of processes of opinion formation (cf. \cite{Grossi_2014}) where agents' opinions are dictated by a personal `guru'.\footnote{Under a convergence assumption, they could be thought of concrete instantiations of profile-transformation functions (from the set of all opinion profiles to the set of all opinion profiles) as studied in \cite{List_2010}.} While this is obviously too constrained a model, it fits well with the sort of opinion formation process underpinning the aggregation method known as liquid democracy.
Liquid democracy\footnote{Liquid democracy is based on the software known as Liquid Feedback (\url{liquidfeedback.org}). Campaigns (e.g., Make Your Laws, \url{www.makeyourlaws.org}, US) and even parties with representatives that sat in national parliaments (e.g., Piratenpartei, Germany) are using and advocating the software.} is an aggregation method considered to stand between direct and representative democracy. At its heart is the so-called method of `proxy voting' \cite{Miller_1969,Tullock_1992}. For each issue submitted to vote, each agent can either cast its own vote, or it can delegate its vote to another agent---a proxy---and that agent can delegate in turn to yet another agent and so on. Finally, the agents that decided not to delegate their votes cast their ballots (e.g., under majority rule). But their votes now carry as weight the number of all agents that entrusted them with their vote.
Analyses of liquid democracy from a social choice-theoretic perspective have been put forth in \cite{Alger_2006} and \cite{Green_Armytage_2014}, and from an algorithmic perspective in \cite{Boldi_2011}. However, the system remains fairly underinvestigated.
\subsection{Cycles in liquid democracy}
In proxy voting agents may decide to delegate their vote to exactly one other agent, or to exercise their voting right themselves. Delegations determine therefore a graph, and it should be clear that such graph has the same properties of the influence graphs studied in the earlier sections (they are serial and functional): every agent delegates to exactly one other agent (possibly itself) who becomes the agent's trustee. So in proxy voting voters are effectively only those agents that entrusted themselves with the vote, and their vote carries as weight the cardinality of the set of all agents connected to them by a path in the delegation graph.
An equivalent narrative, often used by proponents of the liquid democracy system,\footnote{
``While one way to describe delegations is the transfer of voting weight to another person, you can alternatively think of delegations as automated copying of the ballot of a trustee.
While at assemblies with voting by a show of hands it is naturally possible to copy the vote of other people, in Liquid Democracy this becomes an intended principle'' \cite[p. 22]{liquid_feedback}.
} is that each agent's vote is actually a copy of the vote of its trustee. In this perspective, a proxy voting mechanism can be assimilated to a (converging) BDP. This perspective provides an interesting angle on the issue of delegation cycles.
Delegation cycles are seen by some as a key problem for proxy voting systems: if $a$ delegates to $b$, $b$ to $c$ and $c$ to $b$, what is the weight that a vote by any of the three agents will carry, and in general how will the opinions of these agents be counted? Proponents of liquid democracy tend to dismiss delegation cycles as a non-issue: since the three agents delegate their votes, none of them is casting a ballot and the cycles get resolved essentially by not counting the opinions of the agents involved in the cycle \cite{liquid_feedback}.\footnote{Interestingly enough we could not find reference to the problem of delegation cycles in any of the recent work in social choice theory about proxy voting (\cite{Alger_2006,Green_Armytage_2014}).}
However, this seems problematic under the `vote copying' reading of liquid democracy. In such a BDP perspective, this appears to be a drastic solution. The elimination of cycles not only hides to aggregation the opinions of the agents involved in cycles, but also the opinions of agents that may be linked to any of those agents by a delegation path. In other words information about entire connected components in the delegation graph may be lost.
Theorems \ref{theorem:opinion} and \ref{theorem:mu} offer an alternative solution by showing that not all cycles are necessarily bad news for convergence: cycles in which agents agree still support convergence of opinions, and therefore a feasible aggregation of opinions by proxy. This suggests that alternative proxy voting mechanisms could be designed to tolerate delegation cycles in which agents unanimously accept or reject a given issue, rather than simply discarding them, thereby obtaining an arguably better informed outcome of the aggregation.
\section{Conclusions and on-going work} \label{sec:conclusions}
In this work we studied a very simple class of opinion diffusion processes on networks, which we called Boolean DeGroot processes (BDPs). Interestingly these processes lie at the interface of two so far unconnected network diffusion models: the well-known DeGroot processes---of which BDPs constitute the binary special case---and of propositional opinion diffusion processes---of which BDPs constitute the special case where the set of neighbors is a singleton. We established necessary and sufficient conditions for convergence for such processes and showed how these can be captured in modal fixpoint logics. These results have also provided a novel perspective on the issue of delegation cycles in liquid democracy.
In this work we have applied BDPs to a multiple-referenda set up, modeled in a binary aggregation framework. Our goal is now to integrate such processes in a fully-fledged judgment aggregation setting \cite{Grossi_2014} studying opinion diffusion in the presence of interdependences between the issues, that is, introducing constraints into the binary aggregation framework. This a question that no existing work has addressed so far (cf. \cite{Grandi:2015:POD:2772879.2773278}) and will give rise to a variety of different dynamics depending on how issue-inconsistencies are treated by individuals.
\paragraph{Acknowledgments} Both Zo\'{e} Christoff and Davide Grossi acknowledge support for this research by EPSRC (grant EP/M015815/1, ``Foundations of Opinion Formation in Autonomous Systems'').
\paragraph{Contact information}\\
Zo\'{e} Christoff\\
Department of Computer Science\\
University of Liverpool\\
Liverpool, United Kingdom\\
\url{zoe.christoff@gmail.com}
Davide Grossi\\
Department of Computer Science\\
University of Liverpool\\
Liverpool, United Kingdom\\
\url{d.grossi@liverpool.ac.uk}
\bibliographystyle{plain}
\selectlanguage{english}
\FloatBarrier
\bibliographystyle{apacite}
\bibliography{bibliography/converted_to_latex.bib%
}
\end{document}