Local Non-Bayesian Social Learning With Stubborn Agents

Daniel Vial, Vijay G. Subramanian

TL;DR

This paper introduces a model of social learning where agents learn from noisy signals and their peers, but some "stubborn agents" (bots) intentionally spread misinformation. The key finding is that the learning outcome (whether agents learn the truth or are misled) critically depends on the interplay between the "learning horizon" (how long agents learn) and the "density" of bots. This suggests that even if agents initially learn the truth, they can later "forget" it and adopt the bots' misinformation over time.

What Problem Does This Paper Address?

The paper addresses the challenge of understanding how individuals learn and form beliefs in online social networks, particularly in the context of "fake news." Traditional models of social learning often assume agents are rational and aim to learn the true state of the world. However, platforms like Twitter and Facebook are rife with misinformation, often spread by bots or users with malicious intent. These "stubborn agents" don't aim to learn but rather to persuade others of an incorrect state. The paper aims to model this dynamic, exploring how the presence of these misleading agents affects collective learning over time, and how the duration of the learning process (the "learning horizon") interacts with the prevalence of these agents.

Methods

The authors develop a non-Bayesian social learning model where agents update their beliefs based on private signals and the beliefs of a subset of their neighbors. A crucial element is the introduction of "stubborn agents" or "bots" who aim to spread an erroneous state. The core of their analysis involves studying the convergence of agent beliefs under different conditions. They employ mathematical tools like probability theory, random walks on graphs, and concentration inequalities. A key theoretical contribution is Theorem 1, which establishes a "phase transition" in learning outcomes based on the product of the learning horizon and a measure of bot prevalence. They also develop an adversarial setting where an adversary strategically places bots to disrupt learning, proposing both an exact and an approximate algorithm for this problem.

Datasets

The paper uses four real-world social network datasets for empirical evaluation: Gnutella, Wiki-Vote, Pokec, and LiveJournal. These datasets represent networks of varying scales, allowing the authors to test their algorithms on both smaller networks where exact solutions are feasible and larger networks that better resemble platforms like Twitter.

Key Insights and Ideas

  • The "Forgetting" Phenomenon: Agents can initially learn the true state of the world but, over longer learning horizons and with sufficient bot influence, can "forget" the truth and adopt the erroneous state promoted by bots. This highlights a vulnerability in social learning where prolonged exposure to misinformation can override initial learning.
  • Horizon vs. Bot Density is Crucial: The outcome of learning is not solely determined by the number of bots or the learning time, but critically by their interplay. A specific product of the learning horizon and the bot density dictates whether agents learn, are misled, or end up with an intermediate belief.
  • Local Learning Vulnerabilities: The paper suggests that even if agents learn "locally" (i.e., their beliefs are primarily influenced by their immediate network), this local learning can be disrupted. The adversarial setting shows that strategically placed bots can be more effective than simple heuristics, even outperforming methods that consider global network topology like PageRank.
  • Balancing Influence and Susceptibility: The adversarial algorithm's success in disrupting learning stems from its ability to balance influence (e.g., users with many followers) and susceptibility (e.g., users with few followers), suggesting a nuanced strategy for spreading misinformation.

Key Results

  • Theorem 1: Establishes three distinct learning outcomes (convergence to the true state, convergence to the erroneous state, or an intermediate state) based on the asymptotic behavior of the learning horizon ($T_n$) and bot density ($p_n$). Specifically, if $T_n(1-p_n) \to 0$, agents learn the truth; if $T_n(1-p_n) \to \infty$, agents adopt the bot's erroneous state; and if $T_n(1-p_n) \to c \in (0, \infty)$, agents converge to an intermediate belief.
  • Adversarial Algorithm: The paper proposes a randomized approximation algorithm for strategically placing bots that achieves a (2+δ)-approximation to the optimal solution with high probability. This algorithm is computationally efficient (O(n log n + b_n)) and empirically outperforms naive baselines and heuristics.
  • Empirical Validation: Experiments on real-world social networks demonstrate that the proposed adversarial strategy effectively disrupts learning, leading to lower agent estimates (closer to the erroneous state) compared to other methods. The empirical results also show a strong correlation between the adversary's objective function (minimizing bot density) and the actual agent beliefs, supporting the model's assumptions.

Limitations and Future Work

  • Model Assumptions: The model relies on specific assumptions about agent behavior (non-Bayesian updates) and network structure (e.g., the Directed Configuration Model for theoretical analysis). The authors acknowledge that extending the results to more general settings or different agent update rules might be challenging.
  • Generalizability of Adversarial Strategy: While the adversarial algorithm is shown to be effective, its theoretical guarantees are primarily derived for the random graph model. The paper empirically suggests its effectiveness on real-world networks, but further theoretical work might be needed to confirm this for arbitrary graph structures.
  • "Forgetting" Mechanism: The paper highlights that agents can "forget" the truth. Future work could explore the precise cognitive or social mechanisms behind this forgetting phenomenon in online environments.
  • Extension of Theorem 3: The paper notes that extending Theorem 3 (regarding the proportion of agents whose beliefs converge) to all cases of $p_n$ requires a specific condition (24) that is not universally met. Proving this condition or finding alternative approaches for those cases is an open problem.

Summary updated

Abstract

In this article, we study a social learning model in which agents iteratively update their beliefs about the true state of the world using private signals and the beliefs of other agents in a non-Bayesian manner. Some agents are stubborn, meaning they attempt to convince others of an erroneous true state (modeling fake news). We show that while agents learn the true state on short timescales, they “forget” it and believe the erroneous state to be true on longer timescales. Using these results, we devise strategies for seeding stubborn agents so as to disrupt learning, which outperforms intuitive heuristics and gives novel insights regarding vulnerabilities in social learning.
BibTeX
@inproceedings{vial2019local,
  author = {Daniel Vial and Vijay G. Subramanian},
  title = {{Local Non-Bayesian Social Learning With Stubborn Agents}},
  booktitle = {EC},
  year = {2019},
  doi = {10.1145/3328526.3329572},
}
Figure