查看原文
其他

游戏博弈论:洞悉“剪刀-石头-布"背后的纳什均衡

Patrick Honner 集智俱乐部 2019-04-12

|  quantamagazine


导语

现实生活中许多情况都可以看作是在“博弈”,而达到纳什均衡在某种意义上对所有玩家都是积极的结果。本文首先条分缕析了纳什均衡在小游戏中的体现,又对其进行了扩展延伸探讨,更复杂的情况下,“看不见的手”究竟会如何影响你的决策呢?


编译:集智俱乐部翻译组

来源:Quantamagzine

原题:

Why Winning in Rock-Paper-Scissors (and in Life) Isn’t Everything


生活中,我们常用剪刀-石头-布的猜拳游戏来决定谁去做清洁劳动等等,但是,你有没有注意到当你一轮一轮地进行游戏时到底发生了什么?


起初,你可能处于上风,然而,你的对手可能会让游戏又转向对她有利的一面。随着游戏的进行,你们实施着各自的策略,直到最终所有玩家似乎都不能通过改善个人策略而获得更多的胜利。


这是为什么呢?


纳什均衡


其实,早在1950年,数学家约翰·纳什(John F. Nash Jr. )就向我们证明,在任何拥有有限参与者和有限策略的游戏(例如,剪刀-石头-布)中,总是存在这样的混合策略:使得在该策略下没有任何参与者可以通过仅改变自身策略而提高收益。


后来,这种稳定的策略组合被人们称为“ 纳什均衡 ”。它不仅促进了传统的博弈论领域的革新,改变了经济学的进程,也改进了人们在政治条约、网络交通等诸多方面的研究分析方法。而纳什也因此获得了1994年诺贝尔奖。


纳什均衡可行性分析:

https://www.quantamagazine.org/in-game-theory-no-clear-path-to-equilibrium-20170718/


1994年诺奖获得者John F. Nash Jr. 传记:https://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/1994/nash-bio.html


那么,纳什均衡在剪刀-石头-布的游戏中又是如何体现的呢?




纯(pure)策略


让我们模拟你(玩家A)和对手(玩家B)来简单分析一下。其中,玩家每轮胜出得一分,失败则丢掉一分,平局记零分。


现在,假设玩家B首先采用一种(愚蠢的)战略,即每回合都出布。那么,经过几轮的游戏之后,你可能就会发现她的策略并采取每回合都出剪刀的策略来反击。我们将这种策略组合记为(剪刀,布)。如果每一轮以这样的策略组合进行,毫无疑问你将取得胜利。


但是,玩家B很快也会发现自己在这样的策略组合中的劣势。当她观察到你总是出剪刀应对时,她也转而采用总是选择石头的策略。这个策略组合(剪刀,石头)中B又开始赢得胜利。当然,你也可以继续针对新的策略组合而选择出布。


在上述游戏过程中,玩家A和B采用了所谓的“纯”(pure)策略,即选择并重复执行单一的策略。


对于任何纯策略,例如“总是选择石头”,我们都可以采用对立的策略应对,例如“总是选择布”。此时,相关的策略也将再一次发生变化。于是,你和你的对手将永远围绕策略圈互相追逐。


显然,这样的纯策略是不存在平衡点的。



混合策略


当然,你也可以尝试“混合”策略。假设你可以在每轮游戏中随机选择一种策略,而不是一直只选择一种策略。例如,你可以并不“总是选择石头”,而是“一半时间出石头,另一半时间出剪刀”,等等。


纳什证明,当允许这样的混合策略时,每个这样的游戏将至少存在一个平衡点。那么,我们现在来举例说明一下。


首先,我们需要了解,在剪刀-石头-布的游戏中,究竟怎样的混合策略才是合理的呢?例如,我们可以假设“游戏中以相同的概率选择剪刀、石头或布”,那么对应的策略组合表示为(1/3,1/3,1/3),即剪刀、石头或布被选中的概率均为1/3。这会是一个好的策略吗?


好吧,假设你的对手策略是“总是选择石头”这样的纯策略,我们用(1,0,0)表示。那么,在A选择(1/3,1/3,1/3)且B选择(1,0,0)的策略组合中,游戏的结果将会如何呢?


为此,我们绘制如下表格,其中列出了每轮游戏中九种可能的组合结果(例如,A出石头,B出石头; A出石头,B出布,等等)对应的概率。其中,第一行表示玩家B的选择,第一列表示玩家A的选择。

本文所示图中R-石头,P-布,S-剪刀,后文不再赘述


表中展示了任意轮次中策略组合的概率,即双方各自策略对应概率的乘积。例如,玩家A选择布的概率为1/3,而玩家B选择石头的概率为1,那么(A选择布,B选择石头)的概率为1/3×1=1/3;而(A选择布,B选择剪刀)的概率则是1/3×0=0,因为玩家B选择剪刀的概率为零。


那么,在这样的策略组合中,玩家A的表现究竟如何呢?从表中我们可以看到,玩家A将在三分之一的时间取胜(布,石头),三分之一的时间失败(剪刀,石头),另外三分之一的时间打平(石头,石头)。并且,我们可以通过计算每个结果与其相应概率的乘积的总和来得到玩家A每轮的平均得分:

可以看到,玩家A每轮平均得分为0,即以相等的概率获胜,失败或平局。因此,平均而言,双方胜负的次数将均等,从而终究将表现为平局。


但是,正如上文所述,假设你的对手没有改变他们的策略,你可以通过改变个人策略而得到更好的结果。例如,如果你切换到策略(0,1,0)(即“每次都选择布”),那么相应的概率分布如下所示:


每轮游戏中,你选择的布都将战胜对手的石头,于是你每轮都会获得一分。

所以,A选择(1/3,1/3,1/3)且B选择(1,0,0)的策略组合并未达到纳什均衡,因为作为玩家A的你可以通过改变个人策略来改善结果。


正如我们所见,纯策略似乎并没有导致均衡。但是,如果你的对手尝试混合策略,比如(1/2,1/4,1/4),即“一半时间选择石头; 四分之一的时间选择布和剪刀”,那么我们可以得到下表中的概率分布:



现在,我们列出玩家A对于每种结果的得分情况如下:



类似地,将上述两个图表的结果综合起来,我们可以得到玩家A每轮的平均得分:



可以看到,玩家A平均每轮仍然获得0分。于是,A选择(1/3,1/3,1/3) 且B选择(1/2,1/4,1/4)策略组合最终将同样达到平局。


然而,同样地,作为玩家A的你也可以通过切换策略来改善你的结果:对于B 的策略(1/2,1/4,1/4),A应该选择策略(1/4,1/2,1/4),相应的概率图表如下:



此时,对于A,每轮游戏的净得分为:



也就是说, A选择(1/4,1/2,1/4)且B选择(1/2,1/4,1/4)的策略组合进行游戏时,A每轮游戏的平均得分为1/16,。这样,在100场游戏过后,A的得分将高出6.25分。因此,作为玩家A的你转变策略的可能性很大,所以A以(1/3,1/3,1/3)  且B以(1/2,1/4,1/4)的策略组合同样不是纳什均衡。


现在,我们考虑一下这一对策略,即 A以(1/3,1/3,1/3)且B以(1/3,1/3,1/3)的策略进行游戏时,可以得到相应的概率图表如下:



根据对称性我们可以很快得到A每轮游戏的净得分为:



显然,你和你的对手将再一次战成平局。但与上述情况不同的是,此时双方玩家都不会有改变策略的动机


例如,如果玩家B转向任意的不平衡策略,使得其中一种选择(比如石头)更多,那么玩家A只需简单地改变策略使得“布”更多即可。正如上文提到的玩家A采用策略(1/4,1/2,1/4)对抗玩家B 的策略(1/2,1/4,1/4)一样,这将使A在每轮游戏中得到更好的净得分。


当然,如果玩家A从(1/3,1/3,1/3)的策略转换到一种不平衡策略,那么玩家B也可以用类似的方式进行反击。


因此,任何玩家都不能仅通过仅改变个人策略来改善他们的结果。也就是说,这样的策略组合达到了纳什均衡。


设计机制


正如纳什证明的,这些(博弈)游戏都具有纳什均衡,而这一事实的重要性体现在好几个方面。


一方面,现实生活中的许多情况都可以看作是博弈中的情形。例如,在谈判或者在共享资源的竞争中,人们面临着个人与集体利益的权衡,这时你就会发现这些策略在其中得到了很好的应用进而各方利益可以得到相应的评估。也正是这些无所不在的数学模型使得是纳什的工作有如此影响力。


另一方面,纳什均衡在某种意义上对所有玩家都是积极的结果。到达均衡后,没有人能通过仅改变自己的策略来使结果达到更优。当然,如果所有玩家都采取完美的合作的方式,可能会有更好的整体结果,但如果你能控制的只是你自己,最终达到纳什均衡将会是你最好的选择。


因此,我们可能更希望像经济激励方案、税务、条约以及网络设计这些“(博弈)游戏”终究达到纳什均衡。毕竟在这种均衡中,个人为了自己的利益行事,且最终得到满意的结果,并且系统也会很稳定。


但是,在这些博弈之中,“玩家自然会达到纳什均衡”的这个假设是否合理呢?


游戏“升级”


回顾一下,在剪刀-石头-布的游戏中,我们可能已经猜到,玩家以完全随机的方式玩更好。但这部分是因为玩家都知道彼此的偏好:即每个人都知道彼此在各种可能结果中获胜和失败的情况。


可是,如果偏好未知而且情况更复杂呢?


想象一下这样一款新的游戏,其中玩家B在击败剪刀时获得三分,而在任何其他情况下获胜仅获得一分。这将改变混合策略:玩家B将会更频繁地选择石头并希望玩家A选择剪刀从而获得三倍的得分。虽然积分差异不会直接影响玩家A的得分,但玩家B策略的变化将触发A的新的对策。


并且如果玩家B的每一个回报都是不同且未知的,那么玩家A需要一些时间才能弄清楚玩家B的策略是什么。为了估计自己选择布的频率,玩家A需要通过很多回合来理解玩家B选择石头的策略。


进一步地,我们现在想象有100人玩剪刀-石头-布的游戏,每个人的得分情况都保密,每个都取决于他们击败对手的情况。那么,为了达到平衡点,你需要多长时间来计算你选择石头、布或剪刀的正确频率?可能是很长一段时间,也许比游戏还要长。甚至可能比宇宙的寿命更长!


至少,即使是完全理性且深思熟虑的玩家,想制定好的策略按照自己的最佳收益行事并最终在比赛中达到平衡也并不容易。


2016年的一篇论文的核心观点就向我们证明:在所有游戏中,没有统一的方法可以引导玩家达到哪怕是近似的纳什均衡。


论文题目:

Communication complexity of approximate Nash equilibria

论文地址:

https://arxiv.org/abs/1608.06580


这并不是说完全理性的玩家在比赛中从不倾向于达到均衡,实际上他们经常这样做。这只是意味着我们没有理由相信——游戏能实现纳什均衡是因为只由完全理性的玩家参与。


当我们设计一个交通网络时,我们同样可能希望游戏中的玩家(即每个寻求最快回家路线的旅行者)能够共同达到一种平衡,使得即使各方采取不同的路线也不会获得任何额外收益。我们可能希望约翰·纳什的“看不见的手”能够指导他们,以便他们在竞争合作中达到均衡,即采取尽可能短的路线,并避免造成交通拥堵。


然而,上面逐渐复杂的剪刀-石头-布游戏已经向我们展示了为什么这样的希望可能会落空。因为这双"看不见的手"虽然会引导一些博弈,但是其他一些情况可能会抵制它的控制,终于玩家将陷入永无止境的竞争中,永远无法获得收益。


翻译:SBu

审校:高飞

编辑:王怡蔺

原文地址:

https://www.quantamagazine.org/the-game-theory-math-behind-rock-paper-scissors-20180402/


推荐阅读


经济推理与人工智能

博弈机器学习 

协调动力学

偏好依附机制

加入集智,一起复杂!

推荐课程



课程地址:https://campus.swarma.org/gcou=10503




集智QQ群|292641157

商务合作及投稿转载|swarma@swarma.org

◆ ◆ ◆

搜索公众号:集智俱乐部


加入“没有围墙的研究所”

让苹果砸得更猛烈些吧!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存