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

第二部分 完全信息动态博弈,第二章 展开型博弈,一、博弈树,1. 博弈树的所包含的信息 （1）局中人的集合 （2）行动的次序 （3）局中人行动时的纯策略空间 （4）局中人作出行动决策时所获得的信息集合。 （5）局中人的盈利或效用 （6）任何外生事件上的概率分布。,例,2. 博弈树规则,(1) 每一个结至多有一个其他结直接位于它的前面。,(2) 在博弈树中没有一条路径可以使决策结与自身相连。,(3) 博弈树必须有初始结,(4) 每个博弈树只有一个初始结,3、完美信息与不完美信息,定义：假如一个局中人在轮到他行动时知道自己处于博弈树的那个结上，我们称该局中人有完美信息。 博弈中的每一个局中人都具有完美信息，则称该博弈有完美信息。 如果局中人在不知道另外的局中人前面行动的情况下必须行动，则称该局中人具有不完美信息。 倘若至少有一个局中人具有不完美信息，则称该博弈具有不完美信息。,二、展开型博弈的策略与均衡,概念 信息集 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 信息集：H1=h1；行动空间：A(h1)=左,右 纯策略空间：S1=A(h1)=左,右,局中人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),纯策略组合 S=左, (A,C),左, (A,D),左, (B,C),左, (B,D), 右, (A,C),右, (A,D),右, (B,C),右, (B,D),2、展开型博弈的策略型表示,局中人1 信息集：H1=h1；行动空间：A(h1)=左,右 纯策略空间：S1=A(h1)=左,右,局中人2 信息集：H2=h2；行动空间：A(h2)=A,B 纯策略空间：S2=A(h2)=A,B,纯策略组合 S= 左, A,左,B,右,A,右,B,展开型博弈的策略型表示,局中人1 信息集：H1=h1，h21 行动空间：A(h1)=左，右; A(h21)=E,F 纯策略空间： S1=A(h1)A(h21)=(左,E),(左,F),(右,E),(右,F),局中人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),纯策略组合 S= S1S2=(左,E),(左,F),(右,E),(右,F) (A,C),(A,D),(B,C),(B,D),(A,C),(A,D),(B,C),(B,D),(左,E),(左,F),(右,E),(右,F),局中人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),局中人1 信息集：H1=h1 ,h21，h31 行动空间：A(h1)=左,右; 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),纯策略组合=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),展开型博弈的策略型表示,(A,C),(A,D),(B,C),(B,D),(左,a,c),(左,a,d),(左,b,c),(左,b,d),(右,a,c),(右,a,d),(右,b,c),(右,b,d),3. 简化策略型(reduced strategic form),定义：展开型博弈中局中人i的两个纯策略si，si，如果对于其对手的所有纯策略产生博弈结局的同一概率分布，则称 sisi 将等价纯策略类简化为一个，就得到简化的策略型。,(A,C),(A,D),(B,C),(B,D),(左,E),(左,F),(右,E),(右,F),例,简化策略型,例,(A,C),(A,D),(B,C),(B,D),(左,a,c),(左,a,d),(左,b,c),(左,b,d),(右,a,c),(右,a,d),(右,b,c),(右,b,d),简化策略型,(A,C),(A,D),(B,C),(B,D),(左,a,c),(左,b,c),(右,a,c),(右,a,d),4. 展开型博弈的纯策略Nash均衡,定义：纯策略组合s*是展开型博弈的纯策略Nash均衡，如果在给定局中人i的对手策略s*-i时，每一个局中人i的策略s*i使他的条件盈利达到极大化。,5. Nash均衡的存在性,结论：有限展开型博弈至少存在Nash均衡（可能是混合型）。,习题：寻找Nash均衡,局中人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 信息集：H1=h21 ,h22 行动空间：A(h21)=L,R; A(h22)=C,D 纯策略空间：S1=A(h21)A(h22) =(L,C),(L,D),(R,C),(R,D),三、完美信息有限博弈,后退归纳法：Stackelberg 博弈,后退归纳法所隐含的策略组合,左,(B,D),左,右,（A,C）,（A,D）,（B,C