海盜分寶石問(wèn)題匯總

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

他們決定這么分：

1。抽簽決定自己的號(hào)碼（1，2，3，4，5）

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

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

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

條件：

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

問(wèn)題：

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

1號(hào)海盜分給3號(hào)1顆寶石，4號(hào)或5號(hào)海盜2顆，獨(dú)得97顆。分配方案為：97，0，1，2，0或97，0，1，0，2。

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

由于該方案對(duì)于4號(hào)和5號(hào)來(lái)說(shuō)比在3號(hào)分配時(shí)更為有利，他們將支持他不希望他出局而由3號(hào)來(lái)分配。

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

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

發(fā)表于

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

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

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

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

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

給定一個(gè)固定的初值，數(shù)列的下一項(xiàng)有兩個(gè)可能解：一個(gè)奇數(shù)解、一個(gè)偶數(shù)解，且偶數(shù)解比奇數(shù)解小1。再考慮我們?cè)瓎?wèn)題的意義，當(dāng)達(dá)到偶數(shù)解時(shí)，偶數(shù)編號(hào)的海盜已經(jīng)能夠做出決策保全自己。這說(shuō)明我們應(yīng)該舍棄所有奇數(shù)解（因?yàn)橄嗤闆r下，海盜會(huì)選擇把決策人扔出船外）。由a(n)=2a(n-1)-200以及a(0)=202，得到通解：a(n)=200+2

n+1

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

n

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

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