完全信息动态博弈

完全信息动态博弈 第三章 信息与非合作理论 >> 第三节 完全信息动态博弈 本节我们开始讨论动态博弈。动态博弈的根本特征是各博弈方不是同时，而 是先后、依次进行选择或行动，这是与静态博弈的根本区别。我们一般用扩展式 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 述来描述和分析动态博弈。这里博弈的扩展式表述所“扩展”的主要是参与人 的战略空间。战略式表述简单地给出参与人有些什么战略可以选择，而扩展式表 述要给出每个战略的动态描述：谁在什么时候行动，每次行动时有些什么具体行 动可供选择，以及知道些什么。简单地说，在扩展式表述中，战略对应于参与人 的相机行动规则，即什么情况下选择什么行动，而不是简单的、与环境无关的行 动选择。 具体来讲，博弈的扩展式表述包括以下要素： 1.参与人集合：i=1，„，n，此外，我们将用N代表虚拟参与人“自然”； 2.参与人的行动顺序：谁在什么时候行动； 3.参与人的行动空间：在每次行动时，参与人有些什么选择； 4.参与人的信息集：每次行动时，参与人知道些什么； 5.参与人的支付函数：在行动结束之后，每个参与人得到些什么； 6.外生事件（即自然的选择）的概率分布。 n人有限战略博弈的扩展式表述可以用博弈树来表示。为了说明这一点，让 我们来考虑在前面一章开始时引入的房地产开发博弈的例子。我们假定该博弈的 行动顺序如下：（1）开发商A首先行动，选择开发或不开发；（2）在A决策后，自然选择市场需求的大小；（3）开发商B在观测到A的决策和市场需求后，决定开发或不开发。 图3.2是上述房地产开发博弈的博弈树。博弈从最顶端的圆圈A开始，表示开发商A在此点决策，h表示A的信息集（有关信息集，后面介绍）。A有A(1) 两个行动可以选择：开发或不开发，分别用标有“开发”和“不开发”的两个枝 表示。A选择开发（或不开发）后博弈进入标有N的结点，表示不受参与人控制 的自然开始行动。如此，直到Ｂ做出选择，博弈结束。对应于不同的行动路径， 我们得到不同的支付向量，其中每个向量的第一个数字是Ａ的支付，第二个数字 是Ｂ的支付。（注意，习惯上，支付向量的顺序与博弈树上的行动顺序是对应的。） 上述博弈树给出了有限博弈的几乎所有信息。现在让我们首先来介绍一下博弈树的构造。构成博弈树的基本元素包括结、枝和信息集。 1．结(nodes)：博弈中某一参与人（包括自然）采取行动的时点，或者博弈 结束的时点。其中，参与人采取行动的时点称为决策结，博弈行动路径的终点称 为终点结。在上例中，决策结包括内有A、N、B的七个圆圈，终点结包括对应八 个支付向量的点。 一般地，我们用X表示所有结的集合，x?X表示某个特定的结。已经到达结 x后才有可能在随后的博弈中到达的结称为结x的后续结；可能到达结x之前必须到达的结称为结x的前续结。 构造一个博弈树必须满足下列规则： (1) 每一个结(node)至多有一个其他结直接位于它的前面; 在博弈中没有一条路径可以使决策集与自身相连; (2) (3) 每一个结是唯一初始结的后续结, 即博弈树必须有初始结; (4) 每个博弈树“正好”只有一个初始结（多于一个可用“自然连接”） 不允许出现下面的情况： 由以上规则，对于博弈树中的每一个终点结，我们完全可以确定从初始结到终点 结的路径，同时也展示了博弈的动态过程。 2．枝(branches)：在博弈树上，枝是从一个决策结到它的直接后续结的连 线(有时用箭头表述)，每一个枝代表参与人的一个行动选择。比如说，在图3.2中，开发商A有两个选择，分别用标有“开发”和“不开发”的两个枝表示。 3．信息集(information sets)：博弈树上的所有决策结分隔成不同的信息 集，每一个信息集是决策结集合的一个子集。该子集包括所有满足下列条件的决策结：(1)每一个决策结都是同一参与人的决策结；（2）该参与人知道博弈进入 该集合的某个决策结，但不知道自己究竟处于哪一个决策结。引入信息集的目的 是描述下列情况：当一个参与人要作出决策时他可能并不知道“之前”发生的所 有事情(这里，我们将之前放在引号内，因为博弈树中的决策结的排序并不一定 与行动的时间顺序相一致)。 一般地，我们用H代表信息集的集合，h?H来表示一个特定的信息集。特别 地，我们用h(x)表示包含决策结x的信息集。如果x′?h(x), 则x与x′应该由同一个参与人采取行动，且可以选择的策略空间相同：A(x)=A(x′), 由此可以将信息集h上的行动集记为A(h)。 一个信息集可能包含多个决策结，也可能只包含一个决策结。只包含一个决 策结的信息集称为单结信息集。如果博弈树的所有信息集都是单结的，该博弈称 为完美信息博弈。完美信息意味着博弈中没有任何两个参与人同时行动，并且所 有后行动者能确切地知道前行动者选择了什么行动，所有参与人观测到自然的行 动。在博弈树上，完美信息意味着没有任何两个决策结是用虚线连起来的。 在战略式表述的博弈中, 参与人在博弈开始之前就制定出了一个完全的相 机行动计划，即“如果„„发生，我将选择„„”，而在展开式表述的博弈中， 参与人是相机行事，即“等待”博弈到达自己的信息集后再作决策。 我们首先来一般地定义扩展式博弈的战略。使用前面的符号，令H为第i各i参与人的信息集的集合，A??A(h)为其行动集合，其中A(h)是在信息集ihiHi iih的行动集合。参与人i的一个纯战略是从信息集集合H到行动集合A的一个iii映射，用S：H? A表示，其中，对于所有的h?H，S(h) ? A(h)，参与人iiiiiiiii的纯战略空间S就是所有S的集合。因为每一个纯战略都是从信息集到行动集ii 的一个映射，S可以表示为在每一个信息集h上的行动空间A(h)的笛卡尔积： iii S= ×A(h) ihiHi i 一般地，一个参与人可选择的纯战略的总数#S，等于： i ?# ( A(h)) ， h?H iii 下面我们用一抽象的例子对上面的定义进行解释（见图3.4）。 从上图抽象例子的博弈树我们可以得到，参与人2有两个战略集,相应地也有两个信息集，A(h(1))=A(h(2))={左,右}，其中H={h(1),h(2)};参与人222222 的纯战略空间为: = (A(h(1)),Ah(2))={(左,右)×(左,右)}={(左,左),(左,右),(右, S222 左),(右,右)}, 其中纯战略(左,左)表明:当1取“上”时,2取“左”;当1取“下”时,2取“左”, 如此等等。参与人1有三个信息集H={h(i),i=1,2,3},1的纯战略空间1i 为:S=A(h(1))×A(h(2))×A(h(3))={(上,下)×(A,B)×(C,D)},共8种纯战1111 略。 在扩展式表述的博弈中，所有n个参与人的一个纯战略组合s = (s, „,s)1n 决定了博弈树上的一个路径。每一个战略组合决定了一个支付向量u = (u, „,u)。 1n 战略组合s*是扩展式博弈的一个纳什均衡，如果对于所有的i，s*i 最大化u(s*,s*)，即： i i-i ,s*?arg max u(s*,s*), i ii i-i 注意，因为一个参与人的纳什均衡战略是假定其他参与人的战略为给定时的 最优战略，所有参与人似乎是在同时选择战略。但这并不意味着在纳什均衡中， 参与人一定是在同时选择行动。 如果一个扩展式博弈有有限个信息集，每个信息集上参与人有有限个行动选 择，我们说这个博弈是有限博弈。如果一个扩展式博弈是有限博弈，那么，对应 的战略式博弈也是有限博弈。 ：一个有限完美信息博弈有一个纯战略纳什均衡。 我们可以使用动态规划的逆向归纳法证明上述定理。因为博弈是有限的，博弈树上一定存在 一个最后的决策结的集合，在该决策结上行动的参与人将选择一个最大化自己的支付的行 动；给定这个参与人的选择，倒数第二个决策结上的参与人将选择一个可行的行动最大化自 己的支付；如此等等，直到初始结。当这个倒推过程完成时，我们得到一个路径，该路径给 出每一个参与人一个特定的战略，所有这些战略构成一个纳什均衡(这个纳什均衡满足我们后面将要介绍的子博弈精炼纳什均衡的要求)。 1.子博弈精炼纳什均衡 2.子博弈精炼纳什均衡的求解---逆向归纳法 该模型可以看作是子博弈完美纳什均衡的最早版本。如同在库诺特模型中一 样，在斯坦科尔伯格模型中，企业的行动也是选择产量。不同的是，在斯坦科尔 伯格模型中，企业1(称为领头企业)先选择产量q?Q=[0,?), 企业2 (称为尾11随企业)观测到q后选择自己的产量q?Q=[0,?),。因此，这是一个完美信息122 动态博弈。这时企业2的策略应该是从Q到Q一个函数，即S: Q?Q, 而企业122121的策略就是简单地选择产量q；纯策略均衡结果是产出向量(q，s(q) ),支112 1付函数为u ( q，s(q) ),由于产量是一个连续变量,故不能作出博弈树。但i 12 1 读者可以设想初始结是企业1的决策结，对应每一个给定的q，企业2有一个决1策结，因此企业2有无穷多个决策结。 假定逆需求函数为P（Q）=a－q－q,两个企业有相同的不变单位成本c?0，12 则支付(利润)函数为： u (q , q)= q(P(Q)－c), i=1,2 i12i 我们可以用逆向归纳法求解这个博弈的子博弈精炼完美纳什均衡。假定q1已经选定, 企业2的问题是: max u(q, q)= q (a－q－q－c) 212212 最优化一阶条件为 s(q)= (a－q－c)/2 211 假定q＜ a－c。这是实际上是库诺特模型中企业2的反应函数，不同的是，1 这里，s(q)是当企业1选择q时企业2的实际选择，而在库诺特模型中，R(q)2112 1 是企业2对于假设的q的最优反应。 1 因为企业1预测到企业2将根据s (q)选择q，企业1在第一阶段的问题是： 212 max u(q, s (q))= q (a－q－s (q)－c) 11211121 解一阶条件得： q*= (a－c)/2 1 将q*代入s (q)得： 121 *= s (q*)= (a－c)/4 q221 这就是子博弈精炼纳什均衡结果（一般称为斯坦科尔伯格均衡结果）。注意， q*= (a－c)/2 和q*= (a－c)/4是均衡结果，而不是均衡本身，因为q*= (a122－c)/4并不是对于任何给定的q的最优选择（即不是第二阶段的所有子博弈的1 纳什均衡）。子博弈精炼纳什均衡是（q*，s (q)）。 121 对比上一节讲到的库诺特模型，可以看到企业1在斯坦科尔伯格博弈中的利 润大于库诺特博弈中的利润，而企业2的利润下降了，这就是所谓的“先动优势”。 当然，如果企业选择的是价格而不是产量，我们得到的就是“后动优势”。