ZoĆ© Christoff edited section_2_colorability_and_unanimity__.tex  about 8 years ago

Commit id: 7f093e6e87a66abb5cf13d042433bc14168e0bdf

deletions | additions      

       

\end{theorem}  \subsection{modal logic and $2$-colorability} $2$-colorings}  \begin{lemma}  Let $M=<\N,\G,\O>$ be an influence model, such that $\G$ is symmetric (and non-necessarily functional). For any $\i\in\N$, any $p\in\Atoms$, $O_i(p)$ is not stable iff:  \begin{itemize}  \item[] $M,i\models (p\land \Box \lnot p) \lor (\lnot p \land \Box p)  %\item[] $M,i\models \lnot U((p\land \Box \lnot p) \lor (\lnot p \land \Box p))For all $p\in\Atoms$, $G_p$ is not $2$-colorable, or \item[] There is a $p\in\Atoms$, such that: for all $i,j\in\N$ if $j\in R_p(i)$, $O_i(p)\neq O_j(p)$.  \end{itemize}  \end{lemma}  A formula of the basic modal language characterizes the influence profiles which guarantee convergence for any opinion profile under the unanimity rule:  \begin{lemma}  Let $G$ be a symmetric (and non-necessarily functional) influence profile. $G$ makes all $\O$ converge under UP if and only if:  \begin{itemize}  \item[] $<\N,\G>\models \bigvee_{p\in\Atoms}(\lnot U((p\land \Box \lnot p) \lor (\lnot p \land \Box p)))$.  %\item[] $M,i\models \lnot U((p\land \Box \lnot p) \lor (\lnot p \land \Box p))For all $p\in\Atoms$, $G_p$ is not $2$-colorable, or \item[] There is a $p\in\Atoms$, such that: for all $i,j\in\N$ if $j\in R_p(i)$, $O_i(p)\neq O_j(p)$.  \end{itemize}  \begin{lemma}  Let $M=<\N,\G,\O>$ be an influence model, such that $\G$ is symmetric (and non-necessarily functional).  $O_i(p)$ converges iff:  \begin{itemize}  \item[] $<\N,\G>\models \lnot U((p\land \Box \lnot p) \lor (\lnot p \land \Box p))  \item[] $M,i\models \lnot U((p\land \Box \lnot p) \lor (\lnot p \land \Box p))For all $p\in\Atoms$, $G_p$ is not $2$-colorable, or \item[] There is a $p\in\Atoms$, such that: for all $i,j\in\N$ if $j\in R_p(i)$, $O_i(p)\neq O_j(p)$.  \end{itemize}  \end{lemma}  \subsection{backdrop on stability and colorability}  %%%%%%%%%%%%%%%%%%%%%%%%BELOW THIS POINT IS ONLY OLDER STUFF%%%%%%%%%%%%%%