海盗博弈
海盗博弈(英語:Pirate game),或强盗分金问题是一个简单的数学博弈。该博弈描述了如果遵循经济人的行为,结果可能与常人的直觉相悖。这也是最后通牒賽局的多参与者版本。
博弈
[编辑]有五个理性的海盗,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號海盜的分配法為:自己個金幣,其餘海盜中,編號和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.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)