Reasoning about Consensus when Opinions Diffuse through Majority Dynamics

Vincenzo Auletta, Diodato Ferraioli, Gianluigi GrecoIJCAI 2018 · DOI

TL;DR

This paper investigates how opinions spread in social networks where individuals adopt the majority opinion of their neighbors. The authors prove that a majority of just over half the agents can always enforce their opinion, and they provide an algorithm to find such a configuration. However, they also show that it's NP-hard to determine if a minority can achieve consensus or if a network can have multiple stable opinions.

What Problem Does This Paper Address?

Imagine a group of people deciding on something, like where to go for dinner. Each person has an initial preference, and they influence each other. This paper models this scenario using a social network (a graph) where agents (people) have binary opinions (e.g., restaurant vs. pizzeria). The core question is: how do opinions spread, and can a consensus be reached? Specifically, the authors explore:

  • Majority Power: Can a group with a certain fraction of opinions always lead to a consensus on their opinion, regardless of the network structure?
  • Minority Influence: Can a minority opinion spread and become dominant? What are the conditions for this?
  • Stability: Can a network settle into multiple stable states where no single agent wants to change their opinion, even if it's not a complete consensus?

Existing work had hinted that large majorities are powerful in "expander graphs," but this paper provides a comprehensive analysis for any social graph and explores the computational complexity of these questions.

Methods

The paper tackles these questions using tools from computational complexity and algorithm design.

  • Majority Consensus Algorithm: The central algorithmic contribution is a polynomial-time algorithm that, given any graph, finds an initial configuration where a majority (specifically, at least half) of agents hold one opinion, and this opinion will eventually spread to everyone. This algorithm is constructive and relies on identifying and manipulating "nice" partitions of the agent set.
  • "Nice" Partitions: The algorithm iteratively transforms an initial balanced partition into one of three types of "nice" partitions (P1, P2, or P3). These partitions have specific structural properties that guarantee consensus can be reached.
  • Pivotal and Critical Agents: The transformation process involves identifying and removing "pivotal" agents (who obstruct the formation of nice partitions) and "critical" agents (who represent further obstructions). This is done through a series of carefully defined swap and removal operations (REMOVEC1, REMOVEC2) that maintain balance and progress towards a nice partition.
  • Complexity Analysis: The paper uses reductions from known NP-hard problems (like Vertex Cover and 2P3N-3SAT) to prove that determining minority influence and identifying "plural" stable configurations are computationally intractable (NP-hard).

Datasets

Not discussed in the paper. The analysis is theoretical and based on graph structures.

Key Insights and Ideas

  • Overwhelming Power of the Majority: The most striking result is that a group holding just over half the opinions can always enforce their opinion on the entire network, regardless of the network's structure. This is a strong theoretical guarantee and somewhat counter-intuitive, as one might expect network topology to play a larger role.
  • NP-Hardness of Minority Influence: While a majority is always powerful, a minority's ability to spread its opinion is highly dependent on the specific network structure, and determining this is computationally hard. This suggests that influencing a network with a minority opinion is a challenging task.
  • Plurality is Hard to Detect: Identifying networks that can settle into multiple stable states (not just complete consensus) is also NP-hard. This implies that predicting all possible outcomes of opinion dynamics can be computationally difficult.
  • Algorithmic Construction for Majority: The paper doesn't just prove the existence of a majority-driven consensus; it provides a concrete algorithm to find the initial configuration that guarantees it. This has practical implications for understanding how to steer opinion in a network.

Key Results

  • Theorem 1: For any graph, there exists an initial configuration with at least half the agents holding opinion 1, from which consensus on opinion 1 is reached. This configuration can be computed in polynomial time.
  • Theorem 2: For any fraction $a < 1/2$, the problem of deciding if consensus on opinion 1 can be reached from a configuration where at most a fraction $a$ of agents hold opinion 1 is NP-hard.
  • Theorem 3: It is NP-hard to decide if there's a configuration where a minority opinion spreads to a specific, limited fraction of agents.
  • Theorem 4: Deciding whether a graph admits stable configurations other than complete consensus (i.e., is "plural") is NP-complete.

Limitations and Future Work

  • Special Graph Classes: The authors acknowledge that identifying special classes of graphs where these questions are easier to answer is an interesting avenue for future research.
  • Practical Implications: While the paper provides theoretical results, further work could explore the practical implications of the majority consensus algorithm for real-world social network manipulation or intervention.
  • Asynchronous Model: The study focuses on an asynchronous model where one agent changes opinion at a time. Exploring synchronous models or other diffusion dynamics could be a future direction.

Summary updated

BibTeX
@inproceedings{auletta2018reasoning,
  author = {Vincenzo Auletta and Diodato Ferraioli and Gianluigi Greco},
  title = {{Reasoning about Consensus when Opinions Diffuse through Majority Dynamics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/7},
}
Figure