Maximizing the Spread of an Opinion in Few Steps: Opinion Diffusion in Non-Binary Networks

Maximizing the Spread of an Opinion in Few Steps: Opinion Diffusion in Non-Binary Networks

Robert Bredereck, Lilian Jacobs, Leon Kellerhals

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1622-1628. https://doi.org/10.24963/ijcai.2020/225

We consider the setting of asynchronous opinion diffusion with majority threshold: given a social network with each agent assigned to one opinion, an agent will update its opinion if more than half of its neighbors agree on a different opinion. The stabilized final outcome highly depends on the sequence in which agents update their opinion. We are interested in optimistic sequences---sequences that maximize the spread of a chosen opinion. We complement known results for two opinions where optimistic sequences can be computed in time and length linear in the number of agents. We analyze upper and lower bounds on the length of optimistic sequences, showing quadratic bounds in the general and linear bounds in the acyclic case. Moreover, we show that in networks with more than two opinions determining a spread-maximizing sequence becomes intractable; surprisingly, already with three opinions the intractability results hold in highly restricted cases, e.g., when each agent has at most three neighbors, when looking for a short sequence, or when we aim for approximate solutions.
Keywords:
Knowledge Representation and Reasoning: Knowledge Representation and Game Theory; Social Choice
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice