决策树与博弈树

决策树与博弈树

即使一个孤立的决策者，置身于一个有其他参与者参加的策略博弈中，也可能会面对需要向前展望、倒后推理的决策序列。例如，走在黄树林中的罗伯特•费罗斯特（Robert Frost）：两条路在树林里分岔，而我，

我选择人迹罕至的那一条，

从此一切变了样。1我们可以对此图示如下：

到此未必就不用再选择了。每一条路后面可能还会有分岔，这个图相应地会变得越来越复杂。以下是我们亲身经历的一个例子。

从普林斯顿到纽约旅行会遇到几次选择。第一个决策点是选择旅行的方式：乘公共汽车、乘火车还是自己开车。选择自己开车的人接下来就要选择走费拉扎诺（Verrazano）桥、霍兰（Holland）隧道、林肯（Lincoln）隧道还是乔治•华盛顿（George Washington）桥。选择乘火车的人必须决定是在纽瓦克（Newark）换乘PATH列车，还是直达纽约Penn车站。等进入纽约，搭乘火车或公共汽车的人还必须决定怎样抵达自己的最后目的地，是步行、乘地铁（是本地地铁还是高速地铁）、乘公共汽车还是搭出租车。最佳选择取决于多种因素，包括价格、速度、不可避免的交通堵塞、纽约市最终目的地所在，以及对新泽西收费公路上的空气污染的厌恶程度，等等。

这个路线图描述了你在每个岔路口的选择，看起来就像一棵枝繁叶茂的大树，所以称为“决策树”。正确使用这样一张图或一棵树的方法，绝不是选择那个第一个分支看上去最好的路线。例如，当各种方式的其他方面相同时，你会更喜欢自己开车而不是乘火车，然后“到达下一个岔路口的时候再穿过费拉扎诺桥。”相反，你应该预计到以后将面临的决策，然后根据这些决策做出你的早期选择。举个例子，如果你想要去市区，那么乘PATH列车会比开小汽车要好，因为乘PATH列车可以从纽瓦克直达市区。

我们可以通过下图来描述一个策略博弈中的选择。不过，现在图中出现了一个新元素。我们遇到了一个有两个人或更多人参与的博弈。沿着这棵树的各个决策点，可能是不同的参与者在进行决策。每个参与者在前一个决策点做决策时必须向前展望，不仅要展望他自己的未来决策，还要展望其他参与者的未来决策。他必须推断其他人的下一步决策，办法就是想象自己站在他们的位置，按照他们的思维方式思考。为了强调这个做法与前一个做法的区别，我们把反映策略博弈当中决策序列的树称为博弈树，而把决策树留做描述只有一个人参与的情形。

∷足球赛和商界中的查理•布朗

尽管本章开篇提到的查理•布朗的故事非常简单，不过把故事转化成以下的图示，你就可以更加熟悉博弈树。在博弈起点，当露西发出邀请时，查理•布朗面临着是否接受邀请的决策。假如查理拒绝邀请，那么这个博弈到此为止。假如他接受邀请，露西就面临两个选择，一是让查理踢球，二是把球拿开。我们可以通过在路上添加另一个分叉的方法说明这一点。

正如我们先前所述，查理应该预计到露西一定会选择上面那个分支。因此，他应该置身于她的立场，从这棵树上剪掉下面那个分支。现在，如果他再选择自己上面的那个分支，结果一定是仰面跌倒。因此，他最好选择下面的分支。我们用加粗的带箭头的分支来表示这些选择。

你是否认为这个博弈太微不足道？以下是它在商业领域的一个版本。设想以下情景，已成年的查理目前正在（假设）弗里多尼亚国（Freedonia）度假。他和当地的一个生意人弗里多（Fredo）聊了起来，弗里多谈起了一个只要投入资本就可以获利的绝妙机会，他大声地说道：“你给我10万美元，一年后我会把它变成50万美元，到时候我和你平分这笔钱。所以，你将在一年内获得两倍以上的钱。”弗里多所说的机会确实令人向往，何况他很乐意按照弗里多尼亚的法律规定签订一份正规合同。但弗里多尼亚的法律有多可靠？如果一年后弗里多卷款潜逃，已经返回美国的查理能向弗里多尼亚的法院要求执行这份合同吗？法院有可能会偏向自己的国民，或者可能效率很低，又或者可能被弗里多收买。因此，查理实际上是在和弗里多进行一场博弈，博弈树如下图所示。（注意，如果弗里多遵守合同，他会付给查理25万美元；这样，查理获得的利润等于25万美元减去初始投资10万美元，即15万美元。）你认为弗里多会怎样做？在没有十足把握相信弗里多承诺的情况下，查理应该预计到弗里多一定会卷款潜逃，就像小查理确定露西一定会把球拿开一样。事实上，两个博弈的博弈树在本质上是相同的。但是，面临这样的博弈时，多少“查理”做出了错误的推理？

有什么理由可以让查理相信弗里多的承诺？或许，弗里多同时也和其他一些企业做交易，这些企业需要在美国融资或者出口商品到美国去。那么，查理很有可能会毁坏弗里多在美国的声誉或者直接扣押他的货物，以此向弗里多实施报复。所以，这个博弈可能只是更大的博弈的一部分，或许是一个持续的互动过程，这一点确保了弗里多的诚信。但是，在我们上述说明的一次性博弈中，这种倒后推理的逻辑非常明了。

我们希望借助这个博弈得到三点结论。第一，不同的博弈可以采用相同的或者极为相似的数学形式（博弈树，或者在以后章节中提到的用来描述博弈的图标）。用这种形式来进行思考反过来又突出了它们的相似之处，使你更容易将你掌握的关于一种情形下的博弈知识运用到另一种情形中去。这是所有学科理论的重要功能：它提炼出各种明显不同背景的本质相似性，使得一个人能够以一种统一而简单化的方式对各种情形进行思考。许多人本能地讨厌所有理论。但我们认为这是一个错误的反应。当然，理论确实有其局限性。特定的背景和经历通常能大大扩展或修正一些理论方法。但是，抛弃所有理论就相当于抛弃一个有价值的思维出发点，一个克服难题的立足点。当你进行策略思维时，你应该把博弈论当做你的朋友，而不是一个怪物。

第二，弗里多应该认识到，具有策略思维的查理一定会怀疑他所说的话的可靠性，而且根本不会投资，这样，弗里多就失去了赚取25万美元的机会。因此，弗里多有强烈的动机使其承诺可以置信。作为一个生意人，他对弗里多尼亚国脆弱的法律体系几乎没有任何影响力，因此并不能以此来打消这位投资者的顾虑。他还有其他办法让自己的承诺可信吗？我们将会在第6章和第7章考察常见的可信问题，并介绍一些达到可信的方法。

第三，或许也是最重要的一个结论，涉及对参与者不同备择选项不同结果的比较。一个参与者获得更多并不总是意味着另一个参与者获得更少。查理选择投资而弗里多选择遵守合同这种对双方都有利的情形，优于查理根本不投资的情形。和体育比赛或者其他比赛不同，博弈不一定非要有胜出者和失败者；用博弈论的术语来说就是，它们并不一定是零和博弈。博弈可以出现双赢和双输的结果。事实上，共同利益（比如，若弗里多有办法给出一个遵守合约的坚实承诺，则查理和弗里多双方都能获益）和冲突（比如，若弗里多在查理投资之后卷款潜逃，查理就要付出昂贵的代价）的结合同时存在于商界、政界以及社会交往活动的大多数博弈中。这正是使得分析这些博弈如此有趣并具有挑战性的因素。

∷更复杂的树

我们从政界找到了一个例子，用来介绍更复杂一点的博弈树。有一幅讽刺美国政界的漫画谈及，国会希望增加建设经费支出，而总统们则希望削减国会通过的这些巨额预算。当然，在这些经费支出中，有总统们喜欢的也有总统们不喜欢的，而他们也只想削减那些他们不喜欢的经费支出。要达到这个目的，总统们必须有削减一些特定预算项目的权力或者逐项否决权。1987年1月，罗纳德•里根在国情咨文讲话中口若悬河地说道：“给我们和43位州长一样的权力——逐项否决权，我们就可以减少不必要的经费支出，削减那些永远不应独自存在的项目。”

乍一看，似乎拥有法案的部分否决权只会增强总统的权力，而永远不会给他带来任何不好的结果。但是，总统没有这个权力可能会更好。原因在于，逐项否决权的存在会影响到国会通过法案时的策略。以下这个简单的博弈说明了逐项否决权将如何影响国会的策略。

为便于说明，假设1987年的局势如下。有两个支出项目正在考虑中：城市重建（U）和反弹道导弹系统（M）。国会喜欢前者，而总统喜欢后者。但相对于维持现状来说，双方都更喜欢让两个法案都通过。下面的表格展示了两个参与者对可能出现的情况的评价，其中4代表最好，1代表最差。结果国会总统U和M都通过33只有U通过41只有M通过14U和M都未通过22当总统没有逐项否决权时，该博弈的博弈树如下图所示。总统会签署同时包括项目U和项目M的法案，或者只包括项目M的法案，但会否决只包括项目U的法案。国会很清楚这一点，所以会选择两个项目都包括的法案。同样，我们还是用加粗的带箭头的分支来表示每一个决策点处的选择。注意，我们有必要在总统必须做出选择的所有决策点处都做这样的标记，即使其中一些决策点处已经标记了国会的上一步选择。这么做的理由在于，国会的实际行动深受其对每种选择之后总统将如何行动的算计的影响；要说明这一逻辑，我们必须把所有逻辑上可能的情况下总统的行动选择表示出来。我们对该博弈的分析结果是，双方都只得到了自己次佳的结果（评价为3）。

接下来，我们假设总统拥有逐项否决权。于是该博弈变成了如下所示：现在，国会预料到若自己让两个项目都通过，则总统就会选择否决项目U，只留下项目M。因此，国会的最佳行动是，要么只通过项目U，然后眼睁睁地看着它被否决，要么哪个项目也不通过。或许，如果国会可以借助总统否决获得政治积分，那么国会可能会倾向于前一种行动，但总统同样也有可能通过拒绝预算而获得政治积分。我们假设两者相互抵消，于是这两个选择对国会来说是无差异的。但是，这两个选择只给双方带来了第三好的结果（评价为2）。甚至对总统而言，他得到?结果也因其拥有的额外选择自由而变得更糟。2

这个博弈阐述了一个重要且具有一般性的观点。在单人决策中，更大的行动自由可能永远没有坏处。但是在博弈中，它却可能对参与者不利，这是因为行动自由的存在会影响到其他参与者的行动。与此相反，“绑住自己的双手”可能会有帮助。我们将在第6章和第7章探讨这一“承诺优势”。

我们已经将博弈树的倒后推理方法运用到一个微不足道的博弈中（查理•布朗的故事），之后又扩展到一个更复杂的博弈中（逐项否决权）。无论博弈多么复杂，基本的原理仍然是适用的。但是如果在博弈树中，每个参与者在每个决策点上都有几个选择，而且每个参与者都要开展多次行动，那么，博弈树可能很快变得太过复杂，以至于难以画出或者使用。举个例子，在象棋博弈中，有20个分支从第一个决策点发散出去——白方可以将自己的八个兵中的任何一个往前走一格或两格，或者两个马中的任何一个往前走一格或两格。对应于白方的每一种选择，黑方也有20种走法，因此，我们就已经得到400种不同的路径了。从以后的决策点处发散出的分支可能会更多。要运用博弈树的方法使象棋问题得到完全解决，是大多数现存的乃至往后数十年内可能发明出来的最强大的计算机也力所不能及的。在本章后面部分，我们将讨论象棋大师是如何解决这一问题的。

在这两种极端的情况之间，还有很多中等复杂的博弈，这些博弈出现在商界、政界以及日常生活中。有两个方法可以用于解决这样的博弈。第一，电脑程序可以构建博弈树并计算出结果。3或者，很多中等复杂的博弈可以通过树逻辑分析得到解决，而无须明确画出博弈树。我们将借助一个电视游戏节目中的博弈，来说明这个方法。在这个博弈中，每个参与者都尽力去比其他人玩得更好、更聪明且持续得更久。