Davide Grossi edited section_Convergence_label_sec_convergence__.tex  about 8 years ago

Commit id: ec0494587490e81eccebab792061a82dbac73e82

deletions | additions      

       

For the general case of DeGroot processes, an influence structure guarantees that any distribution of opinions will converge if and only if ``every set of nodes that is strongly connected and closed is aperiodic" \cite[p.233]{jackson08social}.  In the propositional opinion diffusion setting, sufficient conditions for stabilization have been given by \cite[Th. 2]{Grandi:2015:POD:2772879.2773278}: on influence structures containing cycles of size at most one (i.e, only self-loops), for agents using an aggregation function satisfying ballot-monotonicity, (ballot-)monotonicity,\footnote{Notice that the rule underpinning BDP, that is the `guru-copying' rule on serial and functional graphs, trivially satisfies monotonicity.}  opinions will always converge in at most at most $k+1$ steps, where $k$ is the diameter of the graph.\footnote{A second convergence sufficient condition is given by \cite{Grandi:2015:POD:2772879.2773278}: when agents use the unanimity aggregation rule, on irreflexive graphs with only vertex-disjoint cycles, such that for each cycle there exists an agent who has at least two influencers, opinions converge after at most $\N$ steps. Note that no BDP can satisfy this second condition.} \subsubsection{Terminology}