this is for holding javascript data
ZoƩ Christoff edited section_Unanimity_and_2_colorability__.tex
about 8 years ago
Commit id: cd8d218fc985fb542d98d00606ee6421ca0d82ad
deletions | additions
diff --git a/section_Unanimity_and_2_colorability__.tex b/section_Unanimity_and_2_colorability__.tex
index da0ddcd..7c1a4b2 100644
--- a/section_Unanimity_and_2_colorability__.tex
+++ b/section_Unanimity_and_2_colorability__.tex
...
Let $G$ be an influence profile and $\O$ be an opinion profile, such that, for some $p\in \Atoms $, for all $i,j\in\N$: if $i\in R_p(j)$, then $O_i_{p}\neq O_j{p}$. Then the UP does not converge.
\end{lemma}
Recall that a graph is properly
two-colored colored if no node has a successor of the same color. The above result can be reformulated as follows: if for some $p\in\Atoms$, $\O$ properly colors $G_p$, then $\O$ does not converge. In fact, it is easy to see that in such a case, all agents will change their opinion on $p$ at every step, entering an oscillation of size $2$. 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 this extreme distribution of opinions relies on the graph $G_p$ being $2$-colorable, which is equivalent to $G_p$ not containing any 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}
influence profiles: ones:
\begin{lemma}
Let $\G$ be a symmetric
(and (serial and non-necessarily functional) influence profile.
All opinion profiles
$\O$ $\O$, converge
in UPs on $\G$
under UP iff:
\begin{itemize}
\item[] For all $p\in\Atoms$, $G_p$ is not
$2$-colorable $2$-colorable.
\end{lemma}
\begin{proof}
Let $p\in\Atoms$ and $G_p$ be not $2$-colorable. This means that for some connected set of nodes $S\subseteq\N$ with diameter $k$ in $G_p$, there is a cycle of length $c$ for $c$ odd. Let $O$ be an arbitrary opinion profile. Since $k$ 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 $\seq k$ will be stable after at most $k$ steps. The lemma above gives the other direction.
\end{proof}
\begin{theorem}
Let $\G$ be a symmetric
(and (serial and non-necessarily functional) influence profile and $\O$ be an opinion profile.
The UP converges for $\O$ on $\G$ iff:
\begin{itemize}
\item[] For all $p\in\Atoms$, $G_p$ is not $2$-colorable, or