海盜分寶石問題匯總

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

他們決定這么分：

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

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

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

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

條件：

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

問題：

第一個海盜提出怎樣的分配方案才能夠使自己的收益最大化?標(biāo)準(zhǔn)答案：

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號分配時更優(yōu)，他們將投1號的贊成票，再加上1號自己的票，1號的方案通過，97顆寶石可以輕松落入囊中。這無疑是1號能夠獲取最大收益的方案了。

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

發(fā)表于

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

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

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

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

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

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

n+1

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

n

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

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