资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2015/3/30,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,基本,概念,对策论又称博弈论，,研究,冲突对抗条件下最优决策问题的理论。,策略,形势：,不完全竞争条件下的对抗行为,，各方收益由自身行为和其他方行为共同决定。,基本要素,局中人（,I,）,：有权决定自己行动方案的对策参加者，理性人,策略,集（,S,）,：供局中人选择的实际可行完整行动方案的集合，,一局对策中，各局中人选定策略的集合，称,局势,赢得函数（,H(s),）,:,对于任一局势，局中人的赢得值。,支付函数,严格占优策略,/,严格劣势,策略,上策均衡,/,纳什,均衡,典型案例和重要结论,结论,1,：不要选择严格劣势策略,。,结论,2,：个人理性选择导致非最优。,结论,3,：学会换位思考,。,囚徒困境,智猪博弈,求解方法：删除严格劣势策略,矩阵对策的基本理论,局中人个数：二个，多个,策略集中的个数：有限，无限,支付,/,赢得代数和：零和，非零和,局中人是否合作：非合作，合作,局中人行动时间：静态，动态,局中人对他者信息了解程度：完全信息，非完全信息,对策次数：单次，重复,对策,/,博弈分类,课程目标,理解并掌握矩阵对策的纯策略,理解,并掌握,矩阵对策的混合策略,掌握矩阵对策的求解方法,矩阵对策的策略,纯策略：确定,的选择某,策略,混合策略：以,某一概率分布选择各策略。,矩阵对策的纯策略,的赢得,矩阵,或,的,支付矩阵,的赢得矩阵为,-A,。,1,、矩阵对策的一般表达,矩阵对策的纯策略,例：,田忌赛马,局中人：田忌（,I,）、齐王（,II,）,S,1,=,（上、中、下），（上、下、中），（中、上、下），,（中、下、上），（下、中、上），（下、上、中）,=,S,2,1,、矩阵对策的一般表达,矩阵对策的纯策略,-8,2,-10,-3,9,2,6,理智,行为：,从各自最不利情形中选择最有利,I,：最大最小,原则,II,：最小最大原则,平衡局势：,双方均可接受，且对双方都是最稳妥的结果。,（,2,，,2,），,局中人,I,和,II,的最优纯策略。,2,、矩阵对策解的引例,矩阵对策的纯策略,从上例看出，矩阵,A,中平衡局势（,2,，,2,）对应的元素,a,22,既是其所在行的最小元素，也是其所在列的最大元素，即有,a,i2,a,22,a,2j,i=1,2,3,4 j=1,2,3,3,、矩阵对策的最优纯策略,矩阵对策的纯策略,1,2,3,1,3,7 4 6,3,、矩阵对策的最优纯策略,矩阵对策的纯策略,对于一个对策,G,=,S,1,S,2,A,若,有,则称局势（,i,*,j,*,）为对策,G,的,鞍点,，,V=a,i*j*,为,对策,G,的值。,注：在,矩阵中，一个数在所在行中是最大值，在所在列中是最小值，则被称为,鞍点,。,4,、矩阵对策的鞍点与解,矩阵对策的纯策略,多鞍点与无鞍点对策,例,:,设有一矩阵对策如下，求它的解。,局势,（,1,2,），（,1,4,），,（,3,2,）,（,3,4,）均构成鞍点，此对策有多个解。,4,、矩阵对策的鞍点与解,矩阵对策的纯策略,性质,1,：无差别性,若,（,i,1,，,j,1,）,和,（,i,2,，,j,2,）,是对策,G,的两个解，则,a,i,1,j,1,=a,i,2,j,2,性质,2,：可交换性,若（,i,1,，,j,1,）和（,i,2,，,j,2,）,是对策,G,的两个解，,则,（,i,1,，,j,2,）,和,（,i,2,，,j,1,）,也是,对策,G,的两个,解。,矩阵对策,的值唯一。,即当一个局中人选择了最优纯策略后，他的赢得值不依赖于对方的纯策略,。,5,、矩阵对策纯策略的性质,作业,P385,习题,12.2,12.3,12.4,矩阵对策的混合策略,3,4,5,6,无鞍点,1,、混合策略,矩阵对策的混合策略,1,、混合策略,矩阵对策的混合策略,2,、混合局势,3,、赢得期望,4,、混合策略对策模型,矩阵对策的混合策略,5,、最优混合策略,设 ，是矩阵对策 的混合扩充。,矩阵对策的混合策略,5,、最优混合策略,矩阵对策的混合策略,定理,2,：,矩阵对策,G,在混合策略意义下有解的充要条件是：,存在 ，使得对于任意 ，有,2,、最优混合策略,矩阵对策的混合策略,3,、最优混合策略解,的引例,矩阵对策的解法,例：求解矩阵对策,G=,其中,解：,（,1,）不存在鞍点，为混合策略求解问题。,（,2,）图解法求解,设局中人,I,的混合策略为（,x,1-x,）,T,，。,0,1,I,I,II,II,数轴上坐标为,0,和,1,的两点分别做两条垂线,I-I,和,II-II,。,画,出局中人,II,的不同策略下局中人,I,的赢得线段。,2,5,7,2,3,11,1,=2x+7(1-x),2,=3x+5(1-x),3,=11x+2(1-x),图解法,仅适用于赢得矩阵为,2n,或,m2,阶的矩阵对策问题。,1,:v,1,1,=2x+7(1-x),2,:,v,1,2,=3x+5(1-x,),3,:,v,1,3,=11x+2(1-x,),由于局中人,II,理性，局中人,I,从最少可能收入中选择最大的一个，为局中人,I,的最优对策。,B,2,求解方程组可得最优混合策略和矩阵对策的值。,图解法,0,1,I,I,II,II,2,5,7,2,3,11,1,=2x+7(1-x),2,=3x+5(1-x),3,=11x+2(1-x),B,1,B,2,B,3,B,4,联立过,B,2,点两,条直线的方程组为,可解得,则，局中人,I,的最优策略为,由图可见局中人,II,的混合策略只有,2,和,3,组成。,设局中人,II,的最优混合策略为 ，且,P365,例,10,图解法,求局中人,II,的最优混合策略。,同理，可得局中人,II,的赢得，,1,:v,2,1,=3y,2,+11y,3,2,:,v,2,2,=5y,2,+2y,3,画出赢得线段，见右图,0,1,y,y,*,3,1,11,5,2,2,局中人,I,理性，局中人,II,取最大损失的最小值,联立方程组可得,解得,方程组法,定理：,设 ，则 为,G,的解的充要条件是：,存在数,v,，使得,x,*,y,*,分别,是下列不等式组的解，且,v=V,G,。,若,x,i,*,y,j,*,均不为,0,，则上述不等式的求解即可转化为下列两个方程组的求解问题。,注：,若上述,两个方程组存在非负解,x,*,y,*,，即矩阵对策的解。若不存在非负解，则将上述方程组中的某些等式转化为不等式，继续求解。,由于事先假设,x,i,*,y,j,*,均不为,0,，故，当最优策略的某些分量为,0,时，方程组可能无解，因此该方法具有一定的局限性。,方程组法,例：求解矩阵对策,G=,其中,A,为,解：（,1,）删除劣势策略，得到,无鞍点,和,（,2,）构造方程组,线性规划法,注：,适用于所有,a,ij,0,若存在,a,ij,0,，可取一充分大的,M,0,，使得,M,+,a,ij,0,线性规划法,例：两人“石头、剪刀、布”矩阵对策求解,解：,(,X,*,，,Y,*,),为,矩阵对策的解,作业,P386,习题,12.5,12.6,12.7,Q&A,33,谢谢！,34,
展开阅读全文