知識社群ePortfolio登入
賽局理論(Game Theory)
by 趙永祥 2020-09-08 01:12:19, 回應(2), 人氣(1833)


賽局理論(Game Theory


又譯為對策論博弈論,是經濟學的一個分支,1944年馮·諾伊曼奧斯卡·摩根斯特恩合著《賽局理論與經濟行為》,標誌著現代系統賽局理論的的初步形成,因此他被稱為「賽局理論之父」。賽局理論被認為是20世紀經濟學最偉大的成果之一。目前在生物學經濟學國際關係計算機科學政治學軍事戰略和其他很多學科都有廣泛的應用。

主要研究公式化了的激勵結構(遊戲或者賽局)間的相互作用。是研究具有鬥爭或競爭性質現象的數學理論和方法。也是運籌學的一個重要學科。 

現代的賽局理論的源頭是約翰·馮·諾伊曼對於雙人零和賽局的混合策略均衡點的發想和證明。



概述[編輯]

賽局理論考慮遊戲中的個體的預測行為和實際行為,並研究它們的優化策略。表面上不同的相互作用可能表現出相似的激勵結構(incentive structure),所以它們是同一個遊戲的特例。其中一個有名有趣的應用例子是囚徒困境

具有競爭或對抗性質的行為稱為賽局行為。在這類行為中,參加鬥爭或競爭的各方各自具有不同的目標或利益。為了達到各自的目標和利益,各方必須考慮對手的各種可能的行動方案,並力圖選取對自己最為有利或最為合理的方案。比如日常生活中的下棋,打牌等。賽局理論就是研究賽局行為中鬥爭各方是否存在著最合理的行為方案,以及如何找到這個合理的行為方案的數學理論和方法。

生物學家使用賽局理論來理解和預測演化(論)的某些結果。

例如,John Maynard Smith和George R. Price在1973年發表於《自然》雜誌上的論文中提出的「evolutionarily stable strategy」的這個概念就是使用了賽局理論。還可以參見演化賽局理論和行為生態學(behavioral ecology)。

賽局理論也應用於數學的其他分支,如概率統計線性規劃等。

數學定義[編輯]

對於「賽局」(game)有不少可以互換的定義。這裡給出簡短的介紹和相互關係的說明。

範式賽局(Normal form game)[編輯]

範式賽局又被譯為正則形式的賽局、策略型賽局或標準型賽局。

設定是一個「參與者」(players)的集合。對於每一個「參與者」都有一個給定的「策略」集合賽局(遊戲)是一個函數,定義為:

也就是說,如果我們知道了參與者的策略集合是什麼,那麼就可以有一個實數值與之對應。我們可以把上面的方程拆成兩個方程來進一步把它一般化。一個方程是正則形式(Normal form game)的參與者方程,描述策略規定結果的方式。另外一個方程描寫參與者對於結果(outcome)集合的偏好(preference)。也就是:

這裡是遊戲(賽局)的結果集合(outcome set)。對於每一個參與者都有一個偏好函數preference function

展開形式的賽局(Extensive form game)[編輯]

展開形式的賽局又可譯為擴展形式的賽局、擴展式賽局或擴展型賽局。

正則形式的定義為數學家們提供了「均衡」(equilibria)問題的研究一個容易使用的表達式。因為它避免了怎麼計算「策略」的問題,也就是說遊戲是怎麼進行的問題。

若要考慮遊戲是如何進行的,展開形式的賽局是一個比較方便的表達式。這個形式與組合賽局理論關係密切。這個定義通過一個的形式給定。在樹的每一個節點(vertex),不同的參與者選擇一個邊(edge)。


賽局分類[編輯]

賽局的分類根據不同的基準也有不同的分類。一般認為,賽局主要可以分為合作賽局非合作賽局。它們的區別在於相互發生作用的當事人之間有沒有一個具有約束力的協議,如果有,就是合作賽局,如果沒有,就是非合作賽局。

從行為的時間序列性,賽局理論進一步分為兩類:靜態賽局是指在賽局中,參與人同時選擇或雖非同時選擇但後行動者並不知道先行動者採取了什麼具體行動;動態賽局是指在賽局中,參與人的行動有先後順序,且後行動者能夠觀察到先行動者所選擇的行動。通俗的理解:「囚徒困境」就是同時決策的,屬於靜態賽局;而棋牌類遊戲等決策或行動有先後次序的,屬於動態賽局。

按照參與人對其他參與人的了解程度分為完全訊息賽局不完全訊息賽局。完全賽局是指在賽局過程中,每一位參與人對其他參與人的特徵、策略空間及收益函數有準確的資訊。如果參與人對其他參與人的特徵、策略空間及收益函數資訊了解的不夠準確、或者不是對所有參與人的特徵、策略空間及收益函數都有準確的準確資訊,在這種情況下進行的賽局就是不完全訊息賽局。

目前經濟學家們現在所談的賽局理論一般是指非合作賽局,由於合作賽局理論比非合作賽局理論複雜,在理論上的成熟度遠遠不如非合作賽局理論。非合作賽局又分為:完全訊息靜態賽局,完全訊息動態賽局,不完全訊息靜態賽局,不完全訊息動態賽局。

與上述四種賽局相對應的均衡概念為:納許均衡子賽局精煉納許均衡貝葉斯納許均衡、精煉貝葉斯納許均衡(perfect Bayesian Nash equilibrium)。

賽局理論還有很多分類,比如:以賽局進行的次數或者持續長短可以分為有限賽局和無限賽局;以表現形式也可以分為一般型(戰略型)或者展開型,等等。


https://zh.wikipedia.org/wiki/%E5%8D%9A%E5%BC%88%E8%AE%BA


回應(2)


囚徒困境[編輯]

維基百科,自由的百科全書
跳至導覽跳至搜尋
若囚徒們不互相合作,則無法脫離困境。

囚徒困境(英語:Prisoner's Dilemma)是賽局理論非零和賽局中具代表性的例子,反映個人最佳選擇並非團體最佳選擇。或者說在一個群體中,個人做出理性選擇卻往往導致集體的非理性。雖然困境本身只屬模型性質,但現實中的價格競爭、環境保護等方面,也會頻繁出現類似情況。

單次發生的囚徒困境,和多次重複的囚徒困境結果不會一樣。

重複的囚徒困境中,賽局被反覆地進行。因而每個參與者都有機會去「懲罰」另一個參與者前一回合的不合作行為。這時,合作可能會作為均衡的結果出現。欺騙的動機這時可能被受到懲罰的威脅所克服,從而可能導向一個較好的、合作的結果。作為反覆接近無限的數量,納許均衡趨向於帕累托最優

囚徒困境的主旨為,囚徒們彼此合作,堅不吐實,可為全體帶來最佳利益(縮短刑期),但在無法溝通的情況下,因為出賣同夥可為自己帶來利益(無罪開釋),也因為同夥把自己招出來可為他帶來利益,因此彼此出賣雖違反最佳共同利益,反而是自己最大利益所在。但實際上,執法機構不可能設立如此情境來誘使所有囚徒招供,因為囚徒們必須考慮刑期以外之因素(出賣同夥會受到報復等),而無法完全以執法者所設立之利益(刑期)作考量,所以這是一個參考性的學術問題。

經典的囚徒困境[編輯]

1950年,由就職於蘭德公司梅里爾·弗勒德梅爾文·德雷希爾擬定出相關困境的理論,後來由顧問艾伯特·塔克以囚徒方式闡述,並命名為「囚徒困境」。經典的囚徒困境如下:

警方逮捕甲、乙兩名嫌疑犯,但沒有足夠證據指控二人有罪。於是警方分開囚禁嫌疑犯,分別和二人見面,並向雙方提供以下相同的選擇:

  • 若一人認罪並作證檢控對方(相關術語稱「背叛」對方),而對方保持沉默,此人將即時獲釋,沉默者將判監10年。
  • 若二人都保持沉默(相關術語稱互相「合作」),則二人同樣判監半年。
  • 若二人都互相檢舉(互相「背叛」),則二人同樣判監5年。

用表格概述如下:

乙沉默(合作)乙認罪(背叛)
甲沉默(合作)二人同服刑半年甲服刑10年;乙即時獲釋
甲認罪(背叛)甲即時獲釋;乙服刑10年二人同服刑5年

解說[編輯]

如同賽局理論的其他例證,囚徒困境假定每個參與者(即「囚徒」)都是利己的,即都尋求最大自身利益,而不關心另一參與者的利益。參與者某一策略所得利益,如果在任何情況下都比其他策略要低的話,此策略稱為「嚴格劣勢」,理性的參與者絕不會選擇。另外,沒有任何其他力量干預個人決策,參與者可完全按照自己意願選擇策略。

囚徒到底應該選擇哪一項策略,才能將自己個人的刑期縮至最短?兩名囚徒由於隔絕監禁,並不知道對方選擇;而即使他們能交談,還是未必能夠盡信對方不會反口。就個人的理性選擇而言,檢舉背叛對方所得刑期,總比沉默要來得低。試設想困境中兩名理性囚徒會如何作出選擇:

  • 若對方沉默、我背叛會讓我獲釋,所以會選擇背叛。
  • 若對方背叛指控我,我也要指控對方才能得到較低的刑期,所以也是會選擇背叛。

二人面對的情況一樣,所以二人的理性思考都會得出相同的結論——選擇背叛。背叛是兩種策略之中的支配性策略。因此,這場賽局中唯一可能達到的納許均衡,就是雙方參與者都背叛對方,結果二人同樣服刑5年。

這場賽局的納許均衡,顯然不是顧及團體利益的帕累托最優解決方案。以全體利益而言,如果兩個參與者都合作保持沉默,兩人都只會被判刑半年,總體利益更高,結果也比兩人背叛對方、判刑5年的情況較佳。但根據以上假設,二人均為理性的個人,且只追求自己個人利益。均衡狀況會是兩個囚徒都選擇背叛,結果二人判監均比合作為高,總體利益較合作為低。這就是「困境」所在。例子有效地證明了:非零和賽局中,帕累托最優納許均衡是互相衝突的。



固定局數的囚徒困境

概括而言囚徒困境進行第一次後會出現以下兩種情況:

狀況1:

甲在第一次中被乙指控,即會在第二次指控乙,最終導致,甲即時獲釋,乙服刑10年或二人同服刑5年這兩種情況。

狀況2:

概括而言囚徒困境進行第一次後會出現以下兩種情況:

甲在第一次中被乙指控,即會在第二次指控乙,最終導致,甲即時獲釋,乙服刑10年或二人同服刑5年這兩種情況。

雙方均保持沉默,即會建立互信的關係,最終導致,二人同服刑半年。

但互信的關係並非牢不可破,這一點也可以被利用,即甲,乙在第一次中共同選擇沉默而贏得對方的信任,但甲或乙中的一人在獲得對方的信任後指控對方而獲得自身最大的利益即自身即時獲釋,但對方將服刑10年。這是一個以犧牲對方利益而獲得自身最大利益的一種策略。

假設,兩個囚徒均欲利用此策略,並將局數推演為十次,那麼就會出現如下的情況:在第一局到第九局的過程中雙方均會保持沉默,以期望建立互信關係,並在第十局指控對方,這將最終導致,二人同服刑5年。


再一次假設,雙方都明確對方會使用與自己同樣的策略,即知道對方會在第十局中指控自己,這樣,在第九局時兩者間的信任關係的建立即是沒有意義的,如此類推,第八局到第一局中信任關係的建立也是沒有意義的,即是十局都會互相背叛,也就是納許均衡。也可推論,在如此的情況下,只有在囚徒困境的局數在不肯定的情況下(即雙方均不知道進行的局數),才會出現互相保持沉默以獲得信任關係的現象。雙方均保持沉默,即會建立互信的關係,最終導致,二人同服刑半年。