扩展式博弈

我们应怎样形式化地描述一个博弈？扩展式博弈是博弈论的基本形式。要以扩展式描述一个博弈，我们必须明确行为者（或称参与者），并且明确它们面临什么决策，以什么顺序行动，由哪一位参与者作出决策，在什么条件下，会产生什么结果。

定义：一个扩展式的n人博弈是：

（1）一个由众多节点和分枝组成的有限的博弈树，在其中，树的每个节点是博弈的一个移动或该博弈的端点，以及连接这些节点的分枝；

（2）把节点在参与者、机会和博弈端点中间作划分，我们给每个节点分派一个并且只有一个参与者、机会或端点[这个划分又称为节点的分隔（partition）]；

（3）机会的每一个移动都有一个概率分布；

（4）把众多节点分割为众多参与者集合，再把这种分割提炼为每位参与者的信息集；

（5）一个由众多结果组成的集合，并且把这些结果分派到博弈树的每个端点，以便每个端点有一个且只有一个结果；

（6）一个由众多效用函数组成的集合，并且每个参与者i有一个对于结果的效用函数ui。

以上各项全部都是所有参与者的共同知识——所有参与者都意识到这一点，所有参与者都意识到所有其他参与者知道这一点，无限类推下去。

博弈树包含一系列被依次连接起来的节点。每个节点有一定数量的分枝，这些分枝通向其他节点。这些节点代表决策，而这些分枝代表在每个决策中能够被选择的行动。因为一些节点是博弈的端点，所以它们没有分枝，我们把它们称为终端节点（terminal nodes）。其他的节点则称为选择节点（choice nodes）或选择点（choice points），因为参与者在该博弈的那一个点上作了一个选择（包括机会移动，即作为机会或自然的选择）。在图3.5中一共有15个节点。8个是终端节点，博弈树的上面部分和下面部分各有4个。有7个选择节点，4个被分派给挑战者，2个分派给防御者，1个分派给机会（初始移动）。各个分枝给出参与者在每个选择节点上所具有的选择，以及机会在博弈开始时移动的可能结果。我把每个分枝都标记出来，以帮助我们看到它们对应于什么行动。各个分枝不能够“长”回它自身。并且分枝不能通向一个在它现在所位于的节点之前的节点。通过博弈树到达博弈的每个节点的路径有一条并且只有一条。图3.6所示的两个例子含有不被允许的节点和分枝。对于在每个节点上存在什么选择以及该博弈何时结束等的全部规定被称为博弈树，因为它形状像一棵树。每个节点顺着分枝伸展出更多的选择。终端节点是每个分枝系统的端点。

一些节点位于别的节点之前。如果有一条由选择或机会移动所组成的路径，它从一个节点通向它后面的一个节点，那么这后面的节点就称为前面的节点的后续节（successor），或称为后续节点（successor node），而前面的节点则称为后面的节点的前续节（predecessor），或称为前续节点（predecessor node）。如果一个行动从一个节点通到下一个节点，那么前者被称为直接前续节（immediate predecessor），而后者则是前者的直接后续节（immediate successor）。在该博弈的每一部分中，防御者要抵抗挑战者的决定都（直接）接续挑战者要挑战现状的决定，并且都（直接）在挑战者要继续推进威胁的决定之前。但是，挑战者在防御者是坚决型的时候要挑战现状的决定并非被防御者在它不是坚决型时要抵抗的决定所接续，因为不存在从前面所说的节点到后面所说的节点的选择路径。在某个节点之前的各个移动所形成的完整顺序被称为该博弈在这个点之前的历史（history）。每个节点都有一个独一无二的历史，它概括了前面的所有移动，因为要到达博弈的一个节点有且只有一条由参与者行动或机会移动所组成的路径。该威慑博弈在到达坚决的防御者必定选择抵抗挑战者这个点之前的历史是“坚决，挑战”。在该历史中，我们明确了机会移动和挑战者的挑战决定。

我们把非终端节点在参与者中间进行划分，每个节点上有一个且只有一个参与者。为了让机会能够移动，我们把机会（有时又被称为自然）看作一位参与者。机会的移动就是机会而不是参与者采取行动的节点。在每个分派给机会的节点上都有关于移动选择的一个单独的概率分布。机会移动所被赋予的概率在博弈的开始就为所有参与者所知。机会移动让我们能够在一个博弈中包含随机因素。威慑博弈包含一个机会移动以明确防御者是不是坚决的。我在前面讨论了包含另一个机会移动以表示战争结果所代表的抽奖。机会移动可以被放置在博弈的任意一点上。

每位参与者的节点还可以进一步划分为不同信息集。信息集表示一位参与者在必须作决策时所拥有的关于前面行动的知识。当一位参与者到达一个多于一个节点的信息集时（例如，见图3.5中虚线所代表的信息集），它只知道它必须作出一个决定，并且它只知道它正位于该信息集的一个节点上。拥有多个节点的信息集反映参与者不知道该博弈树中前面的移动。它不能确定前面的几个移动中哪些已经被作出。从一个信息集内每个节点所发出的各个移动必须是相同的。否则，该参与者可以通过检视可供选择的行动来区分一个信息集内的各个节点。信息集形成博弈的实际选择点，因为信息集概括了参与者在什么时候选择以及在博弈的那一点上它知道什么。只包含一个节点的信息集被称为单节（singletons）。

信息集明确规定参与者能核实的关于博弈中前面的移动的信息。想象一下，每位参与者位于一个单独的房间，该博弈是这样进行的，一个裁判员从一个房间走到另一个房间去告诉每位参与者当他必须作出选择时他正位于哪一个信息集。如果该裁判员告诉一位参与者他正位于一个单节信息集，该参与者就知道他正位于哪一个节点，并且能够从到达该节点的博弈的历史中重构所有前面的移动。然而，如果该裁判员告诉这位参与者他正位于一个有多个节点的信息集，那么该参与者将无法重构该博弈的历史，因为不同的历史通向该信息集内不同的节点。当然，该参与者可以对该博弈的历史作出推断，但是他无法确定这些推断是否正确。作为一个概述参与者对博弈进程的无知的博弈要素，信息集这个术语是一个奇怪的名字。

终端节点表明博弈的结束，并且每个终端节点都被分派一个结果。每位参与者都有一个对于所有结果的效用函数。参与者的效用函数功能在于评价各种结果对于该参与者而言令人向往的程度。很多时候，我们只是给出各位参与者对每个终端节点的结果的效用评价，而不是描述结果本身。如果是这样的话，我们称这些效用为收益（payoffs）。

最后，我们假定参与者们了解他们正在参与的博弈。如果所有参与者都知道博弈的某个方面，所有参与者都知道其他参与者知道它，如此类推，那么，它就是共同知识（common knowledge）。我们假定博弈的扩展式是共同知识。参与者能够使用其关于该博弈的知识来预期其他参与者的移动并在他们面对决策时形成关于该博弈的未来的期望。有关该博弈是共同知识的假定消除了“他们认为我们认为他们知道，如此类推”这样的无限回环的问题。任何一条对一位参与者来说是已知但又不是共同知识的信息是该参与者的私人信息（private information）。

关于博弈是共同知识的假定看起来限制性非常强。我们也许会以为这会妨碍我们分析那些参与者对它们的处境存在根本的不确定性的情形。然而，威慑博弈向我们表明，我们能够在博弈中表示出这样的不确定性。防御者的收益是其私人信息，挑战者不知道防御者的收益。通过仔细建立机会移动和信息集，我们能够用模型表示对一个博弈的不确定性，同时又不违反该博弈是共同知识的假定。

在此，一个简单的例子也许有助于厘清对扩展式的定义。让我们考察硬币配对（Matching Pennies）博弈。两位参与者每人有一枚硬币。每位参与者偷偷地选择使硬币的正面朝上还是使反面朝上。然后，他们让双方都看到硬币。如果两个硬币是同一面朝上，那么两个硬币都归第一位参与者；如果两个硬币是不同的面朝上，那么两个硬币都归第二位参与者。图3.7给出硬币配对的扩展式。该图让我能够介绍我在本书中用来处理扩展式博弈的一些习惯做法。这些方格表示选择节点，每个节点前面列出移动的参与者。博弈开始时，参与者1在正面和反面之间选择，两个选项在图中分别被记为H和T。参与者2也在正面和反面之间选择，分别记为h和t。方便起见，我把参与者2的移动表示为接续着参与者1的移动。因为他们的移动是同时的，我们也可以首先表示参与者2的移动。参与者2有两个可能的节点，一个对应于参与者1选择正面，另一个对应于参与者1选择反面。其行动被列在每个分枝旁边。终端节点用圈点表示，后面紧跟着各参与者对于该结果的收益，以（参与者1的收益，参与者2的收益）的方式给出。虽然参与者2有两个选择节点，当她必须选择时她无法确定参与者1的移动。两位参与者的移动是同时的。我们通过把参与者2的两个移动连接成一个信息集来表示它们是同时的移动，也就是用连接她的两个节点的虚线来表示。该信息集表示，当参与者2必须选择她的移动时，她不知道参与者1的移动。这就是在扩展式博弈中表示同时移动的方法。值得一提的是，参与者2的两个节点都必须有同样的可以采取的行动。否则，它们不能被连接成一个信息集。

我采纳了下列用于更复杂的博弈的习惯做法。方格表示选择节点，而圈点表示终端节点。机会节点前面用大写字母C标明。当我用缩写来标示参与者的行动时，我对这些标示作以下区分。参与者1的行动用大写字母标明，参与者2的行动用小写字母标明，参与者3（如果需要用到的话）的行动用斜体的大写字母标明，而参与者4的行动则用斜体的小写字母标明。如果有超过两位参与者，那么我在括号中按顺序写出他们的收益，中间用逗号隔开。为了方便，我称参与者1为“他”，称参与者2和3为“她”，称参与者4为“他”。当我一般性地讨论参与者时，我使用“它”作称谓。我用一些与政治内容无关的抽象的博弈来阐明关于博弈论的要点。在这些博弈中，我把行动统称为上（Up）和下（Down），分别缩写为U和D或者u和d；或者称为左（Left）和右（Right），分别缩写为L和R或l和r；又或者称为前（Front）和后（Back），分别缩写为F和B或f和b。

练习3.1：画出下面讨价还价博弈的扩展式。两位参与者正试图瓜分6美元。参与者1可以首先向参与者2提议分给后者4美元或者2美元。然后参与者2选择要么接受要么拒绝这第一个提议。如果她拒绝参与者1的提议，那么他们掷硬币。如果硬币的正面朝上，那么参与者1得到3美元而参与者2得到1美元。如果硬币的背面朝上，那么参与者1得到1美元而参与者2得到3美元（也就是说，如果他们不同意，那么掷硬币花费他们2美元）。

练习3.2：用文字描述图3.8的博弈。

练习3.3：画出井字游戏（tic-tac-toe）的最前面两个移动的博弈树，每个行为者做一个移动。1（提示：注意要充分利用博弈的对称性。例如，只有三种可能的初始移动，即一个角落的方格、一个中间的方格或者在各个边的中间的方格之一。）

我们用三个专业术语来描述参与者在进行博弈时可能具有的信息。

定义：如果一个博弈的所有信息集都是单节，那么该博弈就是在完美信息（perfect information）之下进行的。如果一个博弈的全部参与者的收益都是共同知识，那么该博弈就是在完全信息（complete in-formation）之下进行的。如果一个博弈的某位参与者的收益是它的私人信息，那么该博弈就是在不完全信息（incomplete information）之下进行的。

完美信息表示所有参与者的信息集都只包含一个节点，因此所有参与者在采取行动时都知道该博弈的历史。在普通的室内游戏（parlor games）中，国际象棋和西洋棋都是在完美信息之下进行的，而桥牌和扑克则不是。在桥牌和扑克中，在博弈的开始存在一个机会移动（即发牌），它直到游戏结束才完全向参与者展示。完美信息涵盖参与者知道在博弈的每个移动之前发生的所有种种情境。完全信息表示所有参与者都知道相互的收益。威慑博弈是在不完全信息之下进行，因为挑战者在移动时并不知道机会移动的结果。我们运用不完美信息来模型化该不完全信息。带有多个节点的信息集反映出参与者所面对的不确定性。正如在威慑博弈中所体现的，不确定性可以借助初始的机会移动以及紧接着的对该机会移动的结果的不完美信息而被引入博弈中。

我们还假定，各位参与者记得他们前面的移动，以及它们在前面的节点时所知道的任何信息集。这一假定被称为完美回忆。

定义：一个博弈在符合以下条件时是在完美回忆之下进行的：

（1）在博弈中没有任何一个信息集同时包含一个节点和该节点的一个前续节；

（2）对于参与者i的一个信息集内的任意两个节点x和x′，如果x″是x的一个前续节，并且在参与者i的一个信息集内，那么存在x′的一个前续节点y和x″处在同一个信息集内，并且满足：参与者i从y到x′所采取的行动和从x″到x所采取的行动是同样的。（注：节点x″和y可以是同一个节点。）

定义的第一部分要求各位参与者区分当前移动与未来移动。图3.9左边的博弈部分违反了这一条件，即如果参与者1选择D那么他会忘记他刚刚移动过。在该博弈中，参与者1的信息集把他的第一个选择节点和如果他在第一个选择节点处采取D的话会得到的选择节点连接起来。由于他无法区分他的第一个节点和该节点的后续节点，他忘记了他在其第一个节点是选择了D。定义的第二部分更为复杂，并且排除了几种类型的健忘。它排除了一位参与者忘记先前的移动的情形（如图3.9右边的博弈那样）。它还排除了参与者忘记它们在博弈中原先知道的其他参与者（包括机会）的移动的情形。在我知道的政治学的博弈例子中，没有哪个例子是参与者不具有完美回忆的。如果你把桥牌看作一个在两队参与者（南北和东西）之间进行的两参与者博弈的话，桥牌是一个没有完美回忆的博弈的例子。在叫牌（bidding）时，在一手牌叫牌后，每位“牌手”暂时忘记他看到过什么牌。在北叫牌之后，然后参与者南北会忘记当南必须叫牌时北的手上有什么牌。

一些博弈的扩展式可能很不方便把它们写出来。如果参与者们的移动构成一个无限的阵列（array），那么画出无穷多个分枝可能需要一些时间。例如，有关一项议题可能采取的政策的值域（range）常常被模型化为一条直线上的各点而不是一个有限集（finite set）。制定政策的人从无穷多个可能政策中选择所要采取的政策。拥有一个无限但清楚定义的行动集合的博弈常常被描述成时间线形式（time line form）。一个博弈的时间线形式等同于扩展式。它明确各位参与者的决策节点的顺序，在每个选择节点供参与者选择的选项有哪些，当一位参与者必须行动时他或她拥有什么信息，这些选择如何产生结果，参与者对于这些结果的效用函数等等。一个时间线形式按顺序列出各个节点，明确是谁移动、可供选择的选项、特定参与者在特定节点上所拥有的信息等。终端节点给出结果以及各位参与者的效用函数。

在时间线形式和扩展式中均有体现的时间概念是指决策时间（deci-sion time）而不是严格的计时时间（chronological time）。没有一个假定规定节点要在时间上均匀分布，甚至也没有一个假定规定节点的前续节必须要在该节点之前发生。正如在硬币配对博弈中那样，移动可以是同时的。这些形式试图体现选择的决策环境。参与者知道什么？它们的决策如何互动从而产生结果？虽然时间的先后顺序可能影响参与者知道什么以及它们的选择如何导致各种结果，但最重要的是决策环境而不是时间上的先后顺序。