博弈论 完全信息动态博弈课件

《博弈论 完全信息动态博弈课件》由会员分享，可在线阅读，更多相关《博弈论 完全信息动态博弈课件（85页珍藏版）》请在金锄头文库上搜索。

1、第三章完全信息动态博弈（1）,主要内容： 一、博弈的扩展式表述 二、扩展式表述博弈的纳什均衡 三、子博弈精炼纳什均衡 四、子博弈精炼纳什均衡应用举例 五、重复博弈,一、博弈的扩展式表述,1、一个例子：房地产开发博弈 某市房地产市场需求有两种状态：高需求和低需求，两家房地产商决定是否进行小区开发。假设开发商的开发成本为4。 在市场高需求状态下，若市场只有一个楼盘出售，则售价为8，开发商的利润为4；若市场同时有2个楼盘出售，则售价为6，每个开发商的利润均为2。 在市场低需求状态下，若市场只有一个楼盘出售，则售价为5，此时开发商的利润为1；若市场同时有两个楼盘出售，则售价仅为3，开发商各亏损1。,博

2、弈的收益矩阵,博弈分类,按开发商博弈的先后顺序分： 静态博弈：两个开发商同时决策，或后决策者不能观察到先行动者的行动。 动态博弈：博弈有先后顺序，且后决策者能观察到先行动者的行动后再行动。 按开发商是否知道市场需求状态分： 完全信息博弈：若两个开发商都知道市场需求状态（高需求或低需求）。 不完全信息博弈：由自然决定市场的需求状态，两开发商不知道。 共同知识：在市场各种可能状态和各开发商不同策略组合下的得益矩阵是双方的共同知识。,四种博弈类型,完全信息静态博弈：市场需求状态是共同知识，两开发商都能观察到市场需求状态，并同时决策。 完全信息动态博弈：两开发商都能观察到市场需求状态，开发商A先行动，

3、开发商B在观察到A的行动后再行动。 不完全信息静态博弈：两开发商都不能观察到自然决定的市场需求状态，且同时行动。 不完全信息动态博弈：两开发商不知道自然决定的市场需求状态，开发商A先行动，开发商B观察到A的行动后再行动。,（1）完全信息静态情形,（2）不完全信息静态情形,海萨尼转换,（3）完全信息动态情形,N A B情形： 自然先确定市场需求状态：高需求或低需求； 开发商A首先行动， 在观察到市场需求状态后决定是否开发； 开发商B在观察到市场需求状态和A的决策后再决定是否开发。,完全信息动态博弈图示：N A B,开发商A不清楚市场的需求状态，决定是否开发； 开发商B 在观察到市场需求和A的决策

4、后决定是否开发。,（4）不完全信息动态情形：ANB,ANB的等价表示,开发商A不清楚市场的需求状态，决定是否开发； 开发商B 在观察到市场需求和A的决策后决定是否开发。,不完全信息动态博弈的其他情形（1）,思考：该博弈树代表哪种情形？,不完全信息动态博弈的其他情形（2）,思考：该博弈树代表哪种情形？,完全信息静态博弈的博弈树,不完全信息静态博弈的博弈树,铁矿石价格谈判,铁矿石谈判的合同价格与现货价格不同，不完全由供求确定，供求双方博弈的主要是对未来需求的预期。 完全信息情形下的博弈： 高需求 低需求 不完全信息情形下的博弈： 需求方的信号 承诺 长协价格从年度定价到季度定价,2、博弈的扩展式表

5、述的要素,博弈的扩展式表述包含以下要素： （1） 参与人集合：i=1，2，n。此外，用N代表虚拟参与人自然。 （2） 行动顺序：谁在什么时候行动。 （3） 参与人的行动空间： （4）参与人的信息集： （5）参与人的策略集： （6）参与人的支付函数： （7）外生事件的概率分布。 扩展型博弈通常用博弈树来描述。,要素详解,参与人：博弈中的决策主体，有时包括“自然”作为“虚拟参与人”。 行动：是参与人在博弈的某个时点的决策变量。 行动组合：参与人的行动的有序集。 行动顺序：静态博弈和动态博弈 信息：是参与人有关博弈的知识，如有关“自然”的选择、其他参与人的特征和行动的知识等。 完全信息（comple

6、te information） 完美信息（perfect information） 对称信息（symmetric information） 确定信息（certain information）,策略：是参与人在给定信息集情况下的行动规则，它规定参与人在什么时候选择什么行动。在静态博弈中，策略和行动是等价的。 信息集、行动、策略 支付：指在一个特定策略组合下参与人得到的确定（期望）效用水平。 结果：均衡策略组合、均衡行动组合、均衡支付组合 均衡：是所有参与人最优策略的组合，通常记为 s*=(s1*, s2*, , sn*)，即均衡策略。 均衡结果,3、 博弈树的构造,博弈树的基本元素有：结；枝；信

7、息集,（1）结,结。包括： 初始结：博弈的起点 。 决策结：参与人采取行动的时点。 终点结：博弈行动路径的终点。 记X表示所有结的集合，xX表示某特定结。定义X上的半序（偏序）关系“ ”：x x意味着x在x之前。半序“ ”满足： 传递性：若x x且 x x，则有x x。 反对称性：若有 x x，则不可能有 x x。 注意：有的书本是以“ ”来表示这一偏序关系。,博弈树中不允许出现的情形,右图不满足博弈树要求的半序关系：传递性和反对称性。,前列集和后续集,定义x的前列集为：P（x）xx x 定义的x的后续集：T（x）xx x 如果P（x），则称x为初始结（假定为唯一的）；如果T（x），则称x为终

8、点结。 称p(x)为x的直接前列结，若p(x)P（x），且对x P（x），xp(x)，有x p(x)。 如果x是x的直接前列结，则x是x的直接后续结。 通常假定x的前列集P（x）是全序的。这就是说，在博弈树中从初始结点到每一个结点都只有一条路。这意味着任何一个非初始结有且仅有一个直接前列结。,博弈树中不允许出现的情形（2）,x的前列集P（x）不满足全序假定。 博弈树要求，除初始结点外，每一个节点有且仅有一个直接前列结。,（2） 枝（路径）,定义函数i：XN，1，2，n，即i(x)表示在决策结x参与人i行动。 设xX，记t(x)是x直接后续结集合，A(x)是在决策结x的行动集合。在传递性、反对称

9、性和前列结全序假设下，有： 对于一个给定的xX，存在一个一一对应的关系：A(x) t(x)，即当且仅当参与人i(x)选择不同的行动a(x)A(x)时，从一个给定的结x出发，博弈才会到达不同的直接后续结x t(x)。这就是说，从x达到它的每一个直接后续结x，都对应着i(x)的一个唯一行动a(x) 。,枝的图示,枝是一个从决策结到它的直接后续结的连线，代表参与人的一个行动选择。 枝：不但完整地描述了每一个决策结参与人的行动空间，而且给出了从一个决策结到下一个决策结的路径。,（3）信息集,博弈树上所有决策结分割成不同的信息集（记为hH），它是X的一个子集，满足： （1）每一个决策结都是同一参与人的决

10、策结； （2）该参与人知道博弈进入该集合的某个决策结，但不知道究竟处于哪一个决策结。 记h(x)是X中包含x的信息集，如果xh(x)，则满足： （1）xP(x)，且x P(x)； （2）i(x)=i(x)； （3）A(x)=A(x)。 在此基础上，即可用A(h)表示给定信息集h下的行动集合。,信息集的表示,所有同一信息集的决策结（节点）都由一条虚线连结起来。 右图中有几个信息集？,4、完美信息与完全信息,只包含一个决策结的信息集称为单结信息集。 如果一个博弈的所有信息集都是单结的，则称该博弈为完美信息博弈（perfect information） 。 完美信息博弈意味着博弈中没有任何两个参与人

11、同时行动，并且所有后行动者能准确知道前行动者采取了什么行动，并且所有人观察到自然的行动。 完全信息（complete information）是指有关参与人的特征、支付函数和纯策略空间均为博弈各方的共同知识，可以是完美的，也可以是不完美的，如完全信息静态博弈不具有完美信息。,完美信息博弈：N A B情形,自然先确定市场需求状态：高需求或低需求；开发商A在观察到市场需求状态后决定是否开发；开发商B在观察到市场需求状态和A的决策后再决定是否开发。,不完美信息博弈,在房地产开发博弈中，不完美信息博弈有4种情形： （1）若参与人B知道自然的选择和A的选择，A不知道自然的选择。A为非完美信息，有一个信息

12、集，B的信息集有四个。 （2）若参与人B不知道自然的选择但知道A的选择，该博弈可分为两类：ANB（A为非完美信息，只有1个信息集）和NAB（A为完美信息，有两个信息集），B的信息集有两个。 （3）若参与人B知道自然的选择但不知道参与人A的选择时，B有两个信息集。 （4）若参与人B既不知道自然的选择，也不知道参与人A的选择时，B只有一个信息集。,不完美信息博弈：情形（1）,开发商A为非完美信息。,不完美信息博弈：情形（2）,若参与人B不知道自然的选择但知道A的选择， B的信息集有两个，针对A的信息集，可将该博弈分为两类： NAB：A为完美信息，有两个信息集 ANB：A为非完美信息，只有1个信息集

13、,A为完美信息：N A B情形,A为不完美信息：A N B情形,A为不完美信息的等价表示：N A B情形,不完美信息博弈：情形（3）,若参与人B知道自然的选择但不知道参与人A的选择时， B有两个信息集。该博弈可分为两类： NAB：A为完美信息，有两个信息集 ANB：A为非完美信息，只有1个信息集,A为完美信息： N A B情形,A为不完美信息： A N B情形,不完美信息博弈：情形（4）,若参与人B既不知道自然的选择，也不知道参与人A的选择时， B只有一个信息集。该博弈也有两类： NAB：A为完美信息，有两个信息集 ANB：A为非完美信息，只有1个信息集,A为完美信息： N A B情形,A为不

14、完美信息： A N B情形,5、完美回忆,完美回忆是指没有参与人会忘记自己以前知道的事情，并且所有参与人都知道自己以前的选择。 通常，我们假定博弈满足“完美回忆”的要求。,参与人不满足完美回忆要求,参与人不满足完美回忆要求,确保博弈具有完美回忆的条件,如果x2h(x1)，xP(x1)，i(x)=i(x1)成立，就存在一个x（可能是x本身），满足： （1）xh(x) （2）xP(x2) （3）在x点为达到x1的行动与在x为达到x2的行动是一样的。 则该博弈具有完美回忆特征。 完美回忆的实质就是 “同一信息集”假设和“同一行动”假设。,不满足完美回忆的同一行动假设,不满足完美回忆的同一信息集假设,

15、6、博弈的扩展式表述要素小结,参与人集合：i=1，2，n。此外，用N代表虚拟参与人自然。 行动顺序：i(x) 参与人的行动空间：Ai(x) 参与人的信息集：hi(x) 参与人的策略集：策略表示从信息集到行动集上的映射 支和路径 参与人的支付函数： 外生事件的概率分布：,二、扩展式表述博弈的纳什均衡,1、策略与纳什均衡 2、行为策略 3、逆向归纳法,1、策略与纳什均衡,令Hi为第i个参与人的信息集的集合，AihiHiA(hi)为其行动集合，其中A(hi)为在信息集hi的行动集合。 参与人i的一个纯策略是从信息集Hi到行动集合Ai的一个映射si：HiAi，对所有的hiHi，满足si(hi)A(hi

16、)。 策略与行动 纯策略指出了参与人在他的每一个信息集上如何选择行动，而行动只是度量了他在某一个特定信息集上如何选择。 参与人i的纯策略空间Si就是所有纯策略的集合，即：,一般地，参与人i的纯策略空间的纯策略数目为：,混合策略是纯策略空间上的一概率分布。 每一个策略组合决定了一个支付向量u=(u1, u2, , un)。 策略组合s*是扩展式博弈的一个纳什均衡，如果对所有的i，si*最大化ui(si, s-i*)。即：,纯策略和混合策略解释,用Luce和Raiff的比喻来说，参与人i的每一个纯策略si相当于一本指导说明书，书中的每一页表示到了一个特定的信息集hi，在该页上（到达该信息集的一个决策结）告诉参与人i在该信息集上如何行动。Si则表示书架上书的全体，混合策略则表示参与人以一定的概率分布从书架上随机抽取一本书。,N A B情形的纯策略,自然需求是共同信息，开发商A先行动，开发商B在观察到A的决策后行动。 B有两个信息集A开发，A不开发，在每个信息集上有两个可供选择的行动开发，不开发，则B有四个纯策略：（开发，开发），（开发，不开发），（不开发，开发）和（不开发，不