• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

博弈论经典模型解析(入门级)

开发技术 开发技术 3周前 (09-02) 18次浏览

面试的过程中,除了常规的算法题目,我们经常也会被问到一些趣味题型来考察思维,而这类问题中,很多都有博弈论的影子存在。这些公司里以FLAG(Facebook, LinkedIn, Amazon, Google)为典型,特别喜欢考察本类题型。同时,本系列将不一定都是算法问题,不是IT行业的小伙伴也可以进行学习,来提高分析问题的能力~

另外对于Acmer的同学附上 ACM博弈论基本算法入门文章

1、什么是“博弈论”

古语有云,“笑人情似纸,世事如棋”。生活中每个人如同棋手,其每一个行为如同在一张看不见的棋盘 上布子,精明慎重的棋手们相互揣摩、牵制、争赢,下出诸多精彩纷呈、变化多端的棋局。而什么是博 弈论?就是研究棋手们 的“出棋” 过程,从中抽象出可逻辑化的部分,并将其系统化的一门科学,也是运 筹学的一个重要学科。 我们从最简单的一道“囚徒困境”来进行学习~

2、囚徒困境

囚徒困境
一件严重的纵火案发生后,警察在现场抓到两个犯罪嫌疑人。事实上,正是他们一起放火烧了这座 仓库。但是,警方没有掌握足够的证据,只得把他们分开囚禁起来,要求他们坦白交代。

在分开囚禁后,警察对其分别告知:

  • 如果你坦白,而对方不坦白,则将你释放,判对方8年。
  • 如果你不坦白,而对方坦白,则将对方释放,而判你8年。
  • 如果你两都坦白了,则判你两各自4年。

那么两个囚犯应该如何做,是互相背叛还是一起合作?

题目分析: 从表面上看,其实囚犯最应该的就是一起合作,都不坦白,这样因为证据不足,会将两人都进行释放。 但是!因为事实确实是两人放的火,所以他们不得不进行思考,另一人采取了什么样的行为?

犯人甲当然不傻,他根本无法相信同伙不会向警方提供任何信息!因为如果同伙一旦坦白,而自己这边 如果什么都没说的话,就可以潇洒而去。但他同时也意识到,他的同伙也不傻,也会同样来这样设想他。

所以犯人甲只会有一种结论:唯一理性的选择就是背叛同伙,把一切都告诉警方!这样的话,如果他的同伙笨 得只会保持沉默,那么他就会是那个离开的人。而如果他的同伙也根据这个逻辑向警方交代了,那么也 没有关系,起码他不必服最重的刑!

博弈论经典模型解析(入门级)

2.1、 囚徒困境与纳什均衡

这场博弈的过程,显然不是顾及团体利益的最优解决方案。以全体利益而言,如果两个参与者都合作保 持沉默,两人都可以无罪释放,总体利益更高!但根据假设(人性),二人均为理性的个人,且只追求 自己的个人利益。均衡状况会是两个囚徒都选择背叛,这就是“困境”所在!

事实上,这种两人都选择坦白的策略以及因此被判4年的结局被称作“纳什均衡”(也叫非合作均衡),换 言之,在此情况下,无一参与者可以“独自行动”(即单方面改变决定)而增加收获

我们看一下官方释意是多么难懂“所谓纳什均衡,指的是参与人的一种策略组合,在该策略组合上,任何参与人单独改变策略都不会得到好处。”简单点讲,如果在一个策略组合上,当所有其他人都不改变 策略时,没有人会改变自己的策略,则该策略组合就是一个纳什均衡。

3、辛普森悖论

辛普森悖论
羊羊医院里统计了两种胆结石治疗方案的治愈率。在统计过程中,医生将病人分为大胆结石和小胆 结石两组。统计结果如下:

博弈论经典模型解析(入门级)

  • 对于小胆结石而言,手术A的治愈率(93%)高于 手术B(87%)
  • 对于大胆结石而言,手术A的治愈率(73%)高于 手术B(69%)

羊羊医院的医生得出结论:

无论是对于大小胆结石,手术A的治愈率都胜过手术B。

但是真的是这样吗?当然不是,我们根据样本统计出大小胆结石总计的治愈率,发现手术B(治愈率 83%)其实是要高于手术A(治愈率78%)。

博弈论经典模型解析(入门级)

为什么会出现这样的结果?这就是著名的辛普森悖论。

3.1、直觉的缺陷

得到了结论,我们来思考背后的东西。在我们的直觉里有这样一个逻辑:如果一个事物的各部分都分别 大于另一个事物的各部分,那么这个事物大于另一个事物。比如:我们的直觉告诉我们如果手术A在两 组病人中都更好,那么在所有病人中也应该更好。

我们可以将其公式化(该公式错误),假设:

博弈论经典模型解析(入门级)

乍一看,我们觉得该公式没有问题~所以这个公式也就代表了我们大部分人的思维工作。其实在这个公 式中,隐藏掉了一个很重要的条件:A1、A2、An 以及 B1、B2、Bn 并不能简单的通过“加”来得到 A 或者 B。这就是可加性的前提。在大脑的思维过程中,因为我们很难直接看到这个前提,进而就导致了 我们错误的思考!

3.2、辛普森悖论举例

下面我们举一些在生活中常见的辛普森悖论例子:

  • 打麻将的时候,把把都赢小钱,造成赢钱的假象,其实不如别人赢一把大的。
  • 在苹果和安卓的竞争中,你听见身边的人都在逃离苹果,奔向安卓。但是其实苹果的流入率还是要 高于安卓。(有数据证明,很经典的案例)
  • 你男票,这里比别人差,那里比别人差,但是其实他真的比别的男生差吗?(这个纯属本人胡扯 了..)

4、红眼睛和蓝眼睛

红眼睛和蓝眼睛
一个岛上有100个人,其中有5个红眼睛,95个蓝眼睛。这个岛有三个奇怪的宗教规则。
  1. 他们不能照镜子,不能看自己眼睛的颜色。
  2. 他们不能告诉别人对方的眼睛是什么颜色。
  3. 一旦有人知道了自己是红眼睛,他就必须在当天夜里自杀。

某天,有个旅行者到了这个岛上。由于不知道这里的规矩,所以他在和全岛人一起狂欢的时候,不留神 就说了一句话:【你们这里有红眼睛的人。】

问题:假设这个岛上的人每天都可以看到其他所有人,每个人都可以做出缜密的逻辑推理,请问岛上会 发生什么?

4.1、题目分析

题目乍看之下,没有任何逻辑可言!以目测条件,基本无法完成任何正常的推理。但是在仔细推敲之 后,我们可以将问题简化,从假设只有1个红眼睛开始分析。

我们假设岛上只有1个红眼睛的人,还有99个都是蓝眼睛。因为这个旅行者说了“这里有红眼睛的人”, 那么在第一天的时候,这个红眼睛会发现其他的人都是蓝眼睛(与此同时,其他人因为看到了这个红眼 睛的人,所以都确认了自己的安全)那么这天晚上,这个红眼睛的人一定会自杀!

继续分析,假设这个岛上有2个红眼睛,那么当旅行者说“这里有红眼睛的人”之后的第一天,这两个红眼 睛分别发现还有别的红眼睛存在,所以他们当天晚上认为自己是安全的。但是到了第二天,红眼睛惊讶 的发现,另一个红眼睛的人竟然没有自杀(说明岛上有不止一个红眼睛),并且当天他们也没有发现有 别的红眼睛存在(说明另一个红眼睛就是自己)WTF,那肯定另一个红眼睛就是自己了,所以在第二天 夜里,两个红眼睛的人会同时自杀!

继续分析,假如岛上红眼睛有3个。那么在第一天,红眼睛发现了岛上还有另外两个红眼睛,红眼睛呵 呵一笑,“反正不是我”。到了第二天,红眼睛仍然看到了另外两个红眼睛,红眼睛心想,"这下你两该完 蛋了吧",毕竟你两都知道了自己是红眼睛,晚上回去统统自杀吧!(根据上面的推论得出)但是惊奇 的是,到了第三天,红眼睛发现另外两个红眼睛竟然都没有自杀。(说明岛上红眼睛的人不止两个)并 且当天红眼睛也没发现新的红眼睛(说明还有一个红眼睛就是自己)所以在第三天的夜里,三个红眼睛 会同时自杀。

根据上面的推论,假设有N个红眼睛,那么到了第N天,这N个红眼睛就会自杀。所以最终这个岛上红 眼睛的人会统统自杀!这就是答案,生活就是这么朴实无华,且枯燥。

4.2、旅客的挽回

上面的分析大家应该都看懂了。但若是在旅客说完这句话后,其并没有离开这个岛。同时他也看到了周 围人眼里的惊慌和失措,这个时候,旅客为自己的行为感到了懊恼和悔恨!旅客决定对自己的话进行挽回,旅客又该怎么做呢?

这里我提供一种思路,旅客可以在第N次集会上杀掉N个红眼睛,让这N个红眼睛 “GO TO SLEEP”,就 可以中断事件的推理。事实上,基于人道主义,旅客并不需要手动杀人,她只需要在第N天的时候告诉 这N个人,你们是红眼睛,那么这天晚上,这N个人就会自杀。"All RETURN",一切将回归秩序~

5、海盗分金币

海盗分金币
在大海上,有5个海盗抢得100枚金币,他们决定每一个人按顺序依次提出自己的分配方案,如果 提出的方案没有获得半数或半数以上的人的同意,则这个提出方案的人就被扔到海里喂鲨鱼。那么 第一个提出方案的人要怎么做,才能使自己的利益最大化?

海盗们有如下特点:

  1. 足智多谋,总是采取最优策略。
  2. 贪生怕死,尽量保全自己性命。
  3. 贪得无厌,希望自己得到越多宝石越好
  4. 心狠手辣,在自己利益最大的情况下希望越多人死越好。
  5. 疑心多虑,不信任彼此,尽量确保自身利益不寄希望与别人给自己更大利益。

5.1、题目分析

首先我们很容易会觉得,抽签到第一个提方案的海盗会很吃亏!因为只要死的人够多,那么平均每个人 获取的金币就最多,而第一个提方案的人是最容易死的。但是事实是,在满足海盗特点的基础上,第一 个提方案的海盗是最赚的(也就是我们常说的先手优势),我们一起来分析一下。

假如我们设想只有两个海盗。那么不管第一个说什么,只要第二个人不同意,第二个人就可以得到全部 的金币!所以第一个海盗必死无疑,这个大家都能理解。(当然,这样的前提是一号提出方案后不可以 马上自己同意,不然如果自己提出给自己全部金币的方案,然后自己支持,这样就是二号必死无疑)

假如现在我们加入第三个海盗,这时候原来的一号成为了二号,二号成为了三号。这时候现在的二号心 里会清楚,如果他投死了一号,那么自己必死无疑!所以根据贪生怕死的原则,二号肯定会让一号存 活。而此时一号心理也清楚,无论自己提出什么样的方案,二号都会让自己存活,而这时只要加上自己 的一票,就有半数通过,所以一号提出方案:把金币都给我。

现在又继续加入了新的海盗!原来的1,2,3号,成为了现在的2,3,4号。这时候新的一号海盗洞悉了奥 秘,知道了如果自己死了,二号就可以获取全部的金币,所以提出给三号和四号一人一个金币,一起投 死2号。而与此同时,现在的3号和4号获取的要比三个人时多(三个人时自己获取不了任何金币),所 以他们会同意这个方案!

现在加入我们的大Boss,最后一个海盗。根据分析,大Boss海盗1号推知出2号的方案后就可以提出 (97,0,1,2,0)或者(97,0,1,0,2)的方案。这样的分配方案对现在的3号海盗相比现在的2号的分配方案还多了 一枚金币,就会投赞成票,4号或者5号因为得到了2枚金币,相比2号的一枚多,也会支持1号,加上1 号自己的赞成票,方案就会通过,即1号提出(97,0,1,2,0)或(97,0,1,0,2)的分配方案,大Boss成功获得了 97枚金币。

5.2、思考

最终,大Boss一号海盗得到97枚金币,投死了老二和老五,这竟然是我们分析出的最佳方案!这个答 案明显是反直觉的,如果你是老大,你敢这样分金币,必死无疑。可是,推理过程却非常严谨,无懈可 击,那么问题出在哪里呢?

其实,在"海盗分赃"模型中,任何"分配者"想让自己的方案获得通过的关键是,事先考虑清楚"对手"的 分配方案是什么并用最小的代价获取最大收益,拉拢"对手"分配方案中最不得意的人们。1号看 起来最有可能喂鲨鱼,但他牢牢地把握住先发优势,结果不但消除了死亡威胁,还收益最大。而5号, 看起来最安全,没有死亡的威胁,甚至还能坐收渔人之利,却因不得不看别人脸色行事而只能分得一小 杯羹。

不过,模型任意改变一个假设条件,最终结果都不一样。而现实世界远比模型复杂。因为假定所有人都理性,本身就是不理性的。回到“海盗分金”的模型中,只要3号、4号或5号中有一个人偏离了绝对聪明 的假设,海盗1号无论怎么分都可能会被扔到海里去了。所以,1号首先要考虑的就是他的海盗兄弟们的 聪明和理性究竟靠得住靠不住,否则先分者必定倒霉。

如果某人和一号本身不对眼,就想丢他喂鲨鱼。果真如此,1号自以为得意的方案岂不成了自掘坟墓。 再就是俗话所说的“人心隔肚皮”。由于信息不对称,谎言和虚假承诺就大有用武之地,而阴谋也会像杂 草般疯长,并借机获益。如果2号对3、4、5号大放烟幕弹,宣称对于1号所提出任何分配方案,他一定 会再多加上一个金币给他们。这样,结果又当如何?

通常,现实中人人都有自认的公平标准,因而时常会嘟嚷:“谁动了我的奶酪?”可以料想,一旦1号所提 方案和其所想的不符,就会有人大闹。当大家都闹起来的时候,1号能拿着97枚金币毫发无损、镇定自 若地走出去吗?最大的可能就是,海盗们会要求修改规则,然后重新分配。当然,大家也可以讲清楚下 次再得100枚金币时,先由2号海盗来分…然后是3号……

颇有点像美国总统选举,轮流主政。说白了,其 实是民主形式下的分赃制。(仅吐槽)

最可怕的是其他四人形成一个反1号的大联盟并制定出新规则:四人平分金币,将1号扔进大海。这就颇 有点阿Q式的革命理想:高举平均主义的旗帜,将富人扔进死亡深渊。

最后,这里也提供一份代码实现,供有兴趣的同学参考(该代码我大概看了一下,但是因为时间的关 系,没有跑单测进行验证,特此说明!)

以上代码输出:5人时分配方案:[97, 0, 1, 0, 2]

看懂了吗?如果看懂了,这里提出一个问题:假如我们将人性考虑在内,同时也进行理性的分析,如果 你是老大,又该如何提出这个方案呢?大家在留言区留下自己的回答吧

6、结语

好啦,这篇内容就到这里了,你学会了吗?另外经典博弈论还有很多模型,如:以牙还牙手表定律枪手博弈 之类的。这里就先不展开论述了,有兴趣的话可以自行Google。

7、参考

【博弈论】关于三姬分金(五海盗分赃)的博弈论问题分析

李永乐老师对三姬分金视频讲解


喜欢 (0)