deletions | additions       diff --git a/section_Convergence_When_do_the__.tex b/section_Convergence_When_do_the__.tex  index 7db922c..5f90677 100644  --- a/section_Convergence_When_do_the__.tex  +++ b/section_Convergence_When_do_the__.tex 
...
When do the opinions of a group of individuals influencing each other stabilize? Conditions have been given, in the literature, for the general paradigms which our BDPs are limit cases of. In this section, we give 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 $$, 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 $$ between them.   The \emph{diameter} of a graph is the maximal distance between any two of its nodes.  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{connected} if for any $i,j \in \S$: $iR^*j$,   \item[]\emph{strongly connected} if for any $i,j \in \S$: $iRj$,   \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 this cycle forms a closed set.   \end{fact}  \begin{proof}  Assume that $C$ does not contain any cycle. Since $\N$ is finite path do not repeat any node, any path in $C$ is finite. Let $i$ be the last element of the longuest path 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 node 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.  Assume that $C$ contains more than one cycle. Since each cycle forms a closed set, there is no path connecting any node inside the cycle to any node outside the cycle, which contradicts connectedness. So $C$ contains a unique cycle, which forms a closed set.   \end{proof}  This means that influence graphs will look like confluent chains aiming together towards cyclical tails.   \subsection{Convergence of BDPs}  Let us 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 $\O^n = \O^{n+1}$. Such limit profile, when it exists, is denoted $\O^\star$. We will also say that a stream of opinion profiles converges {\em for issue} $p$ if there exists $n \in \mathbb{N}$ such that $\O^n(p) = \O^{n+1}(p)$.  Given a stream of opinion profiles starting at $\O$ we say that agent $i \in \N$ stabilizes in that stream for issue $p$ there exists $n \in \mathbb{N}$ such that $\O^n_i(p) = \O^{n+1}_i(p)$.  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 of the BDP.    %Finally, given an opinion profile $\O$ we say that agent $i \in \N$ stabilizes for issue $p$ (from $\O$) if in the BDP stream starting at $\O$ there exists a stage $n$ such that $\O^n_i(p) = \O^{n+1}_i(p)$.   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   (\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{lemma}\label{lemma:influence}  Let $\G=(G_{p_1},\dots,G_{p_m})$ be an influence profile. Then the following are equivalent:  \begin{itemize}  \item[] The BDP converges for any opinion profile $\O$ on $\G$   %\item[] The BDP converges for any opinion profile $\O$ on $\G$ in at most $k$ steps, where $k$ is the maximum in the set of diameters of $G_{p_j} for all $j\in \{1,\ldots,m\}$.  \item[] For all $j\in \{1,\ldots,m\}$, $G_{p_j}$ contains no cycle of length $\geq 2$.  \item[] For all $j\in \{1,\ldots,m\}$, all closed connected components of $G_{p_j}$ are aperiodic.  \end{itemize}  \end{lemma}  \begin{proof}  Let $j\in\{1,\dots,m\}$ and assume that $G_{p_j}$ contains no cycle of length $\geq 2$ and has diameter $k$. Let $C_{p_j}$ be a connected component of $G_{p_j}$. By \ref{fact:uniquecycle}, $C_{p_j}$ contains a unique cycle, which, by assumption, is of length $1$. Hence, $C_{p_j}$ is aperiodic. Let $i$ be the node in the cycle. The opinion of $i$ will spread to all nodes in $C_{p_j}$ 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_j}$ for all $j\in \{1,\ldots,m\}$.  Assume that for some $j\in\{1,\dots,m\}$, a connected component $C_{p_j}$ of $G_{p_j}$ 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_j}$ is $k$, so $C_{p_j}$ 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$, $O_i{p_j}\neq O_j{p_j}$. Then $O_i{p_j}$ will not converge, but enter a loop of size $k$: for all $x\in\mathbb{N}$, $O^{x\times k}_i{p_j}=\neq O^{(x\times k)+d}_i{p_j}$.   \end{proof}  The above gives a characterization of the class of influence profiles on which \emph{all} opinion streams converge.   But it is also interesting to characterize the class of opinion profiles on which \emph{any} influence graph would make the resulting opinion stream converge:  \begin{lemma}\label{lemma:opinion}  Let $\G=(G_{p_1},\dots,G_{p_m})$ be an influence profile and $\O=(O_1,\dots,O_n)$ be an opinion profile. Then the following are equivalent:  \begin{itemize}  \item[] The BDP converges for $\O$ on $\G$.  \item[] For all $l\in \{1,\ldots,m\}$, there is no set of agents $C\subseteq\N$ such that: $C$ is a cycle in $G_{p_l}$ and there are two agents $i,j\in C$ such that $O_i(p_l)\neq O_j(p_l)$.  \end{itemize}  \end{lemma}  Combining the above results we obtain:  \begin{theorem}{}  Let $\G=(G_{p_1},\dots,G_{p_m})$ be an influence profile and $\O=(O_1,\dots,O_n)$ be an opinion profile. The BDP converges for $\O$ on $\G$ if and only if:  \begin{itemize}  \item[] For all $j\in \{1,\ldots,m\}$, $G_{p_j}$ contains no cycle of length $\geq 2$, or  \item[] For some $l\in \{1,\ldots,m\}$, there is a set of agents $C\subseteq\N$ such that: $C$ is a cycle in $G_{p_l}$ and there are two agents $i,j\in C$ such that $O_i(p_l)\neq O_j(p_l)$.  \end{itemize}  \end{theorem}  \begin{proof}  Direct consequence of Lemmas \ref{lemma:influence} and \ref{lemma:opinion}  \end{proof}  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  \subsection{Backgdrop: Convergence in deGroot Processes and Propositional Opinion Diffusion}  Convergence results have been given both for DeGroot processes \cite{Golub_2010} and for propositional opinion diffusion for specific aggregation procedures \cite{Grandi:2015:POD:2772879.2773278}. Let us briefly recall those results.   In the case of DeGroot processes, a graph guarantees that any distribution of opinion will converge if and only if ''every set of nodes that is strongly connected and closed is aperiodic" (Jackson, p.233).  %\footnote{A set of nodes is said to be ``strongly connected" if there is a directed path from any node to any other node in the set, ``closed" if there is no link from nodes in the set to nodes outside the set, and aperiodic if the greatest common divisor of all directed cycles is $1$}   %This result applies of course to our limit cases, the BDGs.   In propositional opinion diffusion setting, two main results give sufficient conditions for stabilization.   First, on graphs containing cycles of size at most one (i.e, only self-loops), for agents using any aggregation function satisfying ballot-monotonicity, opinions will always converge in at most at most $k+1$ steps, where $k$ is the diameter of the graph.   (THIS IS THM 2 IN THE PAPER. NOTE THAT THE PROPERTY OF ALLOWING ONLY CYCLES OF LENGTH 1 GUARANTEES THAT THE GRAPH IS APERIODIC, ALREADY MEETING DEGROOT'S CONDITION FOR STABILIZATION.)  Second, graphs which contain no cycle of length one and only vertex-disjoint cycles, such that for each cycle there exists an agent who has at least two influencers, when agents aggregate using the unanimity rule, opinions converge after at most $\N$ steps.   (THIS IS THM 6 IN THEIR PAPER, AND I AM STILL UNSURE WHY IT EXCLUDES SELF-LOOPS. WE CANNOT USE THIS RESULT, BECAUSE IT INVOLVES NODES HAVING TWO INFLUENCERS, WHICH WE EXCLUDE ANYWAY BY FUNCTIONALITY.)  What do these results correspond to when applied to our ``follow your guru" policy, that is, when imposing functionality and seriality on graphs and focusing solely on the unanimity rule? They imply the following: if, for all $i\in\{1,\ldots,m\}$, the influence graph $\G_i$ contains only cycles of length $1$, then all opinions profiles on $\G$ converge. Note that this follows directly both from the DeGroot convergence result stated earlier (since graphs with only cycles of length one are trivially aperiodic) and from the propositional opinion diffusion theorem above (since the unanimity rule is trivially monotonic). This illustrates how the BDPs are limit cases both of the opinion diffusion and of the DeGroot stochastic opinion diffusion.