1、第二节 完全信息动态搏弈 -子博弈精炼纳什均衡n一 博弈扩展式表述n二 子博弈精练纳什均衡n三 应用举例 战略式主要用于描述和分析静态博弈,给出的是参与人有什么战略可供选择,用博弈支付矩阵表示;扩展式主要用于描述和分析动态博弈,给出的是参与人的相机行动规则(依据条件选择行动),用博弈树表示。无圈的连通图(每一对定点之间至少存在一条链)是树图。 博弈的扩展式表述所“扩展”的主要是参与人的战略空间。一 博弈扩展式表述博弈的战略表述案例- 房地产开发项目-假设有A、B两家开发商市场需求:可能大,也可能小投入:1亿v假定市场上有两栋楼出售:需求大时,每栋售价1.4亿,需求小时,售价7千万;v如果市场上
2、只有一栋楼需求大时,可卖1.8亿需求小时,可卖1.1亿博弈战略表述40004000,4000400080008000,0 00 0,800080000 0,0 0不开发开发商A开发不开发开发-3000-3000,-3000-300010001000,0 00 0,100010000 0,0 0不开发开发商B开发商A开发不开发开发开发商B需求小的情况需求小的情况需求大的情况需求大的情况博弈的战略式表述一 博弈扩展式表述n博弈的扩展式表述包括三个要素:参与人集合每个参与人的战略集合由战略组合决定的每个参与人的支付进入者进入不进入(0,300)在位者市场进入阻挠博弈树不可置信威胁合作(40,50)斗
3、争(-10,0)A开发不开发NN大小1/21/2大小1/21/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)参与人(A,B,N)战略支付参与人集合参与人行动顺序参与人的行动空间参与人的信息集参与人的支付函数外生事件的概率分布房地产开发博弈结,决策结结,终点结枝结,初始结 信息集一 博弈扩展式表述博弈树的基本构造l结: 包括决策结和终点结两类;决策结是参与人行动的始点,终点结是决策人行动的终点.l一般用X表所有结的集合, 表某个特定结。用“ ”定义X上的顺序关系(半序)。结的传递性:结的反对称性:xX1122
4、,.xxxxxx则,xxxx如果则不成立。博弈树不允许的情况AB一 博弈扩展式表述lx之前的所有结的集合,称为x的前列集P(x);lx之后的所有结的集合称为x的后续集 T(x)。l初始结: 用O表示(空心圆);l终点结: 用Z表示终点结集合;l决策结:用X表示决策结集合(实心圆)。l博弈树的结都是所有之前发生事件的一个完整描述(即初始结到任何其他结的路径唯一)。l传递性和反对称性排除了A的情况,但没排除B的情况。进一步假定:( ),P x ( ),T x 121221,xxxxxxxxx那么或,也即 的所有前列结必须是全排序的。一 博弈扩展式表述nx(非初始结)的直接前列结p(x):n 任何一
5、个非初始结的直接前列结是唯一的(前列结是全排序的)。n如果 是x的直接前列结,x称为 的直接后续结。n除终点结没有后续结外,一个结一般有多个直接后续结(即行动的数量),该集合用t(x).( )( ),( )( ).p xP x stxx xp xxp x即xx一 博弈扩展式表述l在决策结旁标注参与人表示其在该结点行动,定义函数:l即i(x)定义为从决策结集合到参与人的函数,表在决策结参与人i行动。该函数给出了参与人行动的顺序。l终点结下标注参与人的支付向量: , z表从初始结到终点结行为人i行动博弈树路径。l枝: 枝是从一个决策结到它的直接后续结的连线,每一个枝代表参与人的一个行动选择. 含行
6、动空间和路径。n给定决策结 存在一个有限集合A(x)和一个单映射函数 意味对于任意给定的非终结点,可选择的行动集合A(x)与该节点后续结集合t(x)一 一对应:: ,1,2,i XNn( )iu z: ( )( ).a t xA xxX( ),( )( , )( ,).aA x aA xaat x at x a若且一 博弈扩展式表述l信息集: 每个信息集是决策结集合的一个子集,该子集包括所有满足下列条件的决策结:1 每个决策结都是同一个参与人的决策结;2 该参与人知道博弈进入了该集合的某个决策结,但不知道自己究竟处于哪一个决策结.n一般用H代表信息集的集合, 代表一个特定的信息集。h(x)表包
7、含决策结x的信息集:在x点决策的参与人i不确定他/她是否处在x还是 即一个决策结仅且只属于一个信息集: n此外假定 hH( );xh x( )().xh xxh x(1)()( ):(2) ( )()(3) ( )()xP xxP xi xi xA xA x且参与人记得之前的行动;:同一信息的结属同一参与人;:同一信息结的行动空间相同。A开发不开发NN大小1/21/2大小1/21/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)图2.1房地产开发博弈A开发不开发NN大小1/21/2大小1/21/2BBBB开发
8、不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0) B在决策时不确切地知道自然的选择; B的信息集由4个变为2个图2.3房地产开发博弈A开发不开发NN大小1/21/2大小1/21/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0) B知道自然的选择;但不知道A的选择(或A、B同时决策) 图2.4房地产开发博弈一 博弈扩展式表述n只包含一个决策结的信息集称为单结信息集,如果博弈树的所有信息都是单结的,该博弈称为完美信息博弈。n完美信息博弈意味着
9、博弈中没有任何两个参与人同时行动,且后行动者知道所有前序行动(任何两个决策结都无虚线相连)。n自然总是假定是单结的,因为自然在参与人决策之后行动等价于自然在参与人之前行动但参与人不能观测到自然的行动。一 博弈扩展式表述n不同的博弈树可能代表相同的博弈,但是有一个基本规则:一个参与人在决策之前知道的事情,必须出现在该参与人决策结之前。即如果B在决策时知道A 的选择,则A的决策结必是B决策结的前列结。n同一参与人在代表同一博弈的不同博弈树中的信息集的数量必须相同。检验图2.6和图2.7与图2.4代表相同的博弈N大小AA开发不开发1/21/2开发不开发1/21/2BBBB开发不开发开发不开发开发不开
10、发开发不开发(4,4)(8,0)(0,8)(0,0)(-3,-3) (1,0)(0,1)(0,0)图2.6房地产开发博弈:第二种表述N大小BB开发不开发1/21/2开发不开发1/21/2AAAA开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(0,8)(0,0)(-3,-3) (1,0)(0,1)(0,0)图2.7房地产开发博弈:第三种表述AB坦白抵赖BBAA坦白抵赖坦白抵赖(-8,-8)(0,-10)(-10,0) (-1,-1)坦白抵赖坦白抵赖坦白抵赖(-8,-8)(0,-10) (-10,0)(-1,-1)囚徒困境博弈的扩展式表述一 博弈扩展式表述智猪博弈的扩展式表述?5,1
11、4,49,-10,0等待小猪大猪按等待按案例2-智猪博弈1NLR2UD(a).UDRL1U2L1D图2.9 参与人不具完美回忆的两个例子一 博弈扩展式表述LR1R完美回忆:没有参与人会忘记自己之前知道的事 情,所有参与人都知道自己以前的选择。(b).一 博弈扩展式表述n为使博弈树满足完美回忆“参与人能记着之前知道的所有事情”特征特要求:21121111(1)()(,(2)()(),(3) ( )()(),xh xxxxP xxxi xi xxxix如果和属同一信息集)是 的前列集中结和 都是的决策结那么,存在一个 ,满足:212(1)( ),(2)(),(3)xh xxP xxxxx点到达 的
12、行动与 点到达 的行动是一致的。因 和 同属一个信息集, 是 的前列结,那一定存在 的一个前列结 与 同属于一个信息集;参与者记住他选择的行动,从属于同一信息集的 和 出发,一定选择了同样的行动。1x2x1xx2xxxxxRUDLU1LD图2.10 美回忆的例子一 博弈扩展式表述Rxx1x2x1一 博弈扩展式表述n当博弈涉及到外生的不确定性事件时,我们假定“自然”以某种概率选择某个特定事件(用方括号的数字代表概率)。n并假定所有参与人对自然的选择具有相同的先验概率(“海萨尼公理”)。n作业: P233_1人有了知识,就会具备各种分析能力,明辨是非的能力。所以我们要勤恳读书,广泛阅读,古人说“书中自有黄金屋。”通过阅读科技书籍,我们能丰富知识,培养逻辑思维能力;通过阅读文学作品,我们能提高文学鉴赏水平,培养文学情趣;通过阅读报刊,我们能增长见识,扩大自己的知识面。有许多书籍还能培养我们的道德情操,给我们巨大的精神力量,鼓舞我们前进。