# A Decomposability Property to the Weighted Myerson Value and the Weighted Position Value

Authors: Guangming Wang; Erfang Shan
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Myerson value and position value are important values in a cooperative game with a graph structure. Usually, due to the differences of players in the game, the weighted Myerson value and weighted position value are more widely used in practical situations. This article offers a new calculation approach of the weighted Myerson value and weighted position value. Instead of using induced games (point game and edge game), we prove that the weighted Myerson value and weighted position value meet decomposability property.


---

## Body

## 1. Introduction

Transferable utility game (TU game) [1] usually assumes that a viable alliance can be formed between any players in the game. However, due to the influence of different cultures and backgrounds as well as social classes, hierarchies, organization structure, or communication technology constraints, alliance cannot be formed between any players in the game. In order to solve it, some efforts have been made to deal with this problem. Myerson firstly introduced Myerson value and proposed the method of graph-restricted game (point game), where the points in the graph represent the players in the game, and the edges represent the cooperative relationship between the players [2]. Myerson value is a kind of Shapley value depended on graph [3]. Later, Myerson, Slikker, and van den Nouweland studied other axiomatic characterizations of Myerson value, respectively, see Refs. [4, 5]. From then on, an increasing interest has been devoted to the study of Myerson value. Li and Shan studied Myerson value on local structures of coalitions and Myerson value for directed graph games, see Refs [6–8]. In addition, van den Nouweland et al. extended the idea initiated by Myerson to hypergraph games and stable system games, respectively, see Refs. [9, 10]. Motivated by point game, Borm et al. proposed the edge game by using the Shapley value of the edge to obtain the position value [11]. Meessen extended position value on the acyclic graph and axiomatic characterizations of position value [12]. Later, Slikker obtained a complete characterization of the position value on any graph game [13]. Li and Shan studied position value of the structures of graphs [14]. Shan and Zhang investigated position value and the Myerson value for hypergraph [15].However, in many practical situations, a player in the game has many differences, such as different bargaining powers; it is necessary to give a corresponding weight to each player in the game. Haeringer proposed the weighted Myerson value, that is, the weighted Shapley value of the restricted game [16]. Later, Slikker and van den Nouweland extended the weighted Myerson value to layer structure based on the weight systems of Kalai et al. [17–19]. Xu et al. studied weighted harmonic game and matrix expression of Shapley value [20–23]. To calculate the Myerson value and the position value, we usually need to obtain the corresponding induced game firstly: the point game for the Myerson value and the edge game for the position value. However, induced game is too complex in most cases both in generation and follow-up calculation. Motivated by the above discussion, we investigate an approach that allows us to calculate the Myerson value or the position value in a similar way.The rest of this paper is organized as follows. In Section2, we provide some preliminaries on TU games, the weighted graph allocation rule, and the decomposability property. In Section 3, we prove that both weighted Myerson value and weighted position value can be calculated uniformly using the decomposability principle. Section 4 gives conclusions with some remarks.


## 2. Preliminaries

### 2.1. TU Games

A cooperative game with characteristic function is often referred to as transferable utility game (TU game) [1], represented by a pair N,v, where v:2N⟶ℝ is a characteristic function with v∅=0. A value or an allocation rule is a function about the payoff of player in a cooperative game. A very famous allocation rule is the Shapley value:(1)Shiv=∑S⊆NN−S!S−1!N!vS−vS∖i,i∈N.


### 2.2. Smallest Connected Set

The tripleN,v,L represents a graph game, which is composed of two parts: the TU game N,v and the graph structure N,L, L⊆i,j∈N×N:i≠j. Let Li=i,j∈L:j∈N be the set of edges in the graph L containing point i∈N. The dissimilarity points i1,i2,…,ik are called a path of L. If there is a path between two points i,j, then i and j are connection. If S is connection in N,LS and not connection in N,A for any A⊂LS,A≠LS, then we denote by MCLeS the smallest connected (edge) set LS⊂L in N,L.


### 2.3. The Weighted Graph Allocation Rule and Decomposability Property

(a)
The weighted graph allocation rule of the point game:(2)cirθN,L=θiδiN,DL∑j∈DLθj,i∈N,whereθi represents the weight of i and DL represents the set of nonisolated points in the graph N,L. In particular, cirθN,L=δiN,DL/|DL|, if θi=θj for any i,j∈N.(b)
The weighted graph allocation rule of the edge game:(3)dirθN,L=∑ih∈Liθi/θi+θhL,i∈N,whereθi represents the weight of i and DL represents the set of nonisolated points in the graph N,L. In particular, dirθN,L=diN,L/2L, if θi=θj for any i,j∈N, where diN,L represents the degree of the i in the graph.(c)
For anyN,uS,L,S⊂N, S≥2,MCLeS=LkSk=1rS≠ϕγN,uS,L=∑k=1rShN,LkS−∑k≠mhN,LkS∪LmS+⋯+−1rS+1hN,∪k=1rSLkS. We will say that γ meets decomposability property.


## 2.1. TU Games

A cooperative game with characteristic function is often referred to as transferable utility game (TU game) [1], represented by a pair N,v, where v:2N⟶ℝ is a characteristic function with v∅=0. A value or an allocation rule is a function about the payoff of player in a cooperative game. A very famous allocation rule is the Shapley value:(1)Shiv=∑S⊆NN−S!S−1!N!vS−vS∖i,i∈N.


## 2.2. Smallest Connected Set

The tripleN,v,L represents a graph game, which is composed of two parts: the TU game N,v and the graph structure N,L, L⊆i,j∈N×N:i≠j. Let Li=i,j∈L:j∈N be the set of edges in the graph L containing point i∈N. The dissimilarity points i1,i2,…,ik are called a path of L. If there is a path between two points i,j, then i and j are connection. If S is connection in N,LS and not connection in N,A for any A⊂LS,A≠LS, then we denote by MCLeS the smallest connected (edge) set LS⊂L in N,L.


## 2.3. The Weighted Graph Allocation Rule and Decomposability Property

(a)
The weighted graph allocation rule of the point game:(2)cirθN,L=θiδiN,DL∑j∈DLθj,i∈N,whereθi represents the weight of i and DL represents the set of nonisolated points in the graph N,L. In particular, cirθN,L=δiN,DL/|DL|, if θi=θj for any i,j∈N.(b)
The weighted graph allocation rule of the edge game:(3)dirθN,L=∑ih∈Liθi/θi+θhL,i∈N,whereθi represents the weight of i and DL represents the set of nonisolated points in the graph N,L. In particular, dirθN,L=diN,L/2L, if θi=θj for any i,j∈N, where diN,L represents the degree of the i in the graph.(c)
For anyN,uS,L,S⊂N, S≥2,MCLeS=LkSk=1rS≠ϕγN,uS,L=∑k=1rShN,LkS−∑k≠mhN,LkS∪LmS+⋯+−1rS+1hN,∪k=1rSLkS. We will say that γ meets decomposability property.


## 3. The Decomposability Property of the Weighted Values

In this section, we calculate the weighted Myerson value and weight position value using the weighted graph allocation rule. It is proved that both weighted Myerson value and weighted position value can be calculated uniformly using the decomposability principle.Firstly, we introduce the existing approach [11] as follows.Lemma 1.
IfN,uS,L∈CSN, S≥2,MCLeS=LkSk=1rS, then characteristic function of point game N,uSL is(4)uSL=1−∏k=1rS1−uDLkS,MCLeS≠ϕ,0,MCLeS=ϕ.Lemma 2.
IfN,uS,L∈CS0N, S≥2,MCLeS=LkSk=1rS, then characteristic function of edge game L,rLuS is(5)rLuS=1−∏k=1rS1−uLkS,MCLeS≠ϕ,0,MCLeS=ϕ.Theorem 1.
The weighted Myerson value meets the decomposability property.Proof.
IfN,uS,L∈CSN,S≥2,MCLeS=LKSk=1rS, according to Lemma 1,(6)μθN,uS,L=φθuSL=φθ1−∏k=1rS1−uDLKS,1−∏k=1rS1−uDLKS=∑k=1rSuDLkS−∑k≠muDLkS∪DLmS+⋯+−1rS+1u∪k=1rSDLkS.
For anyL1,L2⊂L,DL1∪L2=DL1∪DL2, we have(7)μθN,uS,L=∑k=1rSφθuDLkS−∑k≠mφθuDLKS∪LmS+⋯+−1rS+1φθuD∪k=1rSLkS.
Using expression in (2), it results in(8)μθN,uS,L=∑k=1rScrθN,LkS−∑k≠mcrθN,LkS∪LmS+⋯+−1rS+1crθN,∪k=1rSLkS.
Therefore, the weighted Myerson value meets the decomposability property.Theorem 2.
The weighted position value meets the decomposability property.Proof.
For anyi∈N,(9)πiθN,uS,L=∑ih∈Liθiθi+θhφihrLuS=∑jh∈Lθjθj+θhδjhL,LiφjhrLuS.
For anyjh∈L,φjhrLuS=φjh1−∏k=1rS1−uLkS, according to Lemma 2, we have(10)φjhrLuS=∑k=1rSφjhuLkS−∑k≠mφjhuLkS∪LmS+⋯+−1rS+1φjhu∪k=1rSLkS.
Moreover, we get(11)φjhrLuS=∑k=1rSδjhL,LkSLkS−∑k≠mδjhL,LkS∪LmSLkS∪LmS+⋯+−1rS+1δjhL,∪k=1rSLkS∪k=1rSLkS,and then, it results in(12)πiθN,uS,L=∑jh∈Lθjθj+θhδjhL,Li∑k=1rSδjhL,LkSLkS−∑jh∈Lθjθj+θhδjhL,Li∑k≠mδjhL,LkS∪LmSLkS∪LmS+⋯+−1rS+1∑jh∈Lθjθj+θhδjhL,LiδjhL,∪k=1rSLkS∪k=1rSLkS=∑jh∈Lθjθj+θh∑k=1rSδjhL,Li∩LkSLkS−∑jh∈Lθjθj+θh∑k≠mδjhL,Li∩LkS∪LmSLkS∪LmS+⋯+−1rS+1∑jh∈Lθjθj+θhδjhL,Li∩∪k=1rSLkS∪k=1rSLkS=∑k=1rS∑jh∈Lθjθj+θhδjhL,Li∩LkSLkS−∑k≠m∑jh∈Lθjθj+θhδjhL,Li∩LkS∪LmSLkS∪LmS+⋯+−1rS+1∑jh∈Lθjθj+θhδjhL,Li∩∪k=1rSLkS∪k=1rSLkS=∑k=1rS∑ih∈LkSθiθi+θh1LkS−∑k≠m∑ih∈LkS∪LmSθiθi+θh1LkS∪LmS+⋯+−1rS+1∑ih∈∪k=1rSLkSθiθi+θh1∪k=1rSLkS=∑k=1rS∑ih∈LkSθi/θi+θhLkS−∑k≠m∑ih∈LkS∪LmSθi/θi+θhLkS∪LmS+⋯+−1rS+1∑ih∈∪k=1rSLkSθi/θi+θh∪k=1rSLkS.
Therefore, the weighted position value meets the decomposability property, which completes the proof.Example 1.
LetN,us,L be a communication situation game with Figure 1,(13)N=1,2,3,4,5,L=1,2,2,3,2,4,2,5,3,4,4,5,S=1,4,θi=i,i=1,2,…,5,then(14)MCLe=L1S,L2S,L3S,L1S=1,22,3,3,4,L2S=1,2,2,4,L3S=1,2,2,5,4,5.
If the distribution ruleγθ is the weight Myerson value or weight position value, then(15)γθN,u1,4,L=hθN,L1S+hθN,L2S+hθN,L3S−hθN,L1S∪L2S−hθN,L1S∪L3S−hθN,L2S∪L3S+hθN,L1S∪L2S∪L3S.
Ifhθ=crθ, the weighted Myerson value can be obtained as follows:(16)μθN,u1,4,L=110,210,310,410,0+17,27,0,47,0+112,212,0,412,512−110,210,310,410,0−115,215,315,415,515−112,212,0,412,512+115,215,315,415,515=17,27,0,47,0.
Ifhθ=drθ, the weighted position value can be obtained as follows:(17)πwN,u1,4,L=1/3,2/3+2/5,3/5+3/7,4/7,03+1/3,2/3+2/6,0,4/6,02+1/3,2/3+2/7,0,4/9,5/7+5/93−1/3,2/3+2/5+2/6,3/5+3/7,4/6+4/7,04−1/3,2/3+2/5+2/7,3/5+3/7,4/7,5/7+5/95−1/3,2/3+2/6+2/7,0,4/6+4/9,5/7+5/94+1/3,2/3+2/5+2/6+2/7,3/5+3/7,4/6+4/7+4/9,5/7+5/96=1990,16133150,9175,17105,463.
In particular, ifS=1,4,θi=1,i=1,2,…,5, the weighted Myerson value and the weighted position value are Myerson value and position value, respectively, the following calculation can be obtained:(18)μN,u1,4,L=13,13,0,13,0,πN,u1,4,L=1960,920,120,215,120.Figure 1
(N, L).


## 4. Conclusion

In this paper, a simpler weighted graph allocation rule which is used to calculate the weighted values has been investigated. Without the induced games, the weighted Myerson value and weight position value have been calculated by using the weighted graph allocation rule. It has been proved that both the weighted values can be calculated uniformly using the decomposability principle. In addition, it should be pointed out that the obtained results can be extended to the future research about Myerson with edge weight and point-edge mixed weight.



---

*Source: 5082947-2021-02-03.xml*