海盗博弈
概述
海盗博弈故事1
有五个非常聪明的理性的海盗，分别编号P1,P2,P3,P4,P5。他们一同抢夺了100个金币，现在需要想办法分配这些金币。 海盗们有严格的等级制度：P1 < P2 < P3 < P4 < P5。 海盗们分配原则是：等级最高的海盗P5提出一种分配方案。然后所有的海盗投票决定是否接受分配，包括提议人。并且在票数相同的情况下，提议人有决定权。如果提议通过，那么海盗们按照提议分配金币。如果没有通过，那么提议人将被扔出船外，然后由下一个最高等级的海盗提出新的分配方案。 海盗们基于三个因素来做决定。首先，要能存活下来。其次，自己的利益最大化(即得到最多的金币)。最后，在所有其他条件相同的情况下，优先选择把别人扔出船外。
现在，假如你是等级最高的P1，你会做何选择？直觉上，为了保住自己的生命，你可能会选择留给自己很少的金币，以便让大家同意自己的决策。然而，这和理论结果相差甚远。
解决这个问题的关键是换个思维方向。与其苦思冥想你要做什么决策，不如先想想最后剩下的人会做什么决策。假设现在只剩下P1和P2了，P2会做什么决策？很明显，他将把100金币留给自己，然后投自己一票。由于在票数相同的情况下提议人有决定权，无论P1同不同意，P2都将实现自己的目的。
现在再把P3加进来。P1知道，如果P3被扔下海，那么游戏又将进行到上面的情况，P1终将一无所有。P3同样看到了这一点，所以他知道，只要他给P1一点点利益，P1就会投票支持他的决策。所以P3最终的决策应该是：
P4的策略也类似。由于他需要50%的支持，所以他只需贿赂1个金币给P2就可以了。P2一定会支持他(否则轮到P3做决策，他就一无所有啦)。所以P4最终的决策是：
P5的情况稍有不同。由于这次一共有5个人，所以他至少需要贿赂两个海盗以使自己的决议通过。唯一的决策就是：
有五个理性的海盗，A, B, C, D和E，找到了100个金币，需要想办法分配金币。
海盗们有严格的等级制度：A比B职位高，B比C高，C比D高，D比E高。
海盗世界的分配原则是：等级最高的海盗提出一种分配方案。所有的海盗投票决定是否接受分配，包括提议人。并且在票数相同的情况下，提议人有决定权。如果提议通过，那么海盗们按照提议分配金币。如果没有通过，那么提议人将被扔出船外，然后由下一个最高职位的海盗提出新的分配方案。 海盗们基于三个因素来做决定。首先，要能存活下来。其次，自己得到的利益最大化。最后，在所有其他条件相同的情况下，优先选择把别人扔出船外。
直觉上认为，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的提议中得到相同金币。
假设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那里得到相同的金币。[1]
海盗博弈的延伸1
如果海盗的数目不止5个呢？ 继续按照这个逻辑推理，P6的决策将是：…一直到P200,它会给自己留1个金币，同时给剩下所有偶数编号的海盗1个金币。
| 海盗 | P1 | P2 | P3 | P4 | P5 | … | P197 | P198 | P199 | P200 | |
| 决策者 | |||||||||||
| P1 | 100 | ||||||||||
| P2 | 0 | 100 | |||||||||
| P3 | 1 | 0 | 99 | ||||||||
| P4 | 0 | 1 | 0 | 99 | |||||||
| P5 | 1 | 0 | 1 | 0 | 98 | ||||||
| … | … | … | … | … | … | … | |||||
| P198 | 0 | 1 | 0 | 1 | 0 | … | 0 | 2 | |||
| P199 | 1 | 0 | 1 | 0 | 1 | … | 1 | 0 | 1 | ||
| P200 | 0 | 1 | 0 | 1 | 0 | … | 0 | 1 | 0 | 1 |
如果海盗数是201个，那么P201该怎么做呢？乍一看去，他好像没有足够的钱去贿赂别的海盗了。不过，为了保住自己的性命，他还是可以把自己手中的金币全分出去，即给每个奇数编号的海盗(P_1~P199)一个金币。这样虽然空手而归，但不至于人财两空。
P202也只能把这100个金币全部贿赂给其他100个海盗，这100个海盗必须是在P201做决策的情况下什么也得不到的海盗。由于符合这样条件的海盗有101个(所有偶数编号的海盗P201)，P202的决策不再是唯一的了！有101种方案供他选择。
可怜的是P203。由于人数众多，他实在没有足够的钱去贿赂其他海盗以获得足够的支持(他需要至少102个人的支持，包括他自己)。所以，不论P203做什么决策，他都难逃被扔出船外的厄运了。不过P203并没有我们想象中的那么悲情，因为这样的悲剧发生当且仅当船上正好有203个海盗。我们再增加一个海盗，P204。P204明白，P203现在的唯一愿望就是活下来…所以不论P204做什么决策，P203都会举双手支持他(当然举多少手都只能算一票)。所以P204可以靠他自己的一票，P203的一票和贿赂另外100个海盗获得正好50%的支持。
P204可能的决策也只有101种，如下表：(可能获得1金币的海盗用"Y"标示)
| P1 | P2 | P3 | P4 | … | P199 | P200 | P201 | P202 | P203 | P204 | |
| P_{204} | Y | N | Y | N | Y | N | N | Y | N | N |
P205就没有那么幸运了。他不能无偿的得到P203和P204的支持。所以如果轮到P205做决策，他也必定被扔到船外。P206也一样，尽管他能得到P205的免费支持，但是这还不够。P207需要得到至少104个海盗的支持，所以有了P205,P206的无偿支持还是不够。
P208就比较幸运了。他也是需要得到104个海盗的支持，但P205,P206,P207，加上他自己，再加上贿赂100个海盗，正好104票。
P_208可能的决策：(这次他有种决策)
| P1 | P2 | P3 | P4 | … | P199 | P200 | P201 | P202 | P203 | P204 | P205 | P206 | P207 | P208 | |
| P208 | N | Y | N | Y | N | Y | Y | N | Y | Y | N | N | N | N |
从这里我们又看出了新的规律：
从P201之后，在每两个能够作出决策保住自己生命的海盗之间，存在着一些无论如何决策都会被扔到船外的海盗。而这些海盗会支持在这之后的那个能够做出决策保住自己生命的海盗。用数学来表达，设在P201之后，能够作出决策保住自己生命的海盗的编号所组成的序列为an。则有：
对于(2)，
若an是偶数，则an = 2a(n − 1) − 200
若an是奇数，则an = 2a(n − 1) − 199
给定一个固定的初值，数列的下一项有两个可能解：一个奇数解、一个偶数解，且偶数解比奇数解小1。再考虑我们原问题的意义，到达偶数解时，偶数编号的海盗已经能够做出决策保全自己。这说明我们应该舍弃所有奇数解。
由an = 2a(n − 1) − 200以及a0 = 202，我们得到通解为:an = 200 + 2n + 1。考虑到P201也能保全自己，我们可以把所有能够保全自己但却得不到金币的海盗的编号写成统一表达式：
不难推出这些海盗可能的决策种数为,其中