博弈分析及其应用

1、博弈分析及其应用1 引言在社会生活和经济、 军事活动中， 经常碰到各种各样具有竞争或利益相对抗的现象， 如 下棋、打扑克、 为争夺市场展开的广告战、军事斗争中双方兵力的对垒等， 竞争的各方总是 希望击败对手，取得尽可能好的结果，都想用自己最好的战术去取胜， 这就是博弈现象博 弈现象实际上是一类特殊的决策， 在关于不确定型的决策分析中， 决策者的对手是 “大自然”， 它对决策者的各种策略不产生反应，更没有报复行为但在博弈现象中，代替“大自然”的 是有理性的人，因而任何一方做出决定时都必须充分考虑其他对手可能作出的反应博弈论的英文名为 Game Theory，又称对策论，用比较简短的话来概括，所谓

2、博弈是指 局中人按一定规则， 在充分考虑其他局中人可能采取的策略的基础上， 从自己的策略集中选 取相应策略， 并从中得到回报的过程 尽管博弈论中研究的问题形形色色， 但任何一个博弈 问题都包含下列三个要素：1 局中人(players)是指参与竞争的各方，它可以是一个人，也可以是一个集团，但 局中人必须是有决策权的主体，而不是参谋或从属人员局中人可以有两方，也可以有多 方当存在多方的情况下，局中人之间可以有结盟和不结盟之分2策略(strategies)是指局中人所拥有的对付其他局中人的手段、方案的集合在静 态博弈中， 策略必须是一个独立的完整的行动， 而不能是若干相关行动中的某一步 例如一 次乒

3、乓球男子团体比赛中， 包括两名单打和一对双打选手出场，比赛前提交的名单除规定出场球员姓名之外， 两名单打还必须明确谁是第一单打， 谁是第二单打， 这样不同单打和双打 队员的出场搭配以及两名单打队员的不同排序构成了不同的策略.相应每个局中人的策略选择形成的策略组称为一个局势.3.收益函数(payoff function )指一局博弈后各局中人的输赢得失，通常用正的数字表 示局中人的赢得，负的数字表示局中人的损失.博弈论研究决策主体的行为在发生直接相互作用时，人们如何进行决策以及这种决策 的均衡问题.博弈论是研究理性的决策之间冲突与合作的理论.在博弈论分析中，一定场合中的每个对弈者在决定采取何种行

4、动时都策略地、 有目的地行事， 他考虑到他的决策行为对 其他人的可能影响， 以及其他人的行为对他的可能影响， 通过选择最佳行动计划， 来寻求收 益或效用的最大化.由于在现实生活中人们的利益冲突与一致具有普遍性，因此，几乎所有的决策问题都可以认为是博弈博弈论在政治学、军事学、生物进化学、心理学、社会学、 伦理学、经济学等许多领域都有着广泛的应用.在经济学中博弈论作为一种重要的分析方法已渗透到几乎所有的领域， 每一领域的最新进展都应用了博弈论， 博弈论已经成为主流经济 学的一部分，对经济学理论与方法正产生越来越重要的影响.正因为如此，1994 年瑞典皇家科学院决定将诺贝尔经济学奖授予了纳什(Joh

5、n Nash)、哈萨尼(John Sanyi)和泽尔腾(Rei nhard Selte n)三位博弈理论家和经济学家，表彰他们在博弈论理论和应用研究方面作 出的杰出贡献目前博弈论在定价、招投标、谈判、拍卖、委托代理以及很多重要的经营决策中得到应用，它已成为现代经济学的重要基础.博弈中有关局中人的策略集、 收益函数等构成了博弈的信息.按局中人对信息掌握情况，可区分为完全信息博弈和不完全信息博弈.按局中人采取行动的次序，当同时采取行动或在动的人可以观察到前面人采取的行动， 则属于动态博弈.综合上述，博弈可分为完全信息静 态博弈，完互相保密情况下采取行动，称这种情况为静态博弈. 如果局中人采取行动有

6、先后，后采取行全信息动态博弈， 不完全信息静态博弈和不完全信息动态博弈.当然按局中人是否结盟情况，博弈还可区分为合作博弈和非合作博弈.合作博弈是一种解决多利益主体协调行动产生效益分配问题的有效数学模型.合作是指参与者从自己的利益出发，选择行动，但选择行动的结果对各方都有利.合作博弈研究的问题就是要找到一种效益分配方式，能促使所有利益主体合作.基于合作博弈理论的收益分配是希望通过联合从事某项活动，使每个人的收益比单独从事这项活动或作小范围联合时的收 益多.当代世界，合作与竞争共存成为时代的主题，而企业间各种形式的合作联盟更成为当今经济界竞争的热点模式. 组成合作联盟进行合作创新已经成为越来越多企

7、业的选择.在社会活动中的若干实体，为了在日益激烈的竞争中争得一席之地，也为了获得更多的经济或社会效益，相互合作结成联盟或集团这种合作通常是为了利益，是非对抗性的，确定合理分配这些效益的最佳方案是促成合作的前提.2 多人合作博弈概念在日常生活及社会经济活动中，一个人（或集团）为了克服自身弱点（如力量或财力有限），寻求与他人（集团）进行合作，结成一个联盟，以完成单个人或集团所不能完成的事， 这就是多人合作博弈. 该联盟一旦形成，就作为一个整体共同采取行动，其目标是使联盟获得最大利益.一旦博弈完毕，可以根据某种事先商定的契约以及各个局中人本身的贡献大小， 分配共同所得的利益.联盟的数学定义是：设有n

8、个局中人N1,2,，n?进行博弈，所谓一个联盟就是N的 一个非空子集S.为方便起见，有时称空集 一也是一个联盟.n个局中人共能形成2n个联 盟.一旦联盟S形成，组成联盟S的局中人不再关心自己的特殊利益，而为整个联盟的最大利益去努力.因此，他们主要关心联盟S所能获得的最大值.所有联盟S所获得的最大值都确定以后，整个博弈就完全清楚.这样的博弈可以用特征函数加以描述：定义 11:给定N，1,2,，n合作n人博弈记为】-N,v1, N上的特征函数v是定义在 2N上的实值函数，满足：v一= 0 ,v S T -v S vT ,ST =. ,S,T N.（1）对于一个联盟S,v S的值可以通过下列方式获得

9、：S中局中人形成联盟为使S获得最大利益而努力，这时最糟的情况是剩下的所有局中人N - S形成一个联盟和S抗衡，这样可看成是两个局中人S与N- S在进行非合作博弈，v S就是在上述两人非合作博弈中，S所获得的最大收入.对于合作博弈，局中人之间可以相互协商，共同采取使全体都有利的策略，如果某些局家共同采取的策略使联盟总体的利益达到最大.因此，博弈完毕后，如何分配共同形成的总体联盟N所得的收入v N就是合用博弈研究的主要任务.中人对采取某些特定策略不满意，可以事先订立契约，等博弈完了以后再进行补偿，以便大v S的一种分配方案由n维向量X =LXI,X2,xj表示，Xi表示局中人i的所得显 然，对每一

10、个局中人i来说，它至少期望得到的xi满足：xi_v, N .(2)(2 )称为个体合理性条件；还有一个必须满足的条件是：n Xi=v N.(3)i 4(3)称为群体合理性条件(2)、( 3)合到一起就得到一种分配方案.当所有n个局中人均参与合作时，N =：1,2，n为最大的一个联盟，记v N为最大的联盟成果，如何将v N分配给各局中人？ 一个很自然的方法就是依据各局中人给联盟带 来的贡献来分配.设Xi为第i个局中人从vN中获得的分配，i =1,2，n则有：& =v 1 ,X2=v - v1,X3=v1,2,3? -v 1,2?,Xn= v N；-v N-d .然而上述的分配通常与局中人编号的次

11、序有关，如把局中人n, n -1,，2,1的编号改为1 ,2 / , n则有新的分配方案：X1二v W,X2二v ?n, n- 仁-v，n；X3二v n, n -1, n - 2； v：n, nT ；ixn二v N Lv N对于局中人其它编号的次序均有对应的分配方案，由于n个局中人编号的次序共有n!种，所以对应的分配方案也有n!种.为此取各局中人分配的平均值作为局中人的平均贡献.记iv为第i个局中人的平均贡献，则有：iv - Vsl汗-v SL i =1,2，n.(4)n!H其中二为由1,2,n组成的所有n级排列，7 为针对所有的n!个不同n级排列求和，S，一二(j |二j d?,显然S-为排

12、列二中排在i之前的那些局中人组成的联盟，将满足S排列归为一类，(4)式可以表示为：iV八S ! S1 !v S -vS-,i =1,2,n,(5)&n!其中S为N中包含 3 的所有子集，S为子集S中局中人的人数可以证明：nxi v =v N.(6)i生(6)式表明各局中人在联盟中的平均贡献v之和等于联盟的总“成果”.定义 23栋v：气v ,;:2V ,，;:nv为合作n人博弈的 Shapley 值.在多人合作博弈中，利用 Shapley 值法解决分配问题是一种比较公正、合理且行之有效 的方法本文的目的是探讨 Shapley 值法在利益分配问题，费用分摊问题，及如何确定组合 预测权系数中的应用.

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

14、入 市场，联盟成功后将获得一批可观的收益，现如何用Shapley 值分配这一联盟收益.让我们先看在特定场合单家企业生产或两家联盟生产以及三家联盟生产的收益情况(见表1).表 1联盟博弈收益表单位：万元企业收益A120B80C40A+B ( A、B 企业联盟)240A+C （A、C 企业联盟）280B+C （ B、C 企业联盟）200A+B+C （A、B、C 企业联盟）480由表中可以看出，两家联盟比单家生产合算，三家联盟比两家联盟合算，按Shapley 值法计算：120240 -80280 -40480 -2003 12 31 3仆80240 120 + 20040480 280一 门B140

15、，3汉12汉31x3心小40(280 120 )+(20080 ) 480 240一 门C1403工12疋31x34 费用分摊问题在我国区域经济中中小型制造企业数量很大，行业型企业联盟有利于企业抵御风险、降低成本、提高市场竞争力.行业型企业联盟中企业协作的形式有多种，基于行业信息网络的行业联合采购是联盟企业协作的重要手段之一.在联合采购中，各采购企业通过合作使得在满足各自采购目标时的采购总费用Y小于各采购企业单独采购时的采购总费用X,每个采购企业都希望自身分配的收益越大越好，分摊的联合采购成本费用越少越好下面就用Shapley 值法对联合采购费用进行合理分摊计算.先给出一些符号定义：C S:联

16、盟S的总采购费用;M=1,2,，ml:企业采购物资的集合;y =y1/, yn卢RN M:其中RN M是联盟N购买的所有物资的集合，yr y1,yimRM，其中yj是企业i购买物资j的数量，L N, j M；Pjy:购买第j种物资，数量为y时的价格；fik:企业i采购物资k次时的交易费用，fSk为联盟S联合采购k次的交易费用.物资采购中，采购费用包括采购的交易费用和采购物资的实际费用两部分.采购的交易费用是指一次物资采购中，采购主体（单个企业或行业采购中心） 发布消息、组织招投标等进行辅助交易的费用，而采购物资的实际费用是指采购物资的实际数量和实际采购价格之积.行业联合采购中，联盟S的采购总费

17、用为：mCS = fsks!亠一pjyS jysj（7）对所有的联盟S都算出C S，就得到行业联合采购的一个n人合作博弈N,C.Shapley 值法的行业联合采购的费用分摊计算公式为：-200，Uin _ S !S-1! C s _c S_讣1-(8)i吞n!S N(8)式中Ui表示企业i联合采购时的分摊采购费用，CS-V表示企业i没有加入联盟S时的采购费用，C S -C S一讣1表示企业的边际费用(也称可分离费用)，即企业i加入到联盟S中至少应承担的费用(最小分摊费用).下面举一实例说明 Shapley 值法在行业联合采购中的费用分摊计算.某行业型企业联盟中有四家企业拟联合采购两类物资，假定

18、企业独自均能采购这两类 物资并可任意结盟进行联合采购描述如下：N=比2,3,4?：局中人为四家企业；M A,B?： 有两类采购物资;P N为：P N 1；1；2二34二1,2泊,3泊,4二2,3243,411,2,3汉1,2,4【：2,3,4泊,2,3,4.对每一个联盟S P N，其采购费用函数C S可由(7)式算出.在本实例中，不失一般性，假定企业单独采购或联盟联合采购均能一次采购完所需物资，并且四个企业单独采购的交易费用均相等，即：1 = f2= f3二f/ =2000元.(9)而所有联盟的采购费用也相等，即：fs(1)=3000元，SE P(N且S1.( 10)在本实例中，不失一般性，价

19、格函数Pjy假定为购买数量的线性函数，其表达式为:Pjmax,Pj(y)=bj ajy, yjminSjmax.式中，Pjmax和Pjmin分别是第j种物资在最小购买量yjmin和最大购买量Yjmax时的最高、最低价格本实例中，设PAmax,PAmin,yAmax,yAmin分别为 90 元、60 元、160 单位和 40 单位,PBmax, PBmin,yBmax, yBmin分别为 100 元、60 元、150 单位和 50 单位.因此可分别算出物资A、B的价格函数:(11)Pjmin,y -yjmax因此可算出所有联盟S P N的采购费用如表 2 所示.表 2各种联盟采购物资数量（单位）

20、及采购费用（元）表、联盟S类别、121341,21,31,42,3物资A5030103080608040物资B8030205011010013050价格A87.590909080858090价格B88100100100768068100费用C（S）1341577004900970017760161001824011600续表 2各种联盟采购物资数量（单位）及采购费用（元）表联盟S类别9,43,41,2,31,2,41,3,42,3,41,2,34物资A6040901109070120物资B8070130160150100180价格A859077.572.577.582.570价格B889268

21、60608060费用C（S）15140130401881520575189751677522200利用 Shapley 值法计算公式（8）求行业联合采购的费用分摊，得:,13415丄（11760 7700 ）+（161004900 ）+（182409700仁U1:44 318815 -1160020575 -1514018975 -1304022200 -167754汶34= 8742.08同理可得，U2=4837.08，U3=274375，U4=5877.09.由此可以看出，对联盟贡献少（采购物资少）的企业分摊的采购费用相对较少，将获得更多 收益，因此是一种根据企业对联盟贡献大小来分摊费用的

22、方法.5 组合预测权系数的确定预测是根据以往及现在的已知信息，采取一定的方法或技术， 对事物的未来发展趋势和结果进行估计或推测. 组合预测就是综合利用各种预测方法所提供的信息，以适当的加权平均形式得出组合预测模型.组合预测最关心的问题就是如何求出加权平均系数，使得组合预测模型更加有效地提高预测精度.设某社会经济现象的指标序列的观察值为xt|t=1,2,，M设有n个单项预测方法0,PA八100 -y4I60,y 4040 . y : 160 ,y _160100,pBy =12060,y _ 502y5,50：y：.150y _ 150(12)对其进行预测，n个单预测方法用N二1,2,，n?表示

23、，则N为组合预测方法的局中人集合.N中的任一子集 2N形成组合预测方法的一个联盟，若干个局中人结成联盟后，这个联盟作为一个整体进行组合预测就是希望尽可能多的降低组合预测误差, 方和这个指标来反映预测精度.设x,为第t时刻的预测值，记e=人-x为第i种预测方法在第t时刻的预测误差,i =1,2, n,t =1,2, M.设Xt=hXit l?X2t InXnt为为的组合预测值，12，In为各种预测方法的加权n系数，且满足a li=i,li_0,i =1,2 , n设e为第t时刻组合预测误差，则有:i 4net二XtXt二h XtXiti 4n二lieit.i二(13)组合预测模型的误差平方和为：

24、MM n nJ NA 為e2- liljeitejt.t壬t吕i二j 4(14)记Eeitejt，L =h, I?，In,I丁= 1,1，11 n,称矩阵E为组合预测模2mm型的误差信息矩阵，称L为组合预测模型加权系数向量，则以组合预测误差平方和的非负权最优组合预测模型可写为：min J Ni；二LTEL.ITL=1(15)L 3 0令vS二-JS,v S为特征函数，J S表示联盟S进行组合预测所得的预测误差平方和，vS表示JS相反数.因为预测误差平方和越大， 预测精度越低，所以v S越大，表明预测精度越高.由 Shapley值即可计算第i种单项预测方法同联盟合作的平均贡献v,考虑到v N为误

25、差平方和的负值，需将iv做如下归一化处理可得组合预测的加权系数h,l2，,lni =1,2, ,n. (16)本文采n显然它们满足 迟h =1,h zo,i =1,2,，ni 4组合预测权系数确定的合作博弈方法计算步骤：1） 根据组合预测误差信息矩阵对角线上的元素，采用某种正权组合方法，如方差倒数加权法，均方差倒数加权法等给出初始的组合预测权系数的估计.2） 根据（14）式计算各种联盟合作的特征函数.3） 根据（5）式计算各种预测方法的所获得的平均分配，即Shapley 值.4） 根据（16）式对各种单项预测方法的所获得的平均分配做归一化处理即得组合预测 权系数.下面用一实例来说明.设某组合预测问题有N=1,2,31三种单项预测方法组合而成其预测误差的信息矩阵为：_835E = Qj)3況3 =344i546其中切，,$3分别是1,2,3这三种单项预测方法的预测误差平方和.本例采用方差倒数加 权法，其一般计算公式为：（n y（l1, 12,1n ）=乞eii |（e11,e22,Qn）（17）丿所以按照（17）式1,2,3这三种单项预测方法在组合预测中的加权系数为：再按照（15）式得即v N二-J N