A Phase Transition in Large Network Games

The ever increasing interactions between people in the world has motivated the analysis of network data in a range of disciplines and applications, appearing in such diverse areas as commerce, sociology, epidemiology, computer science, and national security. Network data is characterized by the edges between nodes and edge weights,through an adjacency matrix, wherein the action of individual player is affected by the actions of its neighbors. These actions not only affect the individuals but also the overall society. These outcomes can be modeled and studied through the framework of network games, focusing on understanding the effect of properties of network on Nash equilibria (NE). The authors in (Parise and Ozdaglar, 2017) and (Jackson and Zenou, 2015) study the properties of Nash equilibrium in different types of network games and how these are impacted by network structure.

A majority of real-world networks are large networks, with numerous players and interactions. Many random matrix models have been created that incorporate features of real-world systems, such as, network composition, flexibility, and recurrent motifs (Newman, 2018; Jackson, 2010). These network models appear in the study of complex systems, such as social networks, economic markets, signal processing and natural ecosystems. Characterizing the conditions on such networks for Nash equilibrium, even approximately, helps in understanding the results when players play selfishly. For large network games, we assume that the adjacency matrix is a random matrix, generated through a given distribution.

In statistical physics, the Ising model on large random graphs helps to study the phase transition phenomenon observed in the real world. It is shown in (Landau, 1976; Stanley, 1999), that the critical point behavior occurs for ferromagnetic interactions, where the magnetization vanishes as the continuously increasing temperature crosses a certain threshold. The phase transition between water and steam is an example of a phase transition occurring at a critical, or Curie temperature. This transition can be modeled with the Ising model, where the nodes are points in space, and the presence or absence of a molecule is generated randomly, like spins. Thus the magnetism corresponds to the density of the H₂O. At a hundred degrees Celsius, the density changes substantially; a phase transition. The author Malcolm Gladwell in (Gladwell, 2002) argues that there exist similar ‘tipping points’ in the society that are critical moments when a minor change makes all the difference. Tipping points are derived from ideas in epidemiology, the study of the spread of viruses and other diseases. The example of a simplified flu epidemic, as provided by Gladwell, describes how the start of Christmas season is a tipping point which leads to exponential increase in transmission rate due to such a simple cause as crowded Christmas shopping and cold weather. The theory of epidemic transmission is applicable to many ideas, products, messages, and behaviors we find in society can be characterized by their rapid, exponential spread through our population. The resurgence of brands like Hush Puppies and viral growth of new ones like Airwalk is contributed to early adoption and focus of marketing on influencers in the social network which the book calls as connectors, mavens, and salesmen. Through our paper, we try to use a game theoretic notion to mathematically study how tiny shift across the threshold can create huge effects by propagating the cause throughout the network.

In this paper, we explore a phase transition phenomenon seen in large random matrices in the context of a network game, and observe how the Nash Equilibrium of a game changes on varying a certain parameter. The authors in (Benaych-Georges and Nadakuditi, 2009) have studied the extreme eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. A phase transition phenomenon occurs whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Our results focus on the ‘spiked’ random matrix models with Wigner and Wishart random ensemble for additive and multiplicative perturbations respectively. The key to applying the Baik, Ben Arous and Peche - BBP phase transition results from (Baik et al., 2004) lies in being able to compute the Cauchy or T transforms of the probability measure and their associated functional inverses. We use results on Wigner studied in (Bassler et al., 2008; Capitaine et al., 2009; Féral and Péché, 2007; Hoyle and Rattray, 2007) and Wishart studied in (Baik et al., 2004; Baik and Silverstein, 2006; Karoui, 2005; Nadler, 2008) random ensemble where the transforms and their inverses can be expressed in closed form. Through previous work in (Parise and Ozdaglar, 2017; Bramoullé et al., 2016; Naghizadeh and Liu, 2017) on how network structure affects the properties of Nash Equilibrium, we know that largest eigenvalue/eigenvector of the adjacency matrix plays a major role in determining the conditions of various properties of Nash Equilibrium of Linear Quadratic (LQ) network games. In this paper, we analyse perturbations to the adjacency matrix of large network games, focusing on how the changes to structure of network leads to a phase transition phenomenon of the NE of the perturbed network, due to its dependence on the extreme eigenvalue/eigenvector. To the best of our knowledge this is the first paper that makes a connection between random matrix theory and network games to show a phase transition in large social networks.

The application of such property can be experienced in different domains. The social media enables the communication among people, and promotes several group activities in the society. Based on data from platforms like Facebook, Twitter, etc., some users like celebrities, athletes, or politicians have significantly more followers than the rest. In a network graph terms, these users are the nodes that have much more influence than the rest of nodes. These social media influencers have a loyal follower base, achieving a high level of engagement on their content, such as images, trends, videos, etc., heightening their power of persuasion. Using our analysis, we can see that by introducing a perturbation through a ’teleportation’ term into the adjacency matrix of a random network over a critical threshold, the beliefs of the participants in the network can depend on properties of the perturbation strength. This change in beliefs can lead to adoption of new technology or products through changing the influence of neighbors.

Some examples of network games with linear-quadratic model to observe a phase transition are public goods game (Allouch, 2015; Naghizadeh and Liu, 2018), influence of peers in education (Calvó-Armengol et al., 2009; Ballester et al., 2006) and to model criminal social interactions(Calvó-Armengol and Zenou, 2004). Crime and delinquency are related to connections in social networks, where delinquents often have friends who have committed offenses, and social ties are a means of influence to commit crimes. The ‘tipping point’ concept of using perturbation to affect the NE suggests that the properties of friendship networks should be taken into account to better understand peer influence on delinquent behavior and to craft delinquency-reducing policies.

Another application of the linear quadratic model is to model collaboration between firms as presented in (Koenig et al., 2014). Collaboration takes a variety of forms which includes creation and sharing of knowledge about markets and technologies, setting market standards and sharing facilities. The effects of peers has been evident in case studies on the adoption of high yielding hybrid crops by the farmers during the Dust Bowl in USA in late-1920s and 1930s (McLeman et al., 2014). The farmers were reluctant and slow to adopt hybrid crops, largely contributing to expensive switch and very few neighbors using hybrid crops. It was the focus by the government on young farmers over older farmers in combination with outreach by the USDA (headed by hybrid corn pioneer Henry A. Wallace), which can be interpreted as external perturbation on the existing network,that convinced Midwestern farmers to adopt the new seed (Meyers and Rhode, 2019; Moscona et al., 2021).

A network game $\mathcal{G}$ with set of $N$ players, is played over a weighted directed network whose structure is captured by an $n\times n$ adjacency matrix $G$. The $(i,j)$th entry of $G$, denoted by $g_{ij}$, represents the strength and type of influence of player $j$’s strategy on the utility function of player $i$. The positive (negative) $g_{ij}$ represent strategic substitutes (complements) where an increase in neighbor $j$’s actions leads to a corresponding decrease (increase) in player $i$’s action. The action of a player $i$ is given by $x_{i}\in\mathcal{X}_{i}\subseteq\mathbb{R}_{\geq 0}$, and so $x=(x_{1},x_{2}\dots x_{n})\in\mathcal{X}=\prod_{i=1}^{N}\mathcal{X}_{i}$. Each player $i$ $\in$ $\mathbb{N}[1,N]$ chooses their action $x_{i}\in\mathbb{R}_{\geq 0}$ to maximize a utility function:

which in turn depends on their own action $x_{i}$ and on the aggregate neighbors’ strategies $z_{i}(x)$, defined by the weighted linear combination

The best response for player $i$, i.e., the action that maximizes the utility function is defined as

The set of actions within which no player has an incentive for unilateral deviations (i.e., each player is playing a best response to other player’s actions) is a Nash equilibrium. Mathematically, a vector $x^{*}=(x^{*}_{1},\dots x^{*}_{n})$, is a Nash equilibrium (NE) if, for all players $i$ $\in$ $\mathbb{N}[1,N]$, $x^{*}_{i}$ $\in$ $B_{i}(z_{i}(x))$.

A linear quadratic (LQ) network game is one where each agent chooses a scalar strategy $x_{i}\geq 0$ in order to maximize the linear quadratic utility function:

with $a_{i},q_{i}$ $\in$ $\mathbb{R}$.

The Nash equilibrium (NE) for an LQ game can be derived from the first-order necessary condition to maximize the utility function for each player $i$ given by:

This results in

Our model for the adjacency matrix of a large network is in the category of the random matrices with fixed-rank deformation, which includes the signal-plus-noise model as typical example. A vast amount of work has been devoted to understanding the limiting behavior of the extreme eigenvalues and the associated eigenvectors of the deformed models. Since the seminal work of authors in (Baik et al., 2004), there has significant study to understand that the extreme eigenvalues undergo a so-called BBP phase transition along with the change of the strength of the deformation. There exists a critical threshold such that the extreme eigenvalue of the perturbed matrix will be within the end points of the spectral distribution if the strength of the deformation is less than or equal to the threshold, and will otherwise be outside of support of the limiting spectral distribution.

Assume $X$ be an $n\times n$ symmetric Gaussian Wigner matrix, with independent, zero mean normal distribution with variance $\sigma^{2}/2n$ on off diagonal and $\sigma^{2}/n$ on diagonal. It has been shown that the spectral measure of $X$ converges almost surely to the well known semi-circle distribution with density

Henceforth, $\xrightarrow{\text{a.s.}}$ denotes almost sure convergence. The result from (Anderson et al., 2009) shows that the extreme eigenvalues converge almost surely to the endpoints of the support i.e. $\lambda_{max}(X)\xrightarrow{\text{a.s.}}2\sigma$.

Let perturbation matrix $P$, be a $n\times n$ symmetric matrix with rank r. Its eigenvalues are $\theta_{1}\geq\dots\geq\theta_{s}>0>\theta_{s+1}\geq\dots\geq\theta_{r}$. By phase transition theorem, as $n\rightarrow\infty$ we have, for

Figure 1 shows the blue histogram of the eigenvalues of a Wigner matrix with $n=1000$, where the red curve follows the semi-circle law from (6). The extreme eigenvalues are within the boundaries of the semi-circle. The blue histogram of the Figure 2 is that of the eigenvalues of the same Wigner matrix but perturbed this time by a symmetric rank 1 matrix as in (7). The outlier represented here by blue dot outside red curve is exhibited by the extreme eigenvalue of deformed matrix out of the bulk spectrum. This shows the phase transition phenomenon from (8) when the $\theta>\sigma$

In the setting where $r=1$ and $P=\theta uu^{T}$, let $\tilde{u}$ be a unit-norm eigenvector of $\tilde{X}$ associated with its largest eigenvalue. The parameter $\theta$ represents the signal to noise ratio. By eigenvector phase transition theorem, for norm of the eigenvector projection we have,

Now we explore another strategy to modify a network, through a multiplicative deformation. Assume $M_{n}$ be an $n\times m$ matrix with independent, zero mean, normally distributed entries with variance 1. Then, $X_{n}=M_{n}M_{n}^{*}/m$ is known as Wishart matrix. It has been shown that as $n,m\rightarrow\infty$ with $n/m\rightarrow c>0$, the spectral measure of $X_{n}$ converges almost surely to the well-known Marchenko-Pastur distribution (Marčenko and Pastur, 1967) with density

where $a=(1-\sqrt{c})^{2}$ and $b=(1+\sqrt{c})^{2}$. It is known that the extreme eigenvalues converge almost surely to the endpoints of this support.

Let perturbation matrix $P$, be a $n\times n$ symmetric matrix with rank r. It’s eigenvalues are $\theta_{1}\geq\dots\geq\theta_{s}>0>\theta_{s+1}\geq\dots\geq\theta_{r}$. By phase transition theorem, as $n\rightarrow\infty$ we have, for

In the setting where $P=\theta uu^{T}$, let $\tilde{u}$ be a unit-norm eigenvector of $\tilde{X}$ from (11), associated with its largest eigenvalue. For Wishart matrix $X$ as described above, the eigenvector phase transition occurs as,

In the previous sections, we see how a large network can be influenced through external perturbations. The Nash Equilibrium, for the LQ game in (1), can be affected through additive and multiplicative perturbation. If the perturbation strength $\theta$ is strong, the primary eigenvalue goes beyond the random spectrum and the primary eigenvector, which is the NE of our LQ game is correlated with $\theta$ (in a cone around the perturbation’s eigenvector direction whose deviation angle goes to 0 as $\frac{\theta}{\sigma}\rightarrow\infty$). If $\theta$ is sufficiently low, the primary eigenvalue is buried in the random spectrum, and the NE is random, with no correlation to perturbation’s eigenvector.

The finite rank perturbation of an adjacency matrix of large network can be interpreted in multiple ways. The additive perturbation can be designed such the specific nodes of the network has higher influence through their edges on the neighbors and consequently the entire network. The multiplicative perturbation, though harder to visualize, also affects the edge weights to dominate the influence from certain nodes and affect the NE properties. The NE, through eigenvalue phase transition is shown for rank 1 perturbation matrices. The rank 1 adjacency matrix can be designed is such a way that the influencers of a real world network have a major role to cause a aggressive spread over the network. The NE, which is the optimal participation of each member, is influenced by this perturbation. The shift in primary eigenvectors also affects the eigenvector centrality measure of the large networks.

The deformation to the networks can be manipulated such that influence of some of the important nodes of the network is powerful enough to propagate their beliefs quicker and effectively. Work in the area of identifying the subset of individuals within a network that can maximize spread of idea has studied like in (Kempe et al., 2003). Using our analysis, we could apply sufficient external modifications to a network targeting influential set of individuals, to trigger a large cascade of belief spread.

In this paper, we explore conditions under which the Nash equilibrium of a large network game undergoes a phase transition when the adjacency matrix of the network is deformed through a finite matrix perturbation. Our contribution uses the well known eigenvector and eigenvalue phase transition phenomenon in conjunction with finite rank deformations of random matrices from field of random matrix theory to model such phenomena for linear quadratic games on a large network. For the LQ game, we make certain assumptions on the parameters of the utility function that enable us complete the analysis of transition of the NE. The large network is modelled as Winger and Wishart random matrix for additive and multiplicative deformations respectively. The network property i.e. $\sigma$ or $c$ determines the critical point around which the strength of perturbation shifts the NE. We observe that, as $\theta$ crosses the critical point, the NE jumps out of the spectrum and is dependent on $\theta$. For the values of $\theta$ below the critical point, the NE is unaffected by $\theta$. There are multiple potential applications for this phenomenon, where selfish participants form a large network.

There exists several avenues for future work. In field of network games, multiple settings are described through variety of utility functions. There is possibility of studying such phase transition in other network games with non linear functions. The eigenvalue/eigenvector transition for random matrix deformation occurs for distributions other than Wigner/Wishart as well. It would be a new direction to investigate phase transition for complex systems that are modeled by other density functions. Our model uses rank 1 deformation but studying phase transition for higher rank deformations and what such perturbations would mean to the network is another possible avenue. The extreme eigenvalues and spectral properties of adjacency matrix play an important role on other properties of NE like conditions on uniqueness and stability. Exploring how sudden shift in extreme eigenvalues affects these properties can help in devising appropriate perturbations. To this end, our results provide a framework to tackle some of the above open problems and applications in future work.