黑蓝论坛

标题: 添火：强盗分金[转帖] [打印本页]

作者: batz 时间: 2007-8-4 13:04
标题: 添火：强盗分金[转帖]
（编者注：作者因时间久远，无从考证）

　　数学逻辑有时会导致十分怪异的结论，这道难题已经流传了至少十年，恰好就属于这一类。一般的规则是，如果逻辑推理没有漏洞，那么结论就必定站得住脚，即使它与你的直觉矛盾。

　　先来看看此难题原先的形状。10名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下一提名最厉害的海盗又重复上述过程。
　　所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的，而且知道其他的海盗也是有理性的。此外，没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次，并且每个人都清楚自己和其他所有人的等级。这些金块不能再分，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。
　　最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢？
　　为方便起见，我们按照这些海盗的怯懦程度来给他们编号。最怯懦的海盗为1号海盗，次怯懦的海盗为2号海盗，如此类推。这样最厉害的海盗就应当得到最大的编号，而方案的提出就将倒过来从上至下地进行。
　　分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时，你容易知道何种决策有利而何种决策不利。确定了这一点后，你就可以把它用到倒数第2次决策上，如此类推。如果从游戏的开头出发进行分析，那是走不了多远的。其原因在于，所有的战略决策都是要确定：“如果我这样做，那么下一个人会怎样做？”因此在你以下海盗所做的决定对你来说是重要的，而在你之前的海盗所做的决定并不重要，因为你反正对这些决定也无能为力了。
　　记住了这一点，就可以知道我们的出发点应当是游戏进行到只剩两名海盗——即1号和2号——的时候。这时最厉害的海盗是2号，而他的最佳分配方案是一目了然的：100块金子全归他一人所有，1号海盗什么也得不到。由于他自己肯定为这个方案投赞成票，这样就占了总数的50%，因此方案获得通过。
　　现在加上3号海盗。1号海盗知道，如果3号的方案被否决，那么最后将只剩2个海盗，而1号将肯定一无所获——此外，3号也明白1号了解这一形势。因此，只要3号的分配方案给1号一点甜头使他不至于空手而归，那么不论3号提出什么样的分配方案，1号都将投赞成票。因此3号需要分出尽可能少的一点金子来贿赂1号海盗，这样就有了下面的分配方案：3号海盗分得99块金子，2号海盗一无所获，1号海盗得1块金子。
　　4号海盗的策略也差不多。他需要有50%的支持票，因此同3号一样也需再找一人做同党。他可以给同党的最低贿赂是1块金子，而他可以用这块金子来收买2号海盗。因为如果4号被否决而3号得以通过，则2号将一文不名。因此，4号的分配方案应是：99块金子归自己，3号一块也得不到，2号得1块金子，1号也是一块也得不到。

　　5号海盗的策略稍有不同。他需要收买另两名海盗，因此至少得用2块金子来贿赂，才能使自己的方案得到采纳。他的分配方案应该是：98块金子归自己，1块金子给3号，1块金子给1号。
　　这一分析过程可以照着上述思路继续进行下去。每个分配方案都是唯一确定的，它可以使提出该方案的海盗获得尽可能多的金子，同时又保证该方案肯定能通过。照这一模式进行下去，10号海盗提出的方案将是96块金子归他所有，其他编号为偶数的海盗各得1块金子，而编号为奇数的海盗则什么也得不到。这就解决了10名海盗的分配难题。

　　Omohundro的贡献是他把这一问题扩大到有500名海盗的情形，即500名海盗瓜分100块金子。显然，类似的规律依然成立——至少是在一定范围内成立。事实上，前面所述的规律直到第200号海盗都成立。200号海盗的方案将是：从1到199号的所有奇数号的海盗都将一无所获，而从2到198号的所有偶数号海盗将各得1块金子，剩下的1块金子归200号海盗自己所有。
　　乍看起来，这一论证方法到200号之后将不再适用了，因为201号拿不出更多的金子来收买其他海盗。但是即使分不到金子，201号至少还希望自己不会被扔进海里，因此他可以这样分配：给1到199号的所有奇数号海盗每人1块金子，自己一块也不要。
　　202号海盗同样别无选择，只能一块金子都不要了——他必须把这100块金子全部用来收买100名海盗，而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样的海盗有101名，因此202号的方案将不再是唯一的——贿赂方案有101种。
　　203号海盗必须获得102张赞成票，但他显然没有足够的金子去收买101名同伙。因此，无论提出什么样的分配方案，他都注定会被扔到海里去喂鱼。不过，尽管203号命中注定死路一条，但并不是说他在游戏进程中不起任何作用。相反，204号现在知道，203号为了能保住性命，就必须避免由他自己来提出分配方案这么一种局面，所以无论204号海盗提出什么样的方案，203号都一定会投赞成票。这样204号海盗总算侥幸拣到一条命：他可以得到他自己的1票、203号的1票、以及另外100名收买的海盗的赞成票，刚好达到保命所需的50%。获得金子的海盗，必属于根据202号方案肯定将一无所获的那101名海盗之列。
　　205号海盗的命运又如何呢？他可没有这样走运了。他不能指望203号和204号支持他的方案，因为如果他们投票反对205号方案，就可以幸灾乐祸地看到205号被扔到海里去喂鱼，而他们自己的性命却仍然能够保全。这样，无论205号海盗提出什么方案都必死无疑。206号海盗也是如此——他肯定可以得到205号的支持，但这不足以救他一命。类似地，207号海盗需要104张赞成票——除了他收买的100张赞成票以及他自己的1张赞成票之外，他还需3张赞成票才能免于一死。他可以获得205号和206号的支持，但还差一张票却是无论如何也弄不到了，因此207号海盗的命运也是下海喂鱼。
　　208号又时来运转了。他需要104张赞成票，而205、206、207号都会支持他，加上他自己一票及收买的100票，他得以过关保命。获得他贿赂的必属于那些根据204号方案肯定将一无所获的人（候选人包括2到200号中所有偶数号的海盗、以及201、203、204号）。
　　现在可以看出一条新的、此后将一直有效的规律：那些方案能过关的海盗（他们的分配方案全都是把金子用来收买100名同伙而自己一点都得不到）相隔的距离越来越远，而在他们之间的海盗则无论提什么样的方案都会被扔进海里——因此为了保命，他们必会投票支持比他们厉害的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、204、208、216、232、264、328、456号，即其号码等于200加2的某一方幂的海盗。
　　现在我们来看看哪些海盗是获得贿赂的幸运儿。分配贿赂的方法是不唯一的，其中一种方法是让201号海盗把贿赂分给1到199号的所有奇数编号的海盗，让202号分给2到200号的所有偶数编号的海盗，然后是让204号贿赂奇数编号的海盗，208号贿赂偶数编号的海盗，如此类推，也就是轮流贿赂奇数编号和偶数编号的海盗。

　　结论是：当500名海盗运用最优策略来瓜分金子时，头44名海盗必死无疑，而456号海盗则给从1到199号中所有奇数编号的海盗每人分1块金子，问题就解决了。由于这些海盗所实行的那种民主制度，他们的事情就搞成了最厉害的一批海盗多半都是下海喂鱼，不过有时他们也会觉得自己很幸运——虽然分不到抢来的金子，但总可以免于一死。只有最怯懦的200名海盗有可能分得一份赃物，而他们之中又只有一半的人能真正得到一块金子，的确是怯懦者继承财富。

作者: 赵松 时间: 2007-8-4 13:04
有意思。

作者: 恐怖爱丽丝 时间: 2007-8-4 13:04
赵松，你怎么竟然可以和我一样游手好闲逛来逛去！

作者: Zen 时间: 2007-8-4 13:04
这是典型的不完全信息动态博弈，所求的均衡解是精炼贝叶斯纳什平衡。

作者: batz 时间: 2007-8-4 13:04
我怎么记得Zen以前研究佛教呢
到底是谁给我这个印象

作者: WQJ 时间: 2007-8-4 13:04
是不是青青草里的阿特烦给你这个印象的？

作者: WQJ 时间: 2007-8-4 13:04
你这个课题太复杂了，不适合闲聊玩儿。SIEG以前在青青草贴过一个相同的智力游戏，我转过来玩玩。（注：SIEG也就是这里的七格；奶奶的改穿唐装了！）

原文：http://www.grass-land.com/cgi-bin/BBS.exe?id=BBS_Grass&msg=30332

强盗分钻石及我的解法，大家来看看吧:-)
Sieg

　　5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。
　　他们决定这么分：
　　1。抽签决定自己的号码（1，2，3，4，5）
　　2。首先，由1号提出分配方案，然后大家5人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
　　3。如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
　　4。以次类推。。。。。。
　　
　　条件：
　　每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。
　　
　　问题：
　　第一个海盗提出怎样的分配方案才能够使自己的收益最大化？

------------------------------------
我的想法是：每个人都得拿尽可能多的钻石，但每个人都必须同时让其它超过半数的人也能拿到尽可能多的钻石，很有当年苏格兰那些休谟、斯密、柏克的风度吧。：）

先看
(1)：100,0,0,0,0
这肯定不行。

再看
(2)：50,50,0,0,0
也不行，因为没超过半数。

再看
(3)：34,33,33,0,0。
这样，加上提议者，一共有三个人（超过半数）是可以得到平均数的。由于强盗都是理性的，所以拿到33颗的另两个强盗如果不要这个提议，那么接下来的第二个强盗提的方案里，可以平均分配的也是34、33、33、0,因为如果不是这样，而是50、50、0、0或40、40、20、0等等这类只有两人最大获益的分配方案的话，方案是不可能被超半数通过的，而20、40、40、0这样的方案虽然可以超半数通过，但这样提议者自己是拿得更少的（少于34）。
再看第三个强盗，如果他反对，那么第一个强盗就被扔下水，现在就只有四个人，根据上面推论，我们知道，那接下来第二个强盗的提议也会是按34,33,33,0分配，如果他再反对，那他就可以提出50、50、0方案。这虽然比原来的33要好得多，而且，第四个强盗肯定会同意，因为如果第四个不同意，那么，无论第四个强盗提出什么方案，剩下的第五个，两个人唯一一个控制是否超过半数的强盗，肯定会选择不同意，这样，第五个就能拿到100颗钻石。
当然，第三个强盗不会提50、0、0方案的，他其实会提出100、0、0这样的极端方案，因为第四个强盗是不得不同意的，因为如果他反对，那么，接下来的一轮，根据上段分析，他将连命都保不住。当然，第四个强盗也能反对100、0、0方案，前提是他自己提的方案得是0、100，但这对他个人来说是没什么利益增长的。
如果第二个强盗预见到第三个将会得到100颗钻石，他将选择34、0、33、33，但这没必要继续讨论是否合理，因为它并没有使第二个强盗多拿1颗钻石。
由于第(3)种方案对第三个强盗有比33更好的利益分配前景，所以举手时肯定不会超过半数，所以也不行。

接着看
(4)：25、25、25、25、0
如果第三个强盗和第四个强盗同时选择不同意，那么，根据上面的分析，接下来的第二个强盗也会被淘汰掉，然后就是第三个强盗可以拿到100颗钻石的结果，而第四个将一颗拿不到，这显然是重蹈覆辙，所以，第四个强盗不会跟着反对。
第五个强盗肯定反对，但这样加上第三个，也没有超过半数。

最后看
(5)：20、20、20、20、20
显然第一个强盗不会做这个选择，在第(4)个方案成立的前提下。

这道题目表明，自由主义中边沁式的那种追求最大多数人最大利益的原则，实际上蕴涵了规则所带来的某些不公平，斯密的那只看不见的手，完全且必然导致了第五个强盗成为无产阶级。所以，自由放任的经济主义必须被重商主义在某种程度上加以修正，而修正的方法可以是加入某些补充规则：比如：如果某项方案通过，那么，因此方案通过而受损的社会成员，可以得到相应的福利补偿。

大家以为如何？

作者: Zen 时间: 2007-8-4 13:04
老挖，你终于浮出水面啦

。哦，各位看官，老挖就是WQJ，丫现在换西装了

))
batz，我现在还在琢磨佛学呢，看我的签名，是慧能的偈耶~
我的心得是，佛学越琢磨，说的就越少，当初跟阿特烦绕，是因为我觉得他落入了野狐禅。禅的专业性很强，不是隔靴皮毛所能承载的。藏传佛教的Maha Mudra就是禅，但只对已经有理论修为的僧人传授。

我本来也想弄套唐装，取了个“持阿那”，可穿上一看，觉得象阿三的纱笼，就不大敢拿出来现。我最近又寻么了一个：檀那，是不是有点脂粉气？要是还有天竺味，我干脆就叫“强巴”算了，好歹是个藏名。

作者: batz 时间: 2007-8-4 13:05
老挖就是WQJ？
够深的

//偶也有一藏名：藏獒

作者: 文沁可人 时间: 2007-8-4 13:05
楼上你愿意做狗？

作者: WQJ 时间: 2007-8-4 13:05
batz，红发杰克、纤纤……等都是你吧？老朋友了呵呵！

作者: 凌丁 时间: 2007-8-4 13:05
提示: 作者被禁止或删除内容自动屏蔽

作者: 王老虎 时间: 2007-8-4 13:08
七格的解法真的让1号强盗获得最大收益了吗？

使用逆思表:

            1          2       3          4          5

第一步:                                        0       100

第二步:                         99       1          0

第三步:             0       99       1          0

第四步: 97          1       0          2          0

第一步：如果只剩4和5的话，4的分法必定是：0，100。要不然4就挂定了。第二步如果只剩下3，4，5的话，那他的分法必定是：99，1，0，因为他考虑到4在能保命和获利的条件下一定会支持他。第三步如果只剩下2，3，4，5的话，那他的分法必定是：0，99，1，0。因为这样他才能保命。第四步1，2，3，4，5。那1的分法就应该是：97，1，0，2，0。因为使2和4的获利上升，所以必受他们的支持。

需注意两点：

一是：2和4都是最可能被挂掉的人物，所以只要能让他们保命就行了。
二是：3和5是最想别人挂掉的人物。所以要么就给他们满意的钻石，要么就一点不给。

作者: 王老虎 时间: 2007-8-4 13:08
2，3，4都有可能被扔进海里去，因此事实上他们在最开始就必定选择无条件地同意1的任何提议（他们是理性的，知道生命是最大利益，不可能拿最大利益冒险）。而5则可以完全不予考虑，1获得2，3，4的支持，已过大半。

因此，1的分配方法是：100，0，0，0，0。

[此贴子已经被作者于2004-5-29 21:30:50编辑过]

作者: 七格 时间: 2007-8-4 13:09
老挖干嘛把我一个错误的答案搬过来啊，那里明明有我回答正确的答案的！！！

作者: 七格 时间: 2007-8-4 13:09
不过哦：

如果以下成立：
#5：          100  --虽然是极大值但前提是第3提议不被通过；
#4：       0，100  --否则一定会被5否决而跳海；
#3：    99，1，  0  --4应该同意否则颗粒无收；
#2： 97，0，2，  1  --4的收益比情况#3好，绝对应该同意；5也如此；
#1：95，0，0，3，  2  --4和5的利益此时是最大的，所以他们一定会投赞成票；

那么，假设存在这么个方案：
#1\' 97，0，1，0，  2  --和#1比较，可以发现，4肯定不举手了，但3会举手，因为如果3不举手，接下来的#2肯定会被通过，但要是#2通过的话，3就一颗拿不到。

作者: Zen 时间: 2007-8-4 13:09
王老虎是老挖？？？

欢迎光临黑蓝论坛 (http://www.heilan.com/FORUM/)