一种满足线性与匿名条件的合作对策分量差值简化方法
一种满足线性与匿名条件的合作对策分量差值简化方法
【技术领域】
[0001] 本发明涉及效用可转移合作对策（简称TU合作对策）领域，特别是一种满足线性 与匿名条件的合作对策分量差值简化方法。
【背景技术】
[0002] 近年来，在效用可转移合作对策（简称合作对策或TU合作对策）领域，继Shapley 在 1953 年提出Shapley值之后，Banzhaf值、solidarity值、平均Shapley值、贴现Shapley 值、最小二乘预核仁、广义solidarity值等也被相继提出。一方面，它们的出现体现了合作 对策领域的繁荣，驳斥了"一些不成熟的报告所宣称的合作对策死期将至"的观点。但另一 方面，由于种类太多，而且没有进行很好的归类，从而给理论研宄和实际应用都带来了诸多 不便。为解决这一问题，目前对合作对策值（或简称值）的研宄工作出现了两种趋势。
[0003] -种是研宄对象从单个值转移到一类有共同特点的值。这其中同时满足有效 性、线性性及匿名性的值作为一个整体被研宄得比较多。Ruiz等、Juarez等、Nembua和 Andjiga、Nembua、Radzik和Driessen等都给出了这类值的显式解析表达式。Driessen和 Radzik先后研宄了这类值的势函数及一致性。他们的工作是Hart和Mas-Colell的扩展。 Malawski、Radzik和Driessencript给出了这类值满足一些常见公理的充要条件。
[0004] 另一种是在对值进行公理化刻画时，注重与其它值的刻画的可比较性，尤其是致 力于使得若干个值的刻画只相差一个公理或条件。早在1994年，Nowak和Radzik提出 so1idarity值时，他们给出的so1idarity值的刻画与Shap1ey对Shap1ey值的刻画就只相 差一个公理。这一公理关注哪一类局中人将获得0收益。随后，vandenBrink和Casajus 依次给出了平均值和平均剩余值的刻画。这些刻画与Shapley对Shapley值的刻画也只 相差一个公理。同样地，这一公理关注哪一类局中人将获得〇收益。与此类似，Kamojo和 Kongorscript同时给出了平均值、Shapley值及solidarity值的刻画。这三个刻画也只相 差一个公理。但这一公理不关注哪类局中人将获得0收益，而关注哪类局中人被踢出最大 联盟后，不会影响剩余局中人的收益。Kamojo和Kongo的工作充当了Casajus和Huettner 提出广义solidarity值的主要动机。Alonso-Meijide等对公理化刻画的利弊做了很好的 评论。
【发明内容】
[0005] 本发明的目的在于提供一种满足线性与匿名条件的合作对策分量差值简化方法， 以克服现有技术中存在的缺陷。
[0006] 为实现上述目的，本发明的技术方案是：一种满足线性与匿名条件的合作对策分 量差值简化方法，按照如下步骤实现：
[0007] 步骤S1 :任取vGGN，令v,GGN为该v的r-分队对策，对任意的S[iV，通过
[0008]
[0009] 获取v的r-分队向量：％= (n-l)Sh(v}且该％为一n维实向量；其中，TU合作 对策V，也即效用可转移合作对策V，是从有限集N的幂集到实数集的映射，v:2n-R，有限 集N= {1，2,…，n}即为局中人（编号）集合，有限集N的子集为（局中人）联盟S，G% 有限集N上TU合作对策v的全体；rG{1，2,…，n-1}，n为大于1的正整数；Sh为Shapley 值或Shapley向量；
[0010] 步骤S2 :判断TU合作对策V的待求满足线性与匿名性的值f的类型，根据所述值 f的类型，并通过式
[0012] 获取fi (V)与fj (V)的分量差值dij;其中，jGN\i，万e，对任意的SG汉，
[0014] 且对任意的rG{1，2,…，n-1}，均存在brGR，使得：
[0015] f^zr) =br{zr)：;
[0016] 所述值f:GN-Rn，对于任意的TU合作对策vGGN，均存在EieNfi(v)彡v(N)，fi(v)为用值f在有限集N间分配最大联盟的价值v(N)时，局中人i的收益，局中人i为所 述有限集N中的元素；
[0017] 步骤S3 :判断所述值f是否满足有效性，若满足，则结合所述值f的有效性获取所 述fj(v);否则，根据所述步骤S2中所述值f类型所对应的值f的定义计算(v)，完成fj(v) 获取。
[0018] 在本发明一实施例中，在所述步骤S2中，还包括如下步骤：
[0019] 步骤S21 :判断所述值f的类型，若所述值f为Shapley值，则转入步骤S22 ;若所 述值f为solidarity值，则转入步骤S23 ;若所述值f为广义solidarity值，则转入步骤 S24 ;若所述值f为贴现Shapley值，则转入步骤S25 ;若所述值f为Banzhaf值，则转入步 骤S26 ;
[0020] 步骤S22 :对任意的vGGlrG{1，2,…，n-1}，均存在：
[0022] 其中，Sh为Shapley值或Shapley向量，且结合式
[0024] 以及式
[0026] 得：对任意的vGGliGN、jGN，均存在：
[0028] 并转到步骤S3 ;
[0029] 步骤S23 :对任意的vGGlrG{1，2,…，n-1}，均存在：
[0031]其中，so为solidarity值或solidarity向量，且结合式
[0033]以及式
[0035]得：对任意的vGGliGN、jGN，均存在：
[0037] 并转到步骤S3;
[0038] 步骤S24:对任意的vGGlrG{1，2,…，n-1}，均存在：
[0040]其中，so4为广义solidarity值或广义solidarity向量，且结合式
[0042]以及式
[0044]得：对任意的vGGNSiGN、jGN，均存在：
[0046] 并转到步骤S3 ;
[0047] 步骤S25:对任意的vGGlrG{1，2,…，n-1}，均存在：
[0049]其中，Shs为贴现Shapley值或贴现Shapley向量，且结合式
[0051]以及式
[0053]得：对任意的vGGliGN、jGN，均存在：
[0055] 并转到步骤S3 ;
[0056] 步骤S26 :对任意的vGrG{1，2,…，n-1}，均存在：
[0058]其中，Ba为Banzhaf值或Banzhaf向量，且结合式
[0060]以及式
[0062] 得：对任意的vGGliGN、jGN，均存在：
[0064] 并转到步骤S3。
[0065] 在本发明一实施例中，在所述步骤S22中，对任意的vGiGN，局中人i在 v中的Shapley值为：
[0067] 对任意的iGNU
[0069]若!* =1，则
[0071]若r>l，则
[0073] 在本发明一实施例中，在所述步骤S23中，对任意的vGS^ ，记联盟S内 局中人对S的平均边际贡献为Aav(S，v)，即：
[0075] 则对任意的iGN，局中人i在v中的solidarity值为：
[0077] 对任意的iGNU
[0079]若！*=1，则
[0081]若r>l，则
[0083] 在本发明一实施例中，在所述步骤S24中，对任意的vGiGN，局中人i在 v中的广义solidarity值为：
[0085] 其中
，1 = 0, 2, 3,…，n;当 0 < | # 1 时， so4为广义solidarity值；
[0086] 对任意的iGNU
[0088]若！* = 1，则
[0090] 若r>l，则
[0091]
[0092] 在本发明一实施例中，在所述步骤S25中，对任意的vGiGN，局中人i在 v中的贴现Shapley值为：
[0094] 其中，贴现因子SG[0,1];
[0095] 对任意的iGNU
[0097]若!* =1，则
[0099]若r>l，则
[0101] 在本发 明一实施例中，在所述步骤S26中，对任意的VGiGN，局中人i在 v中的Banzhaf值为：
[0103] 对任意的iGNU
[0105]若r=l，则
[0107]若r>l，则
[0109] 在本发明一实施例中，若所述值f的类型为最小二乘预核仁，则对任意的veGnS igN，局中人i在V中的最小二乘预核仁为：
[0111] 且存在映射k:GN-R，使得对任意的vGiGN，均存在：
[0112] LSPNj(v)-Baj(v) =k(v),
[0114] 在本发明一实施例中，在所述步骤S3中，若所述值f满足对任意的vGGN，均存在 EiENfi(v) =v(N)，则称所述值f满足有效性。
[0115] 在本发明一实施例中，在所述步骤S3中，在所述值f满足有效性的情况下，通过解 线性方程组：
[0116]
对所有的jeN\i，
[0117] 其中，djf-dij，完成f」(v)获取；
[0118] 在所述值f不满足有效性的情况下，任取ieN，通过所述步骤S2中所述值f类型 所对应的值f的定义计算fi(v)，且对任意的jGN\i，结合式：
[0120] 完成f」(v)获取。
[0121] 相较于现有技术，本发明具有以下有益效果：本发明提出了一种满足线性与匿名 条件的合作对策分量差值简化方法，提出了满足线性与匿名要求的合作对策值的分量差值 显式解析表达式及其求解框架，进而给出同时若干种满足线性与匿名要求的合作对策分 量差值简化方法，相较于利用定义逐个计算Shapley值、solidarity值、广义solidarity 值、贴现Shapley值、最小二乘预核仁等的方法，极大地减少了计算工作量，具有较大优越 性与实用性。该方法丰富了合作对策的计算方法，可为开发决策支持系统提供方法支持。
【附图说明】
[0122] 图1为本发明中一种满足线性与匿名条件的合作对策分量差值简化方法的流程 图。
【具体实施方式】
[0123] 下面结合附图，对本发明的技术方案进行具体说明。
[0124] 本发明致力于给出满足匿名性与线性性的合作对策值的简化算法。特别地，如果 被研宄的合作对策值还满足有效性，那么使用本发明的计算方法将会更加简便、有效。提出 这一算法的动机来源于对迈克尔?乔丹问题的研宄，并提出了所谓的分队对策概念。分队 对策是指局中人数量为一常数的联盟价值不为〇的一类合作对策。在分队对策中，尽管不 同的满足匿名性与线性性的合作对策值将产生相同的局中人排序，但其中各分量差值却不 一定相同，且这些分量差值均由一个与具体值无关的向量所决定。本发明利用这一向量，给 出各种满足匿名性与线性性的合作对策值的分量差值显式解析表达式。进一步，由于利用 这些表达式来计算分量差值比较简单方便，本发明还提出利用它们来简化同时计算若干种 满足匿名性与线性性的合作对策值的过程。具体做法如下：如果所考虑的合作对策值不满 足有效性，则先通过该值的定义计算出它的一个分量，再利用分量差值得到其它的分量；如 果所考虑的值满足有效性，则直接利用有效性及分量差值来得到该值的所有分量。事实上， 相对于直接利用值的定义计算这些值的所有分量的做法，采用本发明所提出的方法的计算 量要小得多。这一点将通过具体的实施例分析来进行说明。
[0125] 本发明提供一种满足线性与匿名条件的合作对策分量差值简化方法，如图1所 示，按照如下步骤实现：
[0126]步骤S1 :任取vGGN，令'GGN为该v的r-分队对策，对任意的*通过
[0128]获取v的r-分队向量七=(n-l)Sh(vJ，且该z1?为一n维实向量；其中，TU 合作对策v是从有限集N的幂集到实数集的映射，v:2n-R，满足v(0) = 〇,有限集N= {1，2,…，n}即为局中人集合，有限集N的子集为联盟S，GNS有限集N上TU合作对策v的 全体；rG{1，2,…，n-1}，n为大于1的正整数；Sh为Shapley值；由于Shapley值满足有 效性，因而对任意的rG{1，2,L,n-1}，都有
[0129]步骤S2 :判断TU合作对策v的待求满足线性与匿名性的值f的类型，根据所述值 f?的类型并通过式：
[0131]获取f?与f」(v)的分量差值dij;其中，jGN\i，，对任意的Sd
[0133] 且对任意的rG{1,2,…，n-1}，均存在kGR，使得：
[0135] 所述值f:GN-Rn，对于任意的TU合作对策vGGN，均存在EieNfi(v)彡v(N)， fi(v)为用值f在有限集N间分配最大联盟的价值v(N)时，局中人i的收益，局中人i为所 述有限集N中的元素；
[0136] 步骤S3:判断所述值f?是否满足有效性，若满足，则结合所述值f?的有效性获取所 述A(v);否则，根据所述步骤S2中所述值f的类型所对应的值f的定义计算& (v)，完成 fj(V)获取；在本实施例中，由于在计算不同的满足匿名性与线性性的合作对策值时，％可 以被循环利用，因而采用本发明提出的方法将极大地减少同时求几种满足匿名性与线性性 的合作对策值的计算工作量。
[0137] 在本实施例中，在所述步骤S2中，还包括如下步骤：
[0138] 步骤S21:判断所述值f的类型，若所述值f?为Shapley值，则转入步骤S22;若所 述值f为solidarity值，则转入步骤S23 ;若所述值f为广义solidarity值，则转入步骤 S24 ;若所述值f为贴现Shapley值，则转入步骤S25 ;若所述值f为Banzhaf值，则转入步 骤S26 ;
[0139] 步骤S22 :对任意的vGG{1，2,…，n-1}，均存在：
[0141] 进一步地，在本实施例中，对任意的vGGNSiGN，局中人i在v中的Shapley 值为：
[0143]由Shapley值的定义，对任意的iGN，得
[0145]若r=l，则
[0147]若r>l，则
[0149]故式
成立，其中，Sh为Shapley值，且结合式
[0151]以及式
[0153] 得：对任意的vGGN及iGN、jGN，均存在：
[0155] 转到步骤S3;
[0156] 步骤S23 :对任意的vGGN及rG{1，2,…，n-1}，均存在：
[0158] 在本实施例中，对任意的vG6"及记联盟S内局中人对S的平均边际贡 献为Aav(S，v)，即：
[0160]则对任意的i G N，局中人i在v中的solidarity值为：
[0162]由solidarity值的定义，对任意的i G N，得
[0164]若！* = 1，则
[0166]若r>l，则
[0168]故式
成立，其中，so为solidarity值，且结合式
[0170]以及式
[0172] 得：对任意的v G Gl i G N、j G N，均存在：
[0174] 转到步骤S3;
[0175] 步骤S24 :对任意的vGGlrG{1，2,…，n-1}，均存在：
[0177] 进一步地，对任意的vGGNSiGN，局中人i在v中的广义solidarity值为：
[0179]其中
，1 = 0, 2, 3,…，n;当 0 < | # 1 时， so4为广义solidarity值；
[0180] 由广义solidarity值的定义，对任意的iGN，
[0182]若!* =1，则
[0184]若r>l，则
[0186]故式
成立，且当I=0,1/2时，so4分别退化为 Shapley值、solidarity值；so4 为广义solidarity值，且结合式
[0188]以及式
[0190]得：对任意的vGiGN、jGN，都有
[0192] 并转到步骤S3;
[0193]步骤S25 :对任意的vGG{1，2,…，n-1}，都有：
[0195] 进一步地，对任意的vGGNSiGN，局中人i在v中的贴现Shapley值为：
[0197] 其中，贴现因子5G[0, 1];当6 = 1时，Shs退化为Shapley值；
[0198] 在本实施例中，由贴 现Shapley值的定义，对任意的iGN，
[0200]若r=l，则
[0202]若r>l，则
[0204]故式
.成立，其中，Shs为贴现Shapley值，且结合式
[0206]以及式
[0208] 得：对任意的vGGNSiGN、jGN，都有：
[0210] 并转到步骤S3;
[0211]步骤S26 :对任意的vGG{1，2,…，n-1}，都有：
[0213] 对任意的vGGNSiGN，局中人i在v中的Banzhaf值为：
[0215] 在本实施例中，由Banzhaf值的定义，对任意的iGN，
[0217]若!* =1，则
[0219]若r>l，则
[0221] 故式
成立，其中，Ba为Banzhaf值，且结合式
[0223]以及式
[0225] 得：对任意的vGiGN、jGN，都有
[0227] 并转到步骤S3。
[0228] 在本实施例中，Banzhaf值满足匿名性与线性性，但不满足有效性，而最小二乘预 核仁不仅满足这三条性质，还能保持Banzhaf值的分量差值。若所述值f?的类型为最小二 乘预核仁，则对任意的vGiGN，局中人i在v中的最小二乘预核仁为：
[0230] 所谓保持分量差值是指存在映射k:GN-R，使得对任意的vGG"及iGN，均存 在：
[0231]LSPNj(v)-Baj(v) =k(v),
[0232]进而，
[0233] 进一步地，在本实施例中，在所述步骤S3中，若所述值f满足对任意的veGN，均 存在EieNfi(V) =V(N)，则称所述值f满足有效性。在所述步骤S2中，从N到N的双射 为N上的置换，记N上置换的全体为Q(N);若值f满足对任意的vGJrGQ(N)，都 有f(jiv) =jif(v)，则称f满足匿名性。这里：1)jtvGGN，对任意的, 3iv(S) =V〇 ―1 ⑶）；2) 31f(v) =(L⑴（V)，L⑵（V)，L,L(n) (V));若值f满足对任意的uGGn、 vGaGR、0GR，都有f(au+0v) =af(u) + 0f(v)，则称f满足线性性，其中， au+ 0vGGN，对任意的 51e#，（au+ 0v) (S) =au(S) + 0v(S)。
[0234] 在所述步骤S3中，在所述值f满足有效性的情况下，通过解线性方程组
[0235]
对所有的jeN\i，
[0236] 其中，屯=_du，完成A(v)获取；在所述值f不满足有效性的情况下，任取iGN， 根据所述步骤S2中所述值f的类型所对应的值f的定义计算(v)，且对任意的jGN\i， 结合式
[0238] 完成f」(v)获取。
[0239]近来，经常与Shapley值及solidarity值放在一起研宄的满足匿名性和线性性的 值还有平均值、平均剩余值。平均值是在所有局中人之间平均分配最大联盟的价值，而平均 剩余值则先分配给每个局中人其自身的价值，再将最大联盟价值中剩余的部分在每个局中 人之间做平均分配。这两个值计算起来非常简单，无需使用本发明提出的方法。此外，在本 实施例中，当I=1时，so4退化为平均值；当5 =〇时，sh6退化为平均值。
[0240]与solidarity值类似，兼顾效率和公平的值还有平均Shapley值及合意值。它们 也都满足匿名性与线性性。任取vGiGN，局中人i在v中的平均Shapley值为其 平均值与Shapley值的凸组合，即：
[0242]局中人i在v中的合意值为其平均剩余值与Shapley值的凸组合，即：
[0244]其中，aE[0，1]，具体取值取决于决策者在效率和公平之间的取舍。显然，平均Shapley值与合意值都满足匿名性及线性性。任取jGN，
[0246] 为了让本领域技术人员进一步了解本发明所提出的一种满足线性与匿名条件的 合作对策分量差值简化方法，下面结合具体的实施例进行说明。
[0247] 令N= {1，2, 3}，即n= 3。考虑如下的合作对策vGG%(1) = 3,v(2) =v(3) =4,v(l, 2) =v(l, 3) = 5,v(2, 3) = 6,v(l, 2, 3) = 7。下面将利用本发明提出的方法 依次求出合作对策v的Shapley值、solidarity值、广义solidarity值、贴现Shapley值、 Banzhaf值及最小二乘预核仁。
[0248]为此，下面先求zr。当r=1 时，Vi(1)=3,丫丨（2)=丫丨（3)=4,丫丨（1，2)=丫丨（1，3) =Vi(2, 3) =vjl, 2, 3) = 0。于是，按照所述步骤SI中的式zr= (n-l)Sh(vr)得，Zi= 2Sh(Vl) = (-2/3, 1/3, 1/3)。同理，得z2= (-2/3, 1/3, 1/3)。
[0249]由式
得，(v) =ShgW-Shi(v)= 1。而Shapley值满足有效性，S卩：ShiOO+Sl^OO+Shjv) =7。联立求解这里所述的3个等 式得，Sh(v) = (5/3,8/3,8/3)。
[0250]由式
| 得，so2 (v)-sc^ (v) =so3 (v)-SC4(v) = 5/12。由solidarity值的有效性得，so(v) = (37/18,89/36,89/36)。
[0251] 由式
由广义solidarity值的有效性即可求出so4 (v)。特殊地，当|丨=0时，so4 (v)= (5/3, 8/3, 8/3) =Sh(v);当 1/2 时，so4 (v) = (37/18,89/36,89/36) =so(v);当 I1 时，so4 (v) = (7/3, 7/3, 7/3)，即平均值。
[0252] 由式
由贴现Shapley值的定义得，
，从而
=特 殊地，当S= 〇时，
，即平均值；当S= 1时，
[0253] 由式
得，Baj^W-BaJv)= 1。由Banzhaf值的定义，Bajv) =3/2。从而，Ba(v) =(3/2, 5/2, 5/2)。由于最小二乘预核仁保持Banzhaf值的分量差值，且满足有效性，故得 LSPN(v) = (5/3, 8/3, 8/3) =Sh(v)〇
[0254] 下面，结合上述计算结果将本发明所提出的方法与传统做法（直接采用值的定义 逐个计算）进行计算复杂性比较分析。由于算法的计算量主要由"X"、" + "运算的次数来 决定，因而下面也着重比较所述两种做法所需的"X "运算次数。
[0255] 1)对任意的合作对策v G GN，都有
[0256]v=v1+v2+L+vn,
[0257] 从而由Shapley值满足线性性，有
[0258]Sh(v) =Sh(v)+Sh(v2) +…+Sh(vn)，
[0259] 即利用本发明所提出的方法计算出所需的％(其中，re{1，2,L，n_l})的工作量 与直接采用值的定义进行计算的工作量相差不大。
[0260] 2)利用本发明所提出的方法计算solidarity值，只需进行n次" + "运算（求
;采用值的定义计算solidarity值，至少需要n次"X"运算（计算n个阶 乘）及n2次" "运算（计算平均边际贡献）。
[0261] 3)利用本发明所提出的方法计算广义solidarity值，只需进行n-1次"X"运 算（计算（r-1)U及n次" + "运算（求
；采用值的定义计算广义 solidarity值，至少需要2n次"X"运算（计算n个阶乘与（1- |r)v(S))及n+1次" + " 运算（计算
[0262] 4)利用本发明所提出的方法计算贴现Shapley值，需进行n-1次"X"运算（计 算S-)及1次" + "运算（求
）；采用值的定义计算贴现Shapley值，至少需要n次 "X"运算（计算n个阶乘）及n次" + "运算（计算
[0263] 5)利用本发明所提出的方法计算最小二乘预核仁，只需进行3n_l次"X"运算 (计算2n_2 (n-1)与
及1次" "运算（求
；采用值的定义计算最小二 乘预核仁，至少需要n2+n-l次"X"运算（计算n2n-2个阶乘 与（n-S)(v(SUi)-v⑶））及2 次"+"运算（计算?
[0264] 6)利用本发明所提出的方法计算Banzhaf值，需计算它的1个分量及3n_l次"X" 运算（计算2n_2(n-l)与
）及1次" + "运算（求
）；采用值的定义计算 Banzhaf值，需要进行n-1次"X"运算（计算2n，及1次" "运算（计算.
，
[0265] 通过以上分析可以发现，除Banzhaf值之外，本发明所提出的方法比传统算法所 需的"X"、" + "运算次数少了很多。因此，在需要同时计算一个合作对策的若干个满足 匿名性与线性性的合作对策值时，可以先利用本发明所提出的方法求出除Banzhaf值以外 的其它值，再利用值的定义求Banzhaf?值。事实上，除投票表决情境之外，没有被标准化的 Banzhaf值也极少应用。
[0266] 本发明致力于给出同时计算一类值的简便、有效方法，这一工作往往为决策支持 系统所需要，因为在辅助决策时，它不仅要从理论上告诉决策者不同的值之间有什么区别， 更应该让决策者同时看到选择不同值的分配后果。另外，以往研宄提出的单个值的简化算 法与本发明所提出的算法并非是不相容的。事实上，由于本发明所提出的方法往往需要先 计算值的一个分量，此时以往的简化算法将会派上用场。
[0267] 以上是本发明的较佳实施例，凡依本发明技术方案所作的改变，所产生的功能作 用未超出本发明技术方案的范围时，均属于本发明的保护范围。
【主权项】
1. 一种满足线性与匿名条件的合作对策分量差值简化方法，其特征在于，按照如下步 骤实现： 步骤Sl :任取V e Gn，令'e Gn为该V的r-分队对策，对任意的SgiV，通过获取V的r-分队向量a= (n-1) Sh (V J，且该Z1?为一 η维实向量；其中，TU合作对策 V是从有限集N的幂集到实数集的映射，v:2n-R，有限集N= {1，2, 一,η}为局中人集合， 有限集N的子集为局中人联盟S，I S I表示联盟S中的局中人数，即集合S的元素个数；GnS 有限集N上TU合作对策V的全体；r e {1，2,…，η-1}，η为大于1的正整数；Sh为Shapley 值； 步骤S2 :判断TU合作对策V的待求满足线性与匿名性的值f的类型，根据所述值f的 类型，并通过式：获取圮(V)与fj (V)的分量差值dij;其中，j e N\i，，对任意的S d且对任意的r e {1，2,…，n-1}，均存在R，使得： Zi(Zr) = Br(Zr)i; 所述值f :GN- R n，f = (f\，f2，…，fn)，对于任意的TU合作对策V e Gn，均存在 Σ ieNfi(v)彡v(N)，f?为用值f在有限集N间分配最大联盟的价值V(N)时，局中人i 的收益，局中人i为所述有限集N中的元素； 步骤S3 :判断所述值f是否满足有效性，若满足，则结合所述值f的有效性获取所述 fj (V);否则，根据所述步骤S2中所述值f类型所对应的值f的定义计算(V)，完成fj (V) 获取。2. 根据权利要求1所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S2中，还包括如下步骤： 步骤S21 :判断所述值f的类型，若所述值f为Shapley值，则转入步骤S22 ;若所述值 f为solidarity值，则转入步骤S23 ;若所述值f为广义solidarity值，则转入步骤S24 ;若 所述值f为贴现Shapley值，则转入步骤S25 ;若所述值f为Banzhaf值，则转入步骤S26 ; 步骤S22 :对任意的V e GnS r e {1，2,…，η-I}，均存在：其中，Sh为Shapley值，且结合式以及式 Zi(Zr) = ^(Zr)i 得：对任意的v G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S23 :对任意的V e GnS r e {1，2,…，n-1}，均存在：其中，SO为solidarity值，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S24 :对任意的V e GnS r e {1，2,…，n-1}，均存在：其中，SO4为广义solidarity值，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S25 :对任意的V e GnS r e {1，2,…，n-1}，均存在：其中，Shs为贴现Shapley值，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S26 :对任意的V e GnS r e {1，2,…，n-1}，均存在：\ 其中，Ba为Banzhaf值 表示从n_l个局中人集合中选择出r个局中人的组合 ) 方式，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3。3.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S22中，对任意的V e GnS i e N，局中人i在V中的Shapley值为：其中，η ! = nX (n-1) X…X2X1为阶乘，s = |S|表示联盟S中的局中人数，即集合 S的元素个数；对任意的i e N，若r>l，则4.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S23中，对任意的V e GnS SgiV，记联盟S内局中人对S的平均边 际贡献为Aav(S，v)，即：则对任意的i e N,局中人i在V中的solidarity值为：对任意的i e N，则若r>l，则5.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S24中，对任意的V e GnS i e N，局中人i在V中的广义solidarity 值为：其中：'1 = 0, 2, 3,…，η ;当 0 < ξ # 1 时，so ξ 为广义solidarity值； 对任意的i e N，若r>l，则6.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S25中，对任意的V e GnS i e N，局中人i在V中的贴现Shapley 值为：其中，贴现因子S e [〇，1]; 对任意的i e N，则若r>l，则7. 根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S26中，对任意的V e GnS i e N，局中人i在V中的Banzhaf值为：对任意的i e N，则8. 根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，若所述值f的类型为最小二乘预核仁，则对任意的V e GnS i e N，局中人i在 V中的最小二乘预核仁为：且存在映射k:GN- R，使得对任意的V e GnS i e N，均存在： LSPNi (V) -Bai (V) = k (V)， 进而，9. 根据权利要求1所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S3中，若所述值f满足对任意的V e Gn，均存在Σ i e Nfi (V) = V (N)， 则称所述值f满足有效性。10. 根据权利要求9所述的一种满足线性与匿名条件的合作对策分量差值简化方法， 其特征在于，在所述步骤S3中，在所述值f满足有效性的情况下，通过解线性方程组：对所有的j e N\i ; ， 其中，Clji= -Clij，完成fj(v)获取； 在所述值f不满足有效性的情况下，任取i e N，通过所述步骤S2中所述值f类型所对 应的值f的定义计算fi (V)，且对任意的j e N\i，结合式：完成Α(ν)获取。
【专利摘要】本发明涉及一种满足线性与匿名条件的合作对策分量差值简化方法，提出了满足线性与匿名要求的合作对策值的分量差值显式解析表达式及其求解框架，进而给出同时若干种满足线性与匿名要求的合作对策分量差值简化方法。本发明所提出的一种满足线性与匿名条件的合作对策分量差值简化方法，具有较大优越性与实用性。该方法丰富了合作对策的计算方法，可为开发决策支持系统提供方法支持。
【IPC分类】G06F19/00
【公开号】CN104899470
【申请号】CN201510366768
【发明人】李登峰, 胡勋锋, 刘家财
【申请人】福州大学
【公开日】2015年9月9日
【申请日】2015年6月29日
【技术领域】
[0001] 本发明涉及效用可转移合作对策（简称TU合作对策）领域，特别是一种满足线性 与匿名条件的合作对策分量差值简化方法。
【背景技术】
[0002] 近年来，在效用可转移合作对策（简称合作对策或TU合作对策）领域，继Shapley 在 1953 年提出Shapley值之后，Banzhaf值、solidarity值、平均Shapley值、贴现Shapley 值、最小二乘预核仁、广义solidarity值等也被相继提出。一方面，它们的出现体现了合作 对策领域的繁荣，驳斥了"一些不成熟的报告所宣称的合作对策死期将至"的观点。但另一 方面，由于种类太多，而且没有进行很好的归类，从而给理论研宄和实际应用都带来了诸多 不便。为解决这一问题，目前对合作对策值（或简称值）的研宄工作出现了两种趋势。
[0003] -种是研宄对象从单个值转移到一类有共同特点的值。这其中同时满足有效 性、线性性及匿名性的值作为一个整体被研宄得比较多。Ruiz等、Juarez等、Nembua和 Andjiga、Nembua、Radzik和Driessen等都给出了这类值的显式解析表达式。Driessen和 Radzik先后研宄了这类值的势函数及一致性。他们的工作是Hart和Mas-Colell的扩展。 Malawski、Radzik和Driessencript给出了这类值满足一些常见公理的充要条件。
[0004] 另一种是在对值进行公理化刻画时，注重与其它值的刻画的可比较性，尤其是致 力于使得若干个值的刻画只相差一个公理或条件。早在1994年，Nowak和Radzik提出 so1idarity值时，他们给出的so1idarity值的刻画与Shap1ey对Shap1ey值的刻画就只相 差一个公理。这一公理关注哪一类局中人将获得0收益。随后，vandenBrink和Casajus 依次给出了平均值和平均剩余值的刻画。这些刻画与Shapley对Shapley值的刻画也只 相差一个公理。同样地，这一公理关注哪一类局中人将获得〇收益。与此类似，Kamojo和 Kongorscript同时给出了平均值、Shapley值及solidarity值的刻画。这三个刻画也只相 差一个公理。但这一公理不关注哪类局中人将获得0收益，而关注哪类局中人被踢出最大 联盟后，不会影响剩余局中人的收益。Kamojo和Kongo的工作充当了Casajus和Huettner 提出广义solidarity值的主要动机。Alonso-Meijide等对公理化刻画的利弊做了很好的 评论。
【发明内容】
[0005] 本发明的目的在于提供一种满足线性与匿名条件的合作对策分量差值简化方法， 以克服现有技术中存在的缺陷。
[0006] 为实现上述目的，本发明的技术方案是：一种满足线性与匿名条件的合作对策分 量差值简化方法，按照如下步骤实现：
[0007] 步骤S1 :任取vGGN，令v,GGN为该v的r-分队对策，对任意的S[iV，通过
[0008]
[0009] 获取v的r-分队向量：％= (n-l)Sh(v}且该％为一n维实向量；其中，TU合作 对策V，也即效用可转移合作对策V，是从有限集N的幂集到实数集的映射，v:2n-R，有限 集N= {1，2,…，n}即为局中人（编号）集合，有限集N的子集为（局中人）联盟S，G% 有限集N上TU合作对策v的全体；rG{1，2,…，n-1}，n为大于1的正整数；Sh为Shapley 值或Shapley向量；
[0010] 步骤S2 :判断TU合作对策V的待求满足线性与匿名性的值f的类型，根据所述值 f的类型，并通过式
[0012] 获取fi (V)与fj (V)的分量差值dij;其中，jGN\i，万e，对任意的SG汉，
[0014] 且对任意的rG{1，2,…，n-1}，均存在brGR，使得：
[0015] f^zr) =br{zr)：;
[0016] 所述值f:GN-Rn，对于任意的TU合作对策vGGN，均存在EieNfi(v)彡v(N)，fi(v)为用值f在有限集N间分配最大联盟的价值v(N)时，局中人i的收益，局中人i为所 述有限集N中的元素；
[0017] 步骤S3 :判断所述值f是否满足有效性，若满足，则结合所述值f的有效性获取所 述fj(v);否则，根据所述步骤S2中所述值f类型所对应的值f的定义计算(v)，完成fj(v) 获取。
[0018] 在本发明一实施例中，在所述步骤S2中，还包括如下步骤：
[0019] 步骤S21 :判断所述值f的类型，若所述值f为Shapley值，则转入步骤S22 ;若所 述值f为solidarity值，则转入步骤S23 ;若所述值f为广义solidarity值，则转入步骤 S24 ;若所述值f为贴现Shapley值，则转入步骤S25 ;若所述值f为Banzhaf值，则转入步 骤S26 ;
[0020] 步骤S22 :对任意的vGGlrG{1，2,…，n-1}，均存在：
[0022] 其中，Sh为Shapley值或Shapley向量，且结合式
[0024] 以及式
[0026] 得：对任意的vGGliGN、jGN，均存在：
[0028] 并转到步骤S3 ;
[0029] 步骤S23 :对任意的vGGlrG{1，2,…，n-1}，均存在：
[0031]其中，so为solidarity值或solidarity向量，且结合式
[0033]以及式
[0035]得：对任意的vGGliGN、jGN，均存在：
[0037] 并转到步骤S3;
[0038] 步骤S24:对任意的vGGlrG{1，2,…，n-1}，均存在：
[0040]其中，so4为广义solidarity值或广义solidarity向量，且结合式
[0042]以及式
[0044]得：对任意的vGGNSiGN、jGN，均存在：
[0046] 并转到步骤S3 ;
[0047] 步骤S25:对任意的vGGlrG{1，2,…，n-1}，均存在：
[0049]其中，Shs为贴现Shapley值或贴现Shapley向量，且结合式
[0051]以及式
[0053]得：对任意的vGGliGN、jGN，均存在：
[0055] 并转到步骤S3 ;
[0056] 步骤S26 :对任意的vGrG{1，2,…，n-1}，均存在：
[0058]其中，Ba为Banzhaf值或Banzhaf向量，且结合式
[0060]以及式
[0062] 得：对任意的vGGliGN、jGN，均存在：
[0064] 并转到步骤S3。
[0065] 在本发明一实施例中，在所述步骤S22中，对任意的vGiGN，局中人i在 v中的Shapley值为：
[0067] 对任意的iGNU
[0069]若!* =1，则
[0071]若r>l，则
[0073] 在本发明一实施例中，在所述步骤S23中，对任意的vGS^ ，记联盟S内 局中人对S的平均边际贡献为Aav(S，v)，即：
[0075] 则对任意的iGN，局中人i在v中的solidarity值为：
[0077] 对任意的iGNU
[0079]若！*=1，则
[0081]若r>l，则
[0083] 在本发明一实施例中，在所述步骤S24中，对任意的vGiGN，局中人i在 v中的广义solidarity值为：
[0085] 其中
，1 = 0, 2, 3,…，n;当 0 < | # 1 时， so4为广义solidarity值；
[0086] 对任意的iGNU
[0088]若！* = 1，则
[0090] 若r>l，则
[0091]
[0092] 在本发明一实施例中，在所述步骤S25中，对任意的vGiGN，局中人i在 v中的贴现Shapley值为：
[0094] 其中，贴现因子SG[0,1];
[0095] 对任意的iGNU
[0097]若!* =1，则
[0099]若r>l，则
[0101] 在本发 明一实施例中，在所述步骤S26中，对任意的VGiGN，局中人i在 v中的Banzhaf值为：
[0103] 对任意的iGNU
[0105]若r=l，则
[0107]若r>l，则
[0109] 在本发明一实施例中，若所述值f的类型为最小二乘预核仁，则对任意的veGnS igN，局中人i在V中的最小二乘预核仁为：
[0111] 且存在映射k:GN-R，使得对任意的vGiGN，均存在：
[0112] LSPNj(v)-Baj(v) =k(v),
[0114] 在本发明一实施例中，在所述步骤S3中，若所述值f满足对任意的vGGN，均存在 EiENfi(v) =v(N)，则称所述值f满足有效性。
[0115] 在本发明一实施例中，在所述步骤S3中，在所述值f满足有效性的情况下，通过解 线性方程组：
[0116]
对所有的jeN\i，
[0117] 其中，djf-dij，完成f」(v)获取；
[0118] 在所述值f不满足有效性的情况下，任取ieN，通过所述步骤S2中所述值f类型 所对应的值f的定义计算fi(v)，且对任意的jGN\i，结合式：
[0120] 完成f」(v)获取。
[0121] 相较于现有技术，本发明具有以下有益效果：本发明提出了一种满足线性与匿名 条件的合作对策分量差值简化方法，提出了满足线性与匿名要求的合作对策值的分量差值 显式解析表达式及其求解框架，进而给出同时若干种满足线性与匿名要求的合作对策分 量差值简化方法，相较于利用定义逐个计算Shapley值、solidarity值、广义solidarity 值、贴现Shapley值、最小二乘预核仁等的方法，极大地减少了计算工作量，具有较大优越 性与实用性。该方法丰富了合作对策的计算方法，可为开发决策支持系统提供方法支持。
【附图说明】
[0122] 图1为本发明中一种满足线性与匿名条件的合作对策分量差值简化方法的流程 图。
【具体实施方式】
[0123] 下面结合附图，对本发明的技术方案进行具体说明。
[0124] 本发明致力于给出满足匿名性与线性性的合作对策值的简化算法。特别地，如果 被研宄的合作对策值还满足有效性，那么使用本发明的计算方法将会更加简便、有效。提出 这一算法的动机来源于对迈克尔?乔丹问题的研宄，并提出了所谓的分队对策概念。分队 对策是指局中人数量为一常数的联盟价值不为〇的一类合作对策。在分队对策中，尽管不 同的满足匿名性与线性性的合作对策值将产生相同的局中人排序，但其中各分量差值却不 一定相同，且这些分量差值均由一个与具体值无关的向量所决定。本发明利用这一向量，给 出各种满足匿名性与线性性的合作对策值的分量差值显式解析表达式。进一步，由于利用 这些表达式来计算分量差值比较简单方便，本发明还提出利用它们来简化同时计算若干种 满足匿名性与线性性的合作对策值的过程。具体做法如下：如果所考虑的合作对策值不满 足有效性，则先通过该值的定义计算出它的一个分量，再利用分量差值得到其它的分量；如 果所考虑的值满足有效性，则直接利用有效性及分量差值来得到该值的所有分量。事实上， 相对于直接利用值的定义计算这些值的所有分量的做法，采用本发明所提出的方法的计算 量要小得多。这一点将通过具体的实施例分析来进行说明。
[0125] 本发明提供一种满足线性与匿名条件的合作对策分量差值简化方法，如图1所 示，按照如下步骤实现：
[0126]步骤S1 :任取vGGN，令'GGN为该v的r-分队对策，对任意的*通过
[0128]获取v的r-分队向量七=(n-l)Sh(vJ，且该z1?为一n维实向量；其中，TU 合作对策v是从有限集N的幂集到实数集的映射，v:2n-R，满足v(0) = 〇,有限集N= {1，2,…，n}即为局中人集合，有限集N的子集为联盟S，GNS有限集N上TU合作对策v的 全体；rG{1，2,…，n-1}，n为大于1的正整数；Sh为Shapley值；由于Shapley值满足有 效性，因而对任意的rG{1，2,L,n-1}，都有
[0129]步骤S2 :判断TU合作对策v的待求满足线性与匿名性的值f的类型，根据所述值 f?的类型并通过式：
[0131]获取f?与f」(v)的分量差值dij;其中，jGN\i，，对任意的Sd
[0133] 且对任意的rG{1,2,…，n-1}，均存在kGR，使得：
[0135] 所述值f:GN-Rn，对于任意的TU合作对策vGGN，均存在EieNfi(v)彡v(N)， fi(v)为用值f在有限集N间分配最大联盟的价值v(N)时，局中人i的收益，局中人i为所 述有限集N中的元素；
[0136] 步骤S3:判断所述值f?是否满足有效性，若满足，则结合所述值f?的有效性获取所 述A(v);否则，根据所述步骤S2中所述值f的类型所对应的值f的定义计算& (v)，完成 fj(V)获取；在本实施例中，由于在计算不同的满足匿名性与线性性的合作对策值时，％可 以被循环利用，因而采用本发明提出的方法将极大地减少同时求几种满足匿名性与线性性 的合作对策值的计算工作量。
[0137] 在本实施例中，在所述步骤S2中，还包括如下步骤：
[0138] 步骤S21:判断所述值f的类型，若所述值f?为Shapley值，则转入步骤S22;若所 述值f为solidarity值，则转入步骤S23 ;若所述值f为广义solidarity值，则转入步骤 S24 ;若所述值f为贴现Shapley值，则转入步骤S25 ;若所述值f为Banzhaf值，则转入步 骤S26 ;
[0139] 步骤S22 :对任意的vGG{1，2,…，n-1}，均存在：
[0141] 进一步地，在本实施例中，对任意的vGGNSiGN，局中人i在v中的Shapley 值为：
[0143]由Shapley值的定义，对任意的iGN，得
[0145]若r=l，则
[0147]若r>l，则
[0149]故式
成立，其中，Sh为Shapley值，且结合式
[0151]以及式
[0153] 得：对任意的vGGN及iGN、jGN，均存在：
[0155] 转到步骤S3;
[0156] 步骤S23 :对任意的vGGN及rG{1，2,…，n-1}，均存在：
[0158] 在本实施例中，对任意的vG6"及记联盟S内局中人对S的平均边际贡 献为Aav(S，v)，即：
[0160]则对任意的i G N，局中人i在v中的solidarity值为：
[0162]由solidarity值的定义，对任意的i G N，得
[0164]若！* = 1，则
[0166]若r>l，则
[0168]故式
成立，其中，so为solidarity值，且结合式
[0170]以及式
[0172] 得：对任意的v G Gl i G N、j G N，均存在：
[0174] 转到步骤S3;
[0175] 步骤S24 :对任意的vGGlrG{1，2,…，n-1}，均存在：
[0177] 进一步地，对任意的vGGNSiGN，局中人i在v中的广义solidarity值为：
[0179]其中
，1 = 0, 2, 3,…，n;当 0 < | # 1 时， so4为广义solidarity值；
[0180] 由广义solidarity值的定义，对任意的iGN，
[0182]若!* =1，则
[0184]若r>l，则
[0186]故式
成立，且当I=0,1/2时，so4分别退化为 Shapley值、solidarity值；so4 为广义solidarity值，且结合式
[0188]以及式
[0190]得：对任意的vGiGN、jGN，都有
[0192] 并转到步骤S3;
[0193]步骤S25 :对任意的vGG{1，2,…，n-1}，都有：
[0195] 进一步地，对任意的vGGNSiGN，局中人i在v中的贴现Shapley值为：
[0197] 其中，贴现因子5G[0, 1];当6 = 1时，Shs退化为Shapley值；
[0198] 在本实施例中，由贴 现Shapley值的定义，对任意的iGN，
[0200]若r=l，则
[0202]若r>l，则
[0204]故式
.成立，其中，Shs为贴现Shapley值，且结合式
[0206]以及式
[0208] 得：对任意的vGGNSiGN、jGN，都有：
[0210] 并转到步骤S3;
[0211]步骤S26 :对任意的vGG{1，2,…，n-1}，都有：
[0213] 对任意的vGGNSiGN，局中人i在v中的Banzhaf值为：
[0215] 在本实施例中，由Banzhaf值的定义，对任意的iGN，
[0217]若!* =1，则
[0219]若r>l，则
[0221] 故式
成立，其中，Ba为Banzhaf值，且结合式
[0223]以及式
[0225] 得：对任意的vGiGN、jGN，都有
[0227] 并转到步骤S3。
[0228] 在本实施例中，Banzhaf值满足匿名性与线性性，但不满足有效性，而最小二乘预 核仁不仅满足这三条性质，还能保持Banzhaf值的分量差值。若所述值f?的类型为最小二 乘预核仁，则对任意的vGiGN，局中人i在v中的最小二乘预核仁为：
[0230] 所谓保持分量差值是指存在映射k:GN-R，使得对任意的vGG"及iGN，均存 在：
[0231]LSPNj(v)-Baj(v) =k(v),
[0232]进而，
[0233] 进一步地，在本实施例中，在所述步骤S3中，若所述值f满足对任意的veGN，均 存在EieNfi(V) =V(N)，则称所述值f满足有效性。在所述步骤S2中，从N到N的双射 为N上的置换，记N上置换的全体为Q(N);若值f满足对任意的vGJrGQ(N)，都 有f(jiv) =jif(v)，则称f满足匿名性。这里：1)jtvGGN，对任意的, 3iv(S) =V〇 ―1 ⑶）；2) 31f(v) =(L⑴（V)，L⑵（V)，L,L(n) (V));若值f满足对任意的uGGn、 vGaGR、0GR，都有f(au+0v) =af(u) + 0f(v)，则称f满足线性性，其中， au+ 0vGGN，对任意的 51e#，（au+ 0v) (S) =au(S) + 0v(S)。
[0234] 在所述步骤S3中，在所述值f满足有效性的情况下，通过解线性方程组
[0235]
对所有的jeN\i，
[0236] 其中，屯=_du，完成A(v)获取；在所述值f不满足有效性的情况下，任取iGN， 根据所述步骤S2中所述值f的类型所对应的值f的定义计算(v)，且对任意的jGN\i， 结合式
[0238] 完成f」(v)获取。
[0239]近来，经常与Shapley值及solidarity值放在一起研宄的满足匿名性和线性性的 值还有平均值、平均剩余值。平均值是在所有局中人之间平均分配最大联盟的价值，而平均 剩余值则先分配给每个局中人其自身的价值，再将最大联盟价值中剩余的部分在每个局中 人之间做平均分配。这两个值计算起来非常简单，无需使用本发明提出的方法。此外，在本 实施例中，当I=1时，so4退化为平均值；当5 =〇时，sh6退化为平均值。
[0240]与solidarity值类似，兼顾效率和公平的值还有平均Shapley值及合意值。它们 也都满足匿名性与线性性。任取vGiGN，局中人i在v中的平均Shapley值为其 平均值与Shapley值的凸组合，即：
[0242]局中人i在v中的合意值为其平均剩余值与Shapley值的凸组合，即：
[0244]其中，aE[0，1]，具体取值取决于决策者在效率和公平之间的取舍。显然，平均Shapley值与合意值都满足匿名性及线性性。任取jGN，
[0246] 为了让本领域技术人员进一步了解本发明所提出的一种满足线性与匿名条件的 合作对策分量差值简化方法，下面结合具体的实施例进行说明。
[0247] 令N= {1，2, 3}，即n= 3。考虑如下的合作对策vGG%(1) = 3,v(2) =v(3) =4,v(l, 2) =v(l, 3) = 5,v(2, 3) = 6,v(l, 2, 3) = 7。下面将利用本发明提出的方法 依次求出合作对策v的Shapley值、solidarity值、广义solidarity值、贴现Shapley值、 Banzhaf值及最小二乘预核仁。
[0248]为此，下面先求zr。当r=1 时，Vi(1)=3,丫丨（2)=丫丨（3)=4,丫丨（1，2)=丫丨（1，3) =Vi(2, 3) =vjl, 2, 3) = 0。于是，按照所述步骤SI中的式zr= (n-l)Sh(vr)得，Zi= 2Sh(Vl) = (-2/3, 1/3, 1/3)。同理，得z2= (-2/3, 1/3, 1/3)。
[0249]由式
得，(v) =ShgW-Shi(v)= 1。而Shapley值满足有效性，S卩：ShiOO+Sl^OO+Shjv) =7。联立求解这里所述的3个等 式得，Sh(v) = (5/3,8/3,8/3)。
[0250]由式
| 得，so2 (v)-sc^ (v) =so3 (v)-SC4(v) = 5/12。由solidarity值的有效性得，so(v) = (37/18,89/36,89/36)。
[0251] 由式
由广义solidarity值的有效性即可求出so4 (v)。特殊地，当|丨=0时，so4 (v)= (5/3, 8/3, 8/3) =Sh(v);当 1/2 时，so4 (v) = (37/18,89/36,89/36) =so(v);当 I1 时，so4 (v) = (7/3, 7/3, 7/3)，即平均值。
[0252] 由式
由贴现Shapley值的定义得，
，从而
=特 殊地，当S= 〇时，
，即平均值；当S= 1时，
[0253] 由式
得，Baj^W-BaJv)= 1。由Banzhaf值的定义，Bajv) =3/2。从而，Ba(v) =(3/2, 5/2, 5/2)。由于最小二乘预核仁保持Banzhaf值的分量差值，且满足有效性，故得 LSPN(v) = (5/3, 8/3, 8/3) =Sh(v)〇
[0254] 下面，结合上述计算结果将本发明所提出的方法与传统做法（直接采用值的定义 逐个计算）进行计算复杂性比较分析。由于算法的计算量主要由"X"、" + "运算的次数来 决定，因而下面也着重比较所述两种做法所需的"X "运算次数。
[0255] 1)对任意的合作对策v G GN，都有
[0256]v=v1+v2+L+vn,
[0257] 从而由Shapley值满足线性性，有
[0258]Sh(v) =Sh(v)+Sh(v2) +…+Sh(vn)，
[0259] 即利用本发明所提出的方法计算出所需的％(其中，re{1，2,L，n_l})的工作量 与直接采用值的定义进行计算的工作量相差不大。
[0260] 2)利用本发明所提出的方法计算solidarity值，只需进行n次" + "运算（求
;采用值的定义计算solidarity值，至少需要n次"X"运算（计算n个阶 乘）及n2次" "运算（计算平均边际贡献）。
[0261] 3)利用本发明所提出的方法计算广义solidarity值，只需进行n-1次"X"运 算（计算（r-1)U及n次" + "运算（求
；采用值的定义计算广义 solidarity值，至少需要2n次"X"运算（计算n个阶乘与（1- |r)v(S))及n+1次" + " 运算（计算
[0262] 4)利用本发明所提出的方法计算贴现Shapley值，需进行n-1次"X"运算（计 算S-)及1次" + "运算（求
）；采用值的定义计算贴现Shapley值，至少需要n次 "X"运算（计算n个阶乘）及n次" + "运算（计算
[0263] 5)利用本发明所提出的方法计算最小二乘预核仁，只需进行3n_l次"X"运算 (计算2n_2 (n-1)与
及1次" "运算（求
；采用值的定义计算最小二 乘预核仁，至少需要n2+n-l次"X"运算（计算n2n-2个阶乘 与（n-S)(v(SUi)-v⑶））及2 次"+"运算（计算?
[0264] 6)利用本发明所提出的方法计算Banzhaf值，需计算它的1个分量及3n_l次"X" 运算（计算2n_2(n-l)与
）及1次" + "运算（求
）；采用值的定义计算 Banzhaf值，需要进行n-1次"X"运算（计算2n，及1次" "运算（计算.
，
[0265] 通过以上分析可以发现，除Banzhaf值之外，本发明所提出的方法比传统算法所 需的"X"、" + "运算次数少了很多。因此，在需要同时计算一个合作对策的若干个满足 匿名性与线性性的合作对策值时，可以先利用本发明所提出的方法求出除Banzhaf值以外 的其它值，再利用值的定义求Banzhaf?值。事实上，除投票表决情境之外，没有被标准化的 Banzhaf值也极少应用。
[0266] 本发明致力于给出同时计算一类值的简便、有效方法，这一工作往往为决策支持 系统所需要，因为在辅助决策时，它不仅要从理论上告诉决策者不同的值之间有什么区别， 更应该让决策者同时看到选择不同值的分配后果。另外，以往研宄提出的单个值的简化算 法与本发明所提出的算法并非是不相容的。事实上，由于本发明所提出的方法往往需要先 计算值的一个分量，此时以往的简化算法将会派上用场。
[0267] 以上是本发明的较佳实施例，凡依本发明技术方案所作的改变，所产生的功能作 用未超出本发明技术方案的范围时，均属于本发明的保护范围。
【主权项】
1. 一种满足线性与匿名条件的合作对策分量差值简化方法，其特征在于，按照如下步 骤实现： 步骤Sl :任取V e Gn，令'e Gn为该V的r-分队对策，对任意的SgiV，通过获取V的r-分队向量a= (n-1) Sh (V J，且该Z1?为一 η维实向量；其中，TU合作对策 V是从有限集N的幂集到实数集的映射，v:2n-R，有限集N= {1，2, 一,η}为局中人集合， 有限集N的子集为局中人联盟S，I S I表示联盟S中的局中人数，即集合S的元素个数；GnS 有限集N上TU合作对策V的全体；r e {1，2,…，η-1}，η为大于1的正整数；Sh为Shapley 值； 步骤S2 :判断TU合作对策V的待求满足线性与匿名性的值f的类型，根据所述值f的 类型，并通过式：获取圮(V)与fj (V)的分量差值dij;其中，j e N\i，，对任意的S d且对任意的r e {1，2,…，n-1}，均存在R，使得： Zi(Zr) = Br(Zr)i; 所述值f :GN- R n，f = (f\，f2，…，fn)，对于任意的TU合作对策V e Gn，均存在 Σ ieNfi(v)彡v(N)，f?为用值f在有限集N间分配最大联盟的价值V(N)时，局中人i 的收益，局中人i为所述有限集N中的元素； 步骤S3 :判断所述值f是否满足有效性，若满足，则结合所述值f的有效性获取所述 fj (V);否则，根据所述步骤S2中所述值f类型所对应的值f的定义计算(V)，完成fj (V) 获取。2. 根据权利要求1所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S2中，还包括如下步骤： 步骤S21 :判断所述值f的类型，若所述值f为Shapley值，则转入步骤S22 ;若所述值 f为solidarity值，则转入步骤S23 ;若所述值f为广义solidarity值，则转入步骤S24 ;若 所述值f为贴现Shapley值，则转入步骤S25 ;若所述值f为Banzhaf值，则转入步骤S26 ; 步骤S22 :对任意的V e GnS r e {1，2,…，η-I}，均存在：其中，Sh为Shapley值，且结合式以及式 Zi(Zr) = ^(Zr)i 得：对任意的v G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S23 :对任意的V e GnS r e {1，2,…，n-1}，均存在：其中，SO为solidarity值，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S24 :对任意的V e GnS r e {1，2,…，n-1}，均存在：其中，SO4为广义solidarity值，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S25 :对任意的V e GnS r e {1，2,…，n-1}，均存在：其中，Shs为贴现Shapley值，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3 ; 步骤S26 :对任意的V e GnS r e {1，2,…，n-1}，均存在：\ 其中，Ba为Banzhaf值 表示从n_l个局中人集合中选择出r个局中人的组合 ) 方式，且结合式得：对任意的V G GnS i G N、j G N，均存在：并转到步骤S3。3.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S22中，对任意的V e GnS i e N，局中人i在V中的Shapley值为：其中，η ! = nX (n-1) X…X2X1为阶乘，s = |S|表示联盟S中的局中人数，即集合 S的元素个数；对任意的i e N，若r>l，则4.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S23中，对任意的V e GnS SgiV，记联盟S内局中人对S的平均边 际贡献为Aav(S，v)，即：则对任意的i e N,局中人i在V中的solidarity值为：对任意的i e N，则若r>l，则5.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S24中，对任意的V e GnS i e N，局中人i在V中的广义solidarity 值为：其中：'1 = 0, 2, 3,…，η ;当 0 < ξ # 1 时，so ξ 为广义solidarity值； 对任意的i e N，若r>l，则6.根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S25中，对任意的V e GnS i e N，局中人i在V中的贴现Shapley 值为：其中，贴现因子S e [〇，1]; 对任意的i e N，则若r>l，则7. 根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S26中，对任意的V e GnS i e N，局中人i在V中的Banzhaf值为：对任意的i e N，则8. 根据权利要求2所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，若所述值f的类型为最小二乘预核仁，则对任意的V e GnS i e N，局中人i在 V中的最小二乘预核仁为：且存在映射k:GN- R，使得对任意的V e GnS i e N，均存在： LSPNi (V) -Bai (V) = k (V)， 进而，9. 根据权利要求1所述的一种满足线性与匿名条件的合作对策分量差值简化方法，其 特征在于，在所述步骤S3中，若所述值f满足对任意的V e Gn，均存在Σ i e Nfi (V) = V (N)， 则称所述值f满足有效性。10. 根据权利要求9所述的一种满足线性与匿名条件的合作对策分量差值简化方法， 其特征在于，在所述步骤S3中，在所述值f满足有效性的情况下，通过解线性方程组：对所有的j e N\i ; ， 其中，Clji= -Clij，完成fj(v)获取； 在所述值f不满足有效性的情况下，任取i e N，通过所述步骤S2中所述值f类型所对 应的值f的定义计算fi (V)，且对任意的j e N\i，结合式：完成Α(ν)获取。
【专利摘要】本发明涉及一种满足线性与匿名条件的合作对策分量差值简化方法，提出了满足线性与匿名要求的合作对策值的分量差值显式解析表达式及其求解框架，进而给出同时若干种满足线性与匿名要求的合作对策分量差值简化方法。本发明所提出的一种满足线性与匿名条件的合作对策分量差值简化方法，具有较大优越性与实用性。该方法丰富了合作对策的计算方法，可为开发决策支持系统提供方法支持。
【IPC分类】G06F19/00
【公开号】CN104899470
【申请号】CN201510366768
【发明人】李登峰, 胡勋锋, 刘家财
【申请人】福州大学
【公开日】2015年9月9日
【申请日】2015年6月29日
最新回复(0)