Convergence of Opinion Diffusion is PSPACE-Complete

Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini

Abstract

We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the majority of their influencers. We study the algorithmic properties of the fixed-point behaviour of such networks, showing that the problem of establishing whether individuals converge to stable opinions is PSPACE-complete.

Introduction

How do opinions evolve in a social network? This question, central to social dynamics, is often modeled using "threshold models" where individuals update their beliefs based on the opinions of their neighbors. A deceptively simple question arises: given a network and an initial set of opinions, can we predict if the system will eventually reach a stable state where no one changes their mind anymore?

This paper, presented at AAAI-20, explores the computational complexity of this problem. The researchers demonstrate that determining whether a social network will converge under a synchronous majority update protocol is PSPACE-complete. This result places the problem at the upper bound of practical computational difficulty, suggesting that predicting long-term stability is as hard as simulating a complex computer with limited memory.

The Synchronous Majority Update Model

The model considers a directed graph where each node represents an individual and edges represent influence. In a synchronous majority update, every node simultaneously observes the opinions of its influencers (those with incoming edges to the node) and adopts the opinion held by the majority. If an individual is in the minority among their influencers, they switch their opinion; otherwise, they remain unchanged.

A directed graph representing a social network (left) and an initial distribution of binary opinions (right).

While simple structures like Directed Acyclic Graphs (DAGs) are guaranteed to converge, general networks can enter infinite loops. For instance, two individuals might perpetually swap opinions if they influence each other exclusively, creating a cycle that never stabilizes.

Proving PSPACE-Completeness

To prove that the convergence problem is PSPACE-complete, the authors performed a reduction from a known PSPACE-hard problem, effectively showing that social networks can simulate a Turing machine. This implies that the network can essentially act as a computer.

Technical Innovations

  1. Dual Rail Encoding: The majority rule is self-dual (flipping all inputs flips the output), making logical negation difficult to implement directly. The authors solved this by representing each logical value using a "dual pair" of nodes.
  2. Logic Gadgets: They constructed specific graph structures or "gadgets" that function as AND, NOT, and NOP (no-operation) gates.
  3. Turing Machine Simulation: By combining these gadgets, they built a massive, intricate network that executes the step-by-step operations of a PSPACE-bounded Turing machine.
  4. The Alarm Mechanism: A "fuse line" and an "alarm" (a large clique) were designed. If the simulated machine halts or hits an invalid state, the alarm triggers, forcing the entire network to converge to a single opinion. Thus, the network converges if and only if the machine halts.
A specific configuration of opinions in a 3-node cycle, which can lead to non-convergent behavior.

Key Insights and Implications

The study reveals several profound properties of social influence:

  • Universal Computation: Even with binary opinions and a simple majority rule, social networks possess "universal" computational power.
  • No Efficient Shortcuts: The PSPACE-completeness implies that no general "shortcut" algorithm exists to predict stability. Unless P = PSPACE, one must essentially simulate the network step-by-step to find the outcome.
  • Sparse Hardness: This extreme complexity is not limited to dense networks; it emerges even in sparse graphs where each individual has as few as six influencers.

Conclusion and Future Work

This research closes a significant gap in the algorithmic analysis of threshold-based opinion diffusion. It shows that even the most basic version of the problem is at the ceiling of practical complexity.

Future research may explore:

  • Asynchronous Models: How does the loss of synchronicity (where agents update at different times) affect the nature of the convergence question?
  • Topology Subclasses: Are there specific real-world graph structures (beyond DAGs and cliques) where convergence is easier to check?
  • Fixed-Point Existence: Determining if a non-trivial fixed point (other than all-zero or all-one) exists may be an NP-complete problem.

Summary updated

Abstract

We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the majority of their influencers. We study the algorithmic properties of the fixed-point behaviour of such networks, showing that the problem of establishing whether individuals converge to stable opinions is PSPACE-complete.
BibTeX
@inproceedings{chistikov2020convergence,
  author = {Dmitry Chistikov and Grzegorz Lisowski and Mike Paterson and Paolo Turrini},
  title = {{Convergence of Opinion Diffusion is PSPACE-Complete}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=eUT7UGVRcTp},
}
Figure