运筹学课件去背景ch12对策论

第十二章对策论gametheory

运筹学OperationsResearch12.1引言

12.2纳什均衡12.3反应函数法12.4有限二人零和对策

12.5有限二人非零和对策11.1引言Introduction对策论（gametheory）亦称博弈论，是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。对策论中有一个重要的概念即对策行为，对策行为是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方案,并力图选择对自己最为有利或最为合理的方案

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

例如，战国时代的田忌赛马、三国时代的曹不兴溅墨画蝇、曹操兵败华容道、北宋时期的丁渭挖河修皇宫等都是对策论成功应用的例子。12.1引言

著名法国经济学家泰勒尔（JeanTirole）说：“正如理性预期使宏观经济学发生革命一样，对策论广泛而深远地改变了经济学家的思维方式”。

是研究决策主体的行为发生直接相互作用时的决策及这种决策的均衡问题。即它是研究聪明而又理智的决策者在冲突或合作中的策略选择理论。它将成为当代经济管理学科的前沿领城。

对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理方案的数学理论和方法。12.1引言一个对策需要3个基本要素：

(1)局中人(players)(2)策略集(strategies)(3)得益函数（payoffs）

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

日军盟军北线（）南线()北线（）22南线（）13【解】局中人：盟军、日军；双方策略：北线、南线，记为:盟军的赢得矩阵如下：最优策略是：,即都选择北线。日军舰队受到重创，但未全歼。双方选择的策略是：在最不利中选择最有利的策略。12.1引言囚徒的困境（二人非零和对策）－5，－50，－10－10，0－1，－1囚徒1囚徒2坦白不坦白坦白不坦白双方如何采取对策使结果对自己最有利？12.1引言【例12.2】双寡头削价竞争（两个厂商）100，10020，150150，2070，70亚贸中南高价低价高价低价类似地，广告投资、采用新技术等方面，厂商之间常常耗资巨大，但不一定有利可图的争夺战；对公共资源的掠夺式使用等问题。我们的目的是如何利用这种困境达到有利于社会，合理利用和开发公共资源，保护环境。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)有法律保障法律保障不足12.1引言下一节：纳什均衡12.1引言12.2纳什均衡NashEquilibrium12.2纳什均衡Nash对对策论的贡献有：（1）合作对策中的讨价还价模型，称为Nash讨价还价解；（2）非合作对策的均衡分析。纳什均衡（NashEquilibrium）假定有n个博弈方参加博弈，在给定其他博弈方策略的条件下，每个人选择自己的最优策略（个人最优策略可能依赖也可能不依赖他人策略），一起构成一个策略组合（StrategyProfile），而Nash均衡是这样一种策略组合，由所有参与人的最优策略组成，给定别人策略的条件下，没有任何单个参与人有积极性选择其他策略，从而没有任何人有积极性打破这种均衡，Nash均衡是一种“僵局”：给定别人不动的情况下，没有人有兴趣动。约翰·纳什(JohnF.Nash)

1928年生于美国,1994年获得诺贝尔经济学奖在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响12.2.1纳什均衡定义另一种解释：假定所有博弈方事先达成一项协议，规定每个人的行为规则，在没有外在的强制力约束时，当事人会自觉遵守这个协议，等于说这个协议构成一个纳什均衡：假定别人遵守协议的情况下，没有人有积极性偏离协议规定的自己的行为规则。换句话说，如果一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个参与人会违背此协议，不满足Nash均衡要求的协议是没有意义的。12.2纳什均衡用G表示一个对策，若一个对策中有n个局中人，则每个局中人可选策略的集合称为策略集，分别用

S1，S2，…，Sn表示；Sij表示局中人i的第j个策略，其中j可取有限个值（有限策略对策），也可取无限个值（无限策略对策）；对策方i的得益则用hi表示；hi是各对策方策略的多元函数，n个局中人的对策G常写成：【定义12.1】

在对策G={S1，S2…，Sn；h1，h2…hn}中，如果由各个对策方的各选取一个策略组成的某个策略组合（S1*，S2*…，Sn*）中，任一对策方i的策略Si*，都是对其余策略方策略的组合（S1*，…，S*i-1，S*i+1…，Sn*）的最佳策略，即hi（S1*，…，S*i-1，Si*，S*i+1…Sn*）≥hi（S1*，…，S*i-1，Sij，S*i+1…，Sn*）对任意Sij∈Si都成立，则称（S1*，…，Sn*）为G的一个纯策略“纳什均衡”（NashEquilibrium）．

G={S1，…，Sn；h1，…hn}12.2纳什均衡各选取一个策略组成的某个策略组合构成一个局势，其最优局势称为纯策略意义下的最优局势．【例12.4】

假设有三个厂商在同一市场上生产销售完全相同的产品，它们各自的产量分别用m1、m2和m3表示，再假设m1、m2和m3只能取1、2、3……等正整数值．市场出清价格一定是市场总产量Q=m1+m2+m3的函数，假设该函数为：

不妨先假设三个厂商开始时分别生产3单位，9单位和6单位产量，这时三厂商是否满意各自的产量，要从利润进行分析．由于产量不能超过20，则第i个厂商的利润函数为

12.2纳什均衡可算出在产量组合为（3，9，6）时，市场价格为2，三厂商的利润分8，16和12，再作其它产量组合时亦会有不同的结果，如表12.2．

表12.2三厂商离散产量结合对应价格和利润

m1m2m3pπ1π2π33962618123863924185564202024555525252533311333333633848242412.2纳什均衡【定义12.2】在对策G={S1，…，Sn；h1，…，hn}中，局中人i的策略集为Si={Si1，…，Sik}，则他以概率分布pi=（pi1，…，pik）随机在其k个可选策略中选择的“策略”称为一个混合策略，其中0≤pij≤1对j＝1，…，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*）对任意Sij∈Si都成立，则称（S1*,…，Sn*）为G的一个混合策略纳什均衡．12.2纳什均衡下一节：反应函数法作业：教材P293T1012.2纳什均衡12.3反应函数法12.3反应函数法当得益是对策的多元连续函数时，求出每个对策方的反应函数，而各个反应函数的交点就是纳什均衡【例12.5】设A，B两厂家生产同样产品，厂商A产量为q1，B产量为q2，市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数P＝6－Q。设产品产量的边际成本相等，C1=C2=2。求解两厂商的纳什均（假设产量连续可分）。分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂商各自的利润分别为各自的销售收益减去各自成本，即：12.3反应函数法作反应函数：(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个农户一起放牧羊群，现有一可供大家自由放牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则就会影响到羊群的产出，假设每只羊的产出函数为成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道其它农户的决策，试求出该决策问题的纳什均衡。【解】各农户的得益函数分别为12.3反应函数法反应函数因此该对策的纳什均衡为（18，18，18）下一节：有限二人零和对策

作业：教材P293T912.4有限二人零和对策矩阵对策就是二人有限零和对策。通常矩阵用来表示局中人1的赢得，局中人2的支付。12.4有限二人零和对策

用Ⅰ、Ⅱ表示两个局中人，并设局中人Ⅰ有m个纯策略，α1，α2，…，αm，局中人Ⅱ有n个纯策略β1，β2，…，βn，则按对策论的相关要素定义，局中人Ⅰ、Ⅱ的策略集分别为：可以算出，局中人Ⅰ、Ⅱ所构成的策略组合共有m×n个，记局中人Ⅰ在策略（αi,βj）下的赢得aij，则Ⅰ在每个策略的赢得构成一个矩阵当局中人Ⅰ、Ⅱ的策略集S1,S2及I的赢得矩阵确定后，一个矩阵对策就给定了．通常将矩阵对策记为：

12.4有限二人零和对策

12.4.1数学定义12.4有限二人零和对策

称A为局中人Ⅰ的赢得矩阵（或为Ⅱ的支付矩阵），由于对策为零和的，故局中人Ⅱ的赢得矩阵为－A。矩阵对策记为成立，，则称VG为对策G的值，对应的策略组合

12.4.2纯策略矩阵对策【定义12.4】设G={S1，S2；A}为矩阵对策，其中S1={α1，α2，…，αn}，S2={β1，β2，…，βn}，若等式称为该对策的纳什均衡．12.4有限二人零和对策

【例12.8】求解矩阵对策，其中则有对策G的解为：【解】12.4有限二人零和对策

【定理12.1】矩阵对策G={S1，S2；A}在纯策略定义下有纳什均衡的充要条件是：存在策略组合使得对一切i=1，…，m,j=1，…，n,均有：

矩阵对策在纯策略意义下有解且VG=ai*j*的充要条件是：ai*j*是A的鞍点，在对策论中，矩阵A的鞍点也称为对策的鞍点．

12.4有限二人零和对策

【定义5】设f(x，y)为一个定义在x∈A及y∈B上的实函数，如果存在x*∈A及y*∈B,使得对一切x∈A及y∈B有则称为函数f

的有关鞍点。矩阵对策在纯策略意义下的解且的充要条件是是A的鞍点。12.4有限二人零和对策

【解】

直接在赢得表上计算，有

可知=5，i*=1,3，j*=2,4．故（α1，β2）（α1，β4）（α2，β2）（α2，β4）为对策的纳什均衡，VG=5．12.4有限二人零和对策

【例12.9】

设有矩阵对策G={S1，S2；A}，赢得矩阵为求纳什均衡【性质12.1】

无差别性．若和为G的两个解，则：【性质12.2】

可交换性．若和为G的两个解，则以上方法也称“上策均衡法”(Dominant-strategeEqyilibrium)12.4有限二人零和对策

也是对策的解．及【例12.10】

甲、乙两个企业同时生产一种电子产品（假设市场上只有这两家，为一双寡头竞争局面），两个企业都想通过改革管理获取更多的销售份额，甲企业的策略措施有：（1）降低产品价格；（2）提高产品质量；（3）推出新产品．乙企业措施为：（1）增加广告费用；（2）增设网点；（3）改进产品性能，通过预测，两个企业市场份额变动情况如表12－4所示，试确定最优策略．

乙企业123min甲企业112－13－1213103335855*max13105*

【解】则对策最优解为VG=5，纳什均衡为（α3，β3）．甲企业采用推出新产品策略，乙企业采用改进产品性能策略，结果甲企业赢得5％的市场份额．12.4有限二人零和对策

12.4.3混合策略矩阵对策

纯策略矩阵对策的满足纳什均衡是满足局中人Ⅰ有把握的至少赢得是局中人Ⅱ有把握的至多损失即：

当V1≠V2

时，这时不存在纯策略意义下的纳什均衡。

田忌齐王上中下上下中中上下中下上下上中下中上上中下3，－31，－11，－11，－1－1，11，－1上下中1，－13，－31，－11，－11，－1－1，1中上下1，－1－1，13，－31，－11，－11，－1中下上－1，11，－11，－13，－31，－11，－1下上中1，－11，－11，－1－1，13，－31，－1下中上1，－11，－1－1，11，－11，－13，－312.4有限二人零和对策

利用最大最小和最小最大原则，发现不存在使得成立的点．12.4有限二人零和对策

例：对局中人1来说，v1=－2，i*=2，对局中人2来说，v2=3，j*=1，v1≠v2。没有鞍点。【定义12.6】设矩阵对策，其中记12.4有限二人零和对策

则分别称为局中人Ⅰ、Ⅱ的混合策略集；、分别称为局中人1、2的混合策略，为一个混合局势。称为G的混合扩充。E是赢得期望值。【定义】当时，称为局中人Ⅰ、Ⅱ在混合策略中的纳什均衡。称为局中人Ⅰ在选取混合策略S*1时的赢得函数

【定理12.2】矩阵对象G={S1，S2；A}在混合策略意义下有解的充要条件是：存在x*∈S1*，y*∈S2*，使（x*，y*）为函数E（x，y）的一个鞍点，即对一切x∈S1*，y∈S2*有E（x，y*）≤E（x*，y*）≤E（x*，y）12.4有限二人零和对策

【例12.11】

考虑矩阵对策G={S1，S2；A}，其中局中人1的赢得期望值：取，满足试求纳什均衡．

【解】

纯策略纳什均衡不存在．设x=（x1，x2）为局中人Ⅰ的混合策略，y=(y1，y2)为局中人Ⅱ的混合策略，则：12.4有限二人零和对策

分别为局中人Ⅰ和Ⅱ的最优策略．即该对策的纳什均衡。

12.4.4纳什均衡存在定理【定理12.3】设x*∈S1*，y*∈S2*,则（x*，y*）为对策G的纳什均衡的条件是：对任意i=1,…，m，j=1,…，n，有E(i,y*)≤E(x*,y*)≤E(x*,j)其中：12.4有限二人零和对策

【定理12.4】设x*∈S1*，y*∈S2*，则（x*，y*）是对策G的纳什均衡的充要条件是：存在数V，使得x*，y*分别满足：且V=VG.【定理12.5】对任一矩阵对策G={S1，S2；A}，一定存在混合策略意义下的纳什均衡．12.4有限二人零和对策

【定理12.6】设（x*，y*）为矩阵对策G的一个纳什均衡，V=VG，则(1)若xi*＞0，则

(2)若yi*

＞0，则

(3)若，则

(4)若,则12.4有限二人零和对策

例12.4有限二人零和对策

【定理12.7】设有两个矩阵对策

G1={S1，S2；A},G2={S1，S2；αA}则(1)VG2=αVG1(2)T(G1)=T(G2)其中α＞0为一常数，T(G1)、T(G2)为两个对策的解集合1.优超原则法【例12.12】

设赢得矩阵A为:

求纳什均衡．

【解】第4行优于第1行，第3行优于第2行，故可划去第1行和第2行，得到新的赢得矩阵，x1=x2=012.4有限二人零和对策

12.4.5矩阵对策求解方法“严格下策反复消去法”(IteratedEliminationofStrictly

DominatedStrategies)对于A1第1列优于第3列，第2列优于第4列，(1/2)×（第1列）+(1/2)×（第2列）优超于第5列，因此去掉第3列，第4列和第5列，y3=y4=y5=0，得到A2：

又由于第1行优超于第3行，所以从A2中划去第3行，x5=0，得到A3

，解方程组：该矩阵对策的纳什均衡为：

VG=4.8

12.4有限二人零和对策

2.线性方程组法若最优策略中和均不为零时，有

12.4有限二人零和对策

【例12.14】求解矩阵对策【解】建立方程组求解得：x=(0.525，0.275，0.2),y=(0.2，0.05，0.75);VG=－0.453.线性规划方法任意矩阵对策的求解均等价于一对互为对偶的线性规划问题，而定理12.4表明，对策G的解等价于下面两个不等式的解．

【定理12.9】设矩阵对策的值为v，则：

12.4有限二人零和对策

则局中人Ⅰ、Ⅱ的最优策略等价于线性规划问题：

12.4有限二人零和对策

令

有局中人Ⅰ：12.4有限二人零和对策

同理,令有局中人Ⅱ：12.4有限二人零和对策

【例12.12】

利用线性规划方法求解赢得矩阵为

的矩阵对策的纳什均衡．

【解】

此问题可化为两个互为对偶的线性规划问题：12.4有限二人零和对策

最优解：X＝(0.1065，0.1448，0.0437),Y＝(0.1093，0.1038，0.0819)；w＝0.29508．利用变换

得到x*=(0.36，0.49，0.15)，y*=(0.37，0.35，0.28)；v=3.3912.4有限二人零和对策

下一节：有限二人非零和对策

12.4有限二人零和对策

作业：教材P292T3、4、5、6、812.5有限二人非零和对策12.5有限二人非零和对策12.5.1数学定义【例11.16】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩阵分别为矩阵A1和A2合并为双矩阵依然在混合扩充意义下考虑有限二人非零和对策，记局中人1的混合策略为x，局中人2的混合策略为y，相应的策略集记为12.5有限二人非零和对策【定义12.8】对于某个有限二人非零和对策，其局中人1的赢得（混合策略下）为局中人2的赢得为12.5有限二人非零和对策12.5.2有限二人非零和对策纳什均衡分别是局中人1和2的赢得，，和如果有一对策略为任意策略，满足则称为该对策的纳什均衡，称为对策的纳什均衡解（或赢得）【定理12.10】（纳什定理