经典博弈问题与纳什均衡

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

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

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

囚徒困境

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

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

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

智猪博弈

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

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

范式博弈

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

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

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

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

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

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

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

猎鹿博弈

有两个猎人,有两种猎物,兔子和鹿。鹿需要两个的人合作才能抓到,抓到后够两个猎人吃2天。兔子一个人就可以抓到,但是只够自己吃1天。所以,合作就可以通过劳动得到两天的食物。不合作的结果,要么就是只能抓到兔子,吃1天。要么就是抓不到鹿,只能饿肚子。

猎鹿博弈中,有两个纳什均衡,即只要两个博弈参与者选择相同的策略,无论是猎鹿还是猎兔都是纳什均衡。在这两个纳什均衡中,一个是risk dominant,一个是payoff dominant。对比猎兔与猎鹿,猎兔时不合作的风险较小,但回报同样较小;猎鹿时则要求最大程度的合作,但回报也大得多。

如何能够达到payoff dominant的均衡,实现整体效率的最大化,需要通过促进收益公平等方式来达到。

猎鹿博弈是纳什均衡的一个特例,但是它提出的时间其实比纳什早多了,出自大名鼎鼎的卢梭写的鼎鼎大名的《论人类不平等的起源和基础》。卢梭讲这个故事的本意是说明任何个体的背叛都会给集体的合作带来严重的影响,而无法达到“猎鹿”的最优状态。

饿狮博弈

假设有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)这个方案,不论你采用什么方案,都是不能改变局面的。但是当你也采用最佳策略时,至少可以保证自己输得最少。否则,你会赔掉更多。

未经允许随便转载:看过够 » 经典博弈问题与纳什均衡

赞 (4) 打赏

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏