正文

博弈論與納什平衡

(2006-11-08 08:12:56) 下一個

博弈論(game theory)對人的基本假定是:人是理性的(rational,或者說自私的),理性的人是指他在具體策略選擇時的目的是使自己的利益最大化,博弈論研究的是理性的人之間如何進行策略選擇的。

納什(John Nash)編製的博弈論經典故事"囚徒的困境",說明了非合作博弈及其均衡解的成立,故稱"納什平衡"。

所有的博弈問題都會遇到三個要素。在囚徒的故事中,兩個囚徒是當事人(players)又稱參與者;當事人所做的選擇策略 (strategies)是承認了殺人事實,最後兩個人均贏得(payoffs)了中間的宣判結果。如果兩個囚徒之中有一個承認殺人,另外一個抵賴,不承認殺人,那麽承認者將會得到減刑處理,而抵賴者將會得到最嚴厲的死刑判決,在納什故事中兩個人都承認了犯罪事實,所以兩個囚徒得到的是中間的結果。

類似的: 我們也能從“自私的基因”等理論中看到“納什平衡”的體現。

在互聯網這個原始叢林中:最優策略是如何產生的呢?

一、 博弈中最優策略的產生

艾克斯羅德(Robert Axelrod)在開始研究合作之前,設定了兩個前提:一、每個人都是自私的;二、沒有權威幹預個人決策。也就是說,個人可以完全按照自己利益最大化的企圖進行決策。在此前提下,合作要研究的問題是:第一、人為什麽要合作;第二、人什麽時候是合作的,什麽時候又是不合作的;第三、如何使別人與你合作。

社會實踐中有很多合作的問題。比如國家之間的關稅報複,對他國產品提高關稅有利於保護本國的經濟,但是國家之間互提關稅,產品價格就提高了,喪失了競爭力,損害了國際貿易的互補優勢。在對策中,由於雙方各自追求自己利益的最大化,導致了群體利益的損害。對策論以著名的囚犯困境來描述這個問題。

A和B各表示一個人,他們的選擇是完全無差異的。選擇C代表合作,選擇D代表不合作。如果AB都選擇C合作,則兩人各得3分;如果一方選C,一方選D,則選C的得零分,選D的得5分;如果AB都選D,雙方各得1分。

顯然,對群體來說最好的結果是雙方都選C,各得3分,共得6分。如果一方選C,一方選D,總體得5分。如果兩人都選D,總體得2分。

對策學界用這個矩陣來描述個體理性與群體理性的衝突:每個人在追求個體利益最大化時,就使群體利益受損,這就是囚徒困境。在矩陣中,對於A來說,當對方選C,他選D得5分,選C隻得3分;當對方選D,他選D得1分,選C得零分。因此,無論對方選C或D,對A來說,選D都得分最多。這是A單方麵的優超策略。而當兩個優超策略相遇,即A,B都選D時,結果是各得1分。這個結果在矩陣中並非最優。困境就在於,每個人采取各自的優超策略時,得出的解是穩定的,但不是帕累托最優的,這個結果體現了個體理性與群體理性的矛盾。在數學上,這個一次性決策的矩陣沒有最優解。

如果博弈進行多次,隻要對策者知道博弈次數,他們在最後一次肯定采取互相背叛的策略。既然如此,前麵的每一次也就沒有合作的必要,因此,在次數已知的多次博弈中,對策者沒有一次會合作。

如果博弈在多人間進行,而且次數未知,對策者就會意識到,當持續地采取合作並達成默契時,對策者就能持續地各得3分,但如果持續地不合作的話,每個人就永遠得1分。這樣,合作的動機就顯現出來。多次對局下,未來的收益應比現在的收益多一個折現率W,W越大,表示未來的收益越重要。在多人對策持續進行下去,且W比較大,即未來充分重要時,最優的策略是與別人采取的策略有關的。假設某人的策略是,第一次合作,以後隻要對方不合作一次,他就永不合作。對這種對策者,當然合作下去是上策。假如有的人不管對方采取什麽策略,他總是合作,那麽總是對他采取不合作的策略得分最多。對於總是不合作的人,也隻能采取不合作的策略。

艾克斯羅德做了一個實驗,邀請多人來參加遊戲,得分規則與前麵的矩陣相同,什麽時候結束遊戲是未知的。他要求每個參賽者把追求得分最多的策略寫成計算機程序,然後用單循環賽的方式將參賽程序兩兩博弈,以找出什麽樣的策略得分最高。

第一輪遊戲有14個程序參加,再加上艾克斯羅德自己的一個隨機程序(即以50%的概率選取合作或不合作),運轉了300次。結果得分最高的程序是加拿大學者羅伯布寫的"一報還一報"(tit for tat)。這個程序的特點是,第一次對局采用合作的策略,以後每一步都跟隨對方上一步的策略,你上一次合作,我這一次就合作,你上一次不合作,我這一次就不合作。艾克斯羅德還發現,得分排在前麵的程序有三個特點:第一,從不首先背叛,即"善良的";第二,對於對方的背叛行為一定要報複,不能總是合作,即" 可激怒的";第三,不能人家一次背叛,你就沒完沒了的報複,以後人家隻要改為合作,你也要合作,即"寬容性"。

為了進一步驗證上述結論,艾氏決定邀請更多的人再做一次遊戲,並把第一次的結果公開發表。第二次征集到了62個程序,加上他自己的隨機程序,又進行了一次競賽。結果,第一名的仍是"一報還一報"。艾氏總結這次遊戲的結論是:第一,"一報還一報"仍是最優策略。第二,前麵提到的三個特點仍然有效,因為63人中的前15名裏,隻有第8名的哈靈頓程序是"不善良的",後15名中,隻有1個總是合作的是"善良的"。可激怒性和寬容性也得到了證明。此外,好的策略還必須具有的一個特點是"清晰性",能讓對方在三、五步對局內辨識出來,太複雜的對策不見得好。"一報還一報"就有很好的清晰性,讓對方很快發現規律,從而不得不采取合作的態度。

 二、 合作的進行過程及規律

"一報還一報"的策略在靜態的群體中得到了很好的分數,那麽,在一個動態的進化的群體中,這種合作者能否產生、發展、生存下去呢?群體是會向合作的方向進化,還是向不合作的方向進化?如果大家開始都不合作,能否在進化過程中產生合作?為了回答這些疑問,艾氏用生態學的原理來分析合作的進化過程。

假設對策者所組成的策略群體是一代一代進化下去的,進化的規則包括:一,試錯。人們在對待周圍環境時,起初不知道該怎麽做,於是就試試這個,試試那個,哪個結果好就照哪個去做。第二,遺傳。一個人如果合作性好,他的後代的合作基因就多。第三,學習。比賽過程就是對策者相互學習的過程,"一報還一報"的策略好,有的人就願意學。按這樣的思路,艾氏設計了一個實驗,假設63個對策者中,誰在第一輪中的得分高,他在第二輪的群體中所占比例就越高,而且是他的得分的正函數。這樣,群體的結構就會在進化過程中改變,由此可以看出群體是向什麽方向進化的。

實驗結果很有趣。"一報還一報"原來在群體中占1/63,經過1000代的進化,結構穩定下來時,它占了24%。另外,有一些程序在進化過程中消失了。其中有一個值得研究的程序,即原來前15名中唯一的那個"不善良的"哈靈頓程序,它的對策方案是,首先合作,當發現對方一直在合作,它就突然來個不合作,如果對方立刻報複它,它就恢複合作,如果對方仍然合作,它就繼續背叛。這個程序一開始發展很快,但等到除了"一報還一報"之外的其它程序開始消失時,它就開始下降了。因此,以合作係數來測量,群體是越來越合作的。

進化實驗揭示了一個哲理:一個策略的成功應該以對方的成功為基礎。"一報還一報"在兩個人對策時,得分不可能超過對方,最多打個平手,但它的總分最高。它賴以生存的基礎是很牢固的,因為它讓對方得到了高分。哈靈頓程序就不是這樣,它得到高分時,對方必然得到低分。它的成功是建立在別人失敗的基礎上的,而失敗者總是要被淘汰的,當失敗者被淘汰之後,這個好占別人便宜的成功者也要被淘汰。

那麽,在一個極端自私者所組成的不合作者的群體中,"一報還一報"能否生存呢?艾氏發現,在得分矩陣和未來的折現係數一定的情況下,可以算出,隻要群體的 5%或更多成員是"一報還一報"的,這些合作者就能生存,而且,隻要他們的得分超過群體的總平均分,這個合作的群體就會越來越大,最後蔓延到整個群體。反之,無論不合作者在一個合作者占多數的群體中有多大比例,不合作者都是不可能自下而上的。這就說明,社會向合作進化的棘輪是不可逆轉的,群體的合作性越來越大。艾克斯羅德正是以這樣一個鼓舞人心的結論,突破了"囚犯困境"的研究困境。

在研究中發現,合作的必要條件是:第一、關係要持續,一次性的或有限次的博弈中,對策者是沒有合作動機的;第二、對對方的行為要做出回報,一個永遠合作的對策者是不會有人跟他合作的。

那麽,如何提高合作性呢?首先,要建立持久的關係,即使是愛情也需要建立婚姻契約以維持雙方的合作。(火車站的小販為什麽要騙人?為什麽工作中要形成小組製度?換防的時候一方總是要小小地進攻一下的,在中越前線就是這樣)第二、要增強識別對方行動的能力,如果不清楚對方是合作還是不合作,就沒法回報他了。第三、要維持聲譽,說要報複就一定要做到,人家才知道你是不好欺負的,才不敢不與你合作。第四、能夠分步完成的對局不要一次完成,以維持長久關係,比如,貿易、談判都要分步進行,以促使對方采取合作態度。第五、不要嫉妒人家的成功,"一報還一報"正是這樣的典範。第六、不要首先背叛,以免擔上罪魁禍首的道德壓力。第七、不僅對背叛要回報,對合作也要作出回報。第八、不要耍小聰明,占人家便宜。

(打橋牌和打麻將的區別)

艾克斯羅德在《合作的進化》一書結尾提出幾個結論。第一、友誼不是合作的必要條件,即使是敵人,隻要滿足了關係持續,互相回報的條件,也有可能合作。比如,第一次世界大戰期間,德英兩軍在戰壕戰中遇上了三個月的雨季,雙方在這三個月中達成了默契,互相不攻擊對方的糧車給養,到大反攻時再你死我活地打。這個例子說明,友誼不是合作的前提。第二、預見性也不是合作的前提,艾氏舉出生物界低等動物、植物之間合作的例子來說明這一點。但是,當有預見性的人類了解了合作的規律之後,合作進化的過程就會加快。這時,預見性是有用的,學習也是有用的。

當遊戲中考慮到隨機幹擾,即對策者由於誤會而開始互相背叛的情形時,吳堅忠博士經研究發現,以修正的"一報還一報",即以一定的概率不報複對方的背叛,和 "悔過的一報還一報",即以一定的概率主動停止背叛。群體所有成員處理隨機環境的能力越強,"悔過的一報還一報"效果越好,"寬大的一報還一報"效果越差。

 三、 艾克斯羅德的貢獻與局限性

艾克斯羅德通過數學化和計算機化的方法研究如何突破囚徒困境,達成合作,將這項研究帶到了一個全新境界,他在數學上的證明無疑是十分雄辯和令人信服的,而且,他在計算機模擬中得出的一些結論是非常驚人的發現,比如,總分最高的人在每次博弈中都沒有拿到最高分。(劉邦和項羽的戰爭)

艾氏所發現的"一報還一報"策略,從社會學的角度可以看作是一種"互惠式利他",這種行為的動機是個人私利,但它的結果是雙方獲利,並通過互惠式利他有可能覆蓋了範圍最廣的社會生活,人們通過送禮及回報,形成了一種社會生活的秩序,這種秩序即使在多年隔絕,語言不通的人群之間也是最易理解的東西。比如,哥倫布登上美洲大陸時,與印地安人最初的交往就開始於互贈禮物。有些看似純粹的利他行為,比如無償損贈,也通過某些間接方式,比如社會聲譽的獲得,得到了回報。研究這種行為,將對我們理解社會生活有很重要的意義。

囚徒困境擴展為多人博弈時,就體現了一個更廣泛的問題──"社會悖論",或"資源悖論"。人類共有的資源是有限的,當每個人都試圖從有限的資源中多拿一點兒時,就產生了局部利益與整體利益的衝突。人口問題、資源危機、交通阻塞,都可以在社會悖論中得以解釋,在這些問題中,關鍵是通過研究,製定遊戲規則來控製每個人的行為。

艾克斯羅德的一些結論在中國古典文化道德傳統中可以很容易地找到對應,"投桃報李"、"人不犯我,我不犯人"都體現了"tit for tat"的思想。但這些東西並不是最優的,因為"一報還一報"在充滿了隨機性的現實社會生活裏是有缺陷的。對此,孔子在幾千年前就說出了"以德報德,以直報怨"這樣精彩的修正策略,所謂"直",就是公正,以公正來回報對方的背叛,是一種修正了的"一報還一報",修正的是報複的程度,本來會讓你損失5分,現在隻讓你損失3分,從而以一種公正審判來結束代代相續的報複,形成文明。

但是,艾氏對博弈者的一些假設和結論使其研究不可避免地與現實脫節。首先,《合作的進化》一書暗含著一個重要的假定,即,個體之間的博弈是完全無差異的。現實的博弈中,對策者之間絕對的平等是不可能達到的。一方麵,對策者在實際的實力上有差異,雙方互相背叛時,可能不是各得1分,而是強者得5分,弱者得0 分,這樣,弱者的報複就毫無意義。另一方麵,即使對局雙方確實旗鼓相當,但某一方可能懷有賭徒心理,認定自己更強大,采取背叛的策略能占便宜。艾氏的得分矩陣忽視了這種情形,而這種賭徒心理恰恰在社會上大量引發了零和博弈。因此,程序還可以在此基礎上進一步改進。

其次,艾氏認為合作不需預期和信任。這是他受到質疑頗多之處。對策者根據對方前麵的戰術來製定自己下麵的戰術,合作要求個體能夠識別那些曾經相遇過的個體並且記得與其相互作用的曆史,以便作出反應,這些都暗含著"預期"行為。在應付複雜的對策環境時,信任可能是對局雙方達成合作的必不可少的環節。但是,預期與信任如何在計算機的程序中體現出來,仍是需要研究的。

最後,重複博弈在現實中是很難完全實現的。一次性博弈的大量存在,引發了很多不合作的行為,而且,對策的一方在遭到對方背叛之後,往往沒有機會也沒有還手之力去進行報複。比如,資本積累階段的違約行為,國家之間的核威懾。在這些情況下,社會要使交易能夠進行,並且防止不合作行為,必須通過法製手段,以法律的懲罰代替個人之間的"一報還一報",規範社會行為。這是艾克斯羅德的研究對製度學派的一個重要啟發。

[ 打印 ]
閱讀 ()評論 (1)
評論
明亮 回複 悄悄話 這個好,把複雜的理論給解釋清楚了。謝謝。
登錄後才可評論.