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 $\ell$ 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 $\ell=n$. Conversely, we prove that the simple voter model (in which $\ell=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.
翻译:我们在一个完全连接的系统中调查意见动态,这个系统由相同和匿名代理人组成,其中一种意见(称为正确)代表了需要传播的信息。更详细地说,一个来源代理人最初持有正确的意见,在整个执行过程中仍然持有这种意见。对于非来源代理人来说,目标是迅速就正确的意见达成一致,并强有力地这样做,即从任何初始配置中进行。在每轮中,一个随机选择的代理人被激活:除非它是来源,该代理人会引用美元随机代理人的意见,然后根据某些规则更新其意见。我们考虑一个限制性的设置,即该来源代理人没有记忆,而在整个执行过程中,他们只根据他们目前抽样的代理人的意见修改他们的意见。这个设置尽管有局限性,包含非常流行的意见动态,例如选民模型和美元中最优多数的规则。从表面上看,我们显示缺乏记忆会阻碍有效的趋同。具体地说,我们的意见无法在某个预期的步骤中实现正确的趋正一致,在这个模式下,在快速的版本中,我们无法在快速的版本中,我们使用一个快速的版本的序列中,我们也可以使用一个快速的版本。