博弈论是一门很有趣的学科，本文将以博弈问题《三个枪手》为脉络，从零基础开始介绍博弈论，和大家一起博弈论是如何解决实际问题的。希望通过本文，让大家都能听懂博弈论。

题目：《三个枪手》

       三个小伙子同时爱上了一个姑娘，为了决定他们谁能娶这个姑娘，他们决定用枪进行一次决斗。A的命中率是30％，B比他好些，命中率是50％，最出色的枪手是C，他从不失误，命中率是100％。由于这个显而易见的事实，为公平起见，他们决定按这样的顺序：A先开枪，B第二，C最后。然后这样循环，直到他们只剩下一个人。那么A第一枪应该怎么打？谁活下来的概率最大？

       以下是初步讨论过程，启发大家思考：

论证：每个人的目标都是活下来，为了目标寻找最好的策略。以下开始分人讨论
A：
•若A开枪射杀了B，则下个开枪是C，C会100%射杀A，这不是一个好策略
•若A开枪射杀了C，则下一轮B会有50%的几率杀掉自己
•若A开枪未打中，则下一轮可以坐山观虎斗，所以A最好的策略看似是故意打空枪更好一些
B：
•若A已经将C射杀，此时B与A互相射击，B的生存率高于A
•B只能选择射杀C，因为只要C活着，都会优先射杀B
C：
•先消除威胁大的B，然后再杀掉A，只要自己有开2枪的机会，直接获胜

问题分析 & 博弈论基础

       不得不说，三个枪手在这种你死我亡的死斗中还能严格遵守决斗顺序，实在是令人钦佩😳👍。

       接下来，让我们一起分析这个问题，并在分析的过程中介绍一些博弈论概念。

   （1）基本特征

       我们继续分析这个情况，首先需要明确：这是一场零和博弈，相信大家对这个词都不陌生。

在零和博弈中，资源总量是固定的，合作不会产生任何额外收益，任何人的收益都意味着其他人等量的损失。

       在这场决斗中，大家争斗的资源就是这一个胜者的名额，任何一人的胜利就一定伴随着其他二人的失败，没有任何共赢的途径。因此这属于典型的零和博弈。

       这种“不是你死，就是我活”的零和博弈属于典型的非合作博弈，其典型特点是博弈者需要绝对的利己，因为合作不会共赢的。

       同时，这场决斗还满足两个条件：

       ① 每个人都知道其他人的命中率是多少。即，每个参与者都掌握了其他参与者的信息。

       ② 每个人行动有先后顺序，且后行者能够观察到先行者所选择的行动。

       这两个条件不妨概括为：“信息透明”和“动态变化”。满足这两个条件，这种博弈被称作完全信息动态博弈。

   （2）关键——纳什均衡

       从以上分析中，我们得出了这场博弈的三个特征：1️⃣ 绝对利己、2️⃣ 信息透明、3️⃣ 动态变化。总结：

       每个人想要获胜，首先需要基于当前形势（因为局势动态变化），并结合对手的信息（因为信息透明），做出对自己最有利的决策（因为绝对利己）。

       基于以上特征做出假设：不仅所有人都会做出自己的最优决策，并且他们做出最优决策的前提，是假设其他人也会做出最优决策。因为信息透明，既然所有人都知根知底，大家就都会试图预测其他人的决策，都是高手过招，谁的心眼儿也不比谁的少，谁也不觉得其他人会走一步臭棋😏。因此，我们可以认为：每个人都是在“预判”其他人的最优决策，并以此为基础做出自己的最优决策。

       这个假设是解答本问题的关键，只有建立了这个假设，我们才可能计算出每位枪手的生存概率。否则，这个问题将变得完全随机，再多的推理都没有意义。试想，如果B、C上来一通乱打，不消灭对自己威胁最大的，先一致把枪口对准“小菜鸡”A，那A的生存概率，可以说是几乎没有，计算A的生存概率还有意义吗？

       为了方便大家理解，再举个小栗子：

       鱼羊问题：A、B二人合伙做饭，A买肉，B下厨；A可以决定买什么肉，B可以决定怎么做。A可以买到的肉有：羊肉、鱼肉，B会的做法分别是：烤肉、肉汤。A想吃到烤鱼或者羊汤，B只想喝汤。A、B都知道对方的喜好，但都只想满足自己的口味。那么，A应该怎么决策才能收益最大？
       分析：这也是一个完全信息动态博弈问题：

       完全信息——A、B都清楚对方想吃什么；动态博弈——只有A先买完肉，B才能烹饪。

       对于动态博弈问题，最好的分析工具是博弈树。博弈树的根节点代表博弈的开始，叶子节点代表博弈的终止。我们可以画出这场博弈的博弈树，如下：

       这个博弈树出现了两次分叉，分别代表了A、B的两次选择，最终得到了4种结果。聪明的读者们，如果你是A，会怎么选呢？不妨用刚才的假设推理：

       因为A知道：B选择做汤对B的收益更高；

       所以A假定：B一定会选择对B收益更高的决策——做汤（预判其他人会做出最优决策）；

       于是A推演：如果A选了鱼肉，也得不到烤鱼，只会得到鱼汤；如果A选了羊肉，可以得到羊汤，而羊汤对A的收益更高。

       因此，A的最佳决策是选择羊肉。A、B二人最终达成的最佳选择是羊汤。

       在鱼羊问题中，正因为A对B的选择进行了预判，才让自己得到了最大收益。

       当我们发现，在一场博弈中，所有参与者都做到如此的“机关算尽”，在任何情况下都做出了最优决策，让自己得到最大收益。当每个人的收益都无法再继续扩大，这时博弈到达了一种均衡状态，我们称这个状态为纳什均衡。所有参与者的最优策略集合被称为均衡解/均衡点。在纳什均衡状态下，各方的收益/胜率才是可能被计算的。一局博弈也可能存在不止一个纳什均衡解。

       我们可以把博弈看作天平，如果每个博弈者都使出了浑身解数，让胜利的天平向自己倾斜，直到任何一方都无法再扩大自己的优势，达到一种“僵持”，那这就是纳什均衡状态。

       比如在上面的鱼羊问题中，“羊汤”就是这个博弈的纳什均衡点。在该点，A、B双方均获得了各自的最高收益。

Tips：纳什均衡（Nash Equilibrium）和约翰·纳什
       纳什均衡是指这样一种策略组合，在该策略组合中，每一个博弈者都相信，在给定竞争对手策略的情况下，他选择了最优策略。任何一位玩家在此策略组合下，单方面改变自己的策略都不会提高自身的收益。
       有趣的是，纳什均衡下所达到的个人最大收益，并不一定能带来整体的最大收益，比如经典的博弈案例“囚徒困境”，感兴趣的读者可以去看一看。
       1950年，纳什均衡由22岁的美国数学家约翰·纳什提出，发表在他27页的博士论文《非合作博弈》中。以“纳什均衡”理论为核心的非合作博弈论一经发布，随即引起轰动，在经济学以及与经济学原理相关的金融、会计、营销和政治等各个学科都掀起了巨大变革，奠定了现代主流博弈论和经济理论的根本基础。1994年，约翰·纳什获得诺贝尔经济学奖。以约翰·纳什为原型的电影《美丽心灵》获得了第74届奥斯卡金像奖最佳导演与最佳影片奖。

   （3）子博弈的纳什均衡

       在动态博弈问题中，博弈会按顺序分多次进行，在整个博弈过程中会出现若干中间状态，这些状态源于这场博弈，由于博弈还未结束，因此如果将中间态视为开始，也可以看作一场新的博弈，我们把这些博弈的中间状态称为子博弈。对应到博弈树中，博弈树的每个非叶子节点都可看作一个子博弈。

如何理解子博弈：围棋、象棋等棋类运动是一种典型的动态博弈游戏。整场博弈始于棋局开始，而「残局」就可以视作整场博弈的子博弈。
棋类运动中的纳什均衡：在棋类运动中，让双方都“不吃亏”的下法也属于纳什均衡。象棋中的“当头炮，把马跳”，围棋中的定式，这种几乎约定俗成的经典下法，使双方都能满意，几乎成为了双方的最优解，其本质就是纳什均衡。

       回到上文的鱼羊问题，让我们再次从子博弈和纳什均衡的角度分析A的最佳决策。当A第一次做出决策后，我们看看A的两个选择所形成的两个子博弈：

       在“羊肉”分支的子博弈中，“羊汤”决策对B的收益更高，B选择该决策收益最大，在这一子博弈中构成纳什均衡；

       在“鱼肉”分支的子博弈中，“鱼汤”决策对B的收益更高，B选择该决策收益最大，在这一子博弈中构成纳什均衡。

       （这两个子博弈是B的回合，所以只需让B的收益最大）

       那么，我们就可以认为：“羊汤”决策是“羊肉”子博弈的纳什均衡解；“鱼汤”决策是“鱼肉”子博弈的纳什均衡解。

   （4）反向归纳法

       如上面的例子，如果一个子博弈可以确定一个唯一的纳什均衡解，那就意味着这个子博弈拥有一个让博弈者利益最大的最优解，我们相信，只要博弈者愿意让自己的利益最大，他就一定会做出这个最优选择。因此在纳什均衡的假设下，我们可以用这个最优解作为这个子博弈的结果。这正是我们之前提到的核心原则：“每个人都假设其他人也会做出最优决策”。

       基于这个原理，我们可以用子博弈的最优解来作为子博弈的结果，即：

       在“羊肉”节点，双方的预期收益为“ A：✅  B：✅”，在“鱼肉”节点，双方的预期收益为“ A：❌ B：✅”。

       显然在这二者中，羊肉节点为纳什均衡解，因此A的最佳选择就是羊肉。与之对应，羊汤就是整场博弈的纳什均衡解。很遗憾，鱼汤虽然是鱼肉子博弈的纳什均衡解，但不是整场博弈的纳什均衡解。 由此，鱼羊问题的整棵博弈树为：

       以上，我们从纳什均衡的角度重新推导了鱼羊问题，这也是求解完全信息动态博弈问题的基本方法：

       从博弈树的所有叶子节点开始，找出所有叶子节点的纳什均衡解，再反向推导回上一层节点，并得出上一层节点的纳什均衡解，直到博弈树根节点，最终得出整场博弈的纳什均衡解。由于最终的纳什均衡解是从子博弈中层层“精炼”而来，整个求解过程被称为子博弈精炼纳什均衡，这个基本方法被称为反向归纳法。

       简单理解，反向归纳法是一种基于结果去反向推理的思维，通过预测不同决策所带来不同结果的好坏，从而选择最好的决策。

问题求解

       恭喜你！读到这里，你已经了解了博弈论的基本概念，并掌握了解决博弈问题的基本方法。

       接下来让我们进入正题，试着用反向归纳法解决一下「三个枪手」问题。

   （1）画博弈树

       分析这类动态博弈问题的第一步是：画出博弈树。

       从第一回合开始，枪法最差的A先开枪，他有三个选择：打B、打C，还有故意放空枪。

       我们发现，对A而言，情况有点不确定性：当A选择打B或打C时，结果不确定。因为A只有30%的几率命中，而有70%的概率打不中，且没打中和放空枪的效果是一样的。因此，A的三个选择只会带来三个可能的结果：命中B、命中C、没打中。我们画出第一轮的博弈树，如下图所示：

       在上面的博弈树中，每个决策都可能导致“没打中”的局面发生，因为它们是一种情况，我们就只展开一个这类节点。

       继续按照这个思路展开博弈树，让我们看看下一回合局势会如何发展：

       如上图所示，到了第二回合，轮到B开枪。这时B会面临三种可能的情况：

       （1）如果B已经被A打死了，那就只能遗憾跳过本轮，直接轮到C的回合（如第一个分支所示）；

       （2）如果C已经被A打死了，那场上只剩下两个人，二人对射即可（如第二个分支所示）。补充一句，在只剩两个人时，我们不考虑放空枪的选择，这显然没有意义。

       （3）如果A没打中，那场上还有三个人，因此此时B仍有三个选择：打A、打C和放空枪（如第三个分支所示）。

       到第三回合，终于轮到百发百中的神枪手C出场啦！此处为了简化讨论，我们不妨排除掉C打空枪的选项。原因有二：

       （1）打空枪是为了鹬蚌相争，渔翁得利，而C作为全场最强，会被其他人当作最大威胁，显然难以“坐山观虎斗”。

       （2）如果C本轮放空枪，博弈局面又将回到起点（轮到A开枪，三人都存活），而只要C开枪，就一定可以淘汰一个对手。对C而言，放弃这一先手机会显然是不明智的。

       那么我们就继续展开博弈树，可以看到：如果本回合场上只剩下两个人，C开枪一定会击杀对手，从而在本轮取得胜利；如何本回合三人都存活，C杀掉一个，还会剩下一个，进入后面的博弈。我们继续将剩下的情况全部推演完毕。整棵博弈树如下图所示：

       可以看到，只要C不死，最快到第三回合，也就是C第一次开枪时，最迟到第六回合，也就是C第二次开枪时，整场博弈结束。

       有的读者会发现，这棵树上有两个被标记为黄色的节点，没有继续展开，它们是博弈过程中，C首先被淘汰后出现的特殊情况，我将它们称为【B先手，AB对射】和【A先手，AB对射】。我们按下不表，稍后我们详细讨论这两种情况。

   （2）求支付矩阵

       画出了博弈树，第二部是求每个叶子节点的支付矩阵。什么叫「支付矩阵」？这个名词其实有点难懂，我们换个叫法，它又被称为「收益矩阵」，用来描述每位博弈者在当前节点下的收益情况。这样是不是好理解多了。举个例子，还记得我们的老朋友——鱼羊问题吗？最右边的一列，分别表示这个菜肴是否满足了A、B二人的胃口，它就是支付矩阵。

       为什么要求支付矩阵呢？因为支付矩阵就是对当前博弈的判断，反映出当前情形对谁更有利，对谁更不利，这样才能方便做出最优选择。

       回到枪手问题中，如何衡量每个人的收益？这是一个零和博弈，所有人追求的就是成为最后的生还者，那么「胜率」就成为衡量收益的标杆。求叶子节点的“胜率矩阵”也很简单，谁赢了，他的胜率就是1，败者是0。

       我们用【A，B，C】的顺序，分别代表三个枪手的胜率，例如C获胜，对应支付矩阵就是【0，0，1】。我们将支付矩阵标注到博弈树的所有叶子节点上，如图中所有绿色的节点：

   （3）反向归纳

       在上面的两步中，我们已经画出了博弈树，并求出了叶子节点的支付矩阵。前两步都是准备工作，接下来就是第三步，也是求解过程中最核心的逻辑：反向归纳法。在这个博弈中，有几个需要提示的规则：

       （1）概率问题：当一个选择可能有多个结果时，这个选择的支付矩阵是多个结果的支付矩阵的加权平均。如B选择打C，命中率是50%，如果命中后的支付矩阵是【0，1，0】，未命中的支付矩阵是【0，0，1】，那么，这个选择的支付矩阵就是【0，1，0】* 50% + 【0，0，1】* 50% = 【0，0.5，0.5】。也就是说，这个选择有50%的概率B获胜，有50%的概率C获胜。

       （2）最优选择：当一个人面临多个选择时，他一定会从每个选择的支付矩阵中，选择他自己胜率最高的那个。这也就是他这个子博弈的纳什均衡解。

       大家可以用上面两个提示，试着反向推导一下博弈树，看看我们得到的结果是否一致：

       以上是用叶子节点反向归纳后得到的博弈树，所有已经求出支付矩阵的节点被标记为了绿色。我们注意到，在图中出现了一个“❌”和一个“✅”，这代表一次分支选择，被标记“✅”的分支是被选中的纳什均衡解，被标记“❌”的分支则是被淘汰的分支。

       让我们看看这次选择：这个子博弈出现在第三回合，此时轮到C开枪，A、B都存活，C需要选择打A还是打B。从图中不难看出，C如果选择打A，自己的胜率是0.5，如果选择打B，自己的胜率会提升到0.7，因为他先解决了更强的对手。因此C一定会选择后者，那么这个子博弈的支付矩阵，就取这个纳什均衡解的支付矩阵。

   （4）「菜鸡互啄」问题

       当问题推导到这里时，我们发现无法进行下去了——因为我们前面还留了两个节点没有展开，无法求支付矩阵。那就让我们看看如何处理这两个节点吧。

       这两个子博弈是在博弈过程中，C首先被淘汰后出现的特殊情况，分别是【B先手，AB对射】和【A先手，AB对射】。此时，由于场上只剩下A、B，因此二人的射击目标只有对方，但由于A、B二人都不能保证百发百中，因此射不到对方的情况理论上永远存在（一般这种情况被称作：菜鸡互啄），如果无限推演下去，博弈树只会陷入死循环，因为没有出口。这下该如何计算双方的胜率呢？让我们以【A先手，AB对射】为例，先分析一下每轮情况。

       设A的命中率为a，B的命中率为b，A先手，则每轮发生的情况的概率如下：

       上表是怎么算出来的？二者只要有一方命中，游戏即会结束。如果未命中，则在本轮未命中概率的基础上，分别乘以下个人的命中率，就会分别得到下轮的命中概率和未命中概率：

       如何计算A的胜率？A的胜率，即为A每回合命中的概率之和，即：

       是不是看起来很眼熟？你没有猜错，我们需要使用微积分了（死去的微积分突然攻击我😭）。友情建议：看到数学就头大的读者请自行跳过这部分。

       上面的式子可以表示为：

       我们可以发现，这是一个幂级数求和问题。如果还没太看清，我们令，则原式变为：

       我们先判断敛散性：由于，则，那么。

       因幂级数的收敛域是，因此该幂级数收敛。

       根据公式，可得：

       这样，我们就得到了A先手，A、B对射时A的胜率。我们知道A的命中率为30%，B的命中率是50%，我们将，带入可得：

       。相应地，此时B的胜率.

       同样的公式，当转换为B先手，A、B对射时，将，代入，可得：

       ，。

（5）得出答案

       有了上一步计算出来的两个特殊子博弈中A、B的胜率，我们可以得出：

       【A先手，AB对射】的支付矩阵是【6/13，7/13，0】。

       【B先手，AB对射】的支付矩阵是【3/13，10/13，0】。

       继续完善博弈树，并完成后续的反向归纳过程，最终得到的结果是：

       我们通过反向归纳法得到了A第一回合的三个选择的支付矩阵，比较三种选择下A的胜率：

       A打B——26.7%；A打C——33.6%；打空枪——38.1%，因此我们终于可以得出这个问题的答案：A的最优策略是打空枪，生存概率是38.1%（99/260）.

       这个答案同样也论证了我们一开始的预期——A最好的策略看似是故意打空枪更好一些。有趣的是，这场博弈中，A、B、C的胜率分别为38.1%、26.9%和35%（纳什均衡状态下），看来枪法最差的A生存下来的概率果然也是最高的呢！当然，个人认为，他之所以能拥有最高胜率，主要还是因为他可以先手啦。

       以上，我们就给出了「三个枪手」动态博弈问题的解决方案，希望通过以上解答，带大家搞懂博弈论的基本原理。想必一定有读者有疑问：太麻烦了，难道每次都要画一遍博弈树，手动推演一遍不成？别着急，我将给出以上问题的代码实现，请看下回分解。