Convergence of Opinion Diffusion is PSPACE-Complete

Authors

  • Dmitry Chistikov University of Warwick
  • Grzegorz Lisowski University of Warwick
  • Mike Paterson University of Warwick
  • Paolo Turrini University of Warwick

DOI:

https://doi.org/10.1609/aaai.v34i05.6197

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.

Downloads

Published

2020-04-03

How to Cite

Chistikov, D., Lisowski, G., Paterson, M., & Turrini, P. (2020). Convergence of Opinion Diffusion is PSPACE-Complete. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7103-7110. https://doi.org/10.1609/aaai.v34i05.6197

Issue

Section

AAAI Technical Track: Multiagent Systems