Network games with three types of players

Technical Summary: Network Games with Three Types of Players

Problem Statement
This paper investigates the existence and structure of Pure Strategy Nash Equilibria (PNE) in multi-strategy network games featuring three distinct behavioral types: conformists, rebels, and stubborn agents. While existing literature extensively studies games of strategic complements (conformists) and strategic substitutes (rebels) separately, or in binary-choice settings with two player types, there is a lack of systematic analysis for networks where these three types coexist with multiple strategies ($m$-strategies). The authors refer to this framework as a CRS game. The core problem is to determine under what network topologies and player compositions a stable equilibrium exists, and how the interplay between coordination incentives (conformists), anti-coordination incentives (rebels), and fixed behaviors (stubborn agents) shapes these outcomes.

Methodology
The authors employ a game-theoretic approach grounded in potential game theory and combinatorial analysis.

1. Model Formulation: The game is defined on a fixed undirected network $G=(N, E)$ with $m$ strategies. Payoffs are defined such that conformists maximize the number of neighbors sharing their strategy, rebels maximize the number of neighbors with different strategies, and stubborn agents have fixed strategies with zero payoff sensitivity to changes.
2. Potential Game Analysis: The authors utilize the concept of exact potential games to establish existence results. They demonstrate that sub-games involving only conformists and stubborn agents (CS) or rebels and stubborn agents (RS) are exact potential games, guaranteeing PNE existence in isolation.
3. Local Obstruction Identification: To address non-existence, the authors identify a specific local configuration (denoted $M^*$) involving a conformist-rebel pair surrounded by uniformly distributed stubborn agents. They prove that the presence of this structure precludes any PNE.
4. Probabilistic Analysis: Using the identified local obstruction, the authors apply probabilistic methods to analyze large random networks (e.g., Erdős–Rényi), showing that the probability of such obstructions existing approaches one as network size increases.
5. Structural Characterization: For specific network architectures (complete networks, lines, rings, trees, and stars), the authors derive necessary and sufficient conditions for PNE existence by analyzing strategy frequencies and neighbor constraints.

Key Contributions and Results

• General Network Existence Conditions:

  • The paper establishes two sufficient conditions for PNE existence on arbitrary networks: (i) the absence of conformist-rebel (CR) edges, or (ii) the existence of a specific strategy such that every conformist has at least half of their neighbors in the set of conformists and stubborn agents playing that strategy.
  • Non-existence in Random Networks: The authors prove that in large random networks with broad degree distributions (including Poisson, scale-free, and exponential), a PNE almost surely fails to exist. This is driven by the high probability of the "local obstruction" ($M^*$) emerging as the network grows, creating unavoidable local conflicts between conformist and rebel incentives.

• Specific Network Architectures:

  • Complete Networks: The authors fully characterize the equilibrium structure. Conformists coordinate on the strictly most common strategy, while rebels distribute themselves as evenly as possible across strategies. Necessary and sufficient conditions are derived based on the counts of stubborn agents and conformists relative to the number of strategies.
  • Lines and Rings: For $m \ge 3$, a PNE exists if and only if every conformist has at least one neighbor who is either a conformist or a stubborn agent. If a conformist is surrounded solely by rebels (e.g., an R-C-R pattern on a ring), no equilibrium exists.
  • Trees: When the number of strategies exceeds the maximum degree of the tree ($m > \Delta$), the same condition as lines/rings applies: every conformist must have a neighbor in $C \cup S$. The paper notes that when $m \le \Delta$, the problem is more complex and may lack a PNE even if the neighbor condition is met.
  • Stars: The authors provide a sharper characterization for star networks. Existence depends on the type of the central player and the composition of the leaf nodes. Specifically, if the center is a conformist, the number of rebel leaves must be small enough to be "absorbed" by the strategy choices of the center and conformist leaves without creating a more popular alternative strategy.

Significance and Claims
The paper claims to provide a unified perspective on how network topology and the distribution of behavioral types jointly determine equilibrium outcomes. The central insight is that PNE is likely to exist when conformists have sufficient local support (neighbors who are conformists or stubborn agents) to coordinate, but fails when the network contains numerous conformist-rebel edges that generate incompatible incentives.

The authors position this work as a systematic framework for studying coordination and conflict in heterogeneous populations with multiple strategies. They acknowledge that while their analysis assumes symmetric treatment of strategies, the core potential game results extend to cases with strategy-specific weights. However, they note that generalizing the non-existence results and specific structural characterizations to these weighted variants requires further analysis. Additionally, the paper leaves the question of equilibrium uniqueness open, suggesting future research could link uniqueness to the spectral properties of the network matrix.

Conclusion
This study bridges a gap in network game theory by integrating three behavioral types and multiple strategies. It demonstrates that while equilibrium can be sustained in structured networks with specific topological constraints, the heterogeneity of behavioral types in large, random networks creates a fundamental instability that almost certainly prevents the formation of a pure strategy Nash equilibrium.