《纳什均衡.ppt》由会员分享，可在线阅读，更多相关《纳什均衡.ppt（24页珍藏版）》请在三一文库上搜索。
1、精品课程运筹学,第二节 纳什均衡,2.1 纳什均衡的概念,2.2 纳什均衡的求解,2.3 混合策略和混合纳什均衡,精品课程运筹学,第二节 纳什均衡,纳什均衡是对策 论中一个重要的概念。尤其在非合作对策分析中具有十分关键的作用。通过对经典对策模型的分析知道:对于对策中的每一个局中人，真正成功的措施应该是针对其他局中人所采取的每次行动，相应地采取有利于自己的策略。于是，每一个局中人应采取的策略必定是他对其他局中人策略的预测的最佳反应。Nash均衡正是体现这一基本原则。,精品课程运筹学,第二节 纳什均衡,2.1 纳什均衡的概念 用 表示一个对策，若一个对策中有 个局中人，每个局中人可选策略的集合分别
2、用 表示； 表示局中人 的第 个策略，其中 可取有限个值、也可取无限个值；对策方 的得益用 表示； 是各对策方策略的多元函数， 个局中人的对策 常写成 =,精品课程运筹学,第二节 纳什均衡,定义8.2.1 在对策 = 中，如果有由各个对策方的各选取一个策略组成的某个策略组合 中，任一对策方 的策略为 ，都是对其余策略方策略的组合 的最佳策略，即 对任意 都成立则称 为一个纯策略纳什均衡。,精品课程运筹学,第二节 纳什均衡,例8.2.1 “囚徒的困境” 警察抓住了两个罪犯，但是警察局缺乏足够的证据指证他们所犯的罪行。如果罪犯中至少有一人供认犯罪，就能确认罪名成立。为了得到所需的口供，警察将这两名
3、罪犯分别关押以防止他们串供或结成攻守同盟，并分别跟他们讲清了他们的处境和面临的选择：如果他们两人都拒不认罪，则他们会被以较轻的妨碍公务罪各判1年徒刑；如果两人中有一人坦白认罪，则坦白者立即释放而另一人将重判8年徒刑；如果两人都坦白认罪，则他们将被各判5年监禁。,精品课程运筹学,第二节 纳什均衡,局中人为两个囚徒，两个人都有两种策略（坦白、不坦白），两人的策略集共有四个 元素。我们用-1、-5、-8分别表示被判刑的得益，用0表示被释放的得益，则可由下面的得益矩阵将此对策予以表示：表8.2.1,精品课程运筹学,第二节 纳什均衡,对囚徒l来说，囚徒2有坦白和不坦白两种选择，假设囚徒2选择的不坦白，则
4、对囚徒l来说，不坦白得益为一l，坦白得益为O，应该选择坦白；假设囚徒2选择的是坦白，则囚徒1不坦白得益为一8，坦白得益为一5，他更应该选择坦白。囚徒2唯一的选择也是坦白。 例8.2.2 设某村庄有3个农户，该村有一片大家都可自由牧羊的公共草地。由于这片草地的面积有限，草的数量只能让数量有限的羊吃饱，如果在此草地上放牧的羊的实际数量超,精品课程运筹学,第二节 纳什均衡,过这个限度，每只羊都无法吃饱，从而羊的产出就会减少，甚至只能勉强存活或要饿死。假设这些农户只有夏天才到公共草地放羊，而每年春天决定养羊的数量，各农户在决定自己养羊的数量时是不知道其他农户的养羊数量的，各农户养羊数的决策是同时作出的
5、。假设下面信息知道的：每只羊的产出（价格）是羊只总数的减函数， ， , 为第 个农户饲养羊的数量，每只羊的饲养成本为8元。,精品课程运筹学,第二节 纳什均衡,第一个农户是这样决策的： 自己养羊的得益为 = - 8 = -8 为方便起见，设羊数量是可分的。不管其他农户数量如何，第一人总希望自己收益最大。 由此得出： 每个农户都得出与此相同的结论 ：,精品课程运筹学,第二节 纳什均衡,三条曲线的交点( )就是纳什均衡。联立解之： （只） 此为三农户同时独立决定数量时所获得的稳定结果。任何单方面的擅自改变会使自己受损。各自得益为784，三农户总收益为2352。 从总体利益的角度来考察公共草地上羊的最
6、佳数量。设羊的总数为 ，则总得益为： = =112 -,精品课程运筹学,第二节 纳什均衡,由 ，解之得 =56（只），总收益 =3136。这说明纳什均衡常是低效的。 2.2 纳什均衡的求解 1.箭头法：纳什均衡是最优的，任何单方面的改变都将使改变者自己受损。这是箭头法的基础。箭头法对每个策略组合判断，看各博弈方能否通过改变自己的策略而改善其得益，如能，则从所考察的策略组合引一箭头到改变后的策略组合。对每个可能的策略组合进行判断,精品课程运筹学,第二节 纳什均衡,求得最优解。 如在囚徒的困境博弈中有，可从任一策略组合开始考察。先看策略组合(不坦白，不坦白)，在该策略组合时，囚徒l和囚徒2都会发觉
7、，如果自己单独改变策略就能增加自己的得益(从一1到O)，因此囚徒1原来的(不坦白，不坦白)变为(坦白，不坦白)，囚徒2也有同样 的结论。,精品课程运筹学,第二节 纳什均衡,（图8.2.1） 2.严格下策反复消去法 不管其他人策略如何变化，自己某一策略带,精品课程运筹学,第二节 纳什均衡,来的收益总被其他某些策略带来的收益要小，称这某一策略为相对于其他某些策略的严格下策策略。决策者是不可能选择任何严格下策的。如果发现某策略是相对于其他某些策略的严格下策，就可以将它从对策方的策略空间中去掉，这样就只需要在剩下的较小的策略空间中进行分析了。 例8.2.3这是一个抽象对策问题：,精品课程运筹学,第二节
8、 纳什均衡,参与人2 参 左 中 右 与 上 人 下 1 图8.2.2 参 参与人2 与 左 中 人 上 1 下 图8.2.3,精品课程运筹学,第二节 纳什均衡,参与人2 左 中 1 上 图8.2.4 对参与人2，左又成为严格劣战略，仅剩的(上，中)就是此博弈的结果 。通过上面的讨论可以看出，严格下策反复消去法与纳什均衡之间有密切的关系。下面的两个定理就是表明这种关系的 。,精品课程运筹学,第二节 纳什均衡,定 理8.2.1 在个博弈方的博弈在对策 = 中，如果严格下策反复消去法排除了 以外的所有策略组合，则一定 是G的唯一的纳什均衡。 定理8.2.2 在个博弈方的博弈 = 中，如果 是G的一
9、个纳什均衡，则严格下策反复消去法一定不会将它消去。 3.反应函数法 （适应于变量为产量等这样连续变化的情况）,精品课程运筹学,第二节 纳什均衡,例8.2.4（古诺的两寡头模型）设市场有1、2两家厂商，他们生产相同的产品。设厂商1的产量为 ，厂商2的产量为 ，则市场总产量为 。 为市场的出清价格 (可以将产品全部卖出去的价格)， =100- 。再假设两厂商的生产无固定成本，两厂家边际生产成本相等， ，两厂家同时决定各自产量，使利润最大。 设第个厂商的利润为 =,精品课程运筹学,第二节 纳什均衡,反应函数的概念：对厂商1来说，给定厂商2的任意产量 ，厂商1的最佳反应为 即厂商1的最佳产量为厂商2的
10、产量的连续函数，称此函数为厂商1对厂商2的产量的反应函数记为 。同理，厂商2对厂商1的产量的反应函数记为 。 用反应函数表示两厂商之间的产量关系为,精品课程运筹学,与 在双方反应函数 对应直线交点上，才是双方都满意的最佳反应组合，此时， 。,图8.2.5,第二节 纳什均衡,精品课程运筹学,第二节 纳什均衡,将上面模型略作修改，即为斯塔克博格模型。两个厂商中，一方较强，一方较弱。强的一方领先行动，而较弱的一方则跟在较强的一方之后行动 。设厂商1是领头厂商先行选择，厂商2追随其后，其他条件不变。 厂商1的产量 为已经确定，厂商2为使利润最大，应选择 ，厂商1知道厂商2的决策思路 = 求其最大得：,
11、精品课程运筹学,第二节 纳什均衡,与古诺模型相比，此时总产量 ，此时价格更低，利润更少。这说明垄断的效果不如自由竞争。 当然并非所有的对策都有纳什均衡，如石头、剪子、布就没有均衡。 2.3 混合策略和混合纳什均衡 定义8.2.2 在对策 = 中，局中人的策略集为 ，则他以概率分布 随机在其 个可选策略中选择的“策略”称为一个混合策略，其中,精品课程运筹学,第二节 纳什均衡,O 1对 =1， 都成立，且 =1。 由定义可以看出，纯策略也可看作混合策略。定义8.2.3 如果一个策略 = 中，参与者 的策略集为 ，如果由各个对策方的策略组成策略集合 式中 都是对其余对策方策略组合的最佳策略，即,精品课程运筹学,第二节 纳什均衡,对任意 都成立，则称 为 的一个混合策略纳什均衡。,