运筹学第六讲对策论.ppt

对策论,GameTheory,运筹学OperationsResearch,(1)1713年，瓦德格拉夫提出两人对策的经典模型；,对策论历史简介：,(2)古诺和博特兰分别在1838年与1883年提出对策论最经典的模型；,(4)1944年，冯诺依曼和摩根斯坦合著出版博弈论与经济行为一书，被看作是对策论真正发展的起点；,(3)中国古代的“齐王赛马”；,(5)1994年，瑞典皇家科学院决定将诺贝尔经济学奖授予纳什、哈萨尼和泽尔腾三人，表彰他们在博弈理论和应用方面作出的杰出贡献；,(6)目前，博弈论在定价、招投标、谈判、拍卖、委托代理以及很多的经营决策中得到应用，它已成为现代经济学的重要基础。现代对策论总体上是一门新兴的发展中的学科。,Nash对对策论的贡献有：(i)合作对策中的讨价还价模型，称为Nash讨价还价解；(ii)非合作对策的均衡分析。,警察抓住两个合伙犯罪的嫌疑犯，但缺乏足够的证据指证他们的罪刑，若其中一个供认犯罪，就能确认罪名成立。为得到所需的口供，警察将两嫌疑犯分开关押并给他们同样的选择机会，若两人都拒不认罪，则他们会以较轻的妨碍公务罪各判一年徒刑；若有一人坦白认罪，则坦白者立即释放，而另一个人则判10年徒刑，若两人同时认罪，则他们各被判5年徒刑，现两个嫌疑犯该如何采取各自的策略(坦白、不坦白)对自己有利？,这是一个二人非零和对策问题，可用一个矩阵来表示两囚徒的得益，如下表所示：,对策论(gametheory)亦称博弈论:是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。,对策论概述,引言,对策行为:是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方案,并力图选择对自己最为有利或最为合理的方案。,对策：是一些个人、对组或其它组织，面对一定的环境条件，在一定的规则下，同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得相应结果的过程。,对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理方案的数学理论和方法。是研究决策主体的行为发生直接相互作用时的决策及这种决策的均衡问题。即它是研究聪明而又理智的决策者在冲突或合作中的策略选择理论。它将成为当代经济管理学科的前沿领城。,一个对策需要3个基本要素：(1)局中人(players)(2)策略集(strategies)(3)得益函数(payoffs),对策三要素,引言,对策的结构和分类,引言,纳什均衡NashEquilibrium,对于对策中的每一个局中人，真正成功的措施应该是针对于其他局中人所采取的每次行动，相应地采取有利于自己地反应策略，于是每一个局中人应采取的必定是他对其他局中人策略的预测的最佳反应。,【定义】在对策G=S1，S2，Sn；h1，h2hn中，如果由各个对策方的各选取一个策略组成的某个策略组合(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*)对任意SijSi都成立，则称(S1*，Sn*)为G的一个纯策略意义下的“纳什均衡”(NashEquilibrium),纳什均衡,纳什均衡定义,定义中各选取一个策略组成的某个策略组合构成一个局势，其最优局势称为纯策略意义下的最优局势,纳什均衡,分析：采用比较和试探的方法来确定本决策的均衡产量。不妨先假设三个厂商开始时分别生产3单位，9单位和6单位产量，这时三厂商是否满意各自的产量，要从利润进行分析。由于产量不能超过20，则第i个厂商的利润函数为,根据上述公式可算出在产量组合为(3，9，6)时，市场价格为2，三厂商的利润分别为6，18和12，再作其它产量组合时亦会有不同的结果，如表12.2,表12.2三厂商离散产量结合对应价格和利润,纳什均衡,注:(1)上述产量组合给各厂商带来的利润并不是市场能给他们的最大利润；(2)三厂商开始并不一定选取这种产量组合，而是在长期的对策过程中逐渐调整到这个产量组合，这个组合就是一个纳什均衡。,由表可看出(5,5,5)这组产量组合是比较稳定的，因为在该组合下，任何一个厂商单独提高或降低产量，都只会减少利润，因此该产量组合是一个均衡。,纳什均衡,【定义】在对策G=S1，Sn；h1，hn中，局中人i的策略集为Si=Si1，Sik，则他以概率分布pi=(pi1，pik)随机在其k个可选策略中选择的“策略”称为一个混合策略，其中0pij1对j1,k都成立，且pi1+pik=1,混合策略纳什均衡,纳什均衡,注：纯策略可看作混合策略的一种特殊情况，只是选择相应纯策略的概率函数服从(0-1)分布,反应函数法,反应函数法是对策论中一种常用的方法，尤其适用于确定决策变量为产量或价格这样的连续函数策略。当得益是对策的多元连续函数时，求出每个对策方的反应函数，而各个反应函数的交点就是纳什均衡。,反应函数法,【例3】设A，B两厂家生产同样产品，厂商A产量为q1，B产量为q2，市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数P6Q。设产品产量的边际成本相等，C1=C2=2。求解两厂商的纳什均衡(假设产量连续可分)。,分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂商各自的利润分别为各自的销售收益减去各自成本，即：,从得益函数表达式中可以看出，两者的利润取决于对方的策略即产量，要寻找一个纳什均衡，即对厂商2的任意产量，厂商1有一个最佳的对应产量，实现利润最大化，即求解,用求极值方法求得,同理厂商2的最佳产量为,反应函数法,作反应函数：,纳什均衡：(4/3,4/3),由上面两个式子，得出对于厂商2的每一个可能的产量，厂商1的最佳产量是厂商2产量的一个连续函数，我们称这个连续函数为厂商1对厂商2产量的一个反应函数。,反应函数法,【例4】考虑上述模型的另一种情况即各厂商所选择的是价格而不是产量，假设产量与价格的函数关系为：,其它条件不变，边际成本为C1、C2，试求解其纳什均衡。,【解】设P1max,P2max为两厂商所能选择的最高价格，则其各自的策略空间为,两方的得益就是各自的利润,利用得益函数在偏导数为0时有最大值，各自的反应函数分别为：,反应函数法,为该对策唯一的纳什均衡,反应函数法,【解】各农户的得益函数分别为,反应函数,因此该对策的纳什均衡为(18，18，18)。,有限二人零和对策,有限二人零和对策也称矩阵对策或二人有限零和对策，其对策中存在两个局中人，并且局中人都只有有限个决策可供选择，在任一局势下，两个局中人的赢得之和总是等于零，双方的利益是激烈对抗的。,有限二人零和对策,用、表示两个局中人，并设局中人有m个纯策略，局中人有n个纯策略，则按对策论的相关要素定义，局中人、的策略集分别为：,数学定义,称A为局中人的赢得矩阵(或为的支付矩阵)，由于对策为零和的，故局中人的赢得矩阵为A。,当局中人、的策略集S1,S2及I的赢得矩阵确定后，一个矩阵对策就给定了通常将矩阵对策记为：,有限二人零和对策,矩阵对策纯策略纳什均衡：矩阵对策模型给定后，对各局中人而言，就是如何选取对自己最有利的策略以获得最大得益。,纯策略矩阵对策,【例6】求矩阵对策，其中，,由A可以看出局中人I的最大得益是7，要想得到这个得益，他需选择策略3，而局中人2也是理智的，他会考虑用策略3来对付，这样局中人1不但得不到7反而会失去11，故双方都不愿意冒险，而是考虑到双方必使自己获得最少这一点。,则有,对策G的解为：,有限二人零和对策,【定理】矩阵对策G=S1，S2；A在纯策略定义下有纳什均衡的充要条件是：存在策略组合使得对一切i=1,m,j=1,n有：,注：矩阵对策在纯策略意义下有解且VG=ai*j*的充要条件是：ai*j*是A的鞍点，在对策论中，矩阵A的鞍点也称为对策的鞍点,有限二人零和对策,可知=5，i*=1,3，j*=2,4,故(1,2)(1,4)(2,2)(2,4)为对策的纳什均衡，VG=5,有限二人零和对策,【解】直接在赢得表上计算，有,【性质1】无差别性若和为G的两个解，则：,注：以上方法也称“上策均衡法”(Dominant-strategeEqyilibrium),有限二人零和对策,纯策略意义下对策解的性质：,混合策略矩阵对策,纯策略矩阵对策的满足纳什均衡是满足局中人有把握的至少赢得,也是局中人有把握的至多损失即：,当V1V2时，这时不存在纯策略意义下的纳什均衡。如：,有限二人零和对策,对局中人1来说，V1=2，i*=3，对局中人2来说，V2=3，j*=1，V1V2,没有鞍点。,有限二人零和对策,当时，称为局中人、在混合策略中的纳什均衡。,称为局中人在选取混合策略S*1时的赢得函数。,有限二人零和对策,【解】纯策略纳什均衡不存在设x=(x1，x2)为局中人的混合策略，y=(y1，y2)为局中人的混合策略，则：,局中人I的赢得期望值：,有限二人零和对策,即取，满足,则分别为局中人I,II的最优策略，,纳什均衡存在定理,【定理】设x*S1*，y*S2*,则(x*，y*)为对策G的纳什均衡的充要条件是：对任意i=1,m，j=1,n,有E(i,y*)E(x*,y*)E(x*,j),其中：,有限二人零和对策,【定理】对任一矩阵对策G=S1，S2；A，一定存在混合策略意义下的纳什均衡,有限二人零和对策,有限二人零和对策,【定理】设有两个矩阵对策G1=S1，S2；A,G2=S1，S2；A，则(1)VG2=VG1(2)T(G1)=T(G2)，其中0为一常数，T(G1)、T(G2)为两个对策的解集合。,矩阵对策求解方法,1、2n矩阵对策的求解方法:,思路:先研究简单的22矩阵对策，然后推广到2n情形。,22矩阵对策的公式法(适用于无最优纯策略),在无最优纯策略情形下可证明，且,设矩阵对策中各局中人的最优混合策略为,由定理12.5可知，该矩阵对策一定存在混合最优策略，根据定理12.6求解,有限二人零和对策,公式的特征(记忆方法)：,有限二人零和对策,2n矩阵对策的代数解法,(1)将A的每两列组成一个子赢得矩阵，设为,(2)用公式法求解,(3),(4)计算子策略,(5)产生最优混合策略：,有限二人零和对策,2.优超原则法,【定义】设矩阵对策，其中若对于一切j=1,2,n有，即矩阵的第行元素不