图上博弈的Page-Shapley值

The Page-Shapley values for graph games

对合作博弈(N,v)和交流图(N,L)所产生的交流局面(N,v,L),现有的分配法则都是重新定义一个特征函数,再归结为新特征函数的Shapley值.为了避免定义新特征函数时的失真(从而使得计算Shapley值出现一定偏差),本文提出一个新的分配法则.设原博弈(N,v)的Shapley值为Sh(N,v)=(s1,s2,…,sn),其中si可视为参与者i的实力.类似于Google的网络搜索算法,对连通的交流图L和表示参与者相互合作程度的转移矩阵P,定义参与者的PageRank(参与者的级别或地位),记为(r1,r2,…,rn),其中ri表示参与者i在合作交流中的地位.新的分配法则,称为Page-Shapley值:其中参与者i所得为cNrisiv(N),而cN取为1/∑j∈N rjsj以便保证值的有效性.当L不连通时,其Page-Shapley值由各分支的Page-Shapley值拼接而成.

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 cNri si v(N),where cN=1/∑j∈N rjsj to ensure the component efficiency,and v(N)can be replaced by the real worth of N in the game restricted by L.