Reasoning about Consensus when Opinions Diffuse through Majority Dynamics

Reasoning about Consensus when Opinions Diffuse through Majority Dynamics

Vincenzo Auletta, Diodato Ferraioli, Gianluigi Greco

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence

Opinion diffusion is studied on social graphs where agents hold binary opinions and where social pressure leads them to conform to the opinion manifested by their neighbors. Within this setting, questions related to whether a minority/majority can spread the opinion it supports to all the other agents are considered.It is shown that, no matter of the graph given at hand, there always exists a group formed by a half of the agents that can annihilate the opposite opinion. Instead, the influence power of minorities depends on certain features of the underlying graphs, which are NP-hard to be identified. Deciding whether the two opinions can coexist in some stable configuration is NP-hard, too.
Keywords:
Agent-based and Multi-agent Systems: Coordination and Cooperation
Agent-based and Multi-agent Systems: Noncooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory