A Note on Network Games with Strategic Complements and the Katz-Bonacich Centrality Measure

Abstract

We investigate a class of network games with strategic complements and bounded strategy sets by using the variational inequality approach. In the case where the Nash equilibrium of the game has some boundary components, we derive a formula which connects the equilibrium to the Katz-Bonacich centrality measure, thus generalizing the classical result for the interior solution case. Furthermore, we prove that any component of the Nash equilibrium is less than or equal to the corresponding component of the social optimal solution and numerically study the price of anarchy for a small size test problem.

1 Introduction

This paper deals with a class of Network Games (see, e.g., [10]), where each player is identified with the node of a graph and players that can interact directly are connected through edges of the graph. This kind of games have proven to be very useful in modeling social and economic interactions, where the action of a typical player is likely to be influenced by the actions taken by her/his friends or colleagues. A feature of these models is the central role played by the graph structure in influencing the social or economic interactions and shaping the resulting equilibrium. As a consequence, the Nash equilibrium and the social optimal solution depend on graph-algebraic quantities. In particular, in the case of interior solution a very interesting representation formula has been derived in the seminal paper by Ballester et al. [1], which involves the so called Katz-Bonacich centrality measure.

In this note, we generalize this formula to the case where the solution has some boundary components. To this end, we focus on the quadratic reference model with strategic complements which, roughly speaking, describe social interactions where the incentive for a player to take an action increases when the number of her/his social contacts who take the action increases. Furthermore, by exploiting the sequential best-response dynamics, we prove that the Nash equilibrium is component-wise less than or equal to the social optimal solution. To obtain our results, we reformulate our problem as an equivalent variational inequality. The relationship between Nash equilibrium problems and variational inequalities has been pioneered by Gabay and Moulin [8], but only recently some authors have applied this methodology to investigate Network Games. In these regards, we refer the interested reader to the beautiful paper by Parise and Ozdaglar [15], which although comprehensive in many respects such as uniqueness and sensitivity of equilibrium, does not focus on the Katz-Bonacich representation of the solution or on the price of anarchy.

The paper is structured as follows. In Sect. 2 we first introduce the notation, the basic definitions and the variational inequality approach. We then specialize to the reference quadratic model and recall the classical Katz-Bonacich formula for the interior solution case, where the strategy set of each player is $\mathbb {R}_+$. We also recall the notions of social optimal solution, efficiency of a Nash equilibrium, and price of anarchy. In Sect. 3, we assume that the strategy sets are bounded also from above and derive a necessary condition that the solution satisfies when some of its components lie on the boundary (Theorem 3). We interpret this condition in terms of the Katz-Bonacich centrality measure. Moreover, we prove the relationship between the Nash equilibrium and the social optimum (Theorem 4). Theorems 3 and 4 of this section are, to the best of our knowledge, new and represent the main contribution of this note, Sect. 4 is devoted to the numerical investigation of a test problem to illustrate our findings. A short concluding section ends the paper.

2 Network Games

2.1 Game Formulation and Variational Inequality Approach

In Network Games players are represented by the nodes of an undirected graph (V, E), where V = {v ₁, …, v _n} is the sets of nodes and E is the set of edges formed by pairs of nodes (v _i, v _j). Here, we consider undirected simple graphs. Two nodes v _i and v _j are said to be adjacent if they are connected by the edge (v _i, v _j). The information about the adjacency of nodes can be stored in the adjacency matrix G whose elements g _ij are equal to 1 if (v _i, v _j) is an edge, 0 otherwise. G is thus a symmetric and zero-diagonal matrix. Given a node v, the nodes connected to v with an edge are called the neighbors of v. A walk in the graph is a finite sequence of the form $v_{i_{0}}, e_{j_{1}}, v_{i_{1}}, e_{j_{2}},\ldots , e_{j_{k}}, v_{j_{k}},$ which consists of alternating nodes and edges of the graph, such that $v_{i_{t-1}}$ and $v_{i_{t}}$ are end nodes of edge $e_{j_{t}}$. The length of a walk is the number of its edges. Let us remark that it is allowed to visit a node or go through an edge more than once. The indirect connections between any two nodes in the graph are described by means of the powers of the adjacency matrix G. Indeed, it can be proved that the element $g_{ij}^{[k]}$ of G ^k gives the number of walks of length k between nodes v _i and v _j.

In the sequel, the set of players will be denoted by {1, 2, …, n} instead of {v ₁, v ₂, …, v _n}. We denote with $A_i\subset \mathbb {R}$ the action space of player i, while A = A ₁ ×⋯ × A _n. For each a = (a ₁, …, a _n) , a _−i = (a ₁, …, a _i−1, a _i+1, …, a _n) and the notation a = (a _i, a _−i) will be used when we want to distinguish the action of player i from the action of all the other players. Each player i is endowed with a payoff function $u_i: A \to \mathbb {R}$ that she/he wishes to maximize. The notation u _i(a, G) is often utilized when one wants to emphasize that the utility of player i also depends on the actions taken by her/his neighbors in the graph.

The solution concept that we consider here is the Nash equilibrium of the game, that is, we seek an element a ^∗∈ A such that for each i ∈{1, …, n}:

$$\displaystyle \begin{aligned} u_{i}(a_i^* , a_{-i}^*) \geq u_{i}(a_i , a_{-i}^*), \qquad \forall\ a_i \in A_i . \end{aligned} $$

(1)

We now posit a further assumption on how variations of the actions of player i’s neighbors affect her/his marginal utility.

Definition 1

The network game has the property of strategic complements if:

$$\displaystyle \begin{aligned} \frac{\partial^2 u_i}{\partial a_{j} \partial a_{i}}(a)>0, \qquad \forall\ (i,j):\ g_{ij}=1,\ \forall\ a\in A. \end{aligned}$$

For the subsequent development it is important to recall that if the u _i are continuously differentiable functions on A, the Nash equilibrium problem is equivalent to the variational inequality V I(F, A): find a ^∗∈ A such that

$$\displaystyle \begin{aligned}{}[F(a^*)]^{\top}(a-a^*) \geq 0, \qquad \forall\ a\in A, \end{aligned} $$

(2)

where

$$\displaystyle \begin{aligned}{}[F(a)]^{\top}:= -\left(\frac{\partial u_1}{\partial a_1}(a), \dots, \frac{\partial u_n}{\partial a_n}(a)\right) \end{aligned} $$

(3)

is also called the pseudo-gradient of the game. For an account of variational inequalities the interested reader can refer to [7, 12, 14]. We recall here some useful monotonicity properties.

Definition 2

A map $T:\mathbb {R}^n \to \mathbb {R}^n$ is said to be monotone on A iff:

$$\displaystyle \begin{aligned}{}[T(x)-T(y)]^{\top} (x-y) \geq 0, \qquad \forall\ x,y \in A.\end{aligned} $$

If the equality holds only when x = y, T is said to be strictly monotone.

T is said to be β-strongly monotone on A iff there exists β > 0 such that

$$\displaystyle \begin{aligned}{}[T(x)-T(y)]^{\top} (x-y) \geq \beta \| x-y\|{}^2, \qquad \forall\ x,y \in A.\end{aligned} $$

For linear operators on $\mathbb {R}^n$ the two concepts of strict and strong monotonicity coincide and are equivalent to the positive definiteness of the corresponding matrix.

Conditions that ensure the unique solvability of a variational inequality problem are given by the following theorem (see, e.g., [7, 14]).

Theorem 1

If$K \subset \mathbb {R}^n$is a compact convex set and$T:\mathbb {R}^n \to \mathbb {R}^n$is continuous on K, then the variational inequality problem V I(F, K) admits at least one solution. In the case K is unbounded, existence of a solution may be established under the following coercivity condition:

$$\displaystyle \begin{aligned}\lim_{\|x\| \to +\infty }\frac{[T(x)-T(x_0)]^{\top} (x-x_0)}{\| x-x_0\|}=+\infty,\end{aligned} $$

for x ∈ K and some x ₀ ∈ K.

Furthermore, if T is strictly monotone on K the solution is unique.

In the following subsection, we describe in detail the linear-quadratic reference model with strategic complements.

2.2 The Linear-Quadratic Model

Let $A_i =\mathbb {R}_+$ for any i ∈{1, …, n}, hence $A=\mathbb {R}^{n}_+$. The payoff of player i is given by:

$$\displaystyle \begin{aligned} u_i (a,G) = -\frac{1}{2}a_i^2 + \alpha a_i +\phi \sum_{j=1}^n g_{ij}a_i a_j, \qquad \alpha, \phi>0.\end{aligned} $$

(4)

In this simplified model α and ϕ take on the same value for all players, which then only differ according to their position in the network. The last term describes the interaction between neighbors, and since ϕ > 0 this interaction falls in the class of strategic complements. The pseudo-gradient’s components of this game are easily computed as:

$$\displaystyle \begin{aligned} F_i (a)= a_i - \alpha - \phi \sum_{j=1}^n g_{ij} a_j, \qquad i\in\{1,\ldots,n\}, \end{aligned}$$

which can be written in compact form as F(a) = (I − ϕG)a − α 1, where $\mathbf {1}=~(1,\ldots ,1)^{\top }\in \mathbb {R}^n$. We will seek Nash equilibrium points by solving the variational inequality:

$$\displaystyle \begin{aligned}{}[F(a^*)]^{\top} (a-a^*) \geq 0, \qquad \forall\ a\in \mathbb{R}^{n}_{+}. \end{aligned} $$

(5)

Since the constraint set is unbounded, to ensure solvability we require that F be strongly monotone, which (implying coercivity, for linear operators) also guarantees the uniqueness of the solution.

Lemma 1 (see, e.g. [10])

The matrix I − ϕG is positive definite iff ϕρ(G) < 1, where ρ(G) is the spectral radius of G.

In the next lemma we recall a well known result about series of matrices.

Lemma 2

Let T be a square matrix and consider the series$\sum _{p=0}^\infty T^p$ . The series converges provided that lim_p→∞ T ^p = 0, which is equivalent to ρ(T) < 1. In such case the matrix I − T is non singular and we have$(I-T)^{-1}=\sum _{p=0}^\infty T^p$.

Theorem 2 (See e.g. [10])

If ϕρ(G) < 1, then the unique Nash equilibrium is

$$\displaystyle \begin{aligned} a^* = \alpha(I-\phi G)^{-1}\mathbf{1} = \alpha \sum_{p=0}^{\infty} \phi^p G^p \mathbf{1}\, . \end{aligned} $$

(6)

Remark 1

The expansion in (6) suggests an interesting interpretation. Indeed, the (i, j) entry, $g_{ij}^{ [p]}$, of the matrix G ^p gives the number of walks of length p between nodes i and j. Based on this observation, a measure of centrality on the network was proposed by Katz and Bonacich [5]. Specifically, for any weight $w\in \mathbb {R}^{n}_+$, the weighted vector of Katz-Bonacich is given by:

$$\displaystyle \begin{aligned} b_w (G,\phi)= M(G,\phi) w= (I-\phi G)^{-1} w= \sum_{p=0}^{\infty} \phi^p G^p w. \end{aligned} $$

(7)

In the case where w = 1, the (non weighted) centrality measure of Katz-Bonacich of node i is given by:

$$\displaystyle \begin{aligned} b_{1,i}(G,\phi)=\sum_{j=1}^n M_{ij}(G,\phi) \end{aligned}$$

and counts the total number of walks in the graph, which start at node i, exponentially damped by ϕ.

Remark 2

The game under consideration also falls in the class of potential games according to the definition introduced by Monderer and Shapley [13]. Indeed, a potential function is given by:

$$\displaystyle \begin{aligned} P(a,G,\phi)= \sum_{i=1}^n u_i (a,G)-\frac{\phi}{2} \sum_{i=1}^n \sum_{j=1}^n g_{ij} a_i a_j. \end{aligned}$$

Monderer and Shapley have proved that, in general, the solutions of the problem max_{a ∈ A}P(a, G, ϕ) form a subset of the solution set of the Nash game. Because under the condition ϕρ(G) < 1 both problems have a unique solution, it follows that the two problems share the same solution.

Let us now define the social welfare function as:

$$\displaystyle \begin{aligned} W(a,G)= \sum_{i=1}^n u_i(a,G) = -\frac{1}{2}a^{\top} (I - 2 \phi G)a + \alpha {\mathbf{1}}^\top a. \end{aligned}$$

The value that W takes on at the Nash equilibrium a ^∗ can be easily computed as $W(a^*,G)= \frac {1}{2} \alpha ^2b_{\mathbf {1}}(G,\phi )^{\top }b_{\mathbf {1}}(G,\phi )$. The natural question arises of comparing this value with the optimal value of W. Under the condition 2ϕρ(G) < 1 it turns out that the maximum of W is reached at a ^so = αb ₁(G, 2ϕ) and $W(a^{so},G)= \frac {1}{2} \alpha ^2 b_{\mathbf {1}}(G,2\phi )^{\top }b_{\mathbf {1}}(G,2\phi )$. Thus, the Nash equilibrium is not efficient and it is interesting to compute the ratio:

$$\displaystyle \begin{aligned} \gamma(G,\phi)=\frac{W(a^*,G)}{W(a^{so},G)}, \end{aligned} $$

(8)

which can be termed the price of anarchy (see, e.g., [16]).

3 Bounded Strategies

We now assume that the strategies of each player have an upper bound, i.e., the strategy set A _i = [0, L _i], with L _i > 0, for any i ∈{1, …, n}, and derive a Katz-Bonacich type representation of the solution, in the case where exactly k components take on their maximum value.

Theorem 3

Let u _ibe defined as in (4), ϕρ(G) < 1, A _i = [0, L _i] for any i ∈{1, …, n} and a ^∗be the unique Nash equilibrium of the game. We then have that ai∗ > 0 for any i ∈{1, …, n}. Moreover, assume that exactly k components of a ^∗take on their maximum value:$a^*_{i_1}=L_{i_1},\ldots , a^*_{i_k}= L_{i_k} ,$and denote with${\tilde a}^*=(\tilde {a}_{i_{k+1}}^*,\ldots , {\tilde a}_{i_n} ^*)$the subvector of the nonboundary components of a ^∗ . We then get:

$$\displaystyle \begin{aligned} {\tilde a}^*= (I_{n-k} -\phi\,G_1)^{-1} w = b_{w}(G_1,\phi), \end{aligned} $$

(9)

where G ₁is the submatrix obtained from G choosing the rows i _k+1, …, i _nand the columns i _k+1, …, i _n ; G ₂is the submatrix obtained from G choosing the rows i _k+1, …, i _nand the columns i ₁, …, i _k ; w = α 1 _n−k + ϕG ₂L and$L= (L_{i_1},\ldots ,L_{i_k})$.

Proof

The Nash equilibrium a ^∗of the game solves the variational inequality

$$\displaystyle \begin{aligned}{}[F(a^*)]^{\top}(a-a^*) \geq 0, \qquad \forall\ a\in A, \end{aligned} $$

(10)

where A = [0, L ₁] ×⋯ × [0, L _n]. Let us assume that there exist l such that $a^*_l=0$, and choose in (10) $a=(a_1^*,\dots ,a_{l-1}^*, L_l, a_{l+1}^*,\dots , a_n^*)\in A$. With this choice, (10) reads:

$$\displaystyle \begin{aligned} 0 \leq F_l (a^*)L_l= \left(-\phi \sum_{j=1}^n g_{lj} a^*_{j} -\alpha\right ) L_l < 0, \end{aligned}$$

which yields the contradiction. Thus, $a^*_i>0$ for any i = 1, …, n.

Let $\tilde A$ denote the face of A obtained intersecting A with the hyperplanes: $a_{i_1}= L_{i_1}, \ldots , a_{i_k}= L_{i_k}$. Moreover, let $\tilde a=(a_{i_{k+1}},\ldots , a_{i_n})$, ${\tilde a}^*=(\tilde {a}_{i_{k+1}}^*,\ldots , {\tilde a}_{i_n} ^*)$ and $\tilde F:\mathbb {R}^{n-k} \to \mathbb {R}^{n-k}$ such that ${\tilde F}_{i_l}({\tilde a})$ is obtained by fixing $a_{i_1}= L_{i_1}, \ldots , a_{i_k}= L_{i_k}$ in $F_{i_l}(a)$. We consider now the restriction of (10) to $\tilde A$, which reads:

$$\displaystyle \begin{aligned} \sum_{l=k+1}^n {\tilde F}_{i_l}({\tilde a}^*)( \tilde{a}_{i_l} -\tilde{a}_{i_l}^*) \geq 0, \qquad \forall\ \tilde a \in \tilde A. \end{aligned} $$

(11)

Since we are assuming that exactly k components of the solution a ^∗ reach their upper bounds, it follows that $\tilde {a}^*$ lies in the interior of $\tilde A$, hence $\tilde F({\tilde a}^*)=0$, that is equivalent to

$$\displaystyle \begin{aligned} a^*_{i_l} - \phi \sum_{m=k+1}^n g_{i_l i_m} a^*_{i_m} =\alpha + \phi \sum_{m=1}^k g_{i_l i_m}L_{i_m}, \;\; l=k+1,\ldots,n, \end{aligned} $$

(12)

which yields:

$$\displaystyle \begin{aligned} (I_{n-k} -\phi G_1) \tilde a^*= \alpha {\mathbf{1}}_{n-k} +\phi G_2 L. \end{aligned} $$

(13)

Because the matrix (I _n−k − ϕG ₁) is not singular, the thesis is proved. □

The following result shows a relationship between the Nash equilibrium and the social optimum of the game.

Theorem 4

Let u _ibe defined as in (4), ϕρ(G) < 1∕2, and A _i = [0, L _i] for any i ∈{1, …, n}. Then,

$$\displaystyle \begin{aligned} a^*_i \leq a^{so}_i \qquad \forall\ i=1,\dots,n, \end{aligned}$$

where a ^∗ is the Nash equilibrium and a ^so is the social optimum of the game.

Proof

Since ϕρ(G) < 1∕2, there exists a unique Nash equilibrium a ^∗ and a unique social optimum a ^so. Moreover, it follows from the KKT conditions that a ^so satisfies the following system: $a^{so}_i = \min \left \{ L_i,\ \alpha + 2 \phi \sum _{j=1}^n g_{ij} a^{so}_j \right \}$, i = 1, …, n. Given any strategy profile a = (a _i, a _−i), the best response of player i to rivals’ strategies a _−i is given by $B_i(a_{-i}) = \arg \max _{a_i \in [0,L_i]} u_i(\cdot ,a_{-i}) = \min \left \{ L_i,\ \alpha + \phi \sum _{j=1}^n g_{ij} a_j \right \}.$

We now consider the sequential best response dynamics starting from the social optimum a ^so, that is the sequence {a ^k} defined as follows:

$$\displaystyle \begin{aligned} a^0 &= a^{so} , a^1 =\left( B_1(a^0_{-1}),\ a^0_2,\ a^0_3,\ \dots\ ,\ a^0_n\right),\\ a^2&=\left(B_1(a^0_{-1}),\ B_2(a^1_{-2}),\ a^0_3,\ \dots\ ,\ a^0_n\right),\\ & \dots \\ a^n&= \left(B_1(a^0_{-1}),\ B_2(a^1_{-2}),\ B_3(a^2_{-3}),\ \dots \ ,\ B_n(a^{n-1}_{-n})\right), \\ a^{n+1}&=\left(B_1(a^n_{-1}),\ B_2(a^1_{-2}),\ \dots\ ,\ B_n(a^{n-1}_{-n})\right),\\ a^{n+2}&=\left(B_1(a^n_{-1}),\ B_2(a^{n+1}_{-2}),\ B_3(a^2_{-3}),\ \dots\ ,\ B_n(a^{n-1}_{-n})\right), \dots. \end{aligned} $$

We note that

$$\displaystyle \begin{aligned} a^1_1 = B_1\left(a^0_{-1}\right) = \min \left\{ L_1,\ \alpha + \phi \sum_{j=1}^n g_{1j} a^0_j \right\} \leq \min \left\{ L_1,\ \alpha + 2 \phi \sum_{j=1}^n g_{1j} a^0_j \right\} = a^0_1, \end{aligned} $$

hence a ¹ ≤ a ⁰. Moreover, we have

$$\displaystyle \begin{aligned} a^2_2 = \min \left\{ L_2,\ \alpha + \phi \sum_{j=1}^n g_{2j} a^1_j \right\} \leq \min \left\{ L_2,\ \alpha + 2\phi \sum_{j=1}^n g_{2j} a^0_j \right\} = a^0_2 = a^1_2, \end{aligned} $$

hence a ² ≤ a ¹. Similarly, we can prove that a ⁿ ≤ a ⁿ⁻¹ ≤⋯ ≤ a ¹ ≤ a ⁰. Furthermore, we get

$$\displaystyle \begin{aligned} a^{n+1}_1 = \min \left\{ L_1,\ \alpha + \phi \sum_{j=1}^n g_{1j} a^{n}_j \right\} \leq \min \left\{ L_1,\ \alpha + \phi \sum_{j=1}^n g_{1j} a^0_j \right\} = B_1\left(a^0_{-1}\right) = a^n_1, \end{aligned} $$

hence a ⁿ⁺¹ ≤ a ⁿ, and

$$\displaystyle \begin{aligned} a^{n+2}_2 = \min \left\{ L_2,\ \alpha + \phi \sum_{j=1}^n g_{2j} a^{n+1}_j \right\} \leq \min \left\{ L_2,\ \alpha + \phi \sum_{j=1}^n g_{2j} a^1_j \right\} = a^{n+1}_2, \end{aligned} $$

thus a ⁿ⁺² ≤ a ⁿ⁺¹. Following the same argument as before, we can prove that a ^k+1 ≤ a ^k for any $k \in \mathbb {N}$ and hence, in particular, a ^k ≤ a ^so holds for any k. Since the potential function P is strongly concave, the sequence {a ^k} converges to the unique Nash equilibrium a ^∗ (see, e.g., [4, Proposition 3.9]), hence a ^∗≤ a ^so. □

4 Numerical Example

In this section, we show a numerical example for the linear-quadratic network game described in Sect. 3.

Example 1

We consider the network shown in Fig. 1 (see also [3]) with eight nodes (players). The spectral radius of the adjacency matrix G is ρ(G) ≃ 3.1019. We set parameters α = 10, ϕ = 0.45∕ρ(G) and upper bounds L _i = L = 18 for any player i = 1, …, 8. Therefore, there exists a unique Nash equilibrium and a unique social optimum. Table 1 shows the unconstrained Nash equilibrium (assuming L = +∞, given by formula (6)), the constrained Nash equilibrium (assuming L = 18) and the social optimum.

Fig. 1

Network topology of Example 1

Table 1 Unconstrained Nash equilibrium, constrained Nash equilibrium (considering upper bound L = 18) and social optimum for Example 1

Figure 2 shows the price of anarchy γ(G, ϕ) of the Nash equilibrium for different values of L and ϕ. The results suggest that (1) the price of anarchy is a non-increasing function of L; (2) it is constant when either L is small enough (i.e., the Nash equilibrium coincides with the social optimum) or greater than some threshold (i.e., the Nash equilibrium and the social optimum are both interior to the feasible region); (3) the larger the value of ϕ, the smaller the asymptotic value of γ(G, ϕ) is.

Fig. 2

Price of anarchy for different values of L and ϕ

5 Conclusions and Further Research Perspectives

A future research direction is the use of the necessary condition for boundary solutions to develop an algorithm for finding the Nash equilibrium. Moreover, the introduction of uncertain data in the model could be done along the same lines as in [11]. From the application viewpoint, our results could be used to further develop several models in social sciences and economy. For instance, in [2] criminal social interactions were analyzed within the framework of a general quadratic model in social networks; in [6], the influence of peers on educational networks has been studied extensively using the approach described in this note; moreover, in [9] the quadratic model was used to investigate the interaction between the social space (i.e., the network) and the geographical space (i.e., the city).