博弈分析及应用

1、博弈分析及其应用葛利萍(绍兴文理学院数学系，浙江绍兴312000)摘 要：系统地阐述了多人合作博弈理论，并提出利用Shapley值法计算联盟的收益函数中各 局中人的分配，且具有一定的公正性和合理性，特别在利益分配问题，费用分摊问题，以及组合 预测权系数的确定中有着广泛的应用，并对这些方面进行举例分析.关键词：合作博弈；Shapley值；利益分配；费用分摊；组合预测1引言在社会生活和经济、军事活动中，经常碰到各种各样具有竞争或利益相对抗的现象，如 下棋、打扑克、为争夺市场展开的广告战、军事斗争中双方兵力的对垒等，竞争的各方总是 希望击败对手，取得尽可能好的结果，都想用自己最好的战术去取胜，这就是

2、博弈现象.博 弈现象实际上是一类特殊的决策，在关于不确定型的决策分析中，决策者的对手是“大自然”， 它对决策者的各种策略不产生反应，更没有报复行为.但在博弈现象中，代替“大自然”的 是有理性的人，因而任何一方做出决定时都必须充分考虑其他对手可能作出的反应.博弈论的英文名为Game Theory，又称对策论，用比较简短的话来概括，所谓博弈是指 局中人按一定规则，在充分考虑其他局中人可能采取的策略的基础上，从自己的策略集中选 取相应策略，并从中得到回报的过程.尽管博弈论中研究的问题形形色色，但任何一个博弈 问题都包含下列三个要素：局中人(players)是指参与竞争的各方，它可以是一个人，也可以是

3、一个集团，但 局中人必须是有决策权的主体，而不是参谋或从属人员.局中人可以有两方，也可以有多 方.当存在多方的情况下，局中人之间可以有结盟和不结盟之分.策略(strategies)是指局中人所拥有的对付其他局中人的手段、方案的集合.在静 态博弈中，策略必须是一个独立的完整的行动，而不能是若干相关行动中的某一步.例如一 次乒乓球男子团体比赛中，包括两名单打和一对双打选手出场，比赛前提交的名单除规定出 场球员姓名之外，两名单打还必须明确谁是第一单打，谁是第二单打，这样不同单打和双打 队员的出场搭配以及两名单打队员的不同排序构成了不同的策略.相应每个局中人的策略选 择形成的策略组称为一个局势.收益函

4、数(payoff function)指一局博弈后各局中人的输赢得失，通常用正的数字 表示局中人的赢得，负的数字表示局中人的损失.博弈论研究决策主体的行为在发生直接相互作用时，人们如何进行决策以及这种决策 的均衡问题.博弈论是研究理性的决策之间冲突与合作的理论.在博弈论分析中，一定场合 中的每个对弈者在决定采取何种行动时都策略地、有目的地行事，他考虑到他的决策行为对 其他人的可能影响，以及其他人的行为对他的可能影响，通过选择最佳行动计划，来寻求收 益或效用的最大化.由于在现实生活中人们的利益冲突与一致具有普遍性，因此，几乎所有 的决策问题都可以认为是博弈.博弈论在政治学、军事学、生物进化学、心理

5、学、社会学、 伦理学、经济学等许多领域都有着广泛的应用.在经济学中博弈论作为一种重要的分析方法 已渗透到几乎所有的领域，每一领域的最新进展都应用了博弈论，博弈论已经成为主流经济 学的一部分，对经济学理论与方法正产生越来越重要的影响.正因为如此，1994年瑞典皇 家科学院决定将诺贝尔经济学奖授予了纳什（John Nash）、哈萨尼（John Sanyi）和泽尔腾 （Reinhard Selten）三位博弈理论家和经济学家，表彰他们在博弈论理论和应用研究方面作 出的杰出贡献.目前博弈论在定价、招投标、谈判、拍卖、委托代理以及很多重要的经营 决策中得到应用，它已成为现代经济学的重要基础.博弈中有关局

6、中人的策略集、收益函数等构成了博弈的信息.按局中人对信息掌握情况， 可区分为完全信息博弈和不完全信息博弈.按局中人采取行动的次序，当同时采取行动或在 互相保密情况下采取行动，称这种情况为静态博弈.如果局中人采取行动有先后，后采取行 动的人可以观察到前面人采取的行动，则属于动态博弈.综合上述，博弈可分为完全信息静 态博弈，完全信息动态博弈，不完全信息静态博弈和不完全信息动态博弈.当然按局中人是 否结盟情况，博弈还可区分为合作博弈和非合作博弈.合作博弈是一种解决多利益主体协调行动产生效益分配问题的有效数学模型.合作是指 参与者从自己的利益出发，选择行动，但选择行动的结果对各方都有利.合作博弈研究的

7、问 题就是要找到一种效益分配方式，能促使所有利益主体合作.基于合作博弈理论的收益分配 是希望通过联合从事某项活动，使每个人的收益比单独从事这项活动或作小范围联合时的收 益多.当代世界，合作与竞争共存成为时代的主题，而企业间各种形式的合作联盟更成为当今 经济界竞争的热点模式.组成合作联盟进行合作创新已经成为越来越多企业的选择.在社会 活动中的若干实体，为了在日益激烈的竞争中争得一席之地，也为了获得更多的经济或社会 效益，相互合作结成联盟或集团.这种合作通常是为了利益，是非对抗性的，确定合理分配 这些效益的最佳方案是促成合作的前提.2多人合作博弈概念在日常生活及社会经济活动中，一个人（或集团）为了

8、克服自身弱点（如力量或财力有 限），寻求与他人（集团）进行合作，结成一个联盟，以完成单个人或集团所不能完成的事， 这就是多人合作博弈.该联盟一旦形成，就作为一个整体共同采取行动，其目标是使联盟获 得最大利益.一旦博弈完毕，可以根据某种事先商定的契约以及各个局中人本身的贡献大小， 分配共同所得的利益.联盟的数学定义是：设有n个局中人N = S,2,A , n进行博弈，所谓一个联盟就是N的一个非空子集S .为方便起见，有时称空集0也是一个联盟.n个局中人共能形成2n个联 盟.一旦联盟S形成，组成联盟S的局中人不再关心自己的特殊利益，而为整个联盟的最 大利益去努力.因此，他们主要关心联盟S所能获得的

9、最大值.所有联盟S所获得的最大 值都确定以后，整个博弈就完全清楚.这样的博弈可以用特征函数加以描述：定义1U：给定N = S,2,A ,n，合作n人博弈记为= N,打，N上的特征函数v是定义在2n上的实值函数，满足：v（0）= 0，（1）v（S YT） v（S）+ v（T） S I T = 0, S, T u N .对于一个联盟s , v（S）的值可以通过下列方式获得：S中局中人形成联盟为使S获得 最大利益而努力，这时最糟的情况是剩下的所有局中人N-S形成一个联盟和S抗衡，这 样可看成是两个局中人S与N - S在进行非合作博弈，v（S）就是在上述两人非合作博弈中， S所获得的最大收入.对于合作

10、博弈，局中人之间可以相互协商，共同采取使全体都有利的策略，如果某些局 中人对采取某些特定策略不满意，可以事先订立契约，等博弈完了以后再进行补偿，以便大 家共同采取的策略使联盟总体的利益达到最大.因此，博弈完毕后，如何分配共同形成的总 体联盟N所得的收入v（N）就是合用博弈研究的主要任务. TOC o 1-5 h z v（S）的一种分配方案由n维向量X = x ,x ,A ,x 表示，x表示局中人i的所得.显 12ni然，对每一个局中人i来说，它至少期望得到的xi满足：x. v（i） i g N .（2）（2）称为个体合理性条件；还有一个必须满足的条件是：W x = v（N）.（3）i i=1（

11、3）称为群体合理性条件.（2）、（3）合到一起就得到一种分配方案.当所有n个局中人均参与合作时，N = S,2,A , n为最大的一个联盟，记v（N）为最大的联盟成果，如何将v（N）分配给各局中人？ 一个很自然的方法就是依据各局中人给联盟带 来的贡献来分配.设x.为第i个局中人从v（N）中获得的分配，i = 1,2,A , n则有：气=v（1），x = v（1,2）- v（1），2x = v（b,2,3）- v（S,2），3，x = v（N）- v（N -n）.然而上述的分配通常与局中人编号的次序有关，如把局中人n,n -1,A ,2,1的编号改为1,2,A , n，则有新的分配方案:=v(n

12、)，x = V(z, n-1)- v(W)，2x = vVSn, n 1, n 2)- vVSn, n -1，3种，x = v(N)- v(N -1).对于局中人其它编号的次序均有对应的分配方案，由于n个局中人编号的次序共有n! 所以对应的分配方案也有n!种.为此取各局中人分配的平均值作为局中人的平均贡献. 记中)为第，个局中人的平均贡献，则有：i(4)(v )= 1 V 匕 Y-v 早 i = 1,2,A , n .其中兀为由1,2,A ,n组成的所有n级排列，Z为针对所有的n!个不同n级排列求和，Si兀排列归为一类，(4)式可以表示为:(v )=ieSn!V(S)- v(S 砌 i = 1

13、,2, A , n,(5)= 1兀八i，显然也为排加中排在之前的那些局中人组成的联盟，将满足S=S其中S为N中包含5的所有子集，|s|为子集S中局中人的人数.可以证明:(6) )= Vn).i i=1(6)式表明各局中人在联盟中的平均贡献七G)之和等于联盟的总“成果”.定义2回 称平(V)=(V)%(v)A ,平(V)为合作n 人博弈的Shapley值.在多人合作博弈中，利用Shapley值法解决分配问题是一种比较公正、合理且行之有效 的方法.本文的目的是探讨Shapley值法在利益分配问题，费用分摊问题，及如何确定组合 预测权系数中的应用.下面就通过实例来说明Shapley值法在这些方面的具

14、体应用.3利益分配问题随着科学技术进步和信息技术的迅速发展，世界市场已由过去的相对稳定变成动态多变 的特征，由过去的局部竞争演变成全球范围的竞争.在此情景下，以最快的速度推出产品、 以最好的质量、最低的成本和最优的服务满足不同用户的需求成为每个企业认真解决的问 题.于是越来越多的企业纷纷寻找合作伙伴，结成联盟，利用各方优势以更好地适应快速变 化的市场要求.各企业结成联盟后获得了更大的收益，如何利用Shapley值把联盟的整体收 益合理地分配给各个企业，下面给出一实例.设现有三家企业A、B、。为了抓住某一市场机遇，决定实施联盟生产某种新产品投入 市场，联盟成功后将获得一批可观的收益，现如何用Sh

15、apley值分配这一联盟收益.让我们 先看在特定场合单家企业生产或两家联盟生产以及三家联盟生产的收益情况（见表1）.表1联盟博弈收益表单位：万元企业收益A120B80C40A+B （A、B企业联盟）240A+C （A、C企业联盟）280B+C （B、C企业联盟）200A+B+C （A、B、C企业联盟）480由表中可以看出，两家联盟比单家生产合算，三家联盟比两家联盟合算，按Shapley值120 （240 - 80）+（280 - 40）480 - 200 “八 TOC o 1-5 h z 中 w=+= 2003 x 12 x 31 x 3心、80（240 -120）+（200 - 40）480

16、 - 280B ）=+= 140，3x12x31x3仁）40（280 -120）+（200 - 80）480 - 240qC 7=+= 140.3 x 12 x 31 x 34费用分摊问题在我国区域经济中中小型制造企业数量很大，行业型企业联盟有利于企业抵御风险、降 低成本、提高市场竞争力.行业型企业联盟中企业协作的形式有多种，基于行业信息网络的 行业联合采购是联盟企业协作的重要手段之一.在联合采购中，各采购企业通过合作使得在 满足各自采购目标时的采购总费用Y）小于各采购企业单独采购时的采购总费用（X），每个 采购企业都希望自身分配的收益越大越好，分摊的联合采购成本费用越少越好.下面就用 Sha

17、pley值法对联合采购费用进行合理分摊计算.先给出一些符号定义：C（S）:联盟S的总采购费用；M = 1,2,A ,m：企业采购物资的集合；y = （ , y ）g Rnxm :其中rnxm是联盟N购买的所有物资的集合，y = （y ,A , y ）c Rm，其中y是企业，购买物资j的数量，i e N, j e M ；ii1imijPj（y）：购买第j种物资，数量为y时的价格；f.（）:企业i采购物资k次时的交易费用，fs （k ）为联盟S联合采购k次的交易费用.物资采购中，采购费用包括采购的交易费用和采购物资的实际费用两部分.采购的交易 费用是指一次物资采购中，采购主体（单个企业或行业采购中

18、心）发布消息、组织招投标等 进行辅助交易的费用，而采购物资的实际费用是指采购物资的实际数量和实际采购价格之 积.行业联合采购中，联盟s的采购总费用为:(7)(8)C(S)= f (k )+* p，)x y .s sj Sj Sjj=1对所有的联盟S都算出C(S)，就得到行业联合采购的一个n人合作博弈(N, C).Shapley值法的行业联合采购的费用分摊计算公式为：U =zS2匝 C(s)- C(s 一砌.1n!ieSS j N(8)式中U表示企业i联合采购时的分摊采购费用，C(S - b表示企业i没有加入联 盟s时的采购费用，1c(S)- C(S-抄表示企业的边际费用(也称可分离费用)，即企

19、业i加入到联盟S中至少应承担的费用(最小分摊费用).下面举一实例说明Shapley值法在行业联合采购中的费用分摊计算.某行业型企业联盟中有四家企业拟联合采购两类物资，假定企业独自均能采购这两类 物资并可任意结盟进行联合采购.描述如下：N = ,2,3,4)：局中人为四家企业；M =(A,b：有两类采购物资;P(N)为：P(N)=即员钺姒很向膈启弘疆 $,2,3 $,2,4 /,3,4处,3,4.对每一个联盟S g P(N)，其采购费用函数C(S)可由(7)式算出.在本实例中，不失一般性，假定企业单独采购或联盟联合采购均能一次采购完所需物资，并且四个企业单独采购的 交易费用均相等，即：f G)=

20、 f G)= f G)= f G)= 2000 元.(9)1234而所有联盟的采购费用也相等，即：(10)fs G)= 3000 元，S g P(N)且 |S| 1.在本实例中，不失一般性，价格函数P, (y)假定为购买数量的线性函数，其表达式为:py )=j max化一孚,y J yj minyjmin V y V yjmax(11)I Pj min，- yj max式中，p和p分别是第j种物资在最小购买量G )和最大购买量G)时的最j max j m inj minj m ax高、最低价格.本实例中，设P, P , y , y分别为90元、60元、160单位和40A max A min A

21、 max A min单位，P ,P , y , y分别为100元、60元、150单位和50单位.因此可分别算出B max B min B max B min物资A、B的价格函数：90,y 40Pa(y)=100-、, 40 y 160100,y 502Pb (y)= 1120 - 2% ,50 y 150(12)因此可算出所有联盟s g P（N）的采购费用如表2所示.表2 各种联盟采购物资数量（单位）及采购费用（元）表、联盟s类别把排贤糖处3)她2,3)物资A5030103080608040物资B8030205011010013050价格A87.590909080858090价格B881001

22、00100768068100费用* ）1341577004900970017760161001824011600续表2 各种联盟采购物资数量（单位）及采购费用（元）表联盟S类别、,4h,41,2,3$,2,4$,3,4,3,4S,2,3,4物资A6040901109070120物资B8070130160150100180价格A859077.572.577.582.570价格B88926860608060费用C (S )15140130401881520575189751677522200利用Shapley值法计算公式（8）求行业联合采购的费用分摊，得：144 x3(18815 -11600)+

23、(20575 -15140)+ (18975 -13040) (22200 -16775)+4 x 34U =也 +。1760 一 77006100-4900）+G824。-9700） +=8742.08同理可得，U2 = 4837.08 , U3 = 2743.75 , U4 = 5877.09 .由此可以看出，对联盟贡献少（采购物资少）的企业分摊的采购费用相对较少，将获得 更多收益，因此是一种根据企业对联盟贡献大小来分摊费用的方法.5组合预测权系数的确定预测是根据以往及现在的已知信息，采取一定的方法或技术，对事物的未来发展趋势和 结果进行估计或推测.组合预测就是综合利用各种预测方法所提供的

24、信息，以适当的加权平 均形式得出组合预测模型.组合预测最关心的问题就是如何求出加权平均系数，使得组合预 测模型更加有效地提高预测精度.设某社会经济现象的指标序列的观察值为b, 11 = 1,2,A , M ，设有n个单项预测方法 对其进行预测，n个单预测方法用N = ,2,A , n表示，则N为组合预测方法的局中人集合.N中的任一子集S e 2州形成组合预测方法的一个联盟，若干个局中人结成联盟后，这 个联盟作为一个整体进行组合预测就是希望尽可能多的降低组合预测误差，本文采用误差平 方和这个指标来反映预测精度.设*为第t时刻的预测值，记e = x - x为第i种预测方法在第t时刻的预测误差， i

25、tit t iti = 1,2,A , n，t = 1,2,A , M .设X = l x +1 x +A +1 x为x的组合预测值,l ,l ,A ,l为各种预测方法的加权 TOC o 1-5 h z t 1 1t 22tn nt t12 n系数，且满足七=l，lj 2 0,i = 1,2,A ,n .设et为第t时刻组合预测误差，则有:i =1(13)(14)e = x -x =Xl (x -x )=l e .t t ti t iti iti=1i =1组合预测模型的误差平方和为：J(N)=Me2 =Ullee .ti j it jtt=1t=1 i=1 j =1L = 12,A七 ,It

26、 =G,1,A ,1)1xn，称矩阵E为组合预测模型的误差信息矩阵，称L为组合预测模型加权系数向量，则以组合预测误差平方和的非负权 最优组合预测模型可写为：min J (N )= LtEL 0令V(S)=-J(S)，v(S)为特征函数，J(S)表示联盟S进行组合预测所得的预测误差平 方和，vQ)表示J(S)相反数.因为预测误差平方和越大，预测精度越低，所以v(S)越大，表明预测精度越高.由Shapley 值即可计算第i种单项预测方法同联盟合作的平均贡献？ (v)，考虑到v(N)为误差平方和的 负值，需将平(v)做如下归一化处理可得组合预测的加权系数l ,l ,A ,l :i12 n(16)l

27、=华.史华，i = 1,2, A , n .i 中 lv)中,Iv )显然它们满足 W l = 1, l 0, i = 1,2,A , n .i ii =1组合预测权系数确定的合作博弈方法计算步骤：1）根据组合预测误差信息矩阵对角线上的元素，采用某种正权组合方法，如方差倒数 加权法，均方差倒数加权法等给出初始的组合预测权系数的估计.2）根据（14）式计算各种联盟合作的特征函数.3）根据（5）式计算各种预测方法的所获得的平均分配，即Shapley值.4）根据（16）式对各种单项预测方法的所获得的平均分配做归一化处理即得组合预测 权系数.下面用一实例来说明.设某组合预测问题有N = 4,2,3三种

28、单项预测方法组合而成.其预测误差的信息矩阵为：835344546加 七33分别是技3这三种单项预测方法的预测误差平方和本例采用方差倒数加权法，其一般计算公式为:们1 ,A ,l )=1 2 nI i=1、Te -1”)-1, e -1, A , e -1).1122nn(17)A生13 13)所以按照（17）式1,2,3这三种单项预测方法在组合预测中的加权系数为:1,12,13 )=再按照（15）式得J(N )=1138 3 5 一64、363 4 413反113 135 4 6=4.3314即 v(N )=- J(N )=-4.3314,同理，采用方差倒数加权法可得v61,2= -1.917

29、2，v(1,3)= -1.7041，vG2.3= -2.5562，v(O=-8，v(2)=-4, v(h)=-6按照（5）式计算得：()_ 8 * R-1.9172)-(- 4)+K-1.7041)(- 6)V - 3123(-4.3314 )-(- 2.5562 )_ 睥+= - 2.31961 x 3同理可得中 2 (v)=-0.6213 ,气(v)=-1.5859 .按(16)式计算组合预测加权系数得：=0.16139 , 12 = 0.60255 , 13 = 0.23606 .所以8 3 5J(N)=(0.16139 0.60255 0.23606)3 4 4(0.16139 0.6

30、0255 0.23606 = 4.09734 .若1,2,3这三种单项预测方法按(15)式利用Mathlab软件包可求得最优组合预测加权系 数得：1 * = 0.1667 , 1 * = 0.8333 , 1 * = 0 .123对应的最小的预测误差平方和：J*(N)= 3.8333 .由此可见，本例用Shapley值法确定的组合预测加权系数明显优于用方差倒数加权法确 定的，且与最优组合预测方法预测精度很接近.该方法不仅适用于以误差平方和为准则的组 合预测模型，而且适用于基于预测有效度的组合预测模型.6结束语本文主要阐述了解决多人合作博弈中联盟分配问题的一种方法一一hapley值法.举例 说明

31、此方法在利益分配问题，费用分摊问题，以及组合预测权系数的等方面中有着较好的应 用，而且利用Shapley值法解决这些方面的问题具有一定的公正性和合理性和一定的实用价 值但是，从理论上来说，在多人合作博弈中，如果局中人数量越多，在利用Shapley值法 计算时需要的信息量也就越大，也从不同程度上加大了计算量.因此，在实际应用中，是否 采用Shapley值法来分配联盟的收益也要根据具体问题而确定.致谢：感谢盛宝怀老师的悉心指导！ 参考文献1刘德铭，黄振高.对策论及其应用M.国防科技大学出版社，1995 胡运权等.运筹学基础及应用M.第四版.高等教育出版社，20043谢政.对策论M.国防科技大学出版社，