运筹学第六讲对策论

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