Abstract
This paper investigates the stability of Nash Equilibria (NE) in large-scale network games under structural perturbations. By leveraging Random Matrix Theory, specifically the BBP phase transition, the authors demonstrate that collective behavior remains unaffected by external influences until the perturbation strength exceeds a critical threshold. Below this tipping point, the NE is mathematically "buried" in the network's noise; above it, the equilibrium aligns sharply with the perturbation.
Introduction
In massive social or economic networks, individuals (agents) make decisions based on their own interests and the actions of their neighbors. Researchers often model these interactions as "network games" to find the Nash Equilibrium (NE)—a state where no player wants to change their strategy. However, real-world networks are rarely static. They are subject to perturbations: a new marketing campaign, a policy change, or the rise of a "super-influencer." This research addresses a fundamental question: How much does a perturbation need to change the network structure before it actually shifts the collective behavior of the entire system?
Methods
The authors bridge Algorithmic Game Theory and Random Matrix Theory (RMT) through the following framework:
- Linear Quadratic (LQ) Games: The network is modeled using an LQ framework where the Nash Equilibrium corresponds to the leading eigenvector of the network's adjacency matrix.
- Random Matrix Models: Large, complex networks are represented using Wigner matrices for additive perturbations (e.g., adding connections) and Wishart matrices for multiplicative perturbations (e.g., scaling interactions).
- BBP Phase Transition: The "Baik, Ben Arous, and Péché" (BBP) transition result from RMT is applied to describe how the extreme eigenvalues and eigenvectors of a random matrix behave when a small-rank "spike" (the perturbation) is added.
The theoretical proofs are validated using numerical simulations on synthetic Wigner and Wishart ensembles with sizes up to $N=2000$.
Key Insights and Results
The most striking finding is the "invisibility" of small perturbations. If a perturbation is too weak, it is mathematically buried within the bulk spectrum of the network's natural noise. In this regime, the Nash Equilibrium remains completely uncorrelated with the perturbation.
Additive and Multiplicative Transitions
For the additive case (Wigner matrices), the perturbation only affects the NE if its strength $\theta$ exceeds the noise variance $\sigma$. As shown in Figure 3, the alignment between the perturbed and original NE stays at zero until $\theta$ hits the threshold, then rises sharply.
In the multiplicative case (Wishart matrices), the threshold is defined by the aspect ratio of the matrix. Figure 5 confirms that the NE remains independent of the perturbation until this specific value is reached.
The near-perfect overlap between numerical simulations and theoretical curves confirms that these phase transitions are robust properties of large systems.
Discussion
This research provides a rigorous mathematical framework for the "Tipping Point" concept. It explains why certain social trends or viruses stay dormant for a long time before suddenly exploding across a population. However, the current model assumes linear interactions and specific random matrix structures. Future work is needed to explore non-linear dynamics, higher-rank deformations (multiple competing influencers), and time-varying networks.
Summary updated