[工程科技]第十二章对策论

《[工程科技]第十二章对策论》由会员分享，可在线阅读，更多相关《[工程科技]第十二章对策论（63页珍藏版）》请在金锄头文库上搜索。

1、第十二章 对策论,Game Theory,运筹学 Operations Research,12.1 引 言 12.2 纳什均衡 12.3 反应函数法 12.4 有限二人零和对策 12.5 有限二人非零和对策,11.1 引言 Introduction,警察抓住两个合伙犯罪的嫌疑犯，但缺乏足够的证据指证他们的罪刑，若 其中一个供认犯罪，就能确认罪名成立。为得到所需的口供，警察将两嫌疑犯 分开关押并给他们同样的选择机会，若两人都拒不认罪，则他们会以较轻的妨 碍公务罪各判一年徒刑；若有一人坦白认罪，则坦白者立即释放，而另一个人 则判10年徒刑，若两人同时认罪，则他们各被判5年徒刑，现两个嫌疑犯该如何

2、采取各自的策略(坦白、不坦白)对自己有利？,这是一个二人非零和对策问题，可用一个矩阵来表示两囚徒的得益，如下表所示：,(1) 1713年，瓦德格拉夫提出两人对策的经典模型；,对策论历史简介：,(2) 古诺和博特兰分别在1838年与1883年提出对策论最经典的模型；,(4) 1944年，冯诺依曼和摩根斯坦合著出版博弈论与经济行为一书，被 看作是对策论真正发展的起点；,(3) 中国古代的“齐王赛马”；,(5) 1994年，瑞典皇家科学院决定将诺贝尔经济学奖授予纳什、哈萨尼和泽 尔腾三人，表彰他们在博弈理论和应用方面作出的杰出贡献；,(6) 目前，博弈论在定价、招投标、谈判、拍卖、委托代理以及很多的

3、经营 决策中得到应用，它已成为现代经济学的重要基础。现代对策论总体上是一门 新兴的发展中的学科。,Nash对对策论的贡献有： (i) 合作对策中的讨价还价模型，称为Nash讨价还价解； (ii) 非合作对策的均衡分析。,对策论(game theory)亦称博弈论: 是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。,12.1.1 对策论概述,12.1 引言,对策行为: 是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方案,并力图选择对自己最为有利或最为合理的方案 。,对策：是一些

4、个人、对组或其它组织，面对一定的环境条件，在一定的规则下，同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得相应结果的过程。,对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及 如何找到这个合理方案的数学理论和方法。是研究决策主体的行为发生直接 相互作用时的决策及这种决策的均衡问题。即它是研究聪明而又理智的决策 者在冲突或合作中的策略选择理论。它将成为当代经济管理学科的前沿领城。,一个对策需要3个基本要素： (1)局中人(players) (2)策略集(strategies) (3)得益函数(payoffs),12.1.2 对策三要素,12.1 引言,12.1.3 对

5、策的结构和分类,12.1 引言,下一节：纳什均衡,12.1 引言,12.2 纳什均衡 Nash Equilibrium,对于对策中的每一个局中人，真正成功的措施应该是针对于其他局中 人所采取的每次行动，相应地采取有利于自己地反应策略，于是每一 个局中人应采取的必定是他对其他局中人策略的预测的最佳反应。,【定义 12.1】 在对策G=S1，S2，Sn；h1，h2hn中，如果由各个对策方的各选取一个策略组成的某个策略组合(S1*，S2*，Sn*)中，任一对策方i 的策略Si*，都是对其余策略方策略的组合 (S1*，S*i-1，S*i+1，Sn*)的最佳策略，即h i(S1*, , S*i-1, S

6、i*, S*i+1,Sn*)hi(S1*, , S*i-1, Sij, S*i+1 , , Sn*)对任意 SijSi 都成立，则称(S1*，Sn*)为G的一个纯策略意义下的“纳什均衡”(Nash Equilibrium),12.2 纳什均衡,12.2.1 纳什均衡定义,定义中各选取一个策略组成的某个策略组合构成一个局势，其最优局势称为纯策略意义下的最优局势,12.2 纳什均衡,分析：采用比较和试探的方法来确定本决策的均衡产量。不妨先假设三个厂商开始时分别生产3单位，9单位和6单位产量，这时三厂商是否满意各自的产量，要从利润进行分析。由于产量不能超过20，则第i个厂商的利润函数为,根据上述公式

7、可算出在产量组合为(3，9，6)时，市场价格为2，三厂商的利润分别为6，18和12，再作其它产量组合时亦会有不同的结果，如表12.2,表12.2 三厂商离散产量结合对应价格和利润,12.2 纳什均衡,注: (1)上述产量组合给各厂商带来的利润并不是市场能给他们的最大利润； (2) 三厂商开始并不一定选取这种产量组合，而是在长期的对策过程中逐渐调整到这个产量组合，这个组合就是一个纳什均衡。,由表可看出(5, 5, 5)这组产量组合是比较稳定的，因为在该组合下，任何一个厂商单独提高或降低产量，都只会减少利润，因此该产量组合是一个均衡。,【例12.2】1943年2月，日本统帅山本五十六大将计划由南太

8、平洋新不列颠群岛的拉包尔出发，3天穿过俾斯麦海，开往新几内亚的莱城，支援困守的日军。有两条路线：北线和南线。,美国盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。侦察机重点搜索有两个方案：北线和南线。,当时未来3天中：北线阴雨，能见度差；南线晴天，能见度佳。日美双方各自都仔细分析了两种方案的结果，如表(12.3)所示，问日美双方应采用哪种方案较好？,12.1 引言,北线,南线,【解】局中人：盟军、日军；双方策略：北线、南线，记为: 盟军的赢得矩阵如下：,最优策略是： ,即都选择北线。日军舰队受到重创，但未全歼。,双方选择的策略是：在最 不利中选择最有利的策略。,12.1 引

9、言,【定义12.2】 在对策G=S1，Sn；h1，hn中，局中人 i 的策略集为Si=Si1，Sik，则他以概率分布pi=(pi1，pik)随机在其k个可选策略中选择的“策略”称为一个混合策略，其中 0pij1 对 j1, , k 都成立，且pi1+pik=1,12.2.2 混合策略纳什均衡,12.2 纳什均衡,注：纯策略可看作混合策略的一种特殊情况，只是选择相应纯策略的概率函数服从(0-1)分布,下一节：反应函数法,12.2 纳什均衡,12.3 反应函数法,反应函数法是对策论中一种常用的方法，尤其适用于确定决策变量为产量或价格这样的连续函数策略。当得益是对策的多元连续函数时，求出每个对策方的

10、反应函数，而各个反应函数的交点就是纳什均衡。,12.3 反应函数法,【例12.3】设A，B两厂家生产同样产品，厂商A产量为q1，B产量为q2，市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数P6Q。设产品产量的边际成本相等，C1=C2=2。求解两厂商的纳什均衡(假设产量连续可分)。,分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂商各自的利润分别为各自的销售收益减去各自成本，即：,从得益函数表达式中可以看出，两者的利润取决于对方的策略即产量，要寻找 一个纳什均衡，即对厂商2的任意产量，厂商1有一个最佳的对应产量，实现利润最大化，即求解,用求极值方法求得,同理厂商2的最佳产量为

11、,12.3 反应函数法,作反应函数：,纳什均衡：(4/3,4/3),由上面两个式子，得出对于厂商2的每一个可能的产量，厂商1的最佳产量是 厂商2产量的一个连续函数，我们称这个连续函数为厂商1对厂商2产量的一个 反应函数。,12.3 反应函数法,【例12.4】 考虑上述模型的另一种情况即各厂商所选择的是价格而不是产量，假设产量与价格的函数关系为：,其它条件不变，边际成本为C1、C2，试求解其纳什均衡。,【解】设P1max, P2max为两厂商所能选择的最高价格，则其各自的策略空间为,两方的得益就是各自的利润,利用得益函数在偏导数为0时有最大值，各自的反应函数分别为：,12.3 反应函数法,为该对

12、策唯一的纳什均衡,12.3 反应函数法,【解】各农户的得益函数分别为,反应函数,因此该对策的纳什均衡为(18，18，18) 。,12.3 反应函数法,下一节：有限二人零和对策,作业：教材P293 T 9,12.4 有限二人零和对策,有限二人零和对策也称矩阵对策或二人有限零和对策，其对策中存在两个局中人，并且局中人都只有有限个决策可供选择，在任一局势下，两个局中人的赢得之和总是等于零，双方的利益是激烈对抗的。,12.4 有限二人零和对策,用、表示两个局中人，并设局中人有 m个纯策略 ，局中人有n个纯策略 ，则按对策论的相关要素定义，局 中人、的策略集分别为：,12.4.1 数学定义,称A为局中人

13、的赢得矩阵(或为的支付矩阵)，由于对策为零和的，故局中人的赢得矩阵为A。,当局中人、的策略集S1, S2及I的赢得矩阵确定后，一个矩阵对策就给定了通常将矩阵对策记为：,12.4 有限二人零和对策,矩阵对策纯策略纳什均衡：矩阵对策模型给定后，对各局中人而言，就是如何选取对自己最有利的策略以获得最大得益。,12.4.2 纯策略矩阵对策,【例12.6】求矩阵对策，其中 ，,由A可以看出局中人1的最大得益是7，要想得到这个得益，他需选择策略 3，而局中人2也是理智的，他会考虑用策略3来对付，这样局中人1不但得不到 7 反而会失去11，故双方都不愿意冒险，而是考虑到双方必使自己获得最少这 一点。,则有,

14、对策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，i *=1,3，j *=2, 4, 故 (1,2)(1, 4)(2,2)(2,4) 为对策的纳什均衡，VG=5,12.4 有限二人零和对策,【解】 直接在赢得表上计算，有,【性质12.1】 无差别性若 和 为G的两个解，则：,注：

15、以上方法也称“上策均衡法”(Dominant-stratege Eqyilibrium),12.4 有限二人零和对策,纯策略意义下对策解的性质：,【例12. 8】 甲、乙两个企业同时生产一种电子产品(假设市场上只有这两家，为一双寡头竞争局面)，两个企业都想通过改革管理获取更多的销售份额, 甲 企业的策略措施有: (1)降低产品价格；(2)提高产品质量；(3)推出新产品乙 企业措施为: (1)增加广告费用；(2)增设网点；(3)改进产品性能, 通过预测, 两 个企业市场份额变动情况如表12.4所示，试确定最优策略,【解】,则对策最优解为VG=5，纳什均衡为(3 , 3)甲企业采用推出新产品策略，乙企业采用改进产品性能策略，结果甲企业赢得5的市场份额,12.4 有限二人零和对策,表12.4,12.4.3 混合策略矩阵对策,纯策略矩阵对策的满足纳什均衡是满足局中人有把握的至少赢得是局中人有把握的至多损失即：,当V1V2 时，这时不存在纯策略意义下的纳什均衡 。如：,12.4 有限二人零和对策,对局中人1来说，V1=2，i *=3，对局中人2来说，V2=3，j *=1，V1V2 , 没有鞍点。,【定义12.6】设矩阵对策 ，其中 记,12.4 有限二人零和对策,当 时，称 为局中人