#科普有料#最近幾天看到一個挺有趣的博弈相關的趣談,今天來分享給大家,並且也會詳細講解最終問題的最優解,並且我還好透過這道題扯一扯遞迴。
問題描述
有 5 個海盜,獲得了 100 枚金幣,於是他們要商量一個方法來分配金幣。商議方式如下:
由 5 個海盜輪流提出分配方案,規則如下
1、如果超過半數海盜(包括提出者)同意該方案,則按照該方案分配。
2、如果同意該方案的人數(包括提出者)小於等於半數,則提出者要被扔到海里餵魚,剩下的海盜繼續商議分配。
3、海盜們都是絕對聰明理性的,也是絕對貪婪的,以自己儘可能多獲得金幣為目的。保證自己活命的情況下,且在收益相等的情況下,會傾向把提出者扔到海里。
問:如果你是第一個海盜應該提出怎樣的分配方案,才能保證自己既不被扔到海里,又能使自己利益最大化?
解決問題
先做一些假設和提醒
為了方便後面描述,我們假設輪流提出方案的順序為:海盜1(你),海盜2,海盜3,海盜4,海盜5;也就是說,最開始由海盜1(你) 提出分配方案,海盜5排在最後
並且,大家一定要注意最後一個條件,每個海盜是絕對聰明理性貪婪以及在收益相等的情況下,會傾向把提出者扔到海里。
前方高能,開始扯淡,請你發揮出你的各種猜想
好了,現在如果你是海盜1,你會怎麼分配才能使得獲得的金幣儘可能多,並且不會被扔進海里餵魚呢?
說實話,第一眼看到這個問題,有點無從下手,腦子太特麼亂了,因為完全不知道怎麼證明我的分配方案能夠讓超過一半的海盜都必須支援我,要不平均分配?要不我少一點他們多一點?要不我多一點他們少一點(這樣會不會馬上就被扔下海里)?
你也可以自己先想幾分鐘哦,看看你能否自己想的出來?
事實上,要讓別人同意我們的想法,我們必須得知彼知己,才能百戰百勝。
逐層擊破
1、只有 2 個海盜的情況
現在,我們假設只剩兩個海盜:海盜4和海盜5,這個時候你應該知道分配結果了吧?
很顯然,無論海盜4提出什麼方案,海盜5 都會直接拒絕,這樣海盜5就可能獲得全部的金幣了,也就是說,當只有兩個海盜時,海盜4無論怎麼討好海盜5,最終的結果都是到海里餵魚,海盜4絕不敢讓海盜3死亡。所以分配結果如下
2、只有3個海盜的情況
這個時候突然跳出了個海盜3,也參與到這場分贓活動中,這個時候海盜3該如何分配?
其實也非常簡單,海盜3也知道海盜4心理。他知道如果自己被扔進海里的話,海盜4一定也會被扔進海里,所以海盜3知道,自己無論提出什麼方法,海盜4都必須同意,所以海盜3可以提出如下的分配方案:
海盜3: 100 個金幣
海盜4: 0 個金幣
海盜5: 0 個金幣。
也就是,只要海盜4支援海盜3,就可以形成 2:1的局面,海盜3就可以穩贏,不需要兼顧海盜5是否支援。所以最終的分配結果如下
有人可能會說,我們用不用給海盜4分配一點好處?例如分配給海盜4一個金幣,條件3有個規則:海盜是貪婪聰明理性的。雖然海盜4沒有分配到金幣,但是他並沒有被扔進海里,這就是最大的好處了
看到這裡,你是不是也知道如果是 4 個海盜或者 5 個海盜,你也會分配了?我相信你大機率知道怎麼分配了,不過我還是要講一下,因為後面隨著人數的增加,也並沒有你想的那麼簡單,並且後面還會和遞迴演算法串講一下。
3、只有4個海盜的情況
這個時候又突然蹦出個海盜2,並且海盜2是已經知道了海盜3的分配方案了,這個時候海盜2必須需要獲得其中其他2個人的支援。
如何獲得其他另2個人的支援?
這很容易,拿點錢給海盜4和海盜5就可以了,海盜2可以提出如下分配方案
海盜2:98個
海盜3:0個
海盜4:1個
海盜5:1個
注意,在收益相等的情況下,海盜們會傾向把提出者扔到海里,所以海盜2必須在海盜3的基礎上,多給海盜4和海盜5一個金幣,這個時候海盜4和海盜5一定會支援海盜2,因為要是海盜3來提出方案,他們什麼都得不到只能保命,還不如同意海盜2的方案。此時的局面是 3:1(支援:反對的人數),因此只有4個人的情況下,海盜2分配方案如上。
有人可能會問,為啥要拉攏賄賂海盜4和海盜5,咱能不能嘗試賄賂下海盜3?
答是咱賄賂不起,如果你有這樣的想法,只能說明你不是一個合格的海盜!海盜3當時滿腦子都是想弄死海盜2,什麼賄賂都不會同意海盜2方案的,沒必要給他金幣。
4、5個海盜的情況
如果有5個海盜,其實海盜1和海盜2一樣,只需要拉攏兩個人就可以了,那要拉攏誰呢?
這也不難,首先必須得賄賂海盜3,給他一個金幣就可以了,因為海盜3知道等海盜2來分配時候自己將一個金幣都得不到,只能活命,還不如拿同意海盜1的方案拿1個金幣。其次我們在海盜4或者海盜5之中拉攏一個人即可,想要拉攏哪一個,隨你開心,所以海盜1可以提出如下方案:
海盜1: 97個
海盜2:0個
海盜3:1個
海盜4和海盜5:其中一個0個,另一個給2個。(他們兩個在前面的情況下頂多能拿到1個金幣,那當海盜1方案可以給自己分兩個金幣,那其中拿2個金幣的海盜肯定會同意海盜1的方案。作者的建議是給海盜4,因為夢想這種東西海盜5心裡可能是一直存在的。而海盜4是5個人裡最被動的,能拿到1金幣已經喜極而泣了,如今可以分得2個金幣,完全會是雙手贊成,不然後面的結果不是隻能活命就是隻能拿一個。)
這樣結果將會是3:2透過方案
到這裡,就已經分配完畢了,是不是覺得很不可思議?原本還怕自己無論提出啥方案,都會被扔進海里,結果是如此出人意料。以後和別人分贓,是時候拿出這個規則了
問題的核心
有時候遇到這種看似很複雜的博弈問題,不妨先從問題的規模儘量小處理起,後面在逐一增加問題的規模。
不妨來個拓展
如果又突然冒出了一個海盜呢?也就是在一共有 6 個海盜的情況下,該如何處理呢?
有沒有覺得,從 5 個到 6 個,是一個分水嶺?因為從 5 個開始,就有多種分配方案,這個時候就更加考驗你的邏輯了。
不過,對於 6 個,我姑且給大家分析一下,當然,只是我認為是這樣,其實我看過別人的也有不同的版本。下面我來分析下(你作為海盜1)可以給出的策略:
首先,我們必須拉攏 3 個人,結果必須至少4:2顯然,我們是不可能會拉攏海盜2(即5個海盜中的海盜1)因為咱拉不起。他巴不得你餵魚呀。因為我們會從海盜3~ 海盜6中考慮。
1、首先我們必須拉攏海盜3(前面情況中的海盜2),因為他最容易賄賂,給他 1 個金幣即可,因為如果你沒了,剩5個人時候,海盜2來分配(即上述分配方案)他將一個金幣拿不到。
2、接著,我們拉攏海盜4(前面情況的海盜3),給他兩個金幣即可,等海盜2分配方案中他只能拿1個。還不如此刻拿2個
此時,我們已經拉攏了海盜3和海盜4,接下來我們需要在海盜5和海盜6中選一個即可,那麼問題來了,該給海盜5和海盜6他們多少,他們才願意同意你的方案?
顯然,如果我們給海盜5分配 3 個金幣,海盜6分配 0 個,顯然海盜5一定會同意。
但是,真的需要給海盜5分配 3 個嗎?如果我給他 2 個金幣,他會同意嗎?
答是會的,為什麼呢?因為在5個海盜分配的方案中,海盜5(即前面的海盜4)最多拿2個,且具有不確定性,因為海盜2方案可以在最後兩個海盜中2選一給2個金幣。如今你的方案可以讓他自己可以穩拿2個金幣,後面的分配結果不會比這更多了,還有分不到的風險。那海盜5是6個人裡面最被動的人,穩拿2個金幣的方案中下將不會選擇反對。
因此你(海盜1)可以提出如下方案
你(海盜1):95個
海盜2:0個
海盜3:1個
海盜4:2個
海盜5:2個
海盜6:0個
分析到這裡,就已經結束了,如果又蹦出一個海盜呢?也就是說一共有 7 個海盜呢?
剩下的就交給你了,鑑於篇幅,我就不繼續分析了。
最後
今天這道題也是我花了整整一個上午寫的,希望能夠讓你有所收穫,或者能夠可以給給解解悶,我們下期再見!
老鐵們,要不關注一下我,點個贊再走可好?麼麼噠