海盗分金问题总结 下载本文

海盗分金

题目:

5名海盗抢得了窖藏的100块金子,并打算瓜分这些战利品。这是一些讲民主的海盗(当然是他们自己特有的民主),他们的习惯 是按下面的方式进行分配:最厉害的一名海盗提出分配方案,然后所有的海盗(包括提出方案者本人)就此方案进行表决。如果50%或更多的海盗赞同此方案,此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里,然后下一名最厉害的海盗又重复上述过程。所有的海盗都乐于看到他们的一位同伙被扔进海里,不过,如果让他们选择的话,他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的,而且知道其他的海盗也是有理性的。此外,没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次,并且每个人都清楚自己和其他所有人的等级。这些金块不能再分,也不允许几名海盗共有金块,因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。

最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢?

一、经济学上的“海盗分金”模型

经济学上有个“海盗分金”模型,是说5个海盗抢得100枚金币,他们按抽签的顺序依次提方案:首先由1号提出分配方案,然后5人表决,超过半数同意方案才被通过,否则他将被扔入大海喂鲨鱼,依此类推。

假定“每人海盗都是绝顶聪明且很理智”,那么“第一个海盗提出怎样的分配方案才能够使自己的收益最大化?”

推理过程是这样的:

从后向前推,如果1至3号强盗都喂了鲨鱼,只剩4号和5号的话,5号一定投反对票让4号喂鲨鱼,以独吞全部金币。所以,4号惟有支持3号才能保命。

3号知道这一点,就会提出“100,0,0”的分配方案,对4号、5号一毛不拔而将全部金币归为已有,因为他知道4号一无所获但还是会投赞成票,再加上自己一票,他的方案即可通过。

不过,2号推知3号的方案,就会提出“98,0,1,1”的方案,即放弃3号,而给予4号和5号各一枚金币。由于该方案对于4号和5号来说比在3号分配时更为有利,他们将支持他而不希望他出局而由3号来分配。这样,2号将拿走98枚金币。

同样,2号的方案也会被1号所洞悉,1号并将提出(97,0,1,2,0)或(97,0,1,0,2)的方案,即放弃2号,而给3号一枚金币,同时给4号(或5号)2枚金币。由于1号的这一方案对于3号和4号(或5号)来说,相比2号分配时更优,他们将投1号的赞成票,再加上1号自己的票,1号的方案可获通过,97枚金币可轻松落入囊中。这无疑是1号能够获取最大收益的方案了!答案是:1号强盗分给3号1枚金币,分给4号或5号强盗2枚,自己独得97枚。分配方案可写成(97,0,1,2,0)或(97,0,1,0,2)。

“海盗分金”其实是一个高度简化和抽象的模型,体现了博弈的思想。在“海盗分金”模型中,

任何“分配者”想让自己的方案获得通过的关键是事先考虑清楚“挑战者”的分配方案是什么,并用最小的代价获取最大收益,拉拢“挑战者”分配方案中最不得意的人们。企业中的一把手,在搞内部人控制时,经常是抛开二号人物,而与会计和出纳们打得火热,就是因为公司里的小人物好收买。

1号看起来最有可能喂鲨鱼,但他牢牢地把握住先发优势,结果不但消除了死亡威胁,还收益最大。这不正是全球化过程中先进国家的先发优势吗?而5号,看起来最安全,没有死亡的威胁,甚至还能坐收渔人之利,却因不得不看别人脸色行事而只能分得一小杯羹。

不过,模型任意改变一个假设条件,最终结果都不一样。而现实世界远比模型复杂。

首先,现实中肯定不会是人人都“绝对理性”。回到“海盗分金”的模型中,只要3号、4号或5号中有一个人偏离了绝对聪明的假设,海盗1号无论怎么分都可能会被扔到海里去了。所以,1号首先要考虑的就是他的海盗兄弟们的聪明和理性究竟靠得住靠不住,否则先分者倒霉。

如果某人偏好看同伙被扔进海里喂鲨鱼。果真如此,1号自以为得意的方案岂不成了自掘坟墓!

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

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

而假如由一次博弈变成重复博弈呢?比如,大家讲清楚下次再得100枚金币时,先由2号海盗来分……然后是3号……这颇有点像美国总统选举,轮流主政。说白了,其实是民主形式下的分赃制。

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

制度规范行为,理性战胜愚昧!

如果假设变为,是10人分100枚金币,投票50%或以上才能通过,否则他将被扔入大海喂鲨鱼,依此类推。50%是问题的关键,海盗可以投自己的票。因此如果剩下两个人,无论什么方案都会被通过,即100,0。

往上推一步,3个人时,倒数第三个人知道如果出现两个人的情况,因此它会团结第一个人,给他一个金币

“往前推一步。现在加一个更凶猛的海盗P3。P1知道———P3知道他知道———如果P3

的方案被否决了,游戏就会只由P1和P2来继续,而P1就一枚金币也得不到。所以P3知道,只要给P1一枚金币,P1就会同意他的方案(当然,如果不给P1一枚金币,P1反正什么也得不到,宁可投票让P3去喂鱼)。所以P3的最佳策略是:P1得1枚,P2什么也得不到,P3得99枚。

P4的情况差不多。他只要得两票就可以了,给P2一枚金币就可以让他投票赞同这个方案,因为在接下来P3的方案中P2什么也得不到。P5也是相同的推理方法只不过他要说服他的两个同伴,于是他给每一个在P4方案中什么也得不到的P1和P3一枚金币,自己留下98枚。

依此类推,最终P10的最佳方案是:他自己得96枚,给每一个在P9方案中什么也得不到的P2、P4、P6和P8一枚金币。

结果,“海盗分金”最后的结果是P1、P2、P3、P4、P5、P6、P7、P8、P9、P10各可以获得0、1、0、1、0、1、0、1、0、96枚金币。

在“海盗分金”中,任何“分配者”想让自己的方案获得通过的关键是,事先考虑清楚“挑战者”的分配方案是什么,并用最小的代价获取最大收益,拉拢“挑战者”分配方案中最不得意的人们。

真地是难以置信。P10看起来最有可能喂鲨鱼,但他牢牢地把握住先发优势,结果不但消除了死亡威胁,还获得了最大收益。而P1,看起来最安全,没有死亡的威胁,甚至还能坐收渔人之利,但却因不得不看别人脸色行事,结果连一小杯羹都无法分到,却只能够保住性命而已。

二、最一般性、可随意更改数据的解释。 1、问题的提出:

5个海盗抢到了100颗宝石,每一颗都一样的大小和价值连城。

他们决定这么分:

1。抽签决定自己的号码(1,2,3,4,5)

2。首先,由1号提出分配方案,然后大家5人进行表决,当且仅当半数和超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。

3。如果1号死后,再由2号提出分配方案,然后大家4人进行表决,当且仅当半数和超过半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。

4。以次类推......

条件:

每个海盗都是很聪明的人,都能很理智的判断得失,从而做出选择。

问题:

第一个海盗提出怎样的分配方案才能够使自己的收益最大化

(如果在规则中加上下面一条会更加完善:海盗在自己的收益最大化的前提下乐意看到其他海盗被扔入大海喂鲨鱼)

2、讨论如下:

使用倒推法:

一、假设1、2、3号已被扔入海中,则4号的方案必为100、0,且必定通过。故5号在得到3号1个宝石的情况下会坚决支持3号的方案。

二、3号的方案必为99、0、1,且必定通过。故4号在得到2号1个宝石的情况下会坚决支持2号的方案。

三、2号的方案必为99、0、1、0,且必定通过。2号不能把给4号的1个宝石给5号,5号未必坚定地支持2号的方案,因为3号必定通过的方案也能让他得到1个宝石。为了万无一失的保命,2号必须选4号,且必定通过。故3号、5号在各得到1号1个宝石的情况下会坚决支持1号的方案。

四、1号的方案必为98、0、1、0、1,且必定通过。

故答案是:98,0,1,0,1。

3、本题可推广如下:

有X(1=

则1号海盗的最大化收益 Y =101-((X+1)/2所得数取整)。

(当X=201及X=202时,1号海盗的最大化收益为0,但可保命。)

Z(2=

对于X>202时情况,可先在X=500个的情况下进行讨论,然后再作推广。

依然是使用倒推法。

203号海盗必须获得102张赞成票,但他无法用100个宝石收买到101名同伙的支持。因此,无论203号提出什么样的分配方案,他都注定会被扔到海里去喂鱼。

204号海盗必须获得102张赞成票,203号为了能保住性命,就必须让204号的方案通过,避免由203号自己来提出分配方案,所以无论204号海盗提出什么样的方案,都可以得到203号的坚定支持。这样204号海盗就可以保命:他可以得到他自己的1票、203号的1票、以及用100个宝石收买到的100名同伙的赞成票,刚好达到所需的半数支持。能从204号那里获得1个

宝石的海盗,必属于按照202号海盗的方案将一无所获的那102名海盗之列。

205号海盗必须获得103张赞成票,但他无法用100个宝石收买到102名同伙的支持。因此,无论205提出什么样的分配方案,他都注定会被扔到海里去喂鱼。

206号海盗必须获得103张赞成票,他可以得到205号的坚定支持,但他无法用100个宝石收买到101名同伙的支持。因此,无论206号提出什么样的分配方案,他都注定会被扔到海里去喂鱼。

207号海盗必须获得104张赞成票,他可以得到205号和206号的坚定支持,但他无法用100个宝石收买到101名同伙的支持。因此,无论207号提出什么样的分配方案,他都注定会被扔到海里去喂鱼。

208号海盗必须获得104张赞成票,他可以得到205号、206号、207号的坚定支持,加上他自己1票以及收买的100票,使他得以保命。从208号那里获得1个宝石的海盗,必属于那些按照204号方案将一无所获的那104名海盗之列。

现在可以看出一条新的、此后将一直有效的规律:那些方案能通过的海盗(他们的分配方案全都是把宝石用来收买100名同伙,自己连1个宝石都得不到)相隔的距离越来越远,而在他们之间的海盗则无论提出什么样的方案都会被扔进海里。因此,为了保命,他们必会投票支持排在他们前面的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、204、208、216、232、264、328、456号,

即200+1、200+2、200+4、200+8、200+16、200+32、200+64、200+128、200+256。即

200+2的0次幂,200+2的1次幂,200+2的2次幂,200+2的3次幂,200+2的4次幂,200+2的5次幂,200+2的6次幂,200+2的7次幂,200+2的8次幂,

即其号码等于200加2的某次幂。

4、对本题作更一般的推广,如下:

有X个海盗,A 颗宝石,其它规则同上。

当X=<2A+2时,

则1号海盗的最大化收益 Y=A+1-((X+1)/2所得数取整)。

(当X=2A+1及X=2A+2时,1号海盗的最大化收益为0,但可保命。)

Z号(2=

当X>2A+2时,

若X=2A+2的B次幂,则1号海盗可保命,但无收益。其他海盗的收益情况由前面讨论可知有规律,但海盗的编号不固定,对它们的表述省略。

若X不等于2A+2的某次幂,设B=b是能使(X>2A+2的B次幂)成立的最大B,则(X+1-(2A+2的b次幂))号海盗可保命,但无收益。之前的海盗都会被扔到海里去喂鱼。之后的海盗的收益情况由前面讨论可知有规律,但海盗的编号不固定,对它们的表述省略。

5、其它

著名数学家和经济学家,加利福尼亚州 帕洛阿尔托 的 Stephen M. Omohundro 在1998年对此类问题进行了解答。

本题是该类问题的一个具体题目:

微软经典面试题------海盗分宝石,20分钟给出答案即可获得年薪8万美金的职位:

5个海盗抢到了100颗宝石,即 X=5,A=100。

此类问题体现出的多方博弈情况下的生存哲学:

1、没有永恒的朋友,只有永恒的利益。

2、在临界点之下,以决策者的身份出场,冒最大的风险,得到最大的利益。

3、在接近临界点的地方,是收益分配最接近公平的地方。半数的人均匀地受益,另半数的人均匀地不受益。

4、越过临界点之后,以决策者的身份出场,风险极大,甚至会将老本赔进去,而收益却为零,这是最糟的情况,因为大家的收益都不高。这是一种不稳定的状态,系统会通过自我调整向临界点靠拢。

5、永远都不可能发生所有人都有收益的情况,任何时候都有至少 一半或者接近一半 人无收益,除非只有1个人。

另外,如果逻辑推理没有漏洞,那么结论就必定站得住脚,即使它与你的直觉矛盾。