如何精确解决所有海盗分金问题的算法及案例？

“五个海盗，100 枚金币，怎么分才能让自己活下来，还拿到最多的钱？” 作为最流行的博弈论题目之一，这道题存在多种规则： 投票门槛怎么定：过半就行，还是必须严格多数？ 海盗的偏好顺序是什么：先保命，再要钱，最后是喜欢杀人，还是讨厌死人？ 经典版：半数及以上通过 这是流传最广的版本，也是大家最熟悉的 98, 0, 1, 0, 1。 规则 只要赞成票达到 一半及以上，方案就通过 海盗都绝顶理性 偏好顺序是： 先活下来 再多拿金币 如果生死和金币都一样，更愿意看到别人死 倒着推 1 人：只剩 E。E 独吞 100。 2 人：D、E。D 只要自己投赞成就够了，因为“半数及以上”意味着 2 人局里 1 票就过。 所以：D=100，E=0 3 人：C、D、E。如果 C 死了，下一轮是 D、E，而 D 会拿 100，E 拿 0。所以 C 只要给 E 1 枚，E 就会支持他。 所以 C=99，D=0，E=1 4 人：B、C、D、E。如果 B 死了，下一轮结果是：C=99，D=0，E=1。4 人局只要 2 票就能过，B 只需要自己再拉 1 票。谁最便宜？当然是 D，因为他下一轮只能拿 0。 所以：B=99，C=0，D=1，E=0 5 人：A、B、C、D、E。如果 A 死了，下一轮结果是：B=99，C=0，D=1，E=0。5 人局要 3 票。A 自己算 1 票，还需要 2 票。最便宜的是谁？C 和 E，因为他们下一轮都只能拿 0。所以 A 只要各给他们 1 枚 答案 A=98，B=0，C=1，D=0，E=1 严格多数版：必须超过半数 这个版本常常被忽略，但它会把答案从 98 改成 97。 规则 把“半数及以上通过”改成： 必须超过半数。 于是： 2 人局需要 2 票 4 人局需要 3 票 5 人局仍需要 3 票 倒着推 1 人：只剩 E。不变。 2 人：D、E。D 需要 2 票，但 E 一定反对，因为 D 一死，E 就独吞 100。所以 D 必死，无论提出什么方案。 3 人：C、D、E。如果 C 死了，会进入 2 人局，而 D 会死，E 独吞 100。所以 D 为了活命，会支持 C，哪怕 0 枚也行。 结果：C=100，D=0，E=0 4 人：B、C、D、E。如果 B 死了，下一轮是：C=100，D=0，E=0。4 人局需要 3 票。B 自己只有 1 票，还得再买 2 票。最便宜的是 D 和 E，各给 1 枚即可。 结果：B=98，C=0，D=1，E=1 5 人：A、B、C、D、E。如果 A 死了，下一轮是：B=98，C=0，D=1，E=1。A 需要再买 2 票。C 给 1 枚就够。而 D 或 E至少有一个人得给 2 枚才会改投 于是 A 的最优方案是： 答案 A=97，B=0，C=1，D=2，E=0 或 A=97，B=0，C=1，D=0，E=2 温和版：海盗不想多死人 前两个版本默认海盗有点“残忍”：如果我活着、拿的钱也一样，那我宁可看你死。但如果最后一条改成： 保命 > 金币 > 少死人 也就是：如果结果对我一样，我更愿意让人活着。这个改动非常致命。在这个场景下，答案不再唯一，且给其他所有人 0 个金币就是其中一种方案。提案者能独吞 100。 假如只剩下 D 和 E，D 只需要自己一票就能独吞金币，E 什么也得不到。 假如剩下 C，D 和 E。即使 C 想要独吞金币，虽然 D 会反对，但 E 会赞成（反正 E 一定拿不到金币且一定活）。 用归纳法看，会更清楚：假设在 \(n-1\) 人局里，首领可以提 100,0,0,...,0 并通过，那么在 \(n\) 人局里，1 号也提 100,0,0,...,0。此时： 2 号 会想：1 号一死，下一轮轮到我，我也能独吞 100，所以我反对。 3 号到 n 号 会想： 1 号死了以后，2 号上位，2 号的方案也还是“自己拿 100，别人 0”； 所以我现在支持 1 号，和我反对 1 号相比，我自己的结局一样：都活，都拿 0。 那我当然选少死一个人，所以投赞成。 于是，当前首领能拿到自己 1 票，3 号到 n 号，一共 (n-2) 票，合计就是 (n-1) 票。这显然足以通过。 答案 若半数同意即可，A 可以直接提：100, 0, 0, 0, 0 若要严格多数同意，除了 2 人局无解外，从 3 人开始，A 也可以独吞 100 金币可无限切分版 如果金币不是整数，而是能分成任意小，比如 0.000001 枚，那收买成本会进一步下降。 以经典版（半数及以上通过）为例，A 原本需要买 C 和 E 两票，各给 1 枚。但如果能无限细分，A 其实只需要给他们“比下一轮多一点点”就够了。