# The Efficient Proportional Myerson Values for Hypergraph Games

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

---

## Abstract

This study deals with a class of efficient extensions of Myerson value for games with hypergraph communication situations in which the surplus is allocated proportionally. We introducew-fairness of surplus and provide axiomatic characterizations of the new allocation rule. Furthermore, we give an example of research fund distribution amongst researchers, compare the numerical results with several values, and realize other efficient extensions of Myerson value can be obtained depending on the different measure function w on the hypergraph.


---

## Body

## 1. Introduction

Cooperative games with transferable utility (TU-game) [1] usually describe situations in which a viable alliance can be formed and earn the corresponding worth by cooperating. However, in many situations, viable alliance is restricted by some hierarchical, cultural, or communicational technology constraints. For this reason, Myerson [2] introduced the Myerson value which is a kind of Shapley value [3] depended on graph and characterized by component efficiency and fairness. Later, Myerson [4] and Slikker and van den Nouweland [5] studied other axiomatic characterizations of the Myerson value. In recent years, several works have devoted to the study of Myerson value. Li and Shan [6–8] studied the Myerson value on structures of coalitions or for directed graph games. van den Nouweland [9] and Shan and Zhang [10] extended the idea initiated by Myerson to hypergraph games.The Myerson value satisfying component efficiency, i.e., the worth of every component, is distributed among its members. However, in many situations, every player obtains distribution of the worth generated by the grand coalition such as research fund distribution amongst researchers. Motivated by this idea, van den Brink [11] introduced the efficient egalitarian Myerson value (EEMy) for graph games which is the first efficient extension of the Myerson value. Beal [12] proved that EEMy is the unique efficient and fair extension of Myerson value. Casajus [13–16] introduced the efficient two-step egalitarian surplus Myerson value (ESMy) on graph communication situations which is the first nonfair efficient extension of the Myerson value. However, an axiomatic characterization of the efficient extension of the Myerson value for hypergraph games remains an open problem. Motivated by the above discussion, we investigate a class of efficient extensions of the Myerson value for games with hypergraph communication situations in which the surplus is allocated proportionally.The rest of this paper is organized as follows. In Section2, we provide some preliminaries on TU-games, the graph, and the hypergraph games’ allocation rule. In Section 3, we propose a class of efficient extensions of the Myerson value, provide a characterization of EwMy, and give an example of research fund distribution amongst researchers. Section 4 concludes with some remarks.


## 2. Preliminaries

A transferable utility game (TU-game) represented by a pairN,v, where N=1,2,…,n, is a set of players and v:2N⟶ℝ is a characteristic function with v∅=0. An allocation rule (A value) is a function about the payoff of player in a TU-game. A very famous value is the Shapley value: Shvi=∑S⊆NN−S!S−1!/N!vS−vS∖i,i∈N.The tripleN,v,H represents a hypergraph games, which is composed of two parts: the TU-game N,v and the hypergraph structure N,H on N, where H⊆HN≔e⊆N|e≥2; i.e., H is a family of nonsingleton subsets of N, called hyperlinks. In particular, a hypergraph N,H is a graph if e=2.For each playeri∈N, Hi≔e∈H|i∈e is the set of hyperlinks containing i in N,H. A node i∈N is incident to a hyperlink e∈H if i∈e. Two nodes i,j∈N are adjacent if there is a hyperlink e in H satisfying i,j∈e. We say that nodes i and j are connected inN,H if there exists is a sequence i=i1,e1,i2,e2,…,ik,ek,ik+1=j such that il,il+1∈el, for l=1,2,…,k. A hypergraph is connected if every pair of nodes is connected. Connectedness in N,H induces a partition of N into components. A component is a maximal set of nodes of N in which every pair of nodes are connected. Let N/H be the set of components of N,H and N/Hi be the component containing i∈N. We denote by HG the set of all hypergraph games and G the set of all graph games. Hypergraph (graph) games are called connected if the associated hypergraph (graph) is connected. We denote, by HGC, the class of all connected hypergraph games and, GC, the class of all connected graph games.An allocation rule or valuefN,v,H on hypergraph communication situations is a n-dimensional vector function defined on hypergraph games. The Myerson value for hypergraph communication situations is defined as follows:(1)MyiN,v,H=ShiN,vH,for anyi∈N,where vHS=∑T∈S/HvT for any S⊆N. The game N,vH is called the point game.The Myerson value is the unique hypergraph games’ allocation rule which satisfies component efficiency (CE) and fairness (F).Component efficiency (CE): For any N,v,H∈HG and C∈N/H,(2)∑i∈CfiN,v,H=vC.Fairness (F): For any N,v,H∈HG and ij∈H,(3)fiN,v,H−fiN,v,H∖ij=fjN,v,H−fjN,v,H∖ij.More axioms for efficiency extensions of the Myerson value are as follows.Efficiency (E): For any N,v,H∈HG,(4)∑i∈NfiN,v,H=vN.Coherence with the Myerson value for connected hypergraphs (CMC): For any N,v,H∈HGC,(5)fN,v,H=MyN,v,H.


## 3. A Class of Efficient Extensions of Myerson Value for Hypergraph Games

In this section, we propose a class of efficient extensions of the Myerson value which distributes the surplus of the Myerson value by defining some measure functionw on hypergraph. Let N,v,H be any hypergraph games and let us define a function w: N,H⟶R which assigns to every player i∈N, a real number wiN,H. We define the efficientw−proportional Myerson valueEwMy:(6)EwMyiN,v,H=MyiN,v,H+wiN,H∑k∈NwkN,HvN−vHN.In order to characterizeefficientw−proportional Myerson valueEwMy, we propose the following property.w-fairness of surplus (FSw): a value on HG satisfies FSw if, for any N,v,H∈HG and any i,j∈N,(7)1wiN,HξiN,v,H−ξiCi,vCi,HCi=1wjN,HξjN,v,H−ξjCj,vCj,HCj.Then, we provide a characterization ofEwMy.Theorem 1.
The efficient extension Myerson valueEwMy on hypergraph communication situations is the unique allocation which satisfies efficiency(E), w-fairness of surplus (FSw), and coherence with the Myerson value for connected hypergraphs (CMC).Proof.
(existence). Let N,v,H is any hypergraph games. It is easy to see that EwMyN,v,H satisfies E and CMC.
Next, we prove thatEwMyN,v,H satisfies w-fairness of surplus (FSw). By the definition of EwMyN,v,H, we have(8)1wiN,HEwMyiN,v,H−EwMyiCi,vCi,HCi=1wiN,HMyiN,v,H+wiN,H∑k∈NwkN,HvN−vHN−MyiCi,vCi,HCi=1wiN,HMyiCi,vCi,HCi+wiN,H∑k∈NwkN,HvN−vHN−MyiCi,vCi,HCi=1∑k∈NwkN,HvN−vHN,where the second equality follows from the component decomposability of the Myerson value. Similarly, we have(9)1wjN,HEwMyjN,v,H−EwMyjCj,vCj,HCj=1wjN,HMyjN,v,H+wjN,H∑k∈NwkN,HvN−vHN−MyjCj,vCj,HCj=1wiN,HMyjCj,vCj,HCj+wjN,H∑k∈NwkN,HvN−vHN−MyjCj,vCj,HCj=1∑k∈NwkN,HvN−vHN.
Therefore, we obtain(10)1wiN,HEwMyiN,v,H−EwMyiCi,vCi,HCi=1wjN,HEwMyjN,v,H−EwMyjCj,vCj,HCj.
Hence,EwMyiN,v,H satisfies FSw. To show uniqueness and recall FSw,(11)1wiN,HξiN,v,H−ξiCi,vCi,HCi=1wjN,HξjN,v,H−ξjCj,vCj,HCj=t.
There exists a constantt, such that(12)ξiN,v,H−ξiCi,vCi,HCi=twiN,H,for alli∈N.
We have(13)ξiN,v,H=ξiCi,vCi,HCi+twiN,H.
By summing up over alli∈N, we obtain(14)∑i∈NξiN,v,H=∑i∈NξiCi,vCi,HCi+t∑i∈NwiN,H,
By efficiency,∑i∈NξiN,v,H=vN and ∑i∈NξiCi,vCi,HCi=vHN. Thus,(15)vN=vHN+t∑i∈NwiN,H.
Then,t=1/∑i∈NwiN,HvN−vHN. By equation (13), we obtain(16)ξiN,v,H=ξiCi,vCi,HCi+wiN,H∑i∈NwiN,HvN−vHN.
Sinceξ satisfies CMC, then ξiCi,vCi,HCi=MyiCi,vCi,HCi. Furthermore, MyiCi,vCi,HCi=MyiN,v,H because of component decomposability of the Myerson value. Hence,(17)ξiN,v,H=MyiN,v,H+wiN,H∑i∈NwiN,HvN−vHN.
Obviously,ξiN,v,H=EwMyiN,v,H, as desired.In particular, whenwiN,H=c(c is nonzero constant), w−fairness of surplus is reduced to fairness of surplus:(18)fiN,v,H−fiCi,vCi,HCi=fjN,v,H−fjCj,vCj,HCj.and(19)EwMyiN,v,H:=MyiN,v,H+wiN,H∑k∈NwkN,HvN−vHN=MyiN,v,H+cNcvN−vHN=MyiN,v,H+vN−vHNN=EEMyiN,v,H.Theorem 2.
The efficient egalitarian Myerson valueEEMy on hypergraph communication situations is the unique allocation satisfy efficiency (E), fairness of surplus (FS), and coherence with the Myerson value for connected hypergraphs (CMC).Furthermore, when restrict hypergraph communication situationsN,v,H to graph communication situations N,v,L and wiN,H=c, we obtain the conclusion of van den Brink et al. [11] as an immediate consequence of Theorem 1:(20)EEMyiN,v,L≔MyiN,v,L+vN−vLNN,Theorem 3.
The efficient egalitarian Myerson valueEEMy on graph communication situations is the unique allocation satisfy efficiency (E), fairness of surplus (FS), and coherence with the Myerson value for connected graphs (CMC).WhenwiN,H=1/Ci, w−fairness of surplus is reduced to per capita fairness of surplus:(21)CifiN,v,H−fiCi,vCi,HCi=CjfjN,v,H−fjCj,vCj,HCjand(22)EwMyiN,v,H:=MyiN,v,H+1/Ci∑k∈N1/CkvN−vHN=MyiN,v,H+vN−vHNN/HCi=ESMyiN,v,H.Theorem 4.
The efficient two-step egalitarian surplus Myerson valueESMy on hypergraph communication situations is the unique allocation satisfy per capita fairness of surplus (PRFS), efficiency (E), and coherence with the Myerson value for connected hypergraphs (CMC).Furthermore, when restricting hypergraph communication situationsN,v,H to graph communication situations N,v,L and wiN,H=1/Ci, we obtain the conclusion of Casajus which introduced the efficient two-step egalitarian surplus Myerson value(ESMy) on graph communication situations [13] as another immediate consequence of Theorem 1:(23)ESMyiN,v,L≔MyiN,v,L+vN−vLNN/LT.Theorem 5.
The efficient two-step egalitarian surplus Myerson valueESMy on graph communication situations is the unique allocation which satisfies per capita fairness of surplus (PRFS), efficiency (E), and coherence with the Myerson value for connected graphs (CMC).Example 1.
Consider a problem of research fund distribute amongst researchers. Suppose fund total amounts is 4,A is a researcher of subject one, D is a researcher of subject two, B,C are the researchers of subject one and subject two, E is a researcher of subject there, and hypergraph communication situations is N,v,H with Figure 1, where N=A,B,C,D,E, H=A,B,C,B,C,D, and vS=S−1,S=1,2,3,4,5.
The Shapley value ofv is efficient and Shv=4/5,4/5,4/5,4/5,4/5. The Myerson value is component efficient and Myv,H=2/3,5/6,5/6,2/3,0. Although fund amounts is 4, by component efficient, the total amount of the Myerson value is 3. Fund surplus is vN−vHN=4−3=1.
On the one hand,vN−vHN/N=1/5, efficientw−proportional Myerson valueEwMywiN,H=c reduces to efficient egalitarian Myerson value EEMy, i.e., EwMyv,H=EEMyv,H=13/15,31/30,31/30,13/15,1/5, the allocation satisfy FS:fiN,v,H−fici,vci,Hci=fjN,v,H−fjcj,vcj,Hcj=1/5.
On the other hand,vN−vHN/N/HCi=1/2∗4,i=A,B,C,D, vN−vHN/N/HCi=1/2∗1,i=E, and efficientw−proportional Myerson valueEwMy(wiN,H=1/Ci) reduce to efficient two-step egalitarian surplus Myerson value ESMy, i.e., EwMyv,H=ESMyv,H=19/24,23/24,23/24,19/24,1/2, and the allocation satisfies PRFS: CifiN,v,H−fici,vci,Hci=CjfjN,v,H−fjcj,vcj,Hcj, 4∗1/8=1∗1/2=1/2.Figure 1
Fund distribution amongst researchers.


## 4. Conclusion

In this paper, we investigate a class of efficient extensions of the Myerson value for hypergraph games and provide a characterization ofEwMy. When restricting hypergraph games to graph games, we obtain the conclusion of van den Brink et al. and Casajus as an immediate consequence. Further research can consider degree and probabilistic hypergraph efficient extensions of the Myerson value.



---

*Source: 1468979-2021-06-29.xml*