博弈論(英語:game theory),又譯為對策論,或者賽局理論,經濟學的一個分支,1944年馮·諾伊曼與奧斯卡·摩根斯特恩合著《博弈論與經濟行為》,標誌著現代系統博弈理論的的初步形成,因此他被稱為「博弈論之父」。博弈論被認為是20世紀經濟學最偉大的成果之一。目前在生物學、經濟學、國際關係、計算機科學、政治學、軍事戰略和其他很多學科都有廣泛的應用。主要研究公式化了的激勵結構(遊戲或者博弈)間的相互作用。是研究具有鬥爭或競爭性質現象的數學理論和方法。也是運籌學的一個重要學科。
以下是李永樂老師的解讀。通俗易懂,你一定能看懂。
稍微再複雜一點,以下是五個海盜分金的博弈論解釋,看起來稍微有點費勁,不過很過癮。
沒有了解過「海盜分金」的可能不是很明白,不過具有「算法邏輯」天賦的人或許分分鐘就明白了。我是屬於了解過一點「海盜分金」的前者。
一、問題描述五個海盜搶到了100個金幣,每一顆都一樣的大小和價值連城。
他們決定這麼分:
1.抽籤決定自己的號碼:[1、2、3、4、5]
2.首先,由1號提出分配方案,然後大家5人進行表決,若且唯若超過半數的人同意時,按照他的提案進行分配,否則將被扔入大海餵鯊魚。
3.如果1號死後,再由2號提出分配方案,然後大家4人進行表決,若且唯若超過半數的人同意時,按照他的提案進行分配,否則將被扔入大海餵鯊魚。
4.以次類推
條件:每個海盜都是很聰明的人,都能很理智的判斷得失,從而做出選擇。
問題:第一個海盜提出怎樣的分配方案才能夠使自己免於下海以及自己獲得最多的金幣呢?
(1). 如果剩下4號和5號,那麼4號必定分不到硬幣,因為此時5號有一票否決權。即使4號給出「4號分0枚硬幣,5號分100枚硬幣」的方案,4號都得看5號的心情,要不要處死4號,所以無論怎樣分,只剩下4號和5號的情況下,4號是永遠的劣勢。那麼此時4號就得「挽留」住3號來使得自己的利益最大化;
(2). 如果剩下3號、4號和5號,那麼3號給出「3號99枚,4號1枚,5號0枚」的分配方式,是肯定可通過的。因為由(1)的分析可知,如果3號死了,4號一枚都分不到,而且還得看5號的心情,所以4號一定會極力保全3號,即3號和4號同意3號的分配方式,3號的分配方案通過。剩下的同理推。
===》3號的分配方案可以是(既然輪到3號分配了,說明1號和2號都已經餵鯊魚了):(99,1,0);
(3). 如果剩下2號、3號、4號和5號,那麼2號給出「」的分配方式肯定可以通過的。因為由(2)可知,如果2號死了,那麼5號一個也得不到,此時2號只要去拉攏一下5號,同時2號給4號的不比3號給4號的少即可(因為給的少了,4號會覺得跟2號和3號都一樣,2號就得看4號的心情了)。
===》2號的分配方案可以是(既然輪到2號分配了,說明1號已經餵鯊魚了):(97,0,2,1);
(4). 如果1號開始分配,那麼1號由(3)可知,如果1號死了,3號就一個也得不到,那麼1號就要拉攏一下3號,同時再給點好處4號或者5號,那麼就可以保證同意的人數超過一半了。給5號的成本是最低的,分給5號一枚金幣,就可以讓5號有心情同意了,如果分給5號2枚,那麼5號會感激涕零的。當然,1號為了追求自己利益的最大化,可以給3號1枚的,給5號一枚(當然此時可能受到5號「心情」的影響)。
===》1號的分配方案可以是:(98,0,1,0,1).
為什麼說分配方案看「心情」呢?原因是「人的選擇」,比如說2號也是可以分(98,0,1,1)的,只要4號和5號心情好,覺得跟2號和3號都一樣,但是多個人存在,多份歡樂,2號的利益最大化就可以達到。
這是個博弈的問題,在權利的世界裡「心情」可能就好比「站隊」。此處略去n多字。。。
這也是一個算法題,可以用代碼實現上述的分析的。
1 . 動漫中的」三姬分金」即為3號、4號、5號海盜存在的情形,這個動漫情節設計的作者應該是一個學識淵博,懂博弈論,具有算法天賦(我瞎說的,哈哈哈)的人;
2. 推薦良心國產動漫:《秦時明月》3-5部,《秦時明月——天行九歌》(很多博弈問題)
3. 這篇雖是閒談,但也是我準備沒事時來寫寫我對常見趣味算法的理解的引子。