精選優質文檔-----傾情為你奉上精選優質文檔-----傾情為你奉上專心---專注---專業專心---專注---專業精選優質文檔-----傾情為你奉上專心---專注---專業5海盜分寶石問題5個海盜搶到了100顆寶石，每一顆都一樣的大小和價值。

他們決定這么分：

1。抽簽決定自己的號碼（1，2，3，4，5）

2。首先，由1號提出分配方案，然后大家5人進行表決，當且僅當半數和超過半數的人同意時，按照他的提案進行分配，否則將被扔入大海喂鯊魚。

3。如果1號死后，再由2號提出分配方案，然后大家4人進行表決，當且僅當半數和超過半數的人同意時，按照他的提案進行分配，否則將被扔入大海喂鯊魚。

4。以次類推......

條件：

每個海盜都是很聰明的人，都能很理智的判斷得失，從而做出選擇。

問題：

第一個海盜提出怎樣的分配方案才能夠使自己的收益最大化?標準答案：

1號海盜分給3號1顆寶石，4號或5號海盜2顆，獨得97顆。分配方案為：97，0，1，2，0或97，0，1，0，2。

推理過程：從后向前推，如果1—3號海盜都喂了鯊魚，只剩4號和5號的話，5號一定投反對票讓4號喂鯊魚，以獨吞全部寶石。所以，4號唯有支持3號才能保命。3號知道這一點，就會提出（100，0，0）的分配方案，對4號、5號而將全部寶石占為己有。因為他知道4號一無所有但還是會投贊成票，再加上自己一票他的方案即可通過。不過，2號推知到3號的方案，就會提出（98，0，1，1）的方案，即放棄3號，而給予4號和5號各一顆寶石。

由于該方案對于4號和5號來說比在3號分配時更為有利，他們將支持他不希望他出局而由3號來分配。

這樣，2號將拿走98顆寶石。不過，2號的方案會被1號所洞悉，1號將提出(97，0，1，2，0)或(97，0，1，0，2)的方案，即放棄2號，而給3號一顆寶石，同時給4號（或5號）2顆寶石。由于1號的解決方案對于3號和4號（或5號）來說，相比2號分配時更優，他們將投1號的贊成票，再加上1號自己的票，1號的方案通過，97顆寶石可以輕松落入囊中。這無疑是1號能夠獲取最大收益的方案了。

在"海盜分贓"模型中，任何"分配者"想讓自己的方案獲得通過的關鍵是，事先考慮清楚"挑戰者"的分配方案是什么，并用最小的代價獲取最大收益，拉攏"挑戰者"分配方案中最不得意的人們。1號看起來最有可能喂鯊魚，但他牢牢地把握住先發優勢，結果不但消除了死亡威脅，還收益最大。而5號，看起來最安全，沒有死亡的威脅，甚至還能坐收漁人之利，卻因不得不看別人臉色行事而只能分得一小杯羹。海盜博弈論

發表于

2011-06-0917:39海盜分金是一個非常古老的問題，在1999年《科學美國人》正式把它發表之前，已經至少流行10年了，相信很多人都有所耳聞，也知道解法。此前死理性派也對這個問題也有所

。今天我們就來回顧一下這個有意思的問題，并且在把問題推廣到大規模海盜團伙后，會得出一些非常有意思的結論。

分金的規則有五個非常聰明的海盜，他們都是死理性派，編號分別是P1、P2、P3、P4、P5。他們一同搶奪了100個金幣，現在需要想辦法分配這些金幣。海盜們有嚴格的等級制度：P1海盜們的分配原則是：等級最高的海盜提出一種分配方案。然后所有的海盜投票決定是否接受分配，包括提議人。并且在票數相同的情況下，提議人有決定權。如果提議通過，那么海盜們按照提議分配金幣。如果沒有通過，那么提議人將被扔出船外，由下一個最高等級的海盜再提出新的分配方案。海盜們基于三個因素來做決定。首先，要能留在船上存活下來。其次，要使自己的利益最大化(即得到最多的金幣)。最后，在所有其他條件相同的情況下，優先選擇把別人扔出船外（這是因為每個海盜都想奪占這條船的控制權）。海盜的邏輯現在，假如你是等級最高的P5，你會做何選擇？直覺上，為了保住自己的生命，你可能會選擇留給自己很少的金幣，以便讓大家同意自己的決策。然而，結果和此大相徑庭。解決這個問題的關鍵在于換個思維方向。與其苦思冥想你要做什么決策，不如先想想最后剩下的人會做什么決策。假設現在只剩下P1和P2了，P2會做什么決策？很明顯，他將把100金幣留給自己，然后投自己一票。由于在票數相同的情況下提議人有決定權，無論P1同不同意，P2都能毫無危險地將所有金幣收入囊中。現在再把P3考慮進來。P1知道，如果P3被扔下海，那么游戲就會出現上述的情況，自己終將一無所獲。由于他們都很聰明，P3同樣能看到這一點，所以他知道，只要給P1一點點利益，P1就會投票支持他的決策。所以P3最終的決策應該是：(P3,P2,P1)→(99,0,1)P4的策略也類似：由于他需要50%的支持率，所以他只需賄賂1個金幣給P2就可以了。P2一定會支持他(否則輪到P3做決策，他就一無所獲啦)。所以P4最終的決策是：(P4,P3,P2,P1)→(99,0,1,0)P5的情況稍有不同：由于這次一共有5個人，他至少需要賄賂兩個海盜才能使自己的決議通過。所以決策就是：(P5,P4,P3,P2,P1)→(98,0,1,0,1)這個結果是不是很出乎意料？你不但可以保全自己，還能得到絕大部分的利益！其實這里面蘊含著遞歸的思想，它是解決許多問題(如漢諾塔問題，全排列問題，整數劃分問題等)的有利手段。好了，看到這里，想必你一定在感慨：哎，還是做上司(等級高)好啊！且慢！問題還沒有結束。如果有更多的海盜真實情況下海盜的數目肯定不止5個。繼續按照這個邏輯推理，P6的決策將是：(P6,P5,P4,P3,P2,P1)→(98,0,1,0,1,0)一直到P200，它會給自己留1個金幣，同時給剩下所有偶數編號的海盜1個金幣。如果海盜數是201個，那么P201該怎么做呢？他好像沒有足夠的錢去賄賂別的海盜了。不過，為了保住自己的性命，他可以把自己手中的金幣全分出去，即給每個奇數編號的海盜(P1~P199)一個金幣。這樣雖然空手而歸，但不至于人財兩空。如果海盜數是202個，P202也只能把這100個金幣全部賄賂給其他100個海盜，而這100個海盜必須是在P201做決策時什么也得不到的海盜。由于符合這樣條件的海盜有101個(所有偶數編號的海盜+P201)，P202的決策不再是唯一的！有101種方案供他選擇。可憐的是P203，由于人數眾多，他實在沒有足夠的錢去賄賂其他海盜以獲得足夠的支持(他至少還需要獲得101個人的支持，但只有100個金幣)。所以，不論P203做什么決策，他都難逃被扔出船外的厄運了。不過P203并沒有我們想象中的那么悲劇，除非船上正好有且只有203個海盜。不妨再來看增加一個海盜P204的情況。P204明白，P203現在的唯一愿望就是活下來…不論他做什么決策，P203都會舉雙手支持他(當然舉多少手都只能算一票)。所以P204可以靠他自己的一票，P203的一票和賄賂另外100個海盜獲得正好50%的支持。P204可能的決策也只有101種，如下表：(可能獲得1金幣的海盜用'Y'標示)PP1P2P3P4…P199P200P201P202P203P204P204YNYN

YNNYNNP205就沒有那么幸運了。他不能無償的得到P203和P204的支持。所以如果輪到P205做決策，他也必定被扔到船外。P206也一樣，盡管他能得到P205的免費支持，但是這還不夠。P207需要得到至少104個海盜的支持，所以有了P205,P206的無償支持還是不夠。P208就比較幸運了，他需要得到104個海盜的支持，P205,P206,P207為了保命會無償支持他，加上他自己，再賄賂100個海盜，正好104票。P208可能的決策：PP1P2P3P4…P200P201P202P203P204P205P206P207P208NYNY

YYYYYNNN到這里我們又看出了新的規律：從P201之后，在每兩個能夠作出決策保住自己生命的海盜之間，存在著一些無論如何決策都會被扔到船外的海盜。而這些海盜會支持在這之后的那個能夠做出決策的海盜以保命。用數學來表達，設在P201之后，能在輪到自己作決策時，保住性命的海盜編號所組成的序列為a(n)。我們有a(0)=202(1)a(n)-a(n-1)+100=[a(n)/2](2)對于(2)，若a(n)是偶數，則a(n)=2a(n-1)-200若a(n)是奇數，則a(n)=2a(n-1)-199

給定一個固定的初值，數列的下一項有兩個可能解：一個奇數解、一個偶數解，且偶數解比奇數解小1。再考慮我們原問題的意義，當達到偶數解時，偶數編號的海盜已經能夠做出決策保全自己。這說明我們應該舍棄所有奇數解（因為相同情況下，海盜會選擇把決策人扔出船外）。由a(n)=2a(n-1)-200以及a(0)=202，得到通解：a(n)=200+2

n+1

。考慮到P201也能保全自己，所以我們把所有能夠保全自己但卻得不到金幣的海盜的編號寫成統一表達式：N=200+2

n

(n=0,1,2,…)不難推出這些海盜可能的決策數是在M中任選100的組合數，其中

如果我們都是海盜好了，我們的海盜分金問題就討論到這里。如果我們把這個模型推廣到真