海盗博弈

管理百科
管理营销
资源百科
人力财务
经济百科
经济贸易
金融百科
金融证券
行业百科
物流咨询
综合百科
人物品牌

海盗博弈（Pirate game）

什么是海盗博弈

　　海盗博弈是一个简单的数学博弈。该博弈描述了如果遵循经济人的行为，结果可能让人惊讶。这同时也是最后通牒博弈的多参与者版本

海盗博弈故事^[1]

　　有五个非常聪明的理性的海盗，分别编号 $P 1, P 2, P 3, P 4, P 5$ 。他们一同抢夺了100个金币，现在需要想办法分配这些金币。海盗们有严格的等级制度： $P 1 < P 2 < P 3 < P 4 < P 5$ 。海盗们分配原则是：等级最高的海盗P5提出一种分配方案。然后所有的海盗投票决定是否接受分配，包括提议人。并且在票数相同的情况下，提议人有决定权。如果提议通过，那么海盗们按照提议分配金币。如果没有通过，那么提议人将被扔出船外，然后由下一个最高等级的海盗提出新的分配方案。

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

　　现在，假如你是等级最高的 $P 5$ ，你会做何选择？直觉上，为了保住自己的生命，你可能会选择留给自己很少的金币，以便让大家同意自己的决策。然而，这和理论结果相差甚远。

　　解决这个问题的关键是换个思维方向。与其苦思冥想你要做什么决策，不如先想想最后剩下的人会做什么决策。假设现在只剩下 $P 1$ 和 $P 2$ 了， $P 2$ 会做什么决策？很明显，他将把100金币留给自己，然后投自己一票。由于在票数相同的情况下提议人有决定权，无论 $P 1$ 同不同意， $P 2$ 都将实现自己的目的。

　　现在再把 $P 3$ 加进来。 $P 1$ 知道，如果 $P 3$ 被扔下海，那么游戏又将进行到上面的情况， $P 1$ 终将一无所有。 $P 3$ 同样看到了这一点，所以他知道，只要他给 $P 1$ 一点点利益， $P 1$ 就会投票支持他的决策。所以 $P 3$ 最终的决策应该是： $(P_3,P_2,P_1)\rightarrow(99,0,1)$

　　 $P 4$ 的策略也类似。由于他需要50%的支持，所以他只需贿赂1个金币给 $P 2$ 就可以了。 $P 2$ 一定会支持他(否则轮到 $P 3$ 做决策，他就一无所有啦)。所以 $P 4$ 最终的决策是： $(P_4,P_3,P_2,P_1)\rightarrow(99,0,1,0)$

　　 $P 5$ 的情况稍有不同。由于这次一共有5个人，所以他至少需要贿赂两个海盗以使自己的决议通过。所以唯一的决策就是： $(P_5,P_4,P_3,P_2,P_1)\rightarrow(98,0,1,0,1)$

海盗博弈的延伸^[1]

　　如果海盗的数目不止5个呢？继续按照这个逻辑推理， $P 6$ 的决策将是： $(P_6,P_5,P_4,P_3,P_2,P_1)\rightarrow(98,0,1,0,1,0)$ …一直到 $P 200$ ,它会给自己留1个金币，同时给剩下所有偶数编号的海盗1个金币。

	海盗	$P 1$	$P 2$	$P 3$	$P 4$	$P 5$	…	$P 197$	$P 198$	$P 199$	$P 200$
决策者
$P 1$	100
$P 2$	0	100
$P 3$	1	0	99
$P 4$	0	1	0	99
$P 5$	1	0	1	0	98
…	…	…	…	…	…	…
$P 198$	0	1	0	1	0	…	0	2
$P 199$	1	0	1	0	1	…	1	0	1
$P 200$	0	1	0	1	0	…	0	1	0	1

　　如果海盗数是201个，那么 $P 201$ 该怎么做呢？乍一看去，他好像没有足够的钱去贿赂别的海盗了。不过，为了保住自己的性命，他还是可以把自己手中的金币全分出去，即给每个奇数编号的海盗（ $P 1$ ~ $P 199$ ）一个金币。这样虽然空手而归，但不至于人财两空。

　　 $P 202$ 也只能把这100个金币全部贿赂给其他100个海盗，这100个海盗必须是在 $P 201$ 做决策的情况下什么也得不到的海盗。由于符合这样条件的海盗有101个(所有偶数编号的海盗 $P 201$ )， $P 202$ 的决策不再是唯一的了！有101种方案供他选择。

　　可怜的是 $P 203$ 。由于人数众多，他实在没有足够的钱去贿赂其他海盗以获得足够的支持(他需要至少102个人的支持，包括他自己)。所以，不论 $P 203$ 做什么决策，他都难逃被扔出船外的厄运了。不过 $P 203$ 并没有我们想象中的那么悲情，因为这样的悲剧发生当且仅当船上正好有203个海盗。我们再增加一个海盗， $P 204$ 。 $P 204$ 明白， $P 203$ 现在的唯一愿望就是活下来…所以不论 $P 204$ 做什么决策， $P 203$ 都会举双手支持他(当然举多少手都只能算一票)。所以 $P 204$ 可以靠他自己的一票， $P 203$ 的一票和贿赂另外100个海盗获得正好50%的支持。

　　 $P 204$ 可能的决策也只有101种，如下表：(可能获得1金币的海盗用"Y"标示)

	$P 1$	$P 2$	$P 3$	$P 4$	…	$P 199$	$P 200$	$P 201$	$P 202$	$P 203$	$P 204$
$P 204$	Y	N	Y	N		Y	N	N	Y	N	N

　　 $P 205$ 就没有那么幸运了。他不能无偿的得到 $P 203$ 和 $P 204$ 的支持。所以如果轮到 $P 205$ 做决策，他也必定被扔到船外。 $P 206$ 也一样，尽管他能得到 $P 205$ 的免费支持，但是这还不够。 $P 207$ 需要得到至少104个海盗的支持，所以有了 $P 205$ , $P 206$ 的无偿支持还是不够。

　　 $P 208$ 就比较幸运了。他也是需要得到104个海盗的支持，但 $P 205, P 206, P 207$ ，加上他自己，再加上贿赂100个海盗，正好104票。

　　 $P 208$ 可能的决策：(这次他有 $C_{103}^{100}$ 种决策)

	$P 1$	$P 2$	$P 3$	$P 4$	…	$P 199$	$P 200$	$P 201$	$P 202$	$P 203$	$P 204$	$P 205$	$P 206$	$P 207$	$P 208$
$P 208$	N	Y	N	Y		N	Y	Y	N	Y	Y	N	N	N	N

　　从这里我们又看出了新的规律：

　　从 $P 201$ 之后，在每两个能够作出决策保住自己生命的海盗之间，存在着一些无论如何决策都会被扔到船外的海盗。而这些海盗会支持在这之后的那个能够做出决策保住自己生命的海盗。用数学来表达，设在 $P 201$ 之后，能够作出决策保住自己生命的海盗的编号所组成的序列为 $a n$ 。则有：

　　 $a_0=202\cdots(1)$

　　 $a_n-a_{(n-1)}+100=\frac{a_n}{2}\cdots(2)$

　　对于(2)，

　　若 $a n$ 是偶数，则 $a n = 2 a (n - 1) - 200$

　　若 $a n$ 是奇数，则 $a n = 2 a (n - 1) - 199$

　　给定一个固定的初值，数列的下一项有两个可能解：一个奇数解、一个偶数解，且偶数解比奇数解小1。再考虑我们原问题的意义，到达偶数解时，偶数编号的海盗已经能够做出决策保全自己。这说明我们应该舍弃所有奇数解。

　　由 $a n = 2 a (n - 1) - 200$ 以及 $a 0 = 202$ ，我们得到通解为: $a n = 200 + 2 n + 1$ 。考虑到 $P 201$ 也能保全自己，我们可以把所有能够保全自己但却得不到金币的海盗的编号写成统一表达式：

　　 $N=200+2^n (n=0,1,2,\cdots)$

　　不难推出这些海盗可能的决策种数为 $C_M^{100}$ ,其中

参考文献

↑ ^1.0 ^1.1 逻辑与直觉–海盗博弈

海盗博弈

目录

什么是海盗博弈

海盗博弈故事[1]

海盗博弈的延伸[1]

参考文献

海盗博弈故事^[1]

海盗博弈的延伸^[1]