5海盗分宝石问题

-

-

- . word.zl- 5海盗分宝石问题

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

他们决定这么分：

1。抽签决定自己的〔1，2，3，4，5〕

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

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

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

条件：

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

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

-

-

- . word.zl- 标准答案：

1号海盗分给3号1颗宝石，4号或5号海盗2颗，独得97颗。分配方案为：97，0，1，2，0 或 97，0，1，0，2。

推理过程：从后向前推，如果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号能够获取最大收益的方案了。

在"海盗分赃"模型中，任何"分配者"想让自己的方案获得通过的关-

-

- . word.zl- 键是，事先考虑清楚"挑战者"的分配方案是什么，并用最小的代价获取最大收益，拉拢"挑战者"分配方案中最不得意的人们。1号看起来最有可能喂鲨鱼，但他牢牢地把握住先发优势，结果不但消除了死亡威胁，还收益最大。而5号，看起来最平安，没有死亡的威胁，甚至还能坐收渔人之利，却因不得不看别人脸色行事而只能分得一小杯羹。

海盗博弈论

Charlesgao 发表于 2011-06-09 17:39

海盗分金是一个非常古老的问题，在1999年?科学美国人?正式把它发表之前，已经至少流行10年了，相信很多人都有所耳闻，也知道解法。此前死理性派也对这个问题也有所 涉及 。今天我们就来回忆一下这个有意思的问题，并且在把问题推广到大规模海盗团伙后，会得出一些非常有意思的结论。

分金的规那么 -

-

- . word.zl- 有五个非常聪明的海盗，他们都是死理性派，编号分别是P1、P2、P3、P4、P5。他们一同抢夺了100个金币，现在需要想方法分配这些金币。

海盗们有严格的等级制度：P1

海盗们的分配原那么是：等级最高的海盗提出一种分配方案。然后所有的海盗投票决定是否承受分配，包括提议人。并且在票数一样的情况下，提议人有决定权。如果提议通过，那么海盗们按照提议分配金币。如果没有通过，那么提议人将被扔出船外，由下一个最高等级的海盗再提出新的分配方案。

海盗们基于三个因素来做决定。首先，要能留在船上存活下来。其次，要使自己的利益最大化(即得到最多的金币)。最后，在所有其他条件一样的情况下，优先选择把别人扔出船外〔这是因为每个海盗都想夺占这条船的控制权〕。

海盗的逻辑

现在，假设你是等级最高的P5，你会做何选择？直觉上，为了保住自己的生命，你可能会选择留给自己很少的金币，以便让大家同意自己的决策。然而，结果和此大相径庭。

解决这个问题的关键在于换个思维方向。与其苦思冥想你要做什么决策，不如先想想最后剩下的人会做什么决策。假设-

-

- . word.zl- 现在只剩下P1和P2了，P2会做什么决策？很明显，他将把100金币留给自己，然后投自己一票。由于在票数一样的情况下提议人有决定权，无论P1同不同意，P2都能毫无危险地将所有金币收入囊中。

现在再把P3考虑进来。P1知道，如果P3被扔下海，那么游戏就会出现上述的情况，自己终将一无所获。由于他们都很聪明，P3同样能看到这一点，所以他知道，只要给P1一点点利益，P1就会投票支持他的决策。所以P3最终的决策应该是：( P3,P2,P1 ) → ( 99,0,1 )

P4的策略也类似：由于他需要50%的支持率，所以他只需贿赂1个金币给P2就可以了。P2一定会支持他(否那么轮到P3做决策，他就一无所获啦)。所以P4最终的决策是：( P4,P3,P2,P1 ) → ( 99,0,1,0 )

P5的情况稍有不同：由于这次一共有5个人，他至少需要贿赂两个海盗才能使自己的决议通过。所以决策就是：( P5,P4,P3,P2,P1 ) → ( 98,0,1,0,1 )

这个结果是不是很出乎意料？你不但可以保全自己，还能得到绝大局部的利益！其实这里面蕴含着递归的思想，它是解决许多问题(如汉诺塔问题，全排列问题，整数划分问题等)-

-

- . word.zl- 的有利手段。好了，看到这里，想必你一定在感慨：哎，还是做上司(等级高)好啊！且慢！问题还没有完毕。

如果有更多的海盗

真实情况下海盗的数目肯定不止5个。继续按照这个逻辑推理，P6的决策将是：( P6,P5,P4,P3,P2,P1 ) → ( 98,0,1,0,1,0 )

一直到P200，它会给自己留1个金币，同时给剩下所有偶数编号的海盗1个金币。

如果海盗数是201个，那么P201该怎么做呢？他好似没有足够的钱去贿赂别的海盗了。不过，为了保住自己的性命，他可以把自己手中的金币全分出去，即给每个奇数编号的海盗(P1~P199)一个金币。这样虽然空手而归，但不至于人财两空。 -

-

- . word.zl- 如果海盗数是202个，P202也只能把这100个金币全部贿赂给其他100个海盗，而这100个海盗必须是在P201做决策时什么也得不到的海盗。由于符合这样条件的海盗有101个(所有偶数编号的海盗+P201)，P202的决策不再是唯一的！有101种方案供他选择。

可怜的是P203，由于人数众多，他实在没有足够的钱去贿赂其他海盗以获得足够的支持(他至少还需要获得101个人的支持，但只有100个金币)。所以，不管P203做什么决策，他都难逃被扔出船外的厄运了。不过P203并没有我们想象中的那么悲剧，除非船上正好有且只有203个海盗。不妨再来看增加一个海盗P204的情况。P204明白，P203现在的唯一愿望就是活下来…不管他做什么决策，P203都会举双手支持他(当然举多少手都只能算一票)。所以P204可以靠他自己的一票，P203的一票和贿赂另外100个海盗获得正好50%的支持。

P204可能的决策也只有101种，如下表：(可能获得1金币的海盗用'Y'标示)

P P1 P2 P3 P4 … P199 P200 P201 P202 P203 P204

P204 Y N Y N Y N N Y N N

P205就没有那么幸运了。他不能无偿的得到P203和P204的支持。所以如果轮到P205做决策，他也必定被扔到船外。P206也一样，尽管他能得到P205的免费支持，但是这还不够。P207-

-

- . word.zl- 需要得到至少104个海盗的支持，所以有了P205,P206的无偿支持还是不够。

P208就比拟幸运了，他需要得到104个海盗的支持，

P205,P206,P207为了保命会无偿支持他，加上他自己，再贿赂100个海盗，正好104票。

P208可能的决策：

P P1 P2 P3 P4 … P200 P201 P202 P203 P204 P205 P206 P207