# On the Role of Memory in Robust Opinion Dynamics

arXiv: https://arxiv.org/abs/2302.08600 · HTML: https://mlsanity.com/paper/2302.08600/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 72 references that are in the map.
- First posted on arXiv 16 Feb 2023.

## Builds on (most cited first, 10 of 10)

- [Biased Opinion Dynamics: When the Devil Is in the Details](https://mlsanity.com/paper/2008.13589/) (2020)
- [Opinion control in complex networks](https://mlsanity.com/paper/1412.2170/) (2014)
- [Individual versus collective cognition in social insects](https://mlsanity.com/paper/1701.05080/) (2017)
- [Majority Vote in Social Networks: Make Random Friends or Be Stubborn to Overpower Elites](https://mlsanity.com/paper/2109.14265/) (2021)
- [Intermittent Inverse-Square L'evy Walks are Optimal for Finding Targets of All Sizes](https://mlsanity.com/paper/2003.13041/) (2020)
- [Asynchronous Opinion Dynamics in Social Networks](https://mlsanity.com/paper/2201.12923/) (2022)
- [Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits](https://mlsanity.com/paper/1602.04419/) (2016)
- [The ANTS problem](https://mlsanity.com/paper/1701.02555/) (2017)
- [Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions](https://mlsanity.com/paper/2005.07423/) (2020)
- [Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication](https://mlsanity.com/paper/2203.11522/) (2022)

## Abstract (arXiv)

We investigate opinion dynamics in a fully-connected system, consisting of n identical and anonymous agents, where one of the opinions (which is called correct) represents a piece of information to disseminate. In more detail, one source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal for non-source agents is to quickly agree on this correct opinion, and do that robustly, i.e., from any initial configuration. The system evolves in rounds. In each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of ℓ random agents and then updates its opinion according to some rule. We consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample. As restricted as it is, this setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules. Qualitatively speaking, we show that lack of memory prevents efficient convergence. Specifically, we prove that no dynamics can achieve correct convergence in an expected number of steps that is sub-quadratic in n, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i.e., the case ℓ=n. Conversely, we prove that the simple voter model (in which ℓ=1) correctly solves the problem, while almost matching the aforementioned lower bound. These results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may indeed require the use of memory. This insight may reflect on natural information dissemination processes that rely on a few knowledgeable individuals.