United We Fall: On the Nash Equilibria of Multiplex and Multilayer Network Games

Our work is at the intersection of two lines of literature: (i) the study of properties of Nash equilibria of single- layer network games, and (ii) game-theoretical modeling and analysis on multilayer and multiplex networks.

Nash equilibria in single-layer games. Specifically, our work closely relates to studies that investigate the existence, uniqueness, and stability of Nash equilibria in single-layer networks games with linear [2, 4, 12, 13, 14] and nonlinear [17, 19, 18] best-replies. Our proposed models of multiplex and multilayer network games are extensions of single-layer network games with linear best-replies, by allowing agents to have various types of interactions (multiplex) and operate across different action dimensions (multilayer). For these, we identify conditions under which the multiplex/multilayer network will (or will not) inherit the guarantees of uniqueness/stability of the Nash equilibrium in its constituent layers.

Games on multilayer/multiplex networks. While game-theoretical decision making on multiplex and multilayer networks has also been studied in some prior works [7, 23, 24, 25, 26, 27], the majority of the research has focused on evolutionary games and the emergence of cooperation in public good games. In particular, the emergence and sustainability of cooperation strategies in public good games has been explored in multiplex networks by [24, 25] and in multilayer networks by [26, 27]. Despite considering games on multilayer/multiplex networks and identifying what network structures can enhance the resilience of cooperation, these prior works have considered a binary action (cooperate/defect) game, and often restrict focus to specific classes of graphs. In contrast, we propose and analyze more general classes of multiplex and multilayer networks games, allow for arbitrary directed and weighted interactions among agents, and provide insights into the games’ Nash equilibria properties.

The recent work of [28] is also closely related to ours, as it proposes a “multi-relational” network game which is similar to our model of multilayer games, in that it allows for a multi-dimensional action space. The main focus of [28] is on identifying “summary representations” of the game matrix that can be used to significantly lower the computation complexity of ascertaining the uniqueness of NE. Our focus is however different: we illustrate how the properties of the constituent layers of a multilayer (and multiplex) network can undermine or support the uniqueness of the NE of these games.

This paper extends our earlier work in [29], which investigated the uniqueness of Nash equilibria in multiplex network games. The current work provides additional conditions for uniqueness of NE in multiplex network games, introduces the new class of multilayer network games and its NE uniqueness conditions, establishes new results on stability and existence of NE in both multiplex and multilayer games, and illustrates our findings through numerical experiments.

Consider a set of $N$ agents interacting with each other over a single network $\alpha$. This network is specified by a graph $\mathcal{G}_{\alpha}\coloneqq\langle\mathcal{V},{G^{(1)}}\rangle$, where the $N$ agents constitute the set of vertices $\mathcal{V}$, and ${G^{(1)}}$ is the weighted and directed adjacency or interdependency matrix over network $\alpha$.

Each agent $i$ selects an effort level $x\in\mathbb{R}_{\geq 0}$. The agent’s utility is determined by its own effort, as well as the effort of its neighboring agents in the network. Specifically, an edge $g^{(1)}_{ij}\in{G^{(1)}}$ indicates that agent $i$ is affected by agent $j$’s effort. If $g^{(1)}_{ij}>0$ (respectively, $<0$), we say agent $j$’s effort is a substitute (respectively, complement) to agent $i$’s effort. In our setting, a strategic substitute (resp. complement) means that effort by agent $j$ provides positive (resp. negative) externality to agent $i$, in that an increase in effort by agent $j$ allows agent $i$ to decrease its own effort (resp. requires agent $i$ to increase its effort) and still receive the same overall payoff.

Let $\mathbf{x}=[x_{1},x_{2},\ldots,x_{N}]^{T}$ denote the vector of all agents’ efforts. Agent $i$’s utility in network $\alpha$ is given by:

$\displaystyle u_{i}(\mathbf{x};{G^{(1)}})=b_{i}(x_{i}+\sum_{j}g^{(1)}_{ij}x_{j})-c_{i}x_{i}~{},$

(1)

where $b_{i}(\cdot):\mathbb{R}\rightarrow\mathbb{R}$ is a twice-differentiable, strictly increasing, and strictly concave benefit function, which has as its argument the aggregate effort experienced by the agent, and $c_{i}>0$ is the unit cost of effort for agent $i$.

The (single-layer) network game specified by the set of $N$ agents, their efforts $\mathbf{x}$, and their utility functions $\{u_{i}(\mathbf{x};{G^{(1)}})\}$ has been studied extensively in prior works (e.g., [4, 2, 12, 30]). In particular, these games are known as games of linear best-replies, as the Nash equilibrium $\mathbf{x}^{*}$ is determined by a set of linear best-response equations of the form:

$\displaystyle x_{i}^{*}=\max\{0,q_{i}-\sum_{j}g^{(1)}_{ij}x^{*}_{j}\}~{},$

(2)

where $q_{i}$ satisfies $b_{i}^{\prime}(q_{i})=c_{i}$. Intuitively, an agent $i$ wants to receive an aggregate effort level $q_{i}$ at equilibrium; this is the effort level at which the agent’s marginal benefit and marginal cost of effort are equalized. The best-response (2) states that the agent exerts effort $x_{i}^{*}$ to reach an aggregate effort level $q_{i}$, given the spillover $\sum_{j}g^{(1)}_{ij}x^{*}_{j}$ received from its neighboring agents’ effort at equilibrium, or exerts no effort if the spillovers already provide aggregate effort $q_{i}$ or higher.

We next propose two extensions of these existing models: multiplex network games, and multilayer network games. We present two-layer multiplex and multilayer network games; extensions to games involving more layers is straightforward.

Consider a second network defined by a graph $\mathcal{G}_{\beta}\coloneqq\langle\mathcal{V},G^{(2)}\rangle$, with the same set of vertices as network $\alpha$, but its own interdependency matrix ${G^{(2)}}$. The two-layer multiplex network $\mathcal{G}^{\parallel}\coloneqq\langle\mathcal{N},\{G^{(1)},G^{(2)}\}\rangle$ is the environment in which interactions between the $N$ agents occur over both networks $\alpha$ and $\beta$ simultaneously, but each governed by a different interdependency matrix. Let the utility of agent $i$ in the multiplex network be given by:

	$\displaystyle u_{i}(\mathbf{x};G^{(1)},G^{(2)},\kappa)=$
	$\displaystyle\quad b_{i}(x_{i}+\kappa\sum_{j}g^{(1)}_{ij}x_{j}+(1-\kappa)\sum_{j}g^{(2)}_{ij}x_{j})-c_{i}x_{i},$		(3)

where $\kappa\in[0,1]$ captures the effect of each layer on the utility, with higher $\kappa$’s indicating higher effects from network $\alpha$.

The resulting multiplex network game is again a game of linear best-replies, where at equilibrium, agent $i$ aims to choose $x_{i}^{*}$ to reach the same aggregate level of effort $q_{i}$, but this time while being exposed to spillovers $\kappa\sum_{j}g^{(1)}_{ij}x_{j}^{*}+(1-\kappa)\sum_{j}g^{(2)}_{ij}x_{j}^{*}$ from the multiplex network. Then, the multiplex network game can be viewed as a network game played over the interdependency matrix $G^{\parallel}\coloneqq\kappa G^{(1)}+(1-\kappa)G^{(2)}$.

Consider again the second network $\mathcal{G}_{\beta}\coloneqq\langle\mathcal{V},G^{(2)}\rangle$, with the same set of nodes as network $\alpha$.¹¹1We assume the layers have the same set of nodes to simplify notation. Our results will continue to apply when the set of nodes are different. Assume now that agents take a different action in each layer. Let $x_{i}^{(l)}$ denote agent $i$’s action in layer $l\in\{1,2\}$, and $\mathbf{x}^{(l)}$ denote the vector of all agents’ efforts in layer $l$. Additionally, assume there are dependencies between agents’ actions in different layers, represented by inter-layer dependency matrices $G^{(lk)}$. An edge $g^{(lk)}_{ij}$ captures how agent $i$’s utility in layer $l$ is impacted by agent $j$’s action in layer $k$.

Let agent $i$’s utility from layer $l$ be given by:

		$\displaystyle u_{i}^{(l)}({\mathbf{x}}^{(l)},{\mathbf{x}}^{(k)};G^{(l)},G^{(lk)})=$
		$\displaystyle\qquad b_{i}^{(l)}(\,x_{i}^{(l)}+\sum_{j}g^{(l)}_{ij}x^{(l)}_{j}+\sum_{j}g^{(lk)}_{ij}x^{(k)}_{j}\,)-c^{(l)}_{i}x_{i}^{(l)},$		(4)

where $k$ is the index of the other layer, and $b_{i}^{(l)}(\cdot)$ and $c_{i}^{(l)}$ are the benefit function and unit cost of action dimension $l$, respectively. The argument of the benefit function is the aggregate effort in action dimension $l$ experienced by the agent, and it comes from three sources: the agent’s own effort in action dimension $l$, the intra-layer spillovers from action dimension $l$ of neighboring agents in layer $l$, and the inter-layer spillovers from action dimension $k$ of neighboring agents in layer $k$. Agent $i$’s aggregate utility from the two layers is given by, $u_{i}=\kappa u_{i}^{(1)}+(1-\kappa)u_{i}^{(2)}$, where $\kappa\in[0,1]$ captures the effect of each layer on the agent’s utility.

Accordingly, agent $i$’s best-responses in each action dimension are given by

	$\displaystyle{x}_{i}^{*(1)}=\max\{0,{q}^{(1)}_{i}-\big{(}\begin{pmatrix}G^{(1)}&G^{(12)}\end{pmatrix}\begin{bmatrix}\mathbf{x}^{*(1)}\\ \mathbf{x}^{*(2)}\end{bmatrix}\big{)}_{i}\}~{},$
	$\displaystyle{x}_{i}^{*(2)}=\max\{0,{q}^{(2)}_{i}-\big{(}\begin{pmatrix}G^{(21)}&G^{(2)}\end{pmatrix}\begin{bmatrix}\mathbf{x}^{*(1)}\\ \mathbf{x}^{*(2)}\end{bmatrix}\big{)}_{i}\}~{},$		(5)

with $q^{(l)}_{i}$ satisfying ${b^{(l)}_{i}}^{\prime}(q^{(l)}_{i})=c_{i}^{(l)}$. This can be written more compactly as:

$\displaystyle\mathbf{x}_{i}^{*}=\max\{\mathbf{0},\mathbf{q}_{i}-(G^{\merge}\mathbf{x}^{*})_{[i,i+N]}\}~{},$

(6)

where the max operator is element-wise, $(G^{\merge}\mathbf{x}^{*})_{[i,i+N]}$ is the $2\times 1$ vector consisting of the $i^{\textsuperscript{th}}$ and $(i+N)^{\textsuperscript{th}}$ entries of the $2N\times 1$ vector $G^{\merge}\mathbf{x}^{*}$, and

$\displaystyle G^{\merge}\coloneqq\begin{pmatrix}G^{(1)}&G^{(12)}\\ G^{(21)}&G^{(2)}\end{pmatrix}$

(7)

is a $2N\times 2N$ supra-adjacency matrix. Then, the multilayer network game can be viewed as a network game with a two-dimensional action space played over the matrix $G^{\merge}$.

We first review existing conditions on the game adjacency matrix $G$ under which the equilibria of single-layer network games are (guaranteed to be) unique. We will later evaluate these conditions on $G^{\parallel}$ (for multiplex networks, Section III) and $G^{\merge}$ (for multilayer networks, Section IV), identifying when they do (not) hold in terms of the properties of the layers $G^{(1)}$ and $G^{(2)}$, and inter-layer interactions $\{G^{(12)},G^{(21)}\}$.

We build on the findings of [4], which explored the connection between finding the Nash equilibrium of games of linear best-replies and linear complementarity problems (LCPs), to identify conditions for the existence and uniqueness of the NE of single-layer network games. Formally, an LCP($M$, $\mathbf{b}$) seeks to find two $N\times 1$ vectors, $\mathbf{w}$ and $\mathbf{z}$, satisfying:

		$\displaystyle\mathbf{w}-M\mathbf{z}=\mathbf{b}$
		$\displaystyle\mathbf{w}\geq 0\,,\;\mathbf{z}\geq 0\,,\;\text{and}\;w_{i}z_{i}=0$		(8)

where $M$ is an $N\times N$ matrix and $\mathbf{b}$ is an $N\times 1$ vector. Comparing this with (2), we observe that finding the NE of a single-layer network game is equivalent to solving the LCP$(I+G,-\mathbf{q})$. This equivalence allows us to leverage existing characterizations of the properties of LCP solutions to assess a network game’s NE properties.

To present conditions for NE uniqueness, we begin with the following definition:

The class of P-matrices includes positive definite (PD) matrices as a special case;²²2A common convention adopted in some of the literature is to define positive definiteness for symmetric (or Hermitian) matrices, owing to their roots in quadratic forms. However, we adopt the more general definition here: A square matrix $M$ (whether symmetric or not) is positive definite if $x^{T}Mx>0$ for all $x\neq 0$. in particular, every PD matrix (whether symmetric or not) is a P-matrix, but there are (asymmetric) P-matrices that are not PD [31]. We also note that for symmetric matrices, the two notions are equivalent, i.e., a symmetric matrix is a P-matrix if and only if it is PD.

The following theorem provides the necessary and sufficient condition for the Nash equilibrium of a single-layer network game (whether symmetric or not) to be unique.

The following corollary is the special case of Theorem 1 for symmetric networks.

We now generalize the intuition from Example 1 to identify conditions under which $I+G^{\parallel}$ is not a P-matrix. In particular, note that $I+G^{\parallel}$ is a P-matrix if and only if the determinant of all its principal minors are positive. The following proposition identifies conditions under which at least one of the principal minors has a non-positive determinant.

Intuitive interpretation. It is worthwhile to again note that even if both layers satisfy the P-matrix condition, so that the sub-determinants $\det(M^{l}_{ij})$ are positive, the condition of Proposition 1 can still hold at sufficiently large $g^{(1)}_{ij}$ (the determinant term can be kept constant by adjusting $g^{(1)}_{ji}$ accordingly), so that the multiplex will not satisfy the P-matrix condition. Intuitively, this means that the NE may not be unique if there are sufficiently large cyclical dependencies between a pair of agents across the two layers. Proposition 1 can also be extended to state conditions on higher order principal minors (e.g., highlighting that non-uniqueness can be caused by cyclical interactions among a set of three agents).

While, as shown above, the sum of two P-matrices is in general not a P-matrix, there are specific subclasses of P-matrices which are closed under summation, as shown next.

Intuitive interpretation. We delve deeper into the case of symmetric matrices in the next subsection. The remaining two cases, row diagonally dominant and B-matrices, set limits on the influence of agents on each other. Proposition 2 notes that these limits will carry over when two networks connect. In particular, a row diagonally dominant matrix limits the cumulative maximum influence of neighboring agents on an agent $i$’s utility, relative to the agent’s self-influence (here, normalized to 1). If the externalities received from other agents are limited in both layers, they will also be limited when layers are interconnected. B-matrices on the other hand require that the row averages dominate any off-diagonal entries, meaning that no one neighbor’s externality on agent $i$ is higher than the average of all the other influences the agent experiences (both self-influence and the externality from the remaining neighbors). Again, if this is true in both layers, it will remain true when the two layers are interconnected as well, guaranteeing NE uniqueness.

We now turn to the special case of symmetric (undirected) networks. We begin by noting that the sum of two positive definite matrices is a positive definite matrix. That is, if we know that two symmetric layers already have structures that are conducive to unique NE, so will the symmetric multiplex network emerging from joining them. In light of this, we focus on situations where a symmetric first layer supports a unique NE, yet the second layer does not. We then identify conditions under which the multiplex is (Proposition 3) and is not (Proposition 4) guaranteed to have a unique NE.

We begin with a positive result: a multiplex may retain NE uniqueness under the following condition.

Intuitive interpretation. Proposition 3 is most useful when the multiplex closely resembles the first layer, as the second layer is comparatively “weaker”. Proposition 3 states a condition for quantifying this relative weakness. This metric evaluates the strength (connectivity) of the second layer relative to the bipartiteness of the first layer. Specifically, if the first layer is highly bipartite (with the smallest eigenvalue approaching $-1$), then the second layer should introduce minimal changes to the network by being relatively sparse (have a small largest eigenvalue). Conversely, if the first layer exhibits less bipartiteness, it can accommodate a stronger connectivity in the second layer. This is because the potential fluctuations caused by the second layer can be mitigated by the structural resilience of the first layer.

Now we present a negative result, where the second layer can undermine the uniqueness of the NE of the multiplex.

Intuitive interpretation. Given that the lowest eigenvalue can be interpreted as a measure of a network’s “two-sidedness” (with a smaller (more negative) lowest eigenvalue being an indication that agents’ actions rebound more in a network), it is expected that a second layer with a large $|\lambda_{\min}(G^{(2)})|$ will introduce similar effects in the multiplex network. The condition in Proposition 4 shows that this is indeed the case: when the second layer network is significantly two-sided, it can undermine the uniqueness of the equilibrium in the multiplex network. Also, as expected, for large $\kappa$ (when the second layer is less important in determining agents’ payoffs), $\lambda_{\min}(G^{(2)})$ will have less influence on the NE uniqueness.

More interestingly, the severity of rebound effects due to the second layer network (its $\lambda_{\min}$) are compared against the extent of connectivity of the first layer network (its largest eigenvalue $\lambda_{\max}$). In words, Proposition 4 states that if the connectivity of the first layer (as characterized by its largest eigenvalue) is not high enough to mute the ups and downs introduced by the second layer (as characterized by its smallest eigenvalue), then the multiplex will have either no equilibrium or multiple equilibria for some game instances.

First, we show that in a general network, with both inter-layer and intra-layer edges being directed and weighted, a Nash equilibrium may not be unique even if each layer is guaranteed to have a unique Nash equilibria by itself.

Intuitive interpretation. The first case of the proposition is straightforward: it notes that if the game is not guaranteed to have a unique equilibrium in one action dimension, then it is not guaranteed to have a unique equilibrium in the two dimensional action space. The second case is perhaps more interesting; it argues that despite having a unique equilibrium in each action dimension separately, when the spillovers between action dimensions (due to the inter-layer connections) are taken into account, the game may no longer have a unique NE. The conditions in the second case of Proposition 5 capture the extent of spillovers needed for this to happen.

To further illustrate, consider the following case. From [37], we know that for two non-singular matrices $A$ and $B$ such that $C=B^{-1}A$ is positive semi-definite, $\det(A+B)\geq\det(A)+\det(B)$. Let $A=I+G^{(1)}-G^{(12)}(I+G^{(2)})^{-1}G^{(21)}$ and $B=-(I+G^{(1)})$, and assume these satisfy the requisite conditions above. Then, if

$\displaystyle\det(I+G^{(1)})\det(I+G^{(2)})\leq\det(G^{(12)})\det(G^{(21)})$

the condition in the second case of Proposition 5 would hold, and the multilayer game would not be guaranteed to have a unique NE. This can happen, e.g., if the edge weights in one or both of the inter-layer interactions are sufficiently large and of the same sign both ways. Intuitively, this can be interpreted as large rebound effects of action dimensions across the two layers which can undermine equilibrium uniqueness.

In light of the negative result in the general case, we next explore two special cases when the multilayer network can be guaranteed to have a unique NE: one-way inter-layer connections, and (sufficiently bounded) games of complements.