# Matrix Expression of Shapley Value in Graphical Cooperative Games

Authors: Yuanhua Wang; Fuad E. Alsaadi; Zheng Liu; Xiaomeng Wu; Xiyu Liu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper studies a class of cooperative games, called graphical cooperative games, where the internal topology of the coalition depends on a prescribed communication graph among players. First, using the semitensor product of matrices, the value function of graphical cooperative games can be expressed as a pseudo-Boolean function. Then, a simple matrix formula is provided to calculate the Shapley value of graphical cooperative games. Finally, some practical examples are presented to illustrate the application of graphical cooperative games in communication-based coalitions and establish the significance of the Shapley value in different communication networks.


---

## Body

## 1. Introduction

Game theory provides a formal mathematical formation to describe the complex interactions among rational players [1]. In general, game theory can be divided into two branches: noncooperative games and cooperative games. In noncooperative game theory, the fundamental unit of study is the individual player, and the theory studies the strategic choices in the interactions among competing players. By contrast, the fundamental unit in cooperative game theory is the set of players or coalition, and the theory studies the behaviour of rational players when they cooperate. The fundamental problem in cooperative game theory is how to allocate the profit or value of a coalition to its individual players in such a way that players are encouraged to cooperate. A fair allocation that has been widely used is the Shapley value [2].In recent years, there has been an increasing amount of research on using graph theory to cooperative games, where the players are interconnected and communicate with others in a network graph. For modelling the communication graph, cooperative games in the graph form, called graphical cooperative games or graphical coalitional games, are introduced by Myerson in [3]. These are games where the internal structure of the coalition is described by a network. In the network, nodes represent players and two players are interpreted to have an edge between them if and only if they can communicate with each other. In such games, unlike the value of a coalition depending solely on the members of that coalition in canonical cooperative games, the value function will be dependent of how the players are interconnected within the coalition. In [4–6], the formation and stability of coalitions given an underlying communication graph are studied, and its applications to communication networks have been investigated. In [7], the graphical coalitional games are studied with applications to economic and social networks, and the authors have analyzed the stability of networks when players can choose to form and maintain the links between them. This game model is also used to study biologic networks [8] and so on.It is pointed out in [3] that the Shapley value is the only possible function that provides a fair allocation in graphical coalitional games. However, its computational complexity becomes an obstacle both in practical applications and theoretical deductions [9]; a remark is also presented in [6] to state that “the Shaple value is computationally expensive, but for fairly large structures one time computation is still affordable. For such a graph that even one time computation is not affordable, approximations can be used for its computation.” In our recent work [10], a simple matrix formula is obtained to calculate the Shapley value and the basic mathematical method is the semitensor product of matrices (STP), which is a generalization of the traditional matrix product [11]. This method has been successfully applied in the analysis and control problems of logical networks [12–25], and then it has been used in finite game theory [26–30], evolutionary games [31–38], finite automata [39, 40], graph theory [41], etc. Unlike the canonical cooperative games being considered in [10], this paper studies a new class of cooperative games, called graphical cooperative games. Wang et al. [10] have provided the matrix formulas to calculate the symmetric and weighted Shapley values for canonical cooperative n-person games. However, this paper proposes a simple formula to calculate the Shapley value of graphical cooperative games, and it is more computationally complex than the formulas in [10].The paper is organized as follows. A brief review for the STP method and graphical cooperative games is presented in Section2. In Section 3, the matrix formula of the Shapley value in graphical cooperative games is presented. Section 4 discusses the practical applications of graphical cooperative games to some communication networks. Section 5 is a brief conclusion.Before ending this section, we present some notations used in this paper.D:=0,1. Δn:=δnii=1,…,n, where δni is the ith column of the identity matrix In. ℝn is the n dimensional Euclidean space. ℳm×n denotes the set of m×n real matrices. ColM (RowM) is the set of columns (rows) of M and ColiM (RowiM) is the ith column (row) of M. 1ℓ=1,1,…,1︸ℓT. A matrix L∈ℳm×n is called a logical matrix if the columns of L are of the form of δmk, that is, ColL⊂Δm. Denote by ℒm×n the set of m×n logical matrixes.


## 2. Preliminaries

### 2.1. Semitensor Product of Matrices

The basic technique used in this paper is the STP of matrices. We can refer to [11] for details.Definition 1.
LetM∈ℳm×n, N∈ℳp×q, and t=lcmn,p be the least common multiple of n and p. The STP of M and N is defined as(1)M∝imesN≔M⊗It/nN⊗It/p∈ℳmt/n×qt/p,where ⊗ is the Kronecker product. As a generalization of the conventional matrix product, the STP of matrices keeps the useful properties of the conventional matrix product available. For convenience, the symbol ”∝imes” may be omitted without confusion.
Next, we present some properties of the STP used in this paper.Proposition 1.
LetX∈ℝm be a column and M be a matrix. Then,(2)X∝M=Im⊗MX.
The STP has pseudocommutative properties, and the swap matrix is defined as follows.Definition 2.
The matrixWm,n∈ℳmn×mn, defined by(3)Wm,n=δmn1,m+1,…,n−1m+1;2,m+2,…,n−1m+2;…;m,2m,…,nm,is called the m,nth dimensional swap matrix.Proposition 2.
LetX∈ℝm and Y∈ℝn be two columns. Then,(4)Wm,n∝X∝Y=Y∝X.
Ifx is a logical variable, then x∈D. To use vector expression of logical values, we identify 1∼δ21∈Δ and 0∼δ22∈Δ. Now, a pseudological (or logical) function can be expressed as an algebraic form.Theorem 1.
Letf:Dn⟶ℝ (or f:Dn⟶D) be a pseudological (or logical) function. Then, there exists a unique vector (or matrix) Mf∈ℝ1×2n (or Mf∈ℒ2×2n), such that(5)fx1,x2,…,xn=Mf∝i=1nxi,where Mf is called the structure vector (or matrix) of f, which can be calculated as(6)ColjMf=fδknj,j=1,2,…,kn.


### 2.2. Graphical Cooperative Games

In essence, a canonical cooperative game involves a set of players, denoted byN=1,2,…,n, who seek to form cooperative groups in order to strengthen their positions in the game. Any subset of N is called a coalition, and N is called the grand coalition. The second fundamental concept of the canonical cooperative game is the characteristic function or value function, denoted by υ:2N⟶ℝ with υ∅=0, which quantifies the worth of a coalition in a game. Therefore, a canonical cooperative game can be denoted by a pair N,υ [4]. In general, we can identify a cooperative game N,υ with its value function υ, since for every υ a different game may be defined.Next, we give the definition of graphical cooperative games.Definition 3.
(see [6]). A graphical cooperative game is denoted by Γ=G,υ, where(1)
G=V,E is an undirected graph with V=1,2,…,n a finite nonempty set of players and E⊆V×V a set of edges. The elements of V are also called nodes or vertices. The number of elements in V is called the order or size of G and is denoted as G=n. In this paper, we only consider that G is a simple graph, that is, G does not contain self-loops and multiple edges. Let S=V′,E′ be a graph such that V′⊆V and E′⊆E; then, S is called a subgraph of G. If E′ contains all the edges e=i,j∈E with i,j∈V′, then S is called an induced subgraph of G and denoted as S⊆G.(2)
υ:2G⟶ℝ is called the value function or characteristic function with υ∅=0, where 2G is the collection of all the induced subgraphs of G. It should be noted that υ is required to satisfy four axioms of value [6].
For every induced subgraphS⊆G, that is, S∈2G, the value function υS can be expressed as a pseudological function υ:Dn⟶ℝ by using the logical variables; then, we have(7)υS=vx1S,x2S,…,xnS,S∈2G,where xiS∈D is a logical variable and(8)xiS=1,i∈S,0,i∉S.
Define a lexicographic order as(9)T≺S⟷dT>dS,where dR=∑i=1n2n−ixiR is a decimal number corresponding to each induced subgraph R∈2G, and its binary number is bR=x1Rx2R⋯xnR. That is, we can describe bR1=11…11, bR2=11…10, bR3=11…01, ⋯, bR2n=00…00.
Using Theorem1, for every pseudological function υ, we can find its structure vector Cv∈ℝ2n, such that equation (7) can be expressed into its matrix form as(10)υS=CvxS,where xS=∝imes∝i=1nxiS∈Δ2n and Cv:=υbR1, υbR2,…,υbR2n. Because of υ∅=0, the last element of Cv is 0, that is, υbR2n=0.


## 2.1. Semitensor Product of Matrices

The basic technique used in this paper is the STP of matrices. We can refer to [11] for details.Definition 1.
LetM∈ℳm×n, N∈ℳp×q, and t=lcmn,p be the least common multiple of n and p. The STP of M and N is defined as(1)M∝imesN≔M⊗It/nN⊗It/p∈ℳmt/n×qt/p,where ⊗ is the Kronecker product. As a generalization of the conventional matrix product, the STP of matrices keeps the useful properties of the conventional matrix product available. For convenience, the symbol ”∝imes” may be omitted without confusion.
Next, we present some properties of the STP used in this paper.Proposition 1.
LetX∈ℝm be a column and M be a matrix. Then,(2)X∝M=Im⊗MX.
The STP has pseudocommutative properties, and the swap matrix is defined as follows.Definition 2.
The matrixWm,n∈ℳmn×mn, defined by(3)Wm,n=δmn1,m+1,…,n−1m+1;2,m+2,…,n−1m+2;…;m,2m,…,nm,is called the m,nth dimensional swap matrix.Proposition 2.
LetX∈ℝm and Y∈ℝn be two columns. Then,(4)Wm,n∝X∝Y=Y∝X.
Ifx is a logical variable, then x∈D. To use vector expression of logical values, we identify 1∼δ21∈Δ and 0∼δ22∈Δ. Now, a pseudological (or logical) function can be expressed as an algebraic form.Theorem 1.
Letf:Dn⟶ℝ (or f:Dn⟶D) be a pseudological (or logical) function. Then, there exists a unique vector (or matrix) Mf∈ℝ1×2n (or Mf∈ℒ2×2n), such that(5)fx1,x2,…,xn=Mf∝i=1nxi,where Mf is called the structure vector (or matrix) of f, which can be calculated as(6)ColjMf=fδknj,j=1,2,…,kn.


## 2.2. Graphical Cooperative Games

In essence, a canonical cooperative game involves a set of players, denoted byN=1,2,…,n, who seek to form cooperative groups in order to strengthen their positions in the game. Any subset of N is called a coalition, and N is called the grand coalition. The second fundamental concept of the canonical cooperative game is the characteristic function or value function, denoted by υ:2N⟶ℝ with υ∅=0, which quantifies the worth of a coalition in a game. Therefore, a canonical cooperative game can be denoted by a pair N,υ [4]. In general, we can identify a cooperative game N,υ with its value function υ, since for every υ a different game may be defined.Next, we give the definition of graphical cooperative games.Definition 3.
(see [6]). A graphical cooperative game is denoted by Γ=G,υ, where(1)
G=V,E is an undirected graph with V=1,2,…,n a finite nonempty set of players and E⊆V×V a set of edges. The elements of V are also called nodes or vertices. The number of elements in V is called the order or size of G and is denoted as G=n. In this paper, we only consider that G is a simple graph, that is, G does not contain self-loops and multiple edges. Let S=V′,E′ be a graph such that V′⊆V and E′⊆E; then, S is called a subgraph of G. If E′ contains all the edges e=i,j∈E with i,j∈V′, then S is called an induced subgraph of G and denoted as S⊆G.(2)
υ:2G⟶ℝ is called the value function or characteristic function with υ∅=0, where 2G is the collection of all the induced subgraphs of G. It should be noted that υ is required to satisfy four axioms of value [6].
For every induced subgraphS⊆G, that is, S∈2G, the value function υS can be expressed as a pseudological function υ:Dn⟶ℝ by using the logical variables; then, we have(7)υS=vx1S,x2S,…,xnS,S∈2G,where xiS∈D is a logical variable and(8)xiS=1,i∈S,0,i∉S.
Define a lexicographic order as(9)T≺S⟷dT>dS,where dR=∑i=1n2n−ixiR is a decimal number corresponding to each induced subgraph R∈2G, and its binary number is bR=x1Rx2R⋯xnR. That is, we can describe bR1=11…11, bR2=11…10, bR3=11…01, ⋯, bR2n=00…00.
Using Theorem1, for every pseudological function υ, we can find its structure vector Cv∈ℝ2n, such that equation (7) can be expressed into its matrix form as(10)υS=CvxS,where xS=∝imes∝i=1nxiS∈Δ2n and Cv:=υbR1, υbR2,…,υbR2n. Because of υ∅=0, the last element of Cv is 0, that is, υbR2n=0.


## 3. Matrix Formula of the Shapley Value in Graphical Cooperative Games

In this section, we give a matrix formula to calculate the Shapley value in graphical cooperative games in order to reduce the computational complexity. First, we define the Shapley value of playeri in graphical cooperative games.Definition 4.
(see [6]). Consider a graphical cooperative game Γ=G,υ; the Shapley value of player i is defined as(11)φυGi=1G∑S⊆G\iυS∪i−υSG|−1VertS,i=1,2,…,n,where S⊆G\i means S is an induced subgraph of G\i, and S∪i is an induced subgraph of G that contains all the players in S and player i.
SinceG=n, then we have(12)G−1VertS=Cn−1S=n−1!S!n−1−S!.
Plugging it into (11) yields(13)φυGi=∑S⊆G\iS!n−1−S!nn−1!υS∪i−υS=∑S⊆G\iS!n−1−S!n!υS∪i−υS.
According to (10), we have the matrix expression as(14)υS∪i−υS=Cvx1S⋯xi−1S10xi+1S⋯xnS−x1S⋯xi−1S01xi+1S⋯xnS=CvW2,2i−110x1S⋯xi−1Sxi+1S⋯xnS−W2,2i−101x1S⋯xi−1Sxi+1S⋯xnS=CvW2,2i−11−1x1S⋯xi−1Sxi+1S⋯xnS,where ⋉nj≠ij=1xjS∈Δ2n−1, and in vector form,(15)xjS=δ21,j∈S,δ22,j∉S.
It follows that(16)x1S⋯xi−1Sxi+1S⋯xnS=δ2n−1j,j=1,2,…,2n−1.
According to Definition2, we have(17)W2,2i−11−1=diag1−1,…,1−1︸2i−1∈ℳ2i×2i−1.
Then, we obtain that(18)W2,2i−11−1δ2n−1j=W2,2i−11−1⊗I2n−iδ2n−1j=ColjTi,where(19)Ti=W2,2i−11−1⊗I2n−i=diagI2n−i−I2n−i,…,I2n−i−I2n−i︸2i−1∈ℳ2n×2n−1.
Similar to the construction in [10], we construct a vector ℓj as follows:(20)ℓ1=10,ℓk+1=ℓk+12kℓk∈ℝ2k+1,k=1,2,3,….
LetS=δ2n−1α=ℓn−1α, α=1,2,…,2n−1, where ℓn−1α denotes the αth element of ℓn−1. Use ℓn−1 to construct a new column vector ηn−1=ηn−11,ηn−12,…,ηn−12n−1T, where(21)ηn−1α=ℓn−1α!n−1−ℓn−1α!,α=1,2,…,2n−1.
Setξ=ηn−1, and we divide ξ into k equal blocks as follows:(22)ξ=ξk1,ξk2,…,ξkkT,k=1,2,22,…,2n−1.
That is, whenk=2, then ξ can be divided into two equal blocks ξ=ξ21ξ22, …, and when k=2n−1, then ξ=ξ2n−11,ξ2n−12,…,ξ2n−12n−1T.
Based on the abovementioned derivation, the Shapley value (13) can be written as(23)φυGi=1n!∑j=12n−1Cvηn−1jW2,2i−11−1δ2n−1j=1n!Cv⋅∑j=12n−1ηn−1jColjTi=1n!Cv⋅ξ2i−11−ξ2i−11ξ2i−12−ξ2i−12⋮,ξ2i−12i−1−ξ2i−12i−1,i=1,2,…,n.
Then, we have the following result for calculating the Shapley value in graphical cooperative games.Theorem 2.
Consider a graphical cooperative gameΓ=G,υ, its Shapley value can be calculated by the following matrix formula:(24)φυG=φυG1φυG2…φυGn=1n!Cv⋅Ξ,where(25)Ξ=ξ2n−11−ξ2n−11ξ21ξ2n−12ξ11−ξ21⋯−ξ2n−12−ξ11ξ22⋮−ξ22ξ2n−12n−1−ξ2n−12n−1∈ℳ2n×n.Remark 1.
In the conversional formula of the Shapley value (13), the computational complexity is On!2. Using the STP method, a simple matrix form of the Shapley value is provided in Theorem 2. Observing (24), in order to calculate the Shapley value, we just need to discuss the computational complexity of matrix Ξ. Obviously, the dimension of Ξ is 2n×n and with the help of MATLAB, the matrix Ξ can be easily obtained by using the recursive algorithm, which is the major advantage of Theorem 2.


## 4. Practical Examples of Graphical Cooperative Games

In this section, we consider some practical examples of graphical cooperative games, which are presented in [6]. These examples show the applications of graphical cooperative games to communication network of sensor nodes. Nodes communicate with each other through links.Example 1.
Assume that the value of a communication network is the number of nodes pairs which can communicate with each other; then, the value function for a connected graph of sizen is(26)υn=Cn2,n>1,0,n=1.
Three different communication networks between six nodes are shown in Figure1.
Using (10), the value function of graph Ga shown in Figure 1(a) can be expressed as(27)υGaS=CvGa<ime∝i=16xiS,where CvGa∈ℝ26 is a row vector; using (26), it is easy to calculate that(28)CvGa=6443433342212111311010003110100042212111311010003110100031101000.
Then, we construct a column vectorℓ5∈ℝ25 as(29)ℓ5=54434332433232214332322132212110T.
According to (21), a new column vector ξ can be calculated as(30)ξ=120242412241212122412121212121224241212121212122412121224122424120T.
Now, we divideξ into k equal blocks, where k=1,2,22,23,24,25.
Using Theorem2, we have(31)Ξ=1201201201201201202424242424−12024242424−1202412121212−24−24242424−1202424121212−2412−24121212−24−2412121212−12−12−12⋮⋮⋮⋮⋮⋮−12−12−12121212−12−12−122424−12−12−12−1224−1224−24−24−24120−24−24−12−12−12−122424−24−24−24−24120−24−24−24−24−24−24120−120−120−120−120−120−120∈ℳ26×6.According to (24), we can easily obtain its Shapley value by using MATLAB software, which is presented as(32)φυGa=16!CvGa⋅Ξ=0.8331.3330.833111.
Similarly, the Shapley value of each node in Figures1(b) and 1(c) can also be given by(33)φυGb=16!CvGb⋅Ξ=1.6674.1671.6673.8331.8331.833,φυGc=16!CvGc⋅Ξ=2.353.6831.752.652.5172.05,where(34)CvGb=151010643331066321113110100031101000106632111633110003110100031101000,CvGc=1510106106331066363116310310063103100106632111633110003110100031101000.
It is shown that, in three network graphs, the only difference is the structure vector of value function, which is dependent of its corresponding communication graph. Therefore, for a communication network with the same number of nodes, the matrixΞ is the same. Besides, it is to be noted that our computational results coincide with the values presented in [6].
Based on the above calculated Shapley values, it can be seen that the more a node is involved in the communication network, the more is its Shapley value. For example, in Figure1(a), node 2 is more vital than any of the nodes 4, 5, and 6, since node 2 exclusively supports the communication between nodes 1 and 3. Comparing Figures 1(b) and 1(c), the addition of new link between nodes 1 and 5 in Figure 1(c) can support the communication between nodes 1 and 5, which is exclusively supported by the link between nodes 2 and 4 in Figure 1(b); hence, it assigns more Shapley values to nodes 2 and 4 in Figure 1(b).
The following example presented in [6] shows that, for some communication networks with special structure topologies, the Shapley value can be simple to calculate regardless of the number of players.Figure 1
Communication network graphs.
(a)(b)(c)Example 2.
Consider a network withn nodes, the structure topology between them is a star graph with node 1 as the star point. In [6], a simple formula to compute the Shapley value of each node is given and this formula holds for any number n of nodes. Using our matrix formula (24) in Theorem 2, it is also easy to calculate the Shapley value, and it is shown that, for the star graph between n nodes, the computational complexity between the formula in [6] and our matrix formula (24) is the same. Moreover, it is obvious that, in a star graph for the structure vector Cv of value function in (10), the last ℝ2n−1 elements of Cv are all 0, since x1S=0. For example, when n=6, the network graph is described in Figure 2, and its structure vector can be calculated that(35)Cv=15,10,10,6,10,6,6,3,10,6,6,3,6,3,3,1,10,6,6,3,6,3,3,1,6,3,3,1,3,1,1,0,0,…,0∈ℝ26.
Using (24), where Ξ is the same as in example 1, we have its Shapley value as(36)φυG1=5.833,φυGi=1.833,i=2,…,6.
It is established that node 1 is the most vital node in this communication graph.
From these two simple examples, it is worth noting the advantage of our result in Theorem2. Regardless of the structure topology for communication networks, we only need to calculate the matrix Ξ, which is easily obtained by using recursive algorithm with the help of MATLAB. However, it is pointed in [6] that the Shapey value is computationally expensive and for a fairly large graph even one time computation is not affordable.Figure 2
Star graph with six nodes.


## 5. Conclusion

This paper considers a new class of cooperative games, called graphical cooperate games. Using the STP method, the value function is presented as a pseudo-Boolean function, and a corresponding formula is obtained to calculate the Shapley value for graphical cooperate games. Then, the worth of each player in a coalition based on its connectivity in communication network can be explored. Some examples are given to demonstrate the theoretical results. In our future work, we will study more useful properties of graphical cooperative games based on the Shapley value.With the rapid development of science, the game-theoretic approach will be a promising new method for studying more control problems in the future, such as synchronization [42–49], and consensus problems [50–53].



---

*Source: 2045654-2020-05-22.xml*