三十分鐘理解博弈論“納什均衡” — Nash Equilibrium

三十分鐘理解博弈論“納什均衡” — Nash Equilibrium

歡迎轉載,轉載請註明:本文出自Bin的專欄blog.csdn.net/xbinworld。
技術交流QQ群:433250724,歡迎對演算法、技術感興趣的同學加入。


納什均衡(或者納什平衡),Nash equilibrium ,又稱為非合作博弈均衡,是博弈論的一個重要策略組合,以約翰·納什命名。


約翰·納什,生於1928年6月13日。著名經濟學家、博弈論創始人、《美麗心靈》男主角原型。前麻省理工學院助教,後任普林斯頓大學數學系教授,主要研究博弈論、微分幾何學和偏微分方程。由於他與另外兩位數學家(經濟學家,約翰·C·海薩尼和萊因哈德·澤爾騰)在非合作博弈的均衡分析理論方面做出了開創性的貢獻,對博弈論和經濟學產生了重大影響,而獲得1994年諾貝爾經濟學獎。

納什的人生非常曲折,一度學術成果不被認可,甚至換上嚴重的精神分裂症,在愛的力量下在很多年後奇蹟般地恢復,並最終獲得諾內爾經濟學獎。影片《美麗心靈》(A Beautiful Mind)是一部改編自同名傳記而獲得奧斯卡金像獎的電影,影片以約翰·納什與他的妻子艾莉西亞(曾離婚,但2001年復婚)以及普林斯頓的朋友、同事的真實感人故事為題材,藝術地重現了這個愛心呵護天才的傳奇故事。

這裡寫圖片描述
年輕時的Nash,很帥噢


納什均衡定義

經濟學定義[3]
所謂納什均衡,指的是參與人的這樣一種策略組合,在該策略組合上,任何參與人單獨改變策略都不會得到好處。換句話說,如果在一個策略組合上,當所有其他人都不改變策略時,沒有人會改變自己的策略,則該策略組合就是一個納什均衡。

數學定義
納什均衡的定義:在博弈G=﹛S1,…,Sn:u1,…,un﹜中,如果由各個博弈方的各一個策略組成的某個策略組合(s1*,…,sn*)中,任一博弈方i的策略si*,都是對其餘博弈方策略的組合(s1*,…s*i-1,s*i 1,…,sn*)的最佳對策,也即ui(s1*,…s*i-1,si*,s*i 1,…,sn*)≥ui(s1*,…s*i-1,sij*,s*i 1,…,sn*)對任意sij∈Si都成立,則稱(s1*,…,sn*)為G的一個納什均衡。

:經濟學定義從字面上還是相對比較好理解的;這裡稍微解釋一下數學定義,博弈論也稱Game Theory,一場博弈用G表示,Si表示博弈方i的策略,ui表示收益。因此,納什均衡的意思是:任何一方採取的策略都是對其餘所有方採取策略組合下的最佳對策;當所有其他人都不改變策略時,為了讓自己的收益最大,任何一方都不會(或者無法)改變自己的策略,這個時候的策略組合就是一個納什均衡。

納什證明了在每個參與者都只有有限種策略選擇、並允許混合策略的前提下,納什均衡一定存在。以兩家公司的價格大戰為例,納什均衡意味著兩敗俱傷的可能:在對方不改變價格的條件下,既不能提價,否則會進一步喪失市場;也不能降價,因為會出現賠本甩賣。於是兩家公司可以改變原先的利益格局,通過談判尋求新的利益評估分攤方案,也就是Nash均衡。類似的推理當然也可以用到選舉,群體之間的利益衝突,潛在戰爭爆發前的僵局,議會中的法案爭執等。


納什均衡案例

以下介紹幾個經典的納什均衡案例[2][4],因為本文主要是以科普為主,所以案例不會涉及到複雜深奧的經濟學問題(事實上,我也不懂,哈~)。

(1)囚徒困境

假設有兩個小偷A和B聯合犯事、私入民宅被警察抓住。警方將兩人分別置於不同的兩個房間內進行審訊,對每一個犯罪嫌疑人,警方給出的政策是:如果一個犯罪嫌疑人坦白了罪行,交出了贓物,於是證據確鑿,兩人都被判有罪。如果另一個犯罪嫌疑人也作了坦白,則兩人各被判刑8年;如果另一個犯罪嫌人沒有坦白而是抵賴,則以妨礙公務罪(因已有證據表明其有罪)再加刑2年,而坦白者有功被減刑8年,立即釋放。如果兩人都抵賴,則警方因證據不足不能判兩人的偷竊罪,但可以私入民宅的罪名將兩人各判入獄1年。

此時產生了兩個嫌疑人之間的一場博弈:

這裡寫圖片描述

表中的數字表示A,B各自的判刑結果。博弈論分析中一般都用這樣的表來表示。

該案例,顯然最好的策略是雙方都抵賴,結果是大家都只被判1年。但是由於兩人處於隔離的情況,首先應該是從心理學的角度來看,當事雙方都會懷疑對方會出賣自己以求自保、其次才是亞當·斯密的理論,假設每個人都是“理性的經濟人”,都會從利己的目的出發進行選擇。這兩個人都會有這樣一個盤算過程:假如他坦白,如果我抵賴,得坐10年監獄,如果我坦白最多才8年;假如他要是抵賴,如果我也抵賴,我就會被判一年,如果我坦白就可以被釋放,而他會坐10年牢。綜合以上幾種情況考慮,不管他坦白與否,對我而言都是坦白了划算。兩個人都會動這樣的腦筋,最終,兩個人都選擇了坦白,結果都被判8年刑期。

注:亞當·斯密的理論(“看不見的手”原理),在市場經濟中,每一個人都從利己的目的出發,而最終全社會達到利他的效果。但是我們可以從“納什均衡”中引出“看不見的手”原理的一個悖論:從利己目的出發,結果損人不利己,既不利己也不利他。

(2)智豬博弈

豬圈裡有兩頭豬,一頭大豬,一頭小豬。豬圈的一邊有個踏板,每踩一下踏板,在遠離踏板的豬圈的另一邊的投食口就會落下少量的食物。如果有一隻豬去踩踏板,另一隻豬就有機會搶先吃到另一邊落下的食物。當小豬踩動踏板時,大豬會在小豬跑到食槽之前剛好吃光所有的食物;若是大豬踩動了踏板,則還有機會在小豬吃完落下的食物之前跑到食槽,爭吃到另一半殘羹。

那麼,兩隻豬各會採取什麼策略?答案是:小豬將選擇“搭便車”策略,也就是舒舒服服地等在食槽邊;而大豬則為一點殘羹不知疲倦地奔忙於踏板和食槽之間。

原因何在?因為,小豬踩踏板將一無所獲,不踩踏板反而能吃上食物。對小豬而言,無論大豬是否踩動踏板,不踩踏板總是好的選擇。反觀大豬,已明知小豬是不會去踩動踏板的,自己親自去踩踏板總比不踩強吧,所以只好親力親為了。

(3)普通正規化博弈

GOO公司和SAM公司是某手機產品生態的兩大重量級參與者,雙方在產業鏈的不同位置上各司其職且關係曖昧,有時也往往因商業利益和產品影響力的爭奪而各懷異心。二者的收益也隨著博弈的變化而不斷更替。

這裡寫圖片描述

上圖表格模擬了兩家公司的博弈現狀,雙方各有兩個可選策略“合作”與“背叛”,格中的四組資料表示四個博弈結局的分數(收益),每組資料的第一個數字表示GOO公司的收益,後一個數字表示SAM公司的收益。

博弈是同時進行的,一方參與者必須站在對方的角度上來思考我方的策略選擇,以追求收益最大化。這在博弈論裡稱作Putting yourselves into other people’s shoes。

現在我們以GOO公司為第一人稱視角來思考應對SAM公司的博弈策略。假如SAM公司選擇合作,那麼我方也選擇合作帶來的收益是3,而我方選擇背叛帶來的收益是5,基於理性的收益最大化考慮,我方應該選擇背叛,這叫嚴格優勢策略;假如SAM公司選擇背叛,那麼我方選擇合作帶來的收益是-3,而選擇背叛帶來的收益為-1,為使損失降到最低,我方應該選擇背叛。最後,GOO公司的分析結果是,無論SAM公司選擇合作還是背叛策略,我方都必須選擇背叛策略才能獲得最大化的收益。

同理,當SAM公司也以嚴格優勢策略來應對GOO公司的策略選擇時,我們重複上述分析過程,就能得出結論:無論GOO公司選擇合作還是背叛策略,SAM公司都必須選擇背叛策略才能獲得最大化收益。

最後我們發現,本次博弈的雙方都採取了背叛策略,各自的收益都為-1,這是一個比較糟糕的結局,儘管對任何一方來說都不是最糟糕的那種。這種局面就是著名的“囚徒困境”。

但是,博弈的次數往往不止一次,就像COO與SAM公司雙方的商業往來也許會有很多機會。當二者經歷了多次背叛策略的博弈之後,發現公式上還有一個(3,3)收益的雙贏局面,這比(-1,-1)的收益結果顯然要好很多,因此二者在之後的博弈過程中必然會嘗試互建信任,從而驅使雙方都選擇合作策略。

這裡有一個理想化假設,那就是假設雙方都知道博弈次數是無限的話,也就是說雙方的商業往來是無止盡的,那麼二者的策略都將持續選擇合作,最終的博弈收益將定格在(3,3),這就是一個納什均衡。既然博弈次數是無限的,那麼任何一方都沒有理由選擇背叛策略去冒險追求5點短暫收益,而招致對方在下一輪博弈中的報復(這種報復在博弈論裡稱作“以牙還牙”策略)。

還有另一種假設情況是,假使雙方都知道博弈次數是有限的,也許下一次博弈就是最後一次,那麼為了避免對方在最後一輪博弈中選擇背叛策略而使我方遭受-3的收益損失,於是雙方都重新採取了背叛的策略選擇,最後的博弈結果又回到了(-1,-1),這就形成了第二個納什均衡。

由此可見,隨著次數(博弈性質)的變化,納什均衡點也並非唯一。

(4)餓獅博弈

假設有A、B、C、D、E、F六隻獅子(強弱從左到右依次排序)和一隻綿羊。假設獅子A吃掉綿羊後就會打盹午睡,這時比A稍弱的獅子B就會趁機吃掉獅子A,接著B也會午睡,然後獅子C就會吃掉獅子B,以此類推。那麼問題來了,獅子A敢不敢吃綿羊?

為簡化說明,我們先給出此題的解法。該題須採用逆向分析法,也就是從最弱的獅子F開始分析,依次前推。假設獅子E睡著了,獅子F敢不敢吃掉獅子E?答案是肯定的,因為在獅子F的後面已沒有其它獅子,所以獅子F可以放心地吃掉午睡中的獅子E。

繼續前推,既然獅子E睡著會被獅子F吃掉,那麼獅子E必然不敢吃在他前面睡著的獅子D。

再往前推,既然獅子E不敢吃掉獅子D,那麼D則可以放心去吃午睡中的獅子C。依次前推,得出C不吃,B吃,A不吃。所以答案是獅子A不敢吃掉綿羊。

推理結果如下圖:
這裡寫圖片描述

但是,如果我們在獅子F的後面增加了一隻獅子G,總數變成7只,用逆向分析法按照上題步驟再推一次,很容易得出結論:獅子G吃,獅子F不吃,E吃,D不吃,C吃,B不吃,A吃。這次的答案變成了獅子A敢吃掉綿羊。

這裡寫圖片描述

對比兩次博弈我們發現,獅子A敢不敢吃綿羊取決於獅子總數的奇偶性,總數為奇數時,A敢吃掉綿羊;總數為偶數時,A則不敢吃。因此,總數為奇數和總數為偶數的獅群博弈結果形成了兩個穩定的納什均衡點。

(5)硬幣正反

你正在圖書館枯坐,一位陌生美女主動過來和你搭訕,並要求和你一起玩個數學遊戲。美女提議:“讓我們各自亮出硬幣的一面,或正或反。如果我們都是正面,那麼我給你3元,如果我們都是反面,我給你1元,剩下的情況你給我2元就可以了。”那麼該不該和這位姑娘玩這個遊戲呢?

每一種遊戲依具其規則的不同會存在兩種納什均衡,一種是純策略納什均衡,也就是說玩家都能夠採取固定的策略(比如一直出正面或者一直出反面),使得每人都賺得最多或虧得最少;或者是混合策略納什均衡,而在這個遊戲中,便應該採用混合策略納什均衡。

這裡寫圖片描述

假設我們出正面的概率是x,反面的概率是1-x,美女出正面的概率是y,反面的概率是1-y。為了使利益最大化,應該在對手出正面或反面的時候我們的收益都相等,由此列出方程就是

3x (-2)(1-x)=(-2) * x 1*( 1-x )——解方程得x=3/8;同樣,美女的收益,列方程-3y 2( 1-y)= 2y (-1) * ( 1-y)——解得y也等於3/8。

於是,我們就可以算美女每次的期望收益是: (1-y)(2x-(1-x)) y(-3x 2(1-x)) = 1/8元,也就是說,雙方都採取最優策略的情況下,平均每次美女贏1/8元。

其實只要美女採取了(3/8,5/8)這個方案,不論你再採用什麼方案,都是不能改變局面的。如果全部出正面,每次的期望收益是 (3 3 3-2-2-2-2-2)/8=-1/8元;如果全部出反面,每次的期望收益也是(-2-2-2 1 1 1 1 1)/8=-1/8元。比如你用完全隨機(1/2,1/2)策略,收益是1/2(3/8 * 3 5/8 * (-20)) 1/2(3/8 * (-2) 5/8 * 1) = -1/8;實際上,不論你用什麼策略,你的收益都是-1/8,也就是說,隨便玩一種策略,你都是在納什均衡狀態中的,所以,這個把戲你隨便怎麼玩,都是虧的。

以下一段補充說明(補充於2017年5月30日端午節,大家端午快樂!):
這個例子中是沒有純戰略納什均衡的,因為只出一種策略,肯定有一方要虧錢,所以並不是其均衡狀態(明明只要換一邊就可以賺錢了,所以不是最佳策略);而混合納什均衡是純在的,事實上,Nash告訴我們“每個參與者都只有有限種策略選擇、並允許混合策略的前提下,納什均衡一定存在”,如果美女出(3/8,5/8)這個方案,另一邊任何玩法都是期望收益一樣的,也就滿足了納什均衡的條件。


納什均衡分類

最後講一講納什均衡的分類。納什均衡可以分成兩類:“純戰略納什均衡”和“混合戰略納什均衡”。

要說明純戰略納什均衡和混合戰略納什均衡,要先說明純戰略和混合戰略。所謂純戰略是提供給玩家要如何進行賽局的一個完整的定義。特別地是,純戰略決定在任何一種情況下要做的移動。戰略集合是由玩家能夠施行的純戰略所組成的集合。而混合戰略是對每個純戰略分配一個機率而形成的戰略。混合戰略允許玩家隨機選擇一個純戰略。混合戰略博弈均衡中要用概率計算,因為每一種策略都是隨機的,達到某一概率時,可以實現支付最優。因為機率是連續的,所以即使戰略集合是有限的,也會有無限多個混合戰略。

當然,嚴格來說,每個純戰略都是一個“退化”的混合戰略,某一特定純戰略的機率為 1,其他的則為 0。
故“純戰略納什均衡”,即參與之中的所有玩家都玩純戰略;而相應的“混合戰略納什均衡”,之中至少有一位玩家玩混合戰略。並不是每個賽局都會有純戰略納什均衡,例如“錢幣問題”就只有混合戰略納什均衡,而沒有純戰略納什均衡。不過,還是有許多賽局有純戰略納什均衡(如協調賽局,囚徒困境和獵鹿賽局)。甚至,有些賽局能同時有純戰略和混合戰略均衡。


參考資料

[1] http://baike.baidu.com/view/52630.htm,百度百科:約翰·納什
[2] http://baike.baidu.com/view/28460.htm,百度百科:納什均衡
[3] 高鴻業.西方經濟學(微觀部分)第五版:人民大學出版社,2011:292-296
[4] http://www.vccoo.com/v/7074d4,一般人也能看懂的納什均衡案例