Abstract：Let (N,v) be a cooperative game and (N,L) a graph. Consider the communication situation (N,v,L). The known allocation rules are obtained by defining new characteristic functions and their Shapley values. To avoid the distortion from defining new characteristic functions, we propose a new allocation rule. Let Sh(N,v)=(s1,s2,…,sn) be the Shapley value for the original game (N,v), in which si can be viewed as the personal ability of the player i. Similar to Google search, we define PageRank for the graph (N,L) associated with a matrix of cooperative coefficients, denoted by (r1,r2,…,rn), where ri signifies the importance of the player i in communication graph (N,L). Then we define an allocation rule, called Page-Shapley value, as follows. Let (N,L) be a connected graph. In Page-Shapley value, the share of the player i is cNrisiv(N), where cN=1/∑j∈Nrjsj to ensure the component efficiency, and v(N) can be replaced by the real worth of N in the game restricted by L.
[1] Branzei R, Dimitrov D, Tijs S. Models in cooperative game theory[M]. Berlin:Springer, 2008. [2] Myerson R B. Graphs and cooperation in games[J]. Mathematics of Operations Research, 1977, 2(3):225-229. [3] Shapley L S. A value for n-person games[C]//Tucker A W, Kuhn H W. Contributions to the Theory of Games II. Princeton:Princeton University Press, 1953:307-317. [4] Myerson R B. Conference structures and fair allocation rules[J]. International Journal of Game Theory, 1980, 9:169-182. [5] van den Nouweland A, Borm P, Tijs S. Allocation rules for hypergarph communication situations[J]. International Journal of Game Theory, 1992, 20:255-268. [6] Khmelnitskaya A, Selçuk Ö, Talman D. The Shapley value for directed graph games[J]. Operations Research Letters, 2016, 44:143-147. [7] Calvo E, Lasaga J, Nouweland A. Values of games with probabilistic graphs[J]. Mathematical Social Sciences, 1999, 37:79-95. [8] Béal S, Rémila E, Solal P. Fairness and fairness for neighboirs:The difference between the Myerson value and component-wise egalitarian solutions[J]. Economics Letters, 2012, 117:263-267. [9] van den Brink R, Khmelnitskaya A, van der Laan G. An efficient and fair solution for communication graph games[J]. Economics Letters, 2012, 117:786-789. [10] Shan E, Zhang G, Dong Y. Component-wise proportional solutions for communication graph games[J]. Mathematical Social Sciences, 2016, 81:22-28. [11] Meessen R. Communication games[D]. Department of Mathematics, University of Nijmegen, Netherlands, 1988. [12] Borm P, Owen G, Tijs S. On the position value for communication situations[J]. SIAM Journal on Discrete Mathematics, 1992, 5:305-320. [13] Slikker M. A characterization of the position value[J]. International Journal of Game Theory, 2005, 33:505-514. [14] Ghintran A. Weighted position values[J]. Mathematical Social Sciences, 2013, 65:157-163. [15] Owen G. Values of games with a priori unions[C]//Henn R, Moeschlin O. Mathematical Economic and Game Theory. Springer-Verlag, 1977:76-88. [16] Peleg B. Introduction to the theory of cooperative games[R]. Jerusalem, Israel:Center for Research in Mathematical Economics and Game Theory, The Hebrew University, 1989. [17] Vázquez-Brage M, van der Nouweland A, García-Jurado I. Owen's coalitional value and aircraft landing fees[J]. Mathematical Social Sciences, 1997, 66:255-261. [18] 孙红霞, 张强. 具有联盟结构的限制合作博弈的限制Owen值[J]. 系统工程理论与实践, 2013, 33(4):981-987.Sun H X, Zhang Q. Model of payoff allocation for bi-cooperative game with fuzzy coalitions based on multilinear extension[J]. Systems Engineering-Theory & Practice, 2013, 33(4):981-987. [19] Page L. PageRank:Bringing order to the Web[R]. Stanford Digital Library Project, 1997. [20] Brin S, Page L. The anatomy of a large-scale hypertextual web search engin[J]. Computer Networks ISDN Systems, 1998, 30:107-117. [21] Perra N, Fortunato S. Spectral centrality measures in complex networks[J]. Phys Rev E, 2008, 78(3):036107. [22] Grolmusz V. A note on the PageRank of undirected graphs[J]. Information Processing Letters, 2005, 115:633-634. [23] 李理, 单而芳. 图上合作博弈和边密度[J]. 运筹学学报, 2018, 22(4):99-107.Li L, Shan E F. Graph games and edge density of graphs[J]. Operations Research Transactions, 2018, 22(4):99-107. [24] Bryan K, Leise T. The $25,000,000,000 eigenvector:The linear algebra behind Google[J]. SIAM Review, 2006, 48(3):569-581. [25] Dodsil C, Royle G. Algebraic graph theory[M]. Springer, New York, 2001. [26] Langville A, Meyer C. Google's PageRank and beyond:The science of search engin rankings[M]. Princeton University Press, New Jersey, 2005. [27] 詹兴致. 矩阵论[M]. 高教出版社, 北京, 2008.
2019, Vol. 39 
