Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available

We consider opinion diffusion on social graphs where agents hold opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. Within this setting, we look for dynamics that allows us to maximize the diffusion of a target opinion given the initial opinions of all agents. In particular, we focus on the setting where more than two opinions are available to the agents, and we show that the properties of this setting are entirely different from those characterizing the setting where agents hold binary opinions only. Indeed, while it is well-known that greedy dynamics are always optimal ones in the binary case, this is no longer true in our more general setting and—rather surprisingly—even if just three opinions are available. Moreover, while it is possible to decide in polynomial time if a dynamics leading to consensus exists when agents have two available opinions, the problem becomes computationally intractable with three opinions, regardless of the fraction of agents that have the target opinion as their initial opinion.