展开型博弈 在本章，我们研究博弈的展开型表示法，这种方法能详细描述博弈，包括行动顺序 以及参与人得到的消息等。我们将解释展开型博弈背后的重要概念。由于本书主要考察 策略型博弈，我们在本章给出展开型和策略型之间的联系。我们还将说明如何将任何展 开型博弈转换成策略型博弈。 展开型博弈 展开型为博弈的描述提供了一种详细且结构丰富的描述方法。这种形式首先由冯· 诺依曼和摩根斯坦（vonNeumann andMorgenstern[1]）提出，后被库恩（Kuhn[2]） 凝练。展开型能描述博弈的序贯行动。具体地说，它能描述：（1）在任何给定时点，谁 做出行动；（2）每个参与人可能做出什么行动；（3）在每个阶段，参与人在行动之前， 知道些什么；（4）结果（作为参与人行动的函数）是什么；（5）参与人从每个结果得到 的收益。当参与人为有限个而且每个参与人的行动也为有限个时，可用博弈树描述 博弈。 3.1例子 在正式定义展开型博弈之前，我们首先提供几个例子。 例3.1（可观察情形下的硬币配对）在可观察情形下的硬币配对博弈中，有两个 参与人（1和2），每个人都有一枚硬币。其中一人将自己的硬币放下，正面向上（以H 表示）或反面向上（以T表示）。另外一人看到这个结果，然后也将自已的硬币放下。 如果两枚硬币配对成功（都为正面向上或都为反面向上），那么参与人2给1一元钱。 如果配对不成功，参与人1给2一元钱。该博弈有两个版本，这取决于参与人1还是2

先放硬币。图3一1是参与人1先放硬币时的博弈树，图3一2是参与人2先放硬币时的 情形。 1,- 1,1 1,1 图3一1可观察情形下的硬币配对（参与人1先行动） 1,一1 -1,1 一1,1 图3一2可观察情形下的硬币配对（参与人2先行动） 在博弈树中，节点有三类：（1）根节点（rootnode），也叫初始决策节点；（2）内 部节点（internalnodes），它们是决策节点；（3）叶节点（leafnodes），或称终止节点， 它们是结果节点。博弈的每一串可能事件都可用始于根节点且终于其中一个终止节点的 一条路径描述。当博弈展开时，这样的路径称为行动路径（pathofplay）。每个决策节 点旁边都注明了谁在该节点行动。另外，注意，每个决策节点都可以按下列方法找到： 从根节点出发，沿着一定路径前进，直到到达该决策节点。从决策节点向外发出的连线 （枝）旁边注明了参与人在该节点可能选择的行动。注意，每个节点不仅表示博弈的当 前位置，还表示博弈是如何达到这个位置的。终止节点旁边注明了每个参与人从相应结 果得到的收益。口 例3.2（不可观察情形下的硬币配对）在这种情形下，其中一个参与人将硬币放 下，正面向上或反面向上。另外一个参与人不观察这个结果，随后也将自已的硬币放 下。这个博弈也有两个版本，图3一3画出了参与人1先行动情形下的博弈树，图3一4 画出了参与人2先行动时的情形。注意，图3一1和图3一3中的博弈树几乎完全相同， 只不过在图3—3中参与人2的两个决策节点被虚线连接在一起。图3一2和图3一4的

关系也是这样的。被虚线连接在一起的节点集称为信息集（informationset）。当博弈进 行到信息集中的某个决策节点且轮到某参与人行动时，他不知道自己位于哪个节点上， 原因在于他没有观察到前面发生了什么事情。口 图3一3不可观察情形下的硬币配对（参与人1先行动） 展开型博弈 图3一4不可观察情形下的硬币配对（参与人2先行动） 例3.3（同时行动情形下的硬币配对）在这个博弈中，两个参与人同时将硬币放 下。显然，每个参与人没有机会观察对方行动的结果。在这里，不涉及谁先行动。因 此，图3一3和图3—4都能描述这个博弈。口 3.2展开型博弈：定义 我们现在正式给出展开型博弈的定义。这个定义基本来自OsborneL3]。我们首先定 义信息集。 定义3.1（信息集）参与人的一个信息集（informationset）是一个由他无法区分 的决策节点组成的集合。 参与人的信息集描述的是当轮到他行动时，他不知道自己位于哪个决策节点上，所 有这样的决策节点构成了他的信息集。由于每个决策节点对应着唯一的行动路径（从根

节点到该决策节点的路线），因此参与人的每个信息集由他无法区分的所有真子历史 （propersubhistories）组成。显然，给定参与人（比如，参与人1）的信息集，在该信 息集内的每个节点上，他必定有相同的可能行动集。 例3.4在图3一3所示的硬币配对博弈中，参与人1的唯一信息集是单点集（}， 它由空历史（emptyhistory）组成。参与人2的信息集是集合（H，T），它由参与人2 无法区分的真历史H和T组成。另一方面，在图3一1所示的博弈中，参与人1有唯一 的信息集，即（e）；而参与人2有两个信息集，即（H和（T），因为他能区分这两个真 子历史。口 定义3.2（展开型博弈）展开型博弈是个多元组T=（N，（A）∈N，H，P， （I）ieN，（ui）ieN），其中 ·N={1，2，"，n}是参与人集，这是一个有限集； ·A;（i=1，"，n）是参与人i的行动集； ●H是由所有终止历史（terminalhistory）组成的集合，其中一个终止历史是一条 从根节点到终止节点的行动路径，使得它不是任何其他终正历史的真子历史；以S：表 示由所有终止历史的所有真子历史（包括空历史e）组成的集合； ·P：SH→N是一个参与人函数（playerfunction），它将每个真子历史与相应参 与人联系在一起； ●I（i=1，2，，n）是由参与人i的所有信息集组成的集合； ●u：H→R（i=1，2，，n）给出了参与人i的每个终止历史的效用； 博 例3.5我们用图3—1所示的硬币配对博弈说明定义3.2。 弈论 N={1,2} 与机 A=A={H，T} 制 H={（H,H)，（H，T)，（T，H)，（T，T)} 设计 SH={∈,H，T} P（)=1,P（H)=2,P（T)=2 I={{e}}，I2={{H}，{T}} u（HH)=1,u（HT)=-1,u（TH)=-1,u1（TT)=1 u2（HH)=-1,u2（HT)=1,u2（TH)=1,u2（TT)=-1 显然，不同参与人的行动集可从终止历史和参与人函数推导出来。口 注释尽管参与人的行动集可从终止历史与参与人函数推导出来，但为了更容易理 解展开型博弈的定义，我们还是将其作为这个定义的组成部分。 例3.6（进入博弈）进入博弈（entrygame）有两个参与人，1和2。参与人1为 挑战者，参与人2为在位者（incumbent）。图3一5画出了博弈树。 参与人1（挑战者）可以决定挑战在位者（即参与人1选择“进人"），也可以决定 不挑战（即不进人）。当挑战者决定进人时，参与人2（在位者）可以斗争，也可以容 忍，即接受。各自的收益在博弈树中已注明。对于这个博弈，我们有 N={1,2} A1={进入，不进入}，A2={接受，斗争}

挑战者 进入 不进入 在位者 接受 斗争 1,2 2,1 0,0 图3—5进入博奔的博奔树 H={（进入，接受），（进入，斗争），（不进入）} SH={e，（进入）} P（e)=1，P（进入）=2 I={{e}}，I2={{进入}} u（进入，接受）=2，u（进入，斗争）=0，u（不进入）=1 u2（进入，接受）=1，u2（进入，斗争）=0，u2（不进入）=2 再次注意到，行动集A和A2可从终止历史与参与人函数推导出来。口 例3.7考虑图3—6所示的博弈树。 展开型博弈 (2,0) (3，1) (1，2) (0,0) 图3—6另外一个博弈树 根据这个博弈，可知 N={1,2} A={C,D,G，H}，A={E,F} 终止历史为 H={（C,E,G)，(C,E,H)，(C,F),(D)}

终止历史的真子历史为 SH={e,(C),(C,E)} 参与人函数为 P（）=1;P（C)=2;P（C,E)=1 信息集为 I={{∈}，{（C,E)}}；I2={{（C)}} 效用函数为 u(C,E,G)=1,u（C,E,H)=0,u(C,F)=3，u（D)=2 u2（C,E,G)=2,u2（C,E,H)=0，u2(C,F)=1,u2（D)=0 这样，我们就完整描述了图3一6中的博弈。口 定义3.3（完美信息博弈与不完美信息博弈）给定一个展开型博弈，如果它的所 有信息集都是单点集，那么它是完美信息（perfectinformation）博弈；如果至少一个 参与人至少有一个含有两个或多个元素的信息集，那么它是不完美信息（imperfectin- formation）博弈。 在完美信息博弈中，每个参与人都能看到所有以前行动或到当前位置为止的整个历 史。每个参与人准确知道他在哪个节点上，也准确知道如何达到这个节点。 博奔论与机制设计 例3.8图3—1、图3—2、图3—5和图3—6中的博弈都是完美信息博弈，而图 3一3和图3一4中的博弈都为不完美信息博弈。同时行动的硬币配对博弈显然是不完美 信息博弈。口 3.3将展开型博弈转换为策略型博弈 策略是博弈论中最重要的概念之一。一个策略（strategy）就是一个完整的行动方 案，它规定了参与人在他的每个信息集上将做什么。 回忆一下，I：表示由参与人i的所有信息集组成的集合。与以前一样，令A：表示 参与人i的行动集。给定信息集JEI，令C（J)二A为参与人i在信息集J内的所有可 能行动组成的集合。于是，我们可以将参与人的策略正式定义如下。 定义3.4（策略）参与人i的策略（strategy）s:是一个映射si：I；→A;，使得s（J）∈ C(J),JEIi 参与人i的策略s：是一个完全相机方案，它对此人的每个信息集都规定了相应的行 动。因此，在参与人需要行动的每个阶段或历史，策略都规定了参与人选择什么行动。 事实上，参与人可准备一张查询表，该表有两列，一列是他的信息集，另一列是相应行 动。于是，参与人可让他的代理人代替他博弈，只要代理人按照该查询表行事即可。参 与人的不同策略对应着不同的相机行动方案。我们用例子说明策略这个概念。 例3.9（可观察情形下硬币配对博弈中的策略）考虑图3一1中的博弈。我们有

I={{e}}；I2={{H}，{T}}。参与人1有两个策略： S:{e}→H S12:{e}→T 参与人2有四个策略： S21:{H}→H;{T}→H S22:{H}→H;{T}→T S23:{H}→T;{T}→H S24:{H}→T;{T}→T 现在，参与人1和2的收益可用表3一1描述。例如，当参与人1的策略为s且参与人 2的策略为s2时，参与人1和2分别选择H和H，他们的收益分别为1和一1。 表3-1 可观察情形下的硬币配对博弈中的收益 $22 $23 $24 $11 1,-1 1，-1 -1，1 -1，1 S12 -1，1 1，-1 -1，1 1，-1 上面的策略型博弈等价于原来的展开型博弈。对于图3一2中的博弈，参与人2有 两个策略，参与人1有四个策略，表3一1所示的收益矩阵不难得到。口 例3.10（不可观察情形下的硬币配对博弈中的策略）考虑图3一3所示的博弈。 容易看出Ⅱ={{e}}，I2={{H，T}}。在这里，参与人1有两个策略，参与人2也有两 个策略： 展开型博弈 S:{e}→H $12:{e}→T S21:{H,T}→H S22:{H,T}→T 根据参与人可能选择的策略，我们可以写出收益矩阵，如表3一2所示。 表3-2 不可观察情形下的硬币配对博弈中的收益 12s S22 $11 1，-1 -1，1 S12 -1,1 1,-1 显然，同时行动的硬币配对博弈与上面这个博弈的策略相同，收益矩阵也相 同。口 例3.11考虑图3—6中的博弈。参与人1有四个策略： S1:{e}→C;{(C,E)}→G S12:{e}→C;{(C,E)}→H

S13:{e}→D;{(C,E)}→G S14:{∈}→D；{(C,E)}→H 为简单起见，我们将上面的策略分别记为CG、CH、DG和DH。参与人2有两个策略： S21:{C}→E S21:{C}→F 同样地，为简单起见，我们将上面的策略分别记为E和F。如果令S和S2分别为参与 人1和2的策略集，那么 S={CG,CH,DG,DH} S2={E,F} 由所有策略组组成的集合S×S2为 SXS={(CG,E),(CG,F),(CH,E),(CH,F),(DG,E)， （DG,F),(DH,E),(DH,F)} 注意，一个策略组决定了唯一的终止历史。例如，策略组（CG，E）对应着终止历史 （C，E，G)；策略组（CG，F）对应着终止历史（C，F)；策略组（DH，E）和 （DH，F）都对应着终止历史（D）。这个例子让我们得到下列定义。口 定义3.5（结果）给定展开型博弈G和它的一个策略组s=（s1，，Sn），则策略 组s对应着一个终止历史，与该终止历史相伴的结果称为策略组s的结果（outcome）， 博 奔论与机 记为0（s)。 注释一个展开型博弈对应着唯一的策略型博弈。如果不考虑策略的重新命名或重 新编号，那么这个对应是唯一的。然而，我们将看到，一个策略型博弈可能对应着多个 制 展开型博弈。 设 注释任何给定的展开型博弈都有等价的策略型博弈。然而，这个等价的策略型博 计 弈未必包含原来展开型博弈的所有策略相关信息。事实上，策略型表示法通常反映不出 博弈的动态性，因为策略型是同时行动的。本书主要考察策略型博弈。需要注意，由于 在动态博弈中参与人的行动有先后之分，而且参与人在行动过程中能得到信息，因此动 态博弈需要使用展开型来表示。 3.4小结与参考文献 下面我们总结一下本章的重要知识点。 ·博弈的展开型表示法能够详细描述参与人的行动顺序以及他们在博弈过程中得到 的信息。有限展开型博弈可用博弈树表示，博弈树由决策节点和终止节点组成。每个决 策节点对应着既定参与人，该参与人必须在该决策节点处选择自已的行动。 ·参与人的信息集是展开型博弈的一个重要概念。既定参与人的信息集是由他无法 区分的决策节点组成的集合，也就是说，在这样的集合中，参与人不知道他位于哪个决 策节点上。

·给定展开型博弈，如果每个参与人的每个信息集都是单点集，那么这个博弈是完 美信息的。单点集这句话意味着：在每个决策节点上，对于从根节点到该决策节点的整 段历史，相应参与人是了解的。给定展开型博弈，如果至少一个参与人的至少一个信息 集不是单点集，那么这个博弈不是完美信息的。 ·给定任何展开型博弈，我们都可以使用策略概念将其转变为等价的策略型博弈。 参与人的任何一个策略都是一个完全行动方案，它规定了该参与人在他的每个信息集中 应该选择怎样的行动。 ·策略型博弈通常反映不出博弈的动态性。然而，它简化了分析，而且在很多情形 下，我们使用策略型表示法就足够了。 ·一个策略型博弈可能对应多个展开型博弈，而一个展开型博弈只对应着一个策略 型博弈。 本章的大部分内容改编自OsborneL3]以及Mas-Colell，Whinston，and Green[4]。 本书主要考察策略型博弈，很少涉及展开型博弈（第6章除外）。在第6章我们将短暂 回到展开型博弈的讨论，这是为了介绍子博弈完美均衡（subgameperfectequilibrium） 概念。对于展开型博弈的详细介绍，我们推荐读者学习Osborne[3]、MyersonL6]以及 Maschler, Solan,and Zamir6]。 口参考文献 [1]JohnvonNeumann andOskarMorgenstern.TheoryofGamesandEconomic Behavior.Princeton University Press,1944. 第 [2]H.W.Kuhn.“Extensive form games and the problem of information”.In:Contri- 真 butions to theTheory of Games II.PrincetonUniversityPress,1953，pp.193-216. 展 [3]Martin J.Osborne.AnIntroduction to GameTheory.The MIT Press,2003. 开 型博弈 [4]Andreu Mas-Colell,Michael D.Whinston,andJerryR.Green.Microeconomic Theory.Oxford UniversityPress,1995. [5]Roger B.Myerson.Game Theory:Analysis of Conflict.Harvard University Press,Cambridge,Massachusetts,USA,1997. [6]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam bridgeUniversityPress,2013. 3.5习题 （1）你可能听说过“三子连线棋”（Tic-Tac-Toe）游戏（博弈）。画出它的博 弈树。 （2）在某个博弈中，某个参与人有m个信息集，记为j=1，2，，m。信息集j 有k；个可能行动。该参与人有多少个策略？ （3）给定图3一7中的博弈，写出终止历史、真子历史、信息集以及该博弈的策 略型。

R R -1,1 1,-1 -1,1 1,-1 -1,1 1,-1 -1,1 图3—7一个展开型博弈 博奔论与机制设计