海盗博弈

有五个理性的海盗，A, B, C, D和E，找到了100个金币，需要想办法分配金币。

海盗们有严格的等级制度：A比B职位高，B比C高，C比D高，D比E高。

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

海盗们基于三个因素来做决定。首先，要能存活下来。其次，自己得到的利益最大化。最后，在所有其他条件相同的情况下，优先选择把别人扔出船外。^[1]

直觉上认为，A海盗会给自己分配很少，以避免被扔出船外。然而这和理论结果相差甚远。

让我们反过来看：如果只剩下D和E，D给自己100个金币，给E 0个。因为D有决定权，所以分配达成。

如果剩下三个人（C，D和E），C知道D下轮会给E 0个金币，所以C这轮给E 1个金币，让E支持自己以使得提议通过。因此如果剩下三个人，结果是C：99，D：0，E：1。

如果B, C, D 和 E 剩下， B 知道上述结果。所以为了避免被扔出去，他只需要给D 1个金币，因为他有决定权，只需要D的支持就足够了。因此他会提议 B：99， C：0， D：1，E：0。有人可能想到提议B：99， C：0， D：0，E：1，因为E知道即使把B扔出去，也不会得到更多了。但由于海盗会优先把别人扔出去，所以E会选择杀死B，然后仍然可以从C的提议中得到相同金币。（若要让E同意他，就至少要给他2个金币才行，这样并不划算，因为这样B自己只能得到98金币，所以不用浪费金币给E）

假设A知道所有的一切，他就能选择让C和E来支持他，提议变成：

• A: 98金币
• B: 0金币
• C: 1金币
• D: 0金币
• E: 1金币^[1]

同样的 A：98，B：0，C：0，D：1，E：1 或者其他的提议都不是最好的，因为D会选择把A扔出去，然后从B那里得到相同的金币。（若要让D同意他，就至少要给他2个金币才行，这样并不划算，因为这样A自己只能得到97金币，所以不用浪费金币给D）

该博弈能很容易延伸到200个海盗（如果有更多金币，甚至可以更多）。艾恩·史都华在1999年5月期的《科学美国人》中，将该博弈延伸到任意人数的海盗，得到十分有趣的结果。 ^[1]

设共有N个海盗，等级最低的海盗为1号，其次为2号，依此类推，等级最高的是N号，若N ≤ 200，则N号海盗的分配法为：自己${\displaystyle \left\lfloor {\frac {202-N}{2}}\right\rfloor }$ 个金币，其余海盗中，编号和N的奇偶性相同者每人各1枚金币，奇偶性不同的，什么也得不到。

201号海盗必须要有101票才能通过，他没有办法，只能自己不拿金币，而给1~199号中奇数号的海盗每人各1枚金币，这样他以及1~199号中的奇数号会投赞成票，这样就刚好101票，提案即可通过。

202号与201号类似，自己不拿金币，而给2~200号中的偶数号每人各1枚。

到了203号，情况第一次有了一百八十度的大转弯，因为他需要102票，但是他没有足够的金币去收买101人，无法通过。

204号则较幸运，因为203号知道他唯有支持204号才能保命，所以204号可以给1~199号中奇数号的海盗每人各1枚金币，因为他知道，203号虽然一无所获但还是会投赞成票，再加上自己一票以及1~199号中奇数号的100票，就达成了102票的条件，所以他的提案就可以通过。

205号就没那么走运了，他不能指望203号与204号支持他，所以没法通过。

206号也是一样，因为他需要103票才能通过，所以就算205号会支持他，还是差1票。

207号则需要104票，但是他最多也只能得到103票（他自己、205号和206号、以及1~200号中的100人），所以也不能通过。

208号则又时来运转，他可以给2~200号中的偶数号每人各1枚，这样他们会同意他，同时他自己跟205, 206, 207号也会投赞成票，刚好104票可通过。

此时，我们继续分析，可以得到一个新的序列：201, 202, 204, 208, 216, 232, 264, 328, 456, 712, 1224, ... ，这些编号的海盗能够存活，他们依次要分给1~200中的奇数、偶数、奇数、偶数、奇数、偶数、 ...号每人各1枚金币。所以当有1500位海盗时，前276名等级最高的海盗必死无疑。轮到1224号海盗时，他可以只分给1~199号中奇数号的海盗每人各1枚金币，而其余的海盗什么也得不到。

一般地，对于任意给定的金币 G, 海盗数目 N。上文中等级不高于 (2 * G) 的海盗都有存活机会；但对于等级高于 (2 * G) 的海盗，只有编号 (N - 2 * G) 为 2 的整数次幂的那些海盗有存活机会，其余海盗必死无疑。第 N 号海盗只需给编号在 (2*G) 以内跟他/她相同奇偶性的海盗分配 1 枚金币即可，其余金币都归他/她自己，但编号大于 (2*G) 的海盗分不到金币。利用计算机编程很容易验证这一结论。

1. ^ ^{1.0 1.1 1.2} Stewart, Ian, A Puzzle for Pirates (PDF), Scientific American, 1999-05: 98–99 [2013-08-14], （原始内容存档 (PDF)于2016-10-19）  引文格式1维护：日期与年 (link)