完全信息动态博弈第二章展开型博弈.PPT

《完全信息动态博弈第二章展开型博弈.PPT》由会员分享，可在线阅读，更多相关《完全信息动态博弈第二章展开型博弈.PPT（47页珍藏版）》请在三一文库上搜索。

1、第二部分 完全信息动态博弈第二章 展开型博弈一、博弈树1.博弈树的所包含的信息（1）局中人的集合（2）行动的次序（3）局中人行动时的纯策略空间（4）局中人作出行动决策时所获得的信息集合。（5）局中人的盈利或效用（6）任何外生事件上的概率分布。例122左右ABCD（3，1）（5，6）（4，2）（2，7）2.博弈树规则(1)每一个结至多有一个其他结直接位于它的前面。(2)在博弈树中没有一条路径可以使决策结与自身相连。(3)博弈树必须有初始结(4)每个博弈树只有一个初始结3、完美信息与不完美信息定义定义：假如一个局中人在轮到他行动时知道自己处于博弈树的那个结上，我们称该局中人有完美信息。博弈中的每一

2、个局中人都具有完美信息，则称该博弈有完美信息。如果局中人在不知道另外的局中人前面行动的情况下必须行动，则称该局中人具有不完美信息。倘若至少有一个局中人具有不完美信息，则称该博弈具有不完美信息。122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h22（3,1）（2,7）122左右ABAB（5,6）（4,2）h1h2h2左ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)EFh21h22h12h1右左ABCDh1h12h22右ababcdcdh21h21h31h31(1,2)(0,3)(3,1)(-1,4)(2,1)(0,0)(-1,1)(3,2)二、展开型博弈的策略

3、与均衡1.概念信息集Hi=hi：hi是局中人i的信息集行动空间A(hi)：局中人i基于信息集hi的行动全体Ai=hiHiA(hi)：局中人i的所有行动的集合纯策略空间局中人i的一个纯策略si：HiAi (hiHi，si(hi)A(hi)Si=si：si是局中人i的一个纯策略Si=hiHiA(hi)纯策略组合S=Si局中人局中人1 1信息集：H1=h1；行动空间：A(h1)=左,右纯策略空间：S1=A(h1)=左,右122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h22局中人局中人2 2信息集：H2=h12，h22；行动空间：A(h12)=A,B;A(h22)=C,D纯策略空

4、间：S2=A(h12)A(h22)=(A,C),(A,D),(B,C),(B,D)纯策略组合S=左,(A,C),左,(A,D),左,(B,C),左,(B,D),右,(A,C),右,(A,D),右,(B,C),右,(B,D)122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h222、展开型博弈的策略型表示3,13,15,65,64,22,74,22,7左右（A,C）（A,D）（B,C）（B,D）122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h22（3,1）（2,7）122左右ABAB（5,6）（4,2）h1h2h2局中人局中人1 1信息集：H1=h1；行动

5、空间：A(h1)=左,右纯策略空间：S1=A(h1)=左,右局中人局中人2 2信息集：H2=h2；行动空间：A(h2)=A,B纯策略空间：S2=A(h2)=A,B纯策略组合纯策略组合S=左,A,左,B,右,A,右,B展开型博弈的策略型表示3,15,64,22,7左右AB（3,1）（2,7）122左右ABAB（5,6）（4,2）h1h2h2局中人局中人1 1信息集：H1=h1，h21行动空间：A(h1)=左，右;A(h21)=E,F纯策略空间：S1=A(h1)A(h21)=(左,E),(左,F),(右,E),(右,F)左ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)EFh21h2

6、2h12h1右局中人局中人2 2信息集：H2=h12，h22行动空间：A(h12)=A,B;A(h22)=C,D纯策略空间：S2=A(h12)A(h22)=(A,C),(A,D),(B,C),(B,D)左ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)EFh21h22h12h1右纯策略组合 S=S1S2=(左,E),(左,F),(右,E),(右,F)(A,C),(A,D),(B,C),(B,D)左ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)EFh21h22h12h1右(A,C)(A,D)(B,C)(B,D)(左,E)(左,F)(右,E)(右,F)2,02,01,

7、11,12,02,01,11,10,0.53,10,0.53,10,0.52,20,0.52,2左ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)EFh21h22h12h1右局中人局中人2 2信息集：H2=h12，h22行动空间：A(h12)=A,B;A(h22)=C,D纯策略空间：S2=A(h12)A(h22)=(A,C),(A,D),(B,C),(B,D)左ABCDh1h12h22右ababcdcdh21h21h31h31(1,2)(0,3)(3,1)(-1,4)(2,1)(0,0)(-1,1)(3,2)局中人局中人1 1信息集：H1=h1,h21，h31行动空间：A(h1)

8、左,右;A(h21)=a,b;A(h31)=c,d纯策略空间：S1=A(h1)A(h21)A(h31)=(左,a,c),(左,a,d),(左,b,c),(左,b,d),(右,a,c),(右,a,d),(右,b,c),(右,b,d)左ABCDh1h12h22右ababcdcdh21h21h31h31(1,2)(0,3)(3,1)(-1,4)(2,1)(0,0)(-1,1)(3,2)纯策略组合=S1S2=(左,a,c),(左,a,d),(左,b,c),(左,b,d),(右,a,c),(右,a,d),(右,b,c),(右,b,d)(A,C),(A,D),(B,C),(B,D)左ABCDh1h12h

9、22右ababcdcdh21h21h31h31(1,2)(0,3)(3,1)(-1,4)(2,1)(0,0)(-1,1)(3,2)展开型博弈的策略型表示(A,C)(A,D)(B,C)(B,D)(左,a,c)(左,a,d)(左,b,c)(左,b,d)(右,a,c)(右,a,d)(右,b,c)(右,b,d)1,21,23,13,11,21,23,13,10,30,3-1,4-1,40,30,3-1,4-1,42,1-1,12,1-1,10,03,20,03,22,1-1,12,1-1,10,03,20,03,23.简化策略型(reduced strategic form)定义定义：展开型博弈中局中

10、人i的两个纯策略si，si，如果对于其对手的所有纯策略产生博弈结局的同一概率分布，则称sisi将等价纯策略类简化为一个，就得到简化的策略型。(A,C)(A,D)(B,C)(B,D)(左,E)(左,F)(右,E)(右,F)2,02,01,11,12,02,01,11,10,0.53,10,0.53,10,0.52,20,0.52,2左ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)EFh21h22h12h1右例2,02,01,11,10,0.53,10,0.53,10,0.52,20,0.52,2(左,E)(右,E)(右,F)(A,C)(A,D)(B,C)(B,D)简化策略型例(A

11、C)(A,D)(B,C)(B,D)(左,a,c)(左,a,d)(左,b,c)(左,b,d)(右,a,c)(右,a,d)(右,b,c)(右,b,d)1,21,23,13,11,21,23,13,10,30,3-1,4-1,40,30,3-1,4-1,42,1-1,12,1-1,10,03,20,03,22,1-1,12,1-1,10,03,20,03,2简化策略型(A,C)(A,D)(B,C)(B,D)(左,a,c)(左,b,c)(右,a,c)(右,a,d)1,21,23,13,10,30,3-1,4-1,42,1-1,12,1-1,10,03,20,03,24.展开型博弈的纯策略Nash均衡

12、定定义义：纯策略组合s*是展开型博弈的纯策略Nash均衡，如果在给定局中人i的对手策略s*-i时，每一个局中人i的策略s*i使他的条件盈利达到极大化。3,13,15,65,64,22,74,22,7左右（A,C）（A,D）（B,C）（B,D）122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h223,15,64,22,7左右AB（3,1）（2,7）122左右ABAB（5,6）（4,2）h1h2h22,02,01,11,10,0.53,10,0.53,10,0.52,20,0.52,2(左,E)(右,E)(右,F)(A,C)(A,D)(B,C)(B,D)122左右ABCD(2,

13、0)(1,1)(0,0.5)(3,1)(2,2)1EF(A,C)(A,D)(B,C)(B,D)(左,a,c)(左,b,c)(右,a,c)(右,a,d)1,21,23,13,10,30,3-1,4-1,42,1-1,12,1-1,10,03,20,03,2左ABCDh1h12h22右ababcdcdh21h21h31h31(1,2)(0,3)(3,1)(-1,4)(2,1)(0,0)(-1,1)(3,2)5.Nash均衡的存在性结论结论：有限展开型博弈至少存在Nash均衡（可能是混合型）。习题：寻找Nash均衡122LRCDLR(2,2)(2,-2)(3,1)(-2,2)(-2,2)1AB(2,

14、2)D Ch1h22h21LRCDLR(2,2)(2,-2)(3,1)(-2,2)(-2,2)h12AB(2,-2)DC局中人局中人1 1信息集：H1=h1,h12行动空间：A(h1)=L,R;A(h12)=A,B纯策略空间：S1=A(h1)A(h12)=(L,A),(L,B),(R,A),(R,B)局中人局中人2 2信息集：H1=h21,h22行动空间：A(h21)=L,R;A(h22)=C,D纯策略空间：S1=A(h21)A(h22)=(L,C),(L,D),(R,C),(R,D)(L,C)(L,D)(R,C)(R,D)h1h22h21LRCDLR(2,2)(2,-2)(3,1)(-2,

15、2)(-2,2)h12AB(2,-2)DC(L,A)(L,B)(R,A)(R,B)2,22,22,22,22,22,22,22,23,13,12,-2-2,23,13,1-2,22,-2三、完美信息有限博弈后退归纳法：Stackelberg 博弈122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h22122左右BD（5,6）（2,7）h1h12h2212左B（5,6）h1h12122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h22后退归纳法所隐含的策略组合左,(B,D)3,13,15,65,64,22,74,22,7左右（A,C）（A,D）（B,C）（B,

16、D）122左右ABCD（3,1）（5,6）（4,2）（2,7）h1h12h22122左右ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)1EF122左右BCD(1,1)(0,0.5)(3,1)1E122左右BD(1,1)(3,1)1E12右D(3,1)1E122左右ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)1EF后退归纳法所隐含的策略组合(右，E），(B,D)122左右ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)1EF2,02,01,11,10,0.53,10,0.53,10,0.52,20,0.52,2(左,E)(右,E)(右,F)(A,C)(A,D)(B,C)(B,D)122左右ABCD(2,0)(1,1)(0,0.5)(3,1)(2,2)1EF定定理理：在一个具有完美信息的有限博弈中，使用后退归纳法选择的策略组合总是Nash均衡。定定理理（Zermelo，1913；Kuhn，1953）：完美信息的有限博弈具有一个纯策略Nash均衡。