开发者社区 > 博文 > 博弈论入门篇——「三个枪手」的心理博弈
分享
  • 打开微信扫码分享

  • 点击前往QQ分享

  • 点击前往微博分享

  • 点击复制链接

博弈论入门篇——「三个枪手」的心理博弈

  • jd****
  • 2024-03-15
  • IP归属:北京
  • 100浏览

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


    题目:《三个枪手》

           三个小伙子同时爱上了一个姑娘,为了决定他们谁能娶这个姑娘,他们决定用枪进行一次决斗。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回合二:B回合三:A回合四:B...
    命中的概率a(1-a)b(1-a)(1-b)a(1-a)(1-b)(1-a)b...
    未命中概率1-a(1-a)(1-b)(1-a)(1-b)(1-a)(1-a)(1-b)(1-a)(1-b)...

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

           如何计算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生存下来的概率果然也是最高的呢!当然,个人认为,他之所以能拥有最高胜率,主要还是因为他可以先手啦。

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