纳什均衡

  • A+

纳什均衡

喜欢玩德州扑克的人应该都听说过“GTO”这个词。GTO,即 GameTheory Optimal,翻译成中文应该叫做“游戏理论最优化”。直接翻译过来有点拗口,通俗一点的解释可以是:在游戏中,你可以采取一种最优策略,使得自己的损失最小,同时游戏中的对手也必须采取相对应的策略,否则只会扩大你的受益。

讲到GTO,就不得不提到博弈论中非常著名的一个理论:纳什均衡(Nash Equilibrium)。该理论是由著名的经济学家,博弈论创始人,诺贝尔奖获得者约翰·纳什提出的,也就是电影《美丽心灵》的男主角原型。该理论是说:在非合作类博弈中,存在一种策略组合,使得每个参与人的策略是对其他参与人策略的最优反应。如果参与者当前选择的策略形成了“纳什均衡”,那么对于任何一位参与者来说,单方更改自己的策略不会带来任何好处。

约翰·纳什证明了在每个参与者都只有有限种策略选择,并允许混合策略的前提下,纳什均衡一定存在。上边的解释还是有点拗口,这里通过几个例子,更直观的理解一下这个理论。

纳什均衡

什么是纳什平衡?


纳什均衡是博弈论最重要、最一般化的均衡概念。它是指所有参与人战略的这样一种组合:在这一组合中,给定其他参与人的战略,没有任何人有积极性改变自己的战略。换言之,构成纳什均衡的战略对每个人都是最优的。


纳什均衡有一个很重要的特点,即信念和选择之间的一致性。也就是说,基于信念的选择是合理的,同时支持这个选择的信念也是正确的。所以,纳什均衡具有预测的自我实现(self-enforcement)的特征:如果所有人都认为这个结果会出现,这个结果就真的会出现。(在博弈中的所有组合中,只有纳什均衡能满足自我实施的条件)


我们可以换一个角度来理解纳什均衡:假如在博弈之前,所有的参与人达成一个协议。我们的问题是:在不存在外部强制执行的情况下,每一个人是否有积极性去自觉遵守这个协议?如果每个人都有积极性遵守这个协议,这个协议就构成一个纳什均衡。也就是说,给定这个协议,别人遵守的情况下,没有人会有积极性选择不同于这个协议的行动,这个协议就是一个纳什均衡。反之,如果有任何人有积极性单方面背离这个协议,这个协议就不是一个纳什均衡。


从下面几个例子,可以看出纳什均衡是一个多么有力的分析工具。


囚犯的困境

假设有两个小偷A和B联手闯入民宅盗窃被抓,警方将两人置于不同的房间进行审讯,并给出如下政策:如果一个犯罪嫌疑人坦白并交出了赃物,两人都会被判有罪。如果另一个犯罪嫌疑人也坦白,则两人各被判刑8年;如果另一个犯罪嫌人抵赖,再加刑2年,而坦白者有功,会被立即释放。如果两人都抵赖,偷窃罪证据不足,但会因私入民宅而各判入狱1年。即:

20200706112021

表中的数字表示A,B各自的判刑结果。博弈论分析中一般都用这样的表来表示。

此时有人会觉得双方都抵赖就好了,但问题是双方被隔离,都会怀疑对方会出卖自己以求自保。两个人都会这么想:假如对方坦白,此时如果我抵赖得坐10年监狱,如果我坦白才坐8年监狱;假如对方抵赖,此时如果我也抵赖会被判1年,如果我坦白可以被释放。综合以上考虑,不管对方坦白与否,对我而言都是坦白划算。此时最后的“纳什均衡”只能是两个人都坦白,共同被判8年刑期。

智猪博弈

猪圈里有两头猪,一头大猪,一头小猪。猪圈的一边有个踏板,每踩一下踏板,在远离踏板的猪圈的另一边的投食口就会落下少量的食物。如果一只猪去踩踏板,另一只猪就有机会抢先吃到另一边落下的食物。但当小猪踩踏板时,大猪会在小猪跑到食槽之前刚好吃光所有的食物;大猪踩动了踏板,则有机会在小猪吃完落下的食物之前跑到食槽,争吃到另一半食物。

那么,两只猪各会采取什么策略?当然是小猪等在食槽边,而大猪不知疲倦地奔忙于踏板和食槽之间。因为,小猪踩踏板将一无所获,不踩踏板反而能吃上食物。对小猪而言,无论大猪是否踩动踏板,不踩踏板总是好的选择。反观大猪,已明知小猪不会去踩动踏板,自己亲自去踩踏板还有点吃的,总比不踩强,所以只好去踩踏板。

范式博弈

GOO公司和SAM公司存在利益关系,二者的收益会随着博弈的变化而不断更替。如下图:

双方各有两个可选策略“合作”与“背叛”,格中的四组数据表示四个博弈结局的各自收益,每组数据的第一个数字表示GOO公司的收益,后一个数字表示SAM公司的收益。

现在我们站在GOO公司的角度来思考整个博弈策略。假如SAM选择合作,那么我方合作的收益是3,而我方背叛的收益是5,我方应该选择背叛;假如SAM选择背叛,那么我方合作的收益是 -3,而我方背叛的收益是-1,我方还是应该选择背叛。

同理,SAM公司也会做出相同的选择。最后我们发现,本次博弈的双方都采取了背叛策略,各自的收益都为-1,这是一个比较糟糕的结局,尽管对任何一方来说都不是最糟糕的那种。

但博弈的次数往往不止一次,当二家公司经历了多次背叛策略的博弈之后,发现公式上还有一个(3,3)收益的双赢局面,这个结果显然要好很多,因此二家公司在之后的博弈过程中必然会尝试互建信任,从而驱使双方都选择合作策略。

但假使双方都知道博弈次数是有限的,也许下一次博弈就是最后一次,那么为了避免对方在最后一轮博弈中选择背叛而使我方遭受-3的损失,于是双方都会采取了背叛策略,最后的博弈结果又回到了(-1,-1)。

由此可见,随着次数的变化,博弈的性质也会发生变化,纳什均衡点会发生变化。

饿狮博弈

假设有A、B、C、D、E、F六只狮子(强弱从左到右依次排序)和一只绵羊。假设A吃掉绵羊后就会打盹,这时比A稍弱的B就会趁机吃掉A,接着B也会打盹,然后比B稍弱的C就会吃掉B,以此类推。问:狮子A敢不敢吃绵羊?

该题须采用逆向分析法,从最弱的F开始分析,依次前推。假设E睡着了,F肯定会吃掉E,因为在F的后面已没有其它狮子了,不用担心自己被吃掉。继续前推,既然E知道自己睡着会被F吃掉,那么E必然不敢吃睡着了的D。既然E不敢吃掉D,那么D则可以放心去吃睡着的C。依次前推,得出C不吃,B吃,A不吃。所以答案是狮子A不敢吃掉绵羊。

但是,如果我们在狮子F的后面增加了一只狮子G,总数变成7只,用逆向分析法按照上题步骤再推一次,如下图。这次的答案变成了狮子A敢吃掉绵羊。

对比两次博弈我们发现,狮子A敢不敢吃绵羊取决于狮子总数的奇偶性:当总数为奇数时,A敢吃;总数为偶数时,A则不敢吃。因此,总数为奇数和总数为偶数的狮群博弈结果形成了两个稳定的纳什均衡点。

硬币正反博弈

加入你和一个美女一起玩个数学游戏。美女提议:让我们各自亮出硬币的一面,如果我们都是正面,那么我给你3元;如果我们都是反面,我给你1元;剩下的情况你给我2元。那么你该不该和这位美女玩这个游戏呢?

这里需要讲一下纳什均衡的分类:

(1)纯战略纳什均衡,也就是说玩家都能够采取固定的策略(比如一直出正面或者一直出反面),使得每人都赚得最多或亏得最少。

(2)混合战略纳什均衡,是对每个纯战略分配一个机率而形成的战略。混合战略允许玩家随机选择一个纯战略。混合战略纳什均衡中要用概率计算,达到某一概率时,可以实现支付最优。因为概率是连续的,所以即使战略集合是有限的,也会有无限多个混合战略。

在这个游戏中,应该采用混合策略纳什均衡。

假设我们出正面的概率是x,出反面的概率是1-x,美女出正面的概率是y,出反面的概率是1-y。为了使利益最大化,应该在对手出正面或反面的时候我们的收益都相等,即:

3x + (-2)(1-x) = (-2) * x + 1*(1-x )

解方程得x=3/8;同样,美女的收益:

-3y + 2(1-y) = 2y+ (-1) * (1-y),

解方程同样得y等于3/8。于是,我们就可以算美女每次的期望收益是:

(1-y) * (2x-(1-x)) + y(-3x+2(1-x)) = 1/8元

即双方都采取最优策略的情况下,美女平均每次赢1/8元。所以当然不能和她玩这个游戏。其实只要美女采取了(3/8, 5/8)这个方案,不论你采用什么方案,都是不能改变局面的。但是当你也采用最佳策略时,至少可以保证自己输得最少。否则,你会赔掉更多。


德州扑克
德州扑克