31完全信息动态博弈

完全信息动态博弈扩展型博弈（序惯决策博弈）标准型博弈与扩展型博弈子博弈精炼纳什均衡逆向归纳法求解子博弈精炼纳什均衡重复博弈一、扩展型博弈（序惯决策博弈）引言扩展式博弈的要素博弈树的构造完美信息与完全信息完美回忆博弈的扩展式表述要素小结1、引言－－进入阻挠博弈模型假设：一个新企业（进入者）想进入被垄断企业（在位者）所把持的市场。进入者有两种策略可选择：进入还是不进入；在位者也有两种策略：默许（容忍）还是斗争（低价）。设进入前垄断利润为10，进入之后寡头利润为5，进入成本为4，进入后双方争斗时利润均为2。若将其视为静态博弈（即同时决策），则该博弈有两个纯策略纳什均衡（进入，默许）和（不进入，斗争）。垄断者默许斗争潜在进入者进入1，5-2，2不进入0，100，10市场进入阻挠博弈的博弈树•事实上，该博弈存在先后顺序，在位的垄断者是在观察到是否有进入行为后再进行决策的，因而是一序惯博弈。•对该博弈，采用博弈树来描述，简单直观。潜在进入者在位者进入不进入默许斗争（0，10）（-2，2）（0，10）默许斗争（1，5）2、扩展式博弈的要素博弈的扩展式表述包含以下要素：（1）参与人集合：I={i｜i=1，2，…，n}。此外，用N代表虚拟参与人——自然。（2）行动顺序：谁在什么时候行动。（3）参与人的行动空间：每次行动时，局中人可进行的选择（4）参与人的信息集：信息是参与人有关博弈的知识，如有关“自然”的选择、其他参与人的特征和行动的知识等。（5）参与人的支付函数：指在一个特定策略组合下参与人得到的确定（期望）效用水平（6）外生事件的概率分布（存在外部不确定性时）。3、博弈树的构造博弈树由一系列节点x∈X和它们之间的连线构成。博弈树的基本元素有：节点：x∈X，又称决策结，简称“结”枝：连结结点的连线信息集：一些节点的集合。在同一信息集中，局中人面临完全相同的决策形势。1UDLRz13z2z3z4PQ2x′x″x（1）结结。包括：初始结：博弈的起点。决策结：参与人采取行动的时点。终点结：博弈行动路径的终点。记X表示所有结的集合，xX表示某特定结。定义X上的半序（偏序）关系“≻”：x≻x″意味着x在x″之前。半序“≻”满足：传递性：若x≻x′且x′≻x″，则有x≻x″。反对称性：若有x≻x′，则不可能有x′≻x。1UDLRz13z2z3z4PQ2x′x″x博弈树中不允许出现的情形xx′x″右图不满足博弈树要求的半序关系：传递性和反对称性。前列集和后续集定义x的前列集为：P（x）＝｛x″｜x″≻x｝定义的x的后续集：T（x）＝｛x″｜x≻x″｝如果P（x）＝，则称x为初始结（假定为唯一的）；如果T（x）＝，则称x为终点结。称p(x)为x的直接前列结，若p(x)P（x），且对x″P（x），x″p(x)，有x″≻p(x)。如果x″是x的直接前列结，则x是x″的直接后续结。通常假定x的前列集P（x）是全序的。这就是说，在博弈树中从初始结点到每一个结点都只有一条路。这意味着任何一个非初始结有且仅有一个直接前列结。博弈树中不允许出现的情形（2）x″的前列集P（x）不满足全序假定。博弈树要求，除初始结点外，每一个节点有且仅有一个直接前列结x″x′x（2）枝（路径）定义函数i：X｛N，1，2，…，n｝，即i(x)表示在决策结x参与人i行动。设xX，记t(x)是x直接后续结集合，A(x)是在决策结x的行动集合。在传递性、反对称性和前列结全序假设下，有：对于一个给定的xX，存在一个一一对应的关系：A(x)t(x)，即当且仅当参与人i(x)选择不同的行动a(x)A(x)时，从一个给定的结x出发，博弈才会到达不同的直接后续结x″t(x)。这就是说，从x达到它的每一个直接后续结x″，都对应着i(x)的一个唯一行动a(x)。枝的图示枝是一个从决策结到它的直接后续结的连线，代表参与人的一个行动选择。枝：不但完整地描述了每一个决策结参与人的行动空间，而且给出了从一个决策结到下一个决策结的路径。1UDLRz13z2z3z4PQ2x′x″x（3）信息集博弈树上所有决策结分割成不同的信息集（记为hH），它是X的一个子集，满足：（1）每一个决策结都是同一参与人的决策结；（2）该参与人知道博弈进入该集合的某个决策结，但不知道究竟处于哪一个决策结。记h(x)是X中包含x的信息集，如果x″h(x)，则满足：（1）xP(x″)，且x″P(x)；（2）i(x)=i(x″)；（3）A(x)=A(x″)。在此基础上，即可用A(h)表示给定信息集h下的行动集合。信息集的表示所有同一信息集的决策结（节点）都由一条虚线（椭圆形虚线圈）连结起来。在信息集中，每一个决策结都是同一参与人的决策结；该参与人知道博弈进入该集合的某个决策结，但不知道究竟处于哪一个决策结。右图中有几个信息集？1UDLRLR2114、完美信息与完全信息只包含一个决策结的信息集称为单结信息集。如果一个博弈的所有信息集都是单结的，则称该博弈为完美信息博弈（perfectinformation）。完美信息博弈意味着博弈中没有任何两个参与人同时行动，并且所有后行动者能准确知道前行动者采取了什么行动，并且所有人观察到自然的行动。完全信息（completeinformation）是指有关参与人的特征、支付函数和纯策略空间均为博弈各方的共同知识，可以是完美的，也可以是不完美的，如完全信息静态博弈不具有完美信息。5、完美回忆完美回忆是指没有参与人会忘记自己以前知道的事情，并且所有参与人都知道自己以前的选择。通常，我们假定博弈满足“完美回忆”的要求。参与人不满足完美回忆要求1UDLRLR21A1UDLRLR211参与人不满足完美回忆要求LRLR1122UDUD1NBLRLR1122UDUDN11确保博弈具有完美回忆的条件如果x2h(x1)，xP(x1)，i(x)=i(x1)成立，就存在一个x″（可能是x本身），满足：（1）x″h(x)（2）x″P(x2)（3）在x点为达到x1的行动与在x″为达到x2的行动是一样的。则该博弈具有完美回忆特征。完美回忆的实质就是“同一信息集”假设和“同一行动”假设。LRLR22UDUDx1x2xx″11不满足完美回忆的同一行动假设1UDLRLR21A1UDLRLR211不满足完美回忆的同一信息集假设LRLR1122UDUD1NBLRLR1122UDUDN116、博弈的扩展式表述要素小结参与人集合：i=1，2，…，n。此外，用N代表虚拟参与人——自然。行动顺序：i(x)参与人的行动空间：Ai(x)参与人的信息集：hi(x)支和路径参与人的支付函数：外生事件的概率分布：二、标准式博弈与扩展式博弈1、纯策略与混合策略2、扩展型博弈与标准式博弈的转换3、一个二阶段博弈的例子4、博弈树求解－－逆向归纳法1、纯策略与混合策略（1）行动与策略行动：是参与人在博弈的某个时点（某个信息集）的决策变量。行动组合：参与人的行动的有序集。策略：是参与人在给定信息集情况下的行动规则，它规定参与人在什么时候选择什么行动。在静态博弈中，策略和行动是等价的。在动态博弈中，策略在给定信息集下完整的行动方案，与行动是不同的。一个扩展式博弈的纯策略○UDABLLRR（3,2）（1,1）（0,2）（4,5）这是一扩展型博弈，参与人A有1个信息集，两种行动选择；参与人B有两个信息集（参与人A选择U或D），每个信息集各有两种行动选择L和R，相应地有四个纯策略LL、LR、RL和RR。（2）纯策略令Hi为第i个参与人的信息集的集合，Ai＝hiHiA(hi)为其行动集合，A(hi)为在信息集hi的行动集合。参与人i的一个纯策略是从信息集Hi到行动集合Ai的一个映射si：HiAi，对所有的hiHi，满足si(hi)A(hi)。参与人i的纯策略空间Si就是所有纯策略的集合：一般地，参与人i的纯策略空间的纯策略数目为：)(iHhihASiiiiHhiihAS))((##混合策略是纯策略空间上的一概率分布。每一个策略组合决定了一个支付向量u=(u1,u2,…,un)。策略组合s*是扩展式博弈的一个纳什均衡，如果对所有的i，si*最大化ui(si,s-i*)。即：（3）混合策略与纳什均衡*),(maxarg*iiiSsissusii纯策略和混合策略解释用Luce和Raiff的比喻来说，参与人i的每一个纯策略si相当于一本指导说明书，书中的每一页表示到了一个特定的信息集hi，在该页上（到达该信息集的一个决策结）告诉参与人i在该信息集上如何行动。Si则表示书架上书的全体，混合策略则表示参与人以一定的概率分布从书架上随机抽取一本书。2、扩展型博弈与标准式博弈的转换○UDABLLRR（3,2）（1,1）（0,2）（4,5）这是一扩展型博弈，参与人A有1个信息集，两种行动选择；参与人B有两个信息集（参与人A选择U或D），每个信息集各有两种行动L和R，相应地有四个纯策略。扩展式表述转换为标准式表述○UDABLLRR（3,2）（1,1）（0,2）（4,5）在标准式博弈中，共有三个纯策略纳什均衡。B（L，L）（L，R）（R，L）（R，R）AU3,23,21,11,1D0,24,50,24,5囚徒困境博弈的博弈树－－同时决策囚徒B抵赖坦白囚徒A抵赖-1，-1-10，0坦白0，-10-8，-8抵赖坦白抵赖坦白抵赖B（-1，-1）（0，-10）（-10，0）（-8，-8）坦白A囚徒困境博弈的博弈树－－序惯博弈囚徒B（抵赖，抵赖）（抵赖，坦白）（坦白，抵赖）（坦白，坦白）囚徒A抵赖-1，-1-1，-1-10，0-10，0坦白0，-10-8，-80，-10-8，-8A抵赖坦白抵赖坦白抵赖B（-1，-1）（0，-10）（-10，0）（-8，-8）坦白3、一个二阶段博弈的例子考查如下一个二阶段博弈：第一阶段：局中人1和2同时在U和D中进行选择；第二阶段：在观察到第一阶段结果（共有四种可能结果UU、UD、DU和DD）后，两个局中人同时在L和R中进行选择。二阶段博弈的博弈树1UDUDUD21LRLRLR21LRLRLR21LRLRLR21LRLRLR2信息集行动策略博弈树的信息集、行动与策略信息集：参与人1和2各有五个信息集行动：在每个信息集上各有两种可能的行动选择纯策略：给出了参与人在其所有信息集上可能的策略选择规则1UDUDUD21LRLRLR21LRLRLR21LRLRLR21LRLRLR2二阶段博弈博弈树的纯策略1UDUDUD21LRLRLR21LRLRLR21LRLRLR21LRLRLR2对每个局中人来说，各有多少种纯策略？扩展式博弈的纯策略局中人1有5个信息集：初始结和第一阶段博弈的四种可能结局，即局中人1和2均选择U、局中人1选择U局中人2选择D、局中人1选择D局中人2选择U、局中人1和2均选择D。因而，局中人的一个纯策略是：（U，L，L，L，R）由于在每一信息集有两种可能策略，故共有25＝32种纯策略1UDUDUD21LRLRLR21LRLRLR21LRLRLR21LRLRLR2二阶段博弈博弈树的混合策略1UDUDUD21LRLRLR21LRLRLR21LRLRLR21LRLRLR2对每个局中人来说，各有25＝32种纯策略。该博弈中的混合策略如何描述？4、博弈树求解－－倒推法对局中人B来说，在每一个信息集上都将选择其最优行动。○UDABLLRR（3,2）（1,1）（0,2）（4,5）A的选择局中人A将预料到B的行动选择，从而选择其最优行动。○UDABLLRR（3,2）（1,1）（0,2）（4,5）（3,2）（4,5）逆向归纳法求解○UDABLLRR（3,2）（1,1）（0,2）（4,5）（3,2）（4,5）（D，(L，R)）是该博弈的纯策略纳什均衡（子博弈精炼（完美）纳什均衡）逆向归纳法（倒推法）如果一个扩展式博弈有有限个信息集，每个信息集上参与人有有限个行动选择，则称为有限博弈。由纳什均衡存在性定理，有限博弈存在混合策略纳什均衡。特别地有：定理：一个有限完美信息博弈存在一个纯策略纳什均衡。逆向归纳法思想分析：有限博弈一