一道小智力题:五个聪明的海盗(附英文版)

2009年4月6日 由 Key4ever 留言 »

有五个海盗A、B、C、D、E要分赃100块金币,从A开始依次可以提出分配方案,
每个海盗(包括提方案的海盗自身)可以对分配方案投赞成或反对票,如果某个海盗
提出的方案未能获得半数以上的赞成票,则该海盗会被杀掉。一但某个海盗提出的方案
获得半数以上的赞成票,即按该方案进行分配 。

假定每个海盗都会作出理性的决策,那么分到最多金币的会是哪个海盗,他会
分到多少块金币?

解决问题的关键是先把问题的规模缩小,假定只有两个海盗分配金币的话会出现什么样的
情形?只有三个海盗呢?依次类推到题目中给出的五个海盗的场景。

只有两个海盗D、E的话,不管D提出什么方案,E都会反对,这样D就会被杀掉,E可以获得100块金币。

所以当只有C、D、E的时候,D的最优期望是活命,所以无论C怎样提议,都会接收C的方案,这样自己就可以活 命。最优情况下C可以获得100块金币,
D、E一块也不能获得。

当只有B、C、D、E的时候,C的最优期望是100块金币,而D和E的最优期望是>=1块金币。所以B只要争取
确保能争取到D和E的支持就行。所以最终B的分配方案会是B得98块,C得0块,D、E各得一块。

当A、B、C、D、E一起来分配的时候,B的最优期望是98块金币,C的最优期望是>=1块,D、E的最优期望是
>1块。A只要能够争取到两个其他海盗的赞同票即可,所以,A的分配方案会是A得97块,B得0块,C得1

块,D或E中的一个人得两块,另一个人得0块。这也是最终的分配方案 。>>>>

题目的答案就是A会获得最多数量的97块金币。

出自yangjun的blog

英文版在wiki里的Pirate game词条下,即属于博弈论。题目跟中文的有点不同,但解决方法一样。

The Game

There are five rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.

The Pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.

The Pirate world’s rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates should then vote on whether to accept this distribution; the proposer is able to vote, and has the casting vote in the event of a tie. If the proposed allocation is approved by vote, it happens. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.

Pirates base their decisions on three factors. First of all, each pirate wants to survive. Secondly, each pirate wants to maximize the amount of gold coins he receives. Thirdly, each pirate would prefer to throw another overboard, if all other results would otherwise be equal.[1]

The Result

It might be expected intuitively that Pirate A will have to allocate little if any to himself for fear of being voted off so that there are fewer pirates to share between. However, this is as far from the theoretical result as is possible.

This is apparent if we work backwards: if all except D and E have been thrown overboard, D proposes 100 for himself and 0 for E. He has the casting vote, and so this is the allocation.

If there are three left (C, D and E) C knows that D will offer E 0 in the next round; therefore, C has to offer E 1 coin in this round to make E vote with him, and get his allocation through. Therefore, when only three are left the allocation is C:99, D:0, E:1.

If B, C, D and E remain, B knows this when he makes his decision. To avoid being thrown overboard, he can simply offer 1 to D. Because he has the casting vote, the support only by D is sufficient. Thus he proposes B:99, C:0, D:1, E:0. One might consider proposing B:99, C:0, D:0, E:1, as E knows he won’t get more, if any, if he throws B overboard. But, as each pirate is eager to throw each other overboard, E would prefer to kill B, to get the same amount of gold from C.

Assuming A knows all these things, he can count on C and E’s support for the following allocation, which is the final solution:
A: 98 coins
B: 0 coins
C: 1 coin
D: 0 coins
E: 1 coin[1]

Also, A:98, B:0, C:0, D:1, E:1 or other variants are not good enough, as D would rather throw A overboard to get the same amount of gold from B.

相关日志

广告位

发表评论

使用新浪微博登陆