|4.1 博 弈 树|
完全信息动态博弈可以通过下面的例子更好地解释。
同归于尽:假设玩家M在玩家N带着40 000元离开自动取款机时,威胁玩家N。玩家M说:“把钱给我,否则咱们两人同归于尽!”。
这个博弈可以用图4-1所示的扩展形式来描述,这种形式也称为博弈树。
图4-1 同归于尽的扩展形式
在动态博弈中,由于博弈参与者的行动存在先后顺序,因此可以用更形象的方法来表示动态博弈——博弈树(game tree)。通过效益矩阵的形式表示的博弈通常被称为策略型或正则型博弈(normal form game),而通过博弈树表示的博弈通常被称为扩展型博弈(extensive form game)。
定义4-1(博弈树)
博弈树是满足下列要求的扩展形式博弈结构:该树有一个根节点;该树的每个节点都有零个或多个子节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点都可以分为多个不相交的子树。父节点给出了回到根节点的单一路径。直观地说,一个节点决定了到该节点的整个动作序列。最后一个节点是终端节点,其他节点称为决策节点。终端节点不是任何节点的父节点,并表示所有可能的结果。
在完全信息动态博弈中有一些非博弈者,他们以某种正概率随机进入博弈。这些非博弈者被称为自然,或者叫自然行动。自然既不是玩家M,也不是玩家N。有时候用“玩家0”来表示自然。在一个拓展形式中,它被描述为一个空心圆,括号里是概率,如图4-2所示[1]。
定义4-2(扩展形式)
具有完全信息的无限扩展形式(或框架)由以下项目组成:一个有限的有根定向树;一组玩家和一个为每个决策节点分配一个玩家的函数;一组行动和一个为每条有向边分配一个行动的函数(满足没有两条从同一节点出来的边被分配相同行动的限制);一组结果和一个为每个终端节点分配一个结果的函数。
接下来,我们考虑两个实际问题的扩展形式博弈并尝试用博弈树来表示。
图4-2 含非博弈者的扩展形式
竞选:M(来自右派政党)与N(来自左派政党)竞选。他们首先选择一个政治纲领,即“左派”或“右派”,其中M必须先行动。如果两人选择相同的政治纲领,则M获胜,否则N获胜。假设获胜的价值是10,选择与彼此不一致的政治纲领的价值是-5,效益是这些价值之和[2]。(https://www.daowen.com)
有4种结果。如果两人都选择“左派”,M就会赢得10的价值,但会因为妥协而损失5,所以效益是5。如果M选择“左派”,N选择“右派”,那么M“赢”-5,N得到5的效益。如果M选择“右派”,而N选择“左派”,那么M“赢”0,而N得到10的收益。最后,如果M选择“右派”,N也选择“右派”,那么M得到10的效益,而N得到-5。在4个结果位置之前,有一个父位置,在这个位置上,M必须在“左派”和“右派”之间做出选择,N在M做出决定之后有两个位置要做出选择。一个是M选择“右派”的位置,另一个是M选择“左派”的位置。竞选的扩展形式见图4-3。
图4-3 竞选的扩展形式
我们来看另一个例子。
资产分割:M和N决定注销一家企业,其资产价值为100万元。合伙企业的章程规定,高级合伙人M向初级合伙人N提出资产分割的建议。初级合伙人N可以接受,在这种情况下,拟议的分割将被执行。或者初级合伙人N拒绝,在这种情况下,案件将进入诉讼程序:诉讼涉及每个合伙人10万元的法律费用,典型的判决书将60%的资产分配给高级合伙人M,其余40%分配给初级合伙人N。为简单起见,假设判决没有不确定性。还假设M只能提出两个可能的提议:50-50分成或70-30分成。
这种情况可以用图4-4所示的完全信息有限拓展形式来表示。每个结果都表示为两笔钱:上面一笔是M得到的,下面一笔是N得到的。
图4-4 资产分割的扩展形式
在图4-4所示的游戏中,我们应该期望玩家做什么?考虑以下推理,它被称为逆向归纳推理,因为它从游戏的结束处开始,向上进行根的推理:如果N(初级合伙人)被提出50-50分成,那么,如果他接受,他将得到50万元,而如果他拒绝,他将得到32万元(法院分配的40%减去10万元的法律费用),因此,如果理性,他会接受;同样,如果N被提出70-30分成,那么,如果他接受,他将得到30万元,而如果他拒绝,他将得到32万元(法院分配的40%减去10万元的法律费用),因此,如果理性,他会接受。预计到这一切,M意识到,如果他提出50-50分成,那么他最终将得到50万元,而如果他提出70-30分成,那么他最终将得到70万元,因此,如果M是理性的,并且相信N是理性的,他将提出70-30分成,而N作为理性的人,将接受。
上述推理存在缺陷:它不是一个有效的论证,因为它基于N如何对结果进行排序的隐含假设,而这个假设可能是正确的,也可能是不正确的。例如,N可能觉得他和他的高级合伙人M一样努力工作,唯一公平的分配方式是50-50分成,事实上,他可能对此有如此强烈的感受——如果提供不公平的70-30分成,他愿意牺牲10万元以“教训M”,换句话说,他将拒绝70-30分成排在接受70-30分成之前。
我们说图4-4所代表的情况不是一个博弈,而是一个博弈框架。为了将该框架转换为博弈,我们需要为每个玩家都添加一个结果排名。添加完玩家对结果的排名之后(将拒绝70-30分成排在接受70-30分成之前),我们有了一个博弈(而不仅是一个博弈框架),可以应用后向归纳推理(4.3节),得出结论:M将提出50-50分成,预计N会拒绝70-30分成的提议,N将接受M的50-50分成提议。
应该注意的是,策略的概念涉及冗余。我们可以用多种方式来证明策略概念中的这种冗余性。M非常谨慎,他希望他的计划包括他在执行部分计划时可能犯错的可能性(在这种情况下,他允许存在这样的可能性——尽管他打算玩a,他可能最终玩b),或者我们可以把策略看作给第三方的一套指令,说明如何代表M进行博弈,在这种情况下,M可能确实会担心在执行过程中出现错误的可能性,从而希望涵盖所有的意外情况。另一个理由是依赖于对策略概念的不同解释:不是作为M的计划,而是作为N心中关于M会做什么的一个信念。
我们应该清楚的是,博弈可能有不同扩展形式的描述。在文献中,博弈树大多被用来描述扩展形式。使用博弈树往往可以减少节点的数量。
在一个扩展形式中,不完全信息的博弈可以用信息集来描述。由于每个玩家都不知道先前的所有行动,所以我们必须将玩家的决策节点集划分为子集,称为信息集。当玩家i要移动时,他观察到包含“真实”节点的信息集,但他可能不知道已经到达了哪个节点。与之类比可以得出,在完全信息的博弈中,每个信息集只包含一个节点。在不完全信息的博弈中,每个信息集都可以包含一个以上的节点。所以,我们在下节引出的信息集概念在此特指完全信息博弈中的信息集。
