Davide Grossi edited section_Convergence_label_sec_convergence__.tex  about 8 years ago

Commit id: fb2b2a4fd8cba7f969d736811327f15ffe57d456

deletions | additions      

       

\end{proof}  This trivially implies that the class of opinion profiles which guarantees convergence for {\em any} influence profile, is the one where everybody agrees on everything already.   Note that the only stable distributions of opinions are the ones where, in each connected component in $G$, all members have the same opinion, i.e, on BDPs, converging and reaching a consensus (within each connected component) are equivalent. Moreover, for an influence profile where influence graphs have at most diameter $d$ and the smallest cycle in components with diameter $d$ is of $c$, it is easy to see that if a consensus is reached, it will be reached in at most $d-c$ steps, which is at most $\N-1$. $n-1$.  Finally observe that Theorem \ref{theorem:opinion} subsumes Fact \ref{fact:influence}. If $G_p$ contains only cycles of length $1$ (second statement in Fact \ref{fact:influence}) then, trivially, no two agents in a cycle can disagree (second statement in Theorem \ref{theorem:opinion}).