Reasoning about Consensus when Opinions Diffuse through Majority Dynamics

• DOI: 10.24963/ijcai.2018/7
• Publication Date: 2018-07-05T05:49:10Z
• Authors: Vincenzo Auletta; Diodato Ferraioli; Gianluigi Greco
• Keywords: Artificial Intelligence; 0102 computer and information sciences; 01 natural sciences

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