Majority dynamics and the retention of information (Q2339621)

This paper studies majority dynamics, where agents update their opinions to match that of the majority of their neighbors. Each agent in a social network in question carries one of two possible opinions regarding a certain issue. The focus of this paper is on determining whether information is lost during the process of majority dynamics, or is it still possible to reconstruct the correct opinion after many rounds of updates. Combinatorial results are developed on majority dynamics on both finite and infinite graphs in this paper. It is shown for every odd degree lattice of polynomial growth, that there exists a constant \(c\) such that, regardless of the starting opinion configuration, with probability one one site changes its state more than \(c\) times. Moreover, a rigorous proof is given for the following intuition: If a sufficiently large neighborhood of an agent starts with a certain opinion, then she will always have this opinion.