this is for holding javascript data
ZoƩ Christoff edited section_Unanimity_and_2_colorability__.tex
about 8 years ago
Commit id: 2d5e974e4cf65d8bfc6fe4c71d720aa83132cf06
deletions | additions
diff --git a/section_Unanimity_and_2_colorability__.tex b/section_Unanimity_and_2_colorability__.tex
index 6447db8..e14889a 100644
--- a/section_Unanimity_and_2_colorability__.tex
+++ b/section_Unanimity_and_2_colorability__.tex
...
\end{definition}
We give a sufficient condition for non-convergence of UP:
\begin{lemma} \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}
...
The possibility of such a distribution of opinions on $p$ relies on the graph $G_p$ being $2$-colorable, which is again a requirement about the length of cycles, since a graph 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:influenceUP} \begin{lemma}\label{lemma:symm.opinionUP}
Let $\G$ be a symmetric (serial and non-necessarily functional) influence profile and $\O$ be an opinion profile. $\O$ converges in UP on $\G$ if and only if:
\begin{itemize}
\item[] 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)$.
\end{lemma}
\begin{proof}
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. The above \ref{lemma:suff.UP} provides the other direction.
\end{proof}
\begin{lemma}\label{lemma:symm.influenceUP}
Let $\G$ be a symmetric (serial and non-necessarily functional) influence profile.
All opinion profiles $\O$, converge in UPs on $\G$ iff:
\begin{itemize}
...
\end{itemize}
\end{theorem}
\begin{proof}
This follows from
\ref{lemma:influenceUP} \ref{lemma:symm.influenceUP} and
\end{proof}