运筹学—对策论

《运筹学—对策论》由会员分享，可在线阅读，更多相关《运筹学—对策论（74页珍藏版）》请在金锄头文库上搜索。

1、第十二章 对策论 game theory 运筹学 Operations Research12.1 引 言 12.2 纳什均衡 12.3 反应函数法 12.4 有限二人零和对策 12.5 有限二人非零和对策11.1 引言Introduction对策论（game theory）亦称博弈论，是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。对策论中有一个重要的概念即对策行为，对策行为是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标， 各方需考虑对手的各种可能的行动方案,并力图选择对自己最为有利或最为合理的方案 许多游

2、戏具有特征：（1）有一定的规则 （2）有一个结果 （3）有可供选择的策略 （4）策略与利益相互依存12.1.1对策论概述12.1 引言对策论，不同于日常游戏，它具有理论性，应用的范围也不局 限于游戏。对策是一些个人、对组或其它组织，面对一定的环境条件，在 一定的规则下，同时或先后从各自允许的行为或策略中进行选 择并加以实施，各自取得相应结果的过程。这些规则应用到经济、军事、政治等领域也有类似的特征。例如，市场竞争、经营决策、投资分析、价格制定、费用分摊 、财政转移支付、投标与拍卖、对抗与追踪、资源利用、谈判 、竞选、战争例如，战国时代的田忌赛马、三国时代的曹不兴溅墨画蝇 、曹操兵败华容道、北宋

3、时期的丁渭挖河修皇宫等都是对策 论成功应用的例子。12.1 引言著名法国经济学家泰勒尔（Jean Tirole ）说：“正如理性预期使宏观经济学发生革命一样，对策论广泛而深远地改变了经济学家的思维方式”。是研究决策主体的行为发生直接相互作用时的决策及这种决 策的均衡问题。即它是研究聪明而又理智的决策者在冲突或合 作中的策略选择理论。它将成为当代经济管理学科的前沿领城 。对策论就是研究对策行为中斗争各方是否存在着最合理的行 动方案，以及如何找到这个合理方案的数学理论和方法。 12.1 引言一个对策需要3个基本要素：(1)局中人(players) (2)策略集(strategies)(3)得益函数

4、（payoffs） 12.1.2 对策三要素是一个局势 策略组全体局势的集合S可用各局中人的策略集的迪卡尔集表示 12.1 引言12.1.3 对策的结构和分类12.1 引言【例12.1】1943年2月，日本统帅山本五十六大将计划由南太平洋 新不列颠群岛的拉包尔出发，3天穿过俾斯麦海，开往新几内亚的 莱城，支援困守的日军。有两条路线：北线和南线。盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组 织空中打击。侦察机重点搜索有两个方案：北线和南线。当时未来3天中：北线阴雨，能见度差；南线晴天，能见度佳。 日美双方各自应采用哪种方案 12.1 引言北线南线日军 盟军北线 （ ）南线 ( ) 北

5、线（ ）22南线（ ）13【解】局中人：盟军、日军；双方策略：北线、南线，记为:盟军的赢得矩阵如下：最优策略是： , 即都选择北线。日军舰队 受到重创，但未全歼。 双方选择的策略是：在 最不利中选择最有利的 策略。12.1 引言囚徒的困境（二人非零和对策）5，50，1010，01，1囚徒1囚徒2坦 白 不坦白坦白不坦白双方如何采取对策使结果对自己最有利？12.1 引言【例12.2】双寡头削价竞争（两个厂商）100，10020，150150，2070，70亚贸中南高 价 低 价高价低价类似地，广告投资、采用新技术等方面，厂商之间常常耗资 巨大，但不一定有利可图的争夺战；对公共资源的掠夺式使 用等

6、问题。我们的目的是如何利用这种困境达到有利于社会，合理利 用和开发公共资源，保护环境。12.1 引言多寡头削价竞争（3个厂商:亚贸,中南，中北) ）100，100，10020，150，20150，20，20130，130，20亚 贸中南高 价 低 价高价低价20，20，15020，130，130130，20，13070，70，70亚 贸中南 高 价 低 价高价低价中北采用高价中北采用低价12.1 引言【例12.3】动态对策：甲向乙借一万元钱经营，甲许诺经营成功 后分给乙总利润（4万）的一半，乙是否借给甲？乙甲借不借乙分不分(2，2)(1，0)打乙不打(0，4)(1，0)(1,0) 有法律保障法

7、律保障不足12.1 引言下一节：纳什均衡12.1 引言12.2 纳什均衡 Nash Equilibrium12.2 纳什均衡Nash对对策论的贡献有：（1）合作对策中的讨价还价模型，称 为Nash讨价还价解；（2）非合作对策的均衡分析。纳什均衡（Nash Equilibrium） 假定有n个博弈方参加博弈，在给定其 他博弈方策略的条件下，每个人选择自己的最优策略（个人最优策略 可能依赖也可能不依赖他人策略），一起构成一个策略组合（ Strategy Profile），而Nash均衡是这样一种策略组合，由所有参与人 的最优策略组成，给定别人策略的条件下，没有任何单个参与人有积 极性选择其他策略，

8、从而没有任何人有积极性打破这种均衡，Nash均 衡是一种“ 僵局”：给定别人不动的情况下，没有人有兴趣动。约翰纳什(John F. Nash ) 1928年生于美国,1994年获得诺贝尔经济学奖 在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博 弈论和经济学产生了重大影响 12.2.1 纳什均衡定义另一种解释：假定所有博弈方事先达成一项协议，规定每个人的行 为规则，在没有外在的强制力约束时，当事人会自觉遵守这个协议 ，等于说这个协议构成一个纳什均衡：假定别人遵守协议的情况下 ，没有人有积极性偏离协议规定的自己的行为规则。换句话说，如 果一个协议不构成纳什均衡，它就不可能自动实施，因为至少

9、有一 个参与人会违背此协议，不满足Nash均衡要求的协议是没有意义的 。12.2 纳什均衡用G表示一个对策，若一个对策中有n个局中人，则每个局中人 可选策略的集合称为策略集，分别用S1，S2，Sn 表示；Sij表示局中人i的第j个策略，其中j可取有限个值（有限策 略对策），也可取无限个值（无限策略对策）；对策方i的得益 则用hi表示；hi是各对策方策略的多元函数，n个局中人的对策G 常写成：【定义12.1】 在对策G=S1，S2，Sn；h1，h2hn中，如果由 各个对策方的各选取一个策略组成的某个策略组合（S1*，S2* ，Sn*）中，任一对策方i的策略Si*，都是对其余策略方策略的组 合（S

10、1*，S*i-1，S*i+1，Sn*）的最佳策略，即h i（S1*， ，S*i-1，Si*，S*i+1Sn*）hi（S1*，S*i-1，Sij，S*i+1，Sn*） 对任意SijSi都成立，则称（S1*，Sn*）为G的一个纯策略“ 纳什均衡”（Nash Equilibrium） G=S1，Sn；h1，hn12.2 纳什均衡各选取一个策略组成的某个策略组合构成一个局势，其最优局 势称为纯策略意义下的最优局势【例12.4】 假设有三个厂商在同一市场上生产销售完全相同的 产品，它们各自的产量分别用m1、m2和m3表示，再假设m1、m2 和m3只能取1、2、3等正整数值市场出清价格一定是市场 总产量Q

11、=m1+m2+m3的函数，假设该函数为： 不妨先假设三个厂商开始时分别生产3单位，9单位和6单位产量 ，这时三厂商是否满意各自的产量，要从利润进行分析 由于产量不能超过20，则第i个厂商的利润函数为 12.2 纳什均衡可算出在产量组合为（3，9，6）时，市场价格为2，三厂商的 利润分8，16和12，再作其它产量组合时亦会有不同的结果，如 表12.2 表12.2 三厂商离散产量结合对应价格和利润 m1m2m3p1233962618123863924185564202024555525252533311333333633848242412.2 纳什均衡【定义12.2】 在对策G=S1，Sn；h1，

12、hn中，局中人i 的策略集为Si=Si1，Sik，则他以概率分布pi=（pi1，pik ）随机在其k个可选策略中选择的“策略”称为一个混合策略，其 中0pij1对j1，k都成立，且pi1+pik=1 12.2.2混合策略纳什均衡12.2 纳什均衡【定义12.3】 如果一个策略G=S1，Sn，h1，hn中，参 予者i的策略集为Si=Si1，Sik，如果由各个对策方的策略组 成策略集合G*=S1*，S2*，Sn*，其中都是对其余对策方策略组合的最佳策略，即i（S1*,S2*,，Si-1*，Si*，Sn*）i（S1*,S2*,，Si-1*，Si*， Sn*）对任意SijSi都成立，则称（S1*,，S

13、n*）为G的一个混合策略 纳什均衡12.2 纳什均衡下一节：反应函数法作业：教材P293 T1012.2 纳什均衡12.3 反应函数法12.3 反应函数法当得益是对策的多元连续函数时，求出每个对策方的反应函数 ，而各个反应函数的交点就是纳什均衡 【例12.5】设A，B两厂家生产同样产品，厂商A产量为q1，B产量 为q2，市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数 P6Q。设产品产量的边际成本相等，C1=C2=2。求解两厂商的 纳什均（假设产量连续可分）。 分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂 商各自的利润分别为各自的销售收益减去各自成本，即：12.3 反应函

14、数法作反应函数：(0,4)（0,2)(2,0)(4,0)(4/3,4/3)纳什均衡：(4/3,4/3)12.3 反应函数法【例12.6】 考虑上述模型的另一种情况即各厂商所选择的是价格 而不是产量，假设产量与价格的函数关系为：其它条件不变，边际成本为C1、C2，试求解其纳什均衡。各自的策略空间为 两方的得益就是各自的利润 12.3 反应函数法利用得益函数在偏导数为0时有最大值，各自的反应函数分别为 ：为该对策唯一的纳什均衡 12.3 反应函数法【例12.7】设有3个农户一起放牧羊群，现有一可供大家自由放 牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则就 会影响到羊群的产出，假设每只羊的

15、产出函数为成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道 其它农户的决策，试求出该决策问题的纳什均衡。 【解】各农户的得益函数分别为 12.3 反应函数法反应函数 因此该对策的纳什均衡为（18，18，18） 下一节：有限二人零和对策 作业：教材P293 T 912.4 有限二人零和对策 矩阵对策就是二人有限零和对策。 通常矩阵用来表示局中人1的赢得，局中人2的支付。12.4 有限二人零和对策 用、表示两个局中人，并设局中人有m个纯策略，1，2 ，m，局中人有n个纯策略1，2，n，则按对策论 的相关要素定义，局中人、的策略集分别为：可以算出，局中人、所构成的策略组合共有mn个，记局 中人在策略（i,j）下的赢得aij，则在每个策略的赢得构成 一个矩阵当局中人、的策略集S1,S2及I的赢得矩阵确定后，一个矩阵对 策就给定了通常将矩阵对策记为： 12.4 有限二人零和对策 12.4.1数学定义12.4 有限二人零和对策 称A为局中人的赢得矩阵（或为的支付矩阵），由于对策为 零和的，故局中人的赢得矩阵为A。矩阵对策记为 成立， ，则称VG为