deletions | additions
diff --git a/untitled.tex b/untitled.tex
index aef8406..3c90599 100644
--- a/untitled.tex
+++ b/untitled.tex
...
\item $\Atoms = \set{p_1,\dots,p_m}$ is a finite set of issues, 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}$).
We denote with $\D= \{B \mid B: \I \to \{0,1\}\}$ the set of all possible assignments of truth values to the set of issues $\Atoms$ and call an element $O\in\D$ an \emph{opinion}. 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}
...
\subsection{De Groot Dynamics in Binary Aggregation}
\begin{definition}[BDPs] \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}
\item Base: $\O_0 := \O$
\item Step: for all $i \in \N$, $j\in \{1,...,m\}$, $\O_i^{n+1}(p_j) := \O^{n}_{R_j(i)}(p_j)$.
\end{itemize}
We call processes defined by the above dynamics \emph{Boolean DeGroot processes} (BDPs).
\end{definition}
It should be clear that
this the above dynamics is the extreme case of linear averaging applied on binary opinions and binary influence.
BDPs are also special 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}
...
\subsection{Some graph-theoretic preliminaries}
RELEVANT DEFINITIONS NEEDED IN CONVERGENCE THEOREMS TO BE ADDED We start with some preliminary graph-theoretic remarks about influence graphs.
First, for functional graphs, no node in a cycle can have any successor outside of the cycle. Therefore, all cycles have to be vertex-disjoint:
\begin{fact} \label{fact:vertex}
Let $G$ be an influence graph. All cycles in $G$ are vertex-disjoint.
\end{fact}
\begin{proof}
Let $G$ be an influence graph, such that it contains two cycles which are not vertex disjoint. Then there is a vertex $i$ contained in both cycles, such that $i$ has a different successor in each cycle. But since $G$ is functional, $i$ has at most one successor. Contradiction.
\end{proof}
We can also note that cycles in our influence graphs are not only vertex-disjoint, they cannot belong to the same connected component\footnote{A connected component $C$ of a graph $G = \tuple{\N, R}$ is a set of nodes $C\subseteq \N$ such that: for any $i,j\in C$, $iR^+j$, where $R^+$ is the symmetric closure of $R$.}:
\begin{fact} \label{fact:connected}
Let $G$ be an influence graph and $C$ be a finite connected component of $G$. Then $C$ contains exactly one cycle.
\end{fact}
\begin{proof}
\end{proof}
\subsection{Backgdrop: Convergence in deGroot Processes and Propositional Opinion Diffusion}
...
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 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.
\subsection{Convergence}
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$.
Let us first remark that for functional graphs, no node in So a
cycle can have any successor outside of the cycle. Therefore, all cycles have to be vertex-disjoint:
\begin{lemma}
Let $G$ be an influence graph. All cycles in $G$ are vertex-disjoint.
\end{lemma}
\begin{proof}
Let $G$ be an BDP on influence
graph, such that it contains two cycles which are not vertex disjoint. Then there is a vertex $i$ contained in both cycles, such that $i$ has a different successor in each cycle. But since $G$ graph $\G$ starting with the opinion profile $\0$ is
functional, $i$ has at most one successor. Contradiction.
\end{proof}
We can also note that cycles in our influence graphs are not only vertex-disjoint, they cannot belong said to
converge if the
same connected component\footnote{A connected component $C$ of a graph $G = \tuple{\N, R}$ is a set of nodes $C\subseteq \N$ such that: for any $i,j\in C$, $iR^+j$, stream $\O^0, \O^1, \ldots, \O^n, \ldots$ generated according to Definition \ref{def:BDP} where
$R^+$ is the symmetric closure of $R$.}:
\begin{lemma}
Let $G$ be an influence graph and $C$ be a finite connected component of $G$. Then $C$ contains exactly one cycle.
\end{lemma}
\begin{proof}
\end{proof} $\O = \O^0$ converges.
Since It must be intuitively clear that non-convergence in a BDP is linked to the existence of loops. However, from the above observations (Facts \ref{fact:vertex} and \ref{fact:connected}), we know that nodes in a cycle cannot have any
influencers guru outside this cycle, cycles (including self-loops) can only
be occur at the `tail' of the influence graph.
%be at the ``tail"(s)/root of the graph (i.e WHAT WE CALLED A SINK AND WHAT UMBERTO CALLS A
``SOURCE" %``SOURCE" GIVEN THAT THE ARROWS GO IN THE OPPOSITE DIRECTION).
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 can be 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$.
Note that this brings us back to the general result for (non-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{proposition}{} \begin{lemma}{}
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 [] 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{proposition} \end{lemma}
\begin{proof}
\ldots
\end{proof}
The above gives a characterization of the class of influence profiles on which \emph{all} opinion
profiles streams converge. But
we can also give a full characterization of convergence, i.e, we can it is also
interesting to characterize the class of opinion profiles
which converge for graphs that do \emph{not} belong on
this class: which \emph{any} influence graph would make the resulting opinion stream converge:
\begin{proposition}{} \begin{lemma}{}
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{proposition} \end{lemma}
Below is yet another way to put it: Combining the above results we obtain:
\begin{proposition}{} \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{proposition}
NOTE FOR LATER: WE CAN GIVE THE PARALLEL RESULTS FOR THE CASE OF THE UNANIMITY RULE ON (NON-NECESSARILY-FUNCTIONAL) SYMMETRIC INFLUENCE GRAPHS. WE CAN GIVE THE CLASS OF INFLUENCE PROFILES WHICH GUARANTEE CONVERGENCE OF ALL OPINIONS PROFILES, AND WE CAN GIVE THE CLASS OF OPINION PROFILES WHICH CONVERGE ON THE OTHER INFLUENCE PROFILES:
\begin{proposition}
Let $\G=(G_{p_1},\dots,G_{p_m})$ be a SYMMETRIC AND NON-NECESSARILY FUNCTIONAL influence profile and $\O=(O_1,\dots,O_n)$ be an opinion profile.
The opinion diffusion with unanimity aggregation rule converges for $\O$ on $\G$ iff:
\begin{itemize}
\item[] FOR ALL $j\in\{1,\ldots,m\}$, $G_pj$ IS NOT TWO-COLORABLE, OR
\item[] THERE IS A $j\in\{1,\ldots,m\}$, SUCH THAT $\O$ PROPERLY COLORS $G_pj$, THAT IS SUCH THAT FOR ALL $i,j\in\N$ WITH $iRj$, $O{p_i}=1$ if and only if $O{p_j}=1$.
\end{itemize}
\end{proposition} \end{theorem}
%%%%%%%%%%%%%%%%%%%%
...
\ldots
\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'').
%%%%%%%%%%%%%% NOTES %%%%%%%%%%%%%%%%%%%
---------------------------------------------
...
A model is stable if and only if the formula $p \leftrightarrow\Box p$ is a validity. That is to say $p$ is a fixpoint of $\Box p$.
- Since $\Box p$ is a positive formula (and hence $\Box$ denotes a monotonic function from sets of states to sets of states) the Knaster-Tarski fixpoint theorem applies: so we know that a smallest and largest fixpoints exist (and possibly more in-between). The smallest fixpoint is the empty-set (nothing is $p$) and the largest is the whole domain (everything is $p$).
\section{Convergence}
NOTE FOR LATER: WE CAN GIVE THE PARALLEL RESULTS FOR THE CASE OF THE UNANIMITY RULE ON (NON-NECESSARILY-FUNCTIONAL) SYMMETRIC INFLUENCE GRAPHS. WE CAN GIVE THE CLASS OF INFLUENCE PROFILES WHICH GUARANTEE CONVERGENCE OF ALL OPINIONS PROFILES, AND WE CAN GIVE THE CLASS OF OPINION PROFILES WHICH CONVERGE ON THE OTHER INFLUENCE PROFILES:
\begin{proposition}
Let $\G=(G_{p_1},\dots,G_{p_m})$ be a SYMMETRIC AND NON-NECESSARILY FUNCTIONAL influence profile and $\O=(O_1,\dots,O_n)$ be an opinion profile.
The opinion diffusion with unanimity aggregation rule converges for $\O$ on $\G$ iff:
\begin{itemize}
\item[] FOR ALL $j\in\{1,\ldots,m\}$, $G_pj$ IS NOT TWO-COLORABLE, OR
\item[] THERE IS A $j\in\{1,\ldots,m\}$, SUCH THAT $\O$ PROPERLY COLORS $G_pj$, THAT IS SUCH THAT FOR ALL $i,j\in\N$ WITH $iRj$, $O{p_i}=1$ if and only if $O{p_j}=1$.
\end{itemize}
\end{proposition}
