無名氏定理:修訂版本之間的差異

出自六年制學程
跳轉到: 導覽搜尋
重複博弈詳解
重複博弈詳解
 
第 108 行: 第 108 行:
 
#[http://www.yhcw.net/yuner/articles/prison2.html 自動機與博奕策略]
 
#[http://www.yhcw.net/yuner/articles/prison2.html 自動機與博奕策略]
 
#[http://www.yhcw.net/yuner/articles/prison3.html 大眾定理與文化沖突]
 
#[http://www.yhcw.net/yuner/articles/prison3.html 大眾定理與文化沖突]
 +
google 雲端文件 p1,p2

2019年3月10日 (日) 23:58的最新修訂版本

英語為 folk theorems ,中文又譯為大眾定理。

單憑理性計算,有限次重複博弈,是解決個體理性與集體理性之間矛盾的方法。只要博弈人具有足夠的耐心(貼現因子足夠大),那麼在滿足博弈人個人理性約束的前提下,博弈人之間就總有多種可能達成合作均衡。

「無名氏定理」之得名,是由於重複博弈促進合作的思想,早就有很多人提出,以致無法追溯到其原創者,於是以「無名氏」名之。數學中,「無名氏定理」一詞通常表示人們普遍同意,且已經經過討論卻未曾發表的定理。為了讓名字更直白一些,Roger Myerson 推薦把這類定理叫做「一般可行性定理」(英語:general feasibility theorem)。

一次性博弈與重複博弈

一次性博弈

兩個共謀犯罪的人被關入監獄,被隔離審訊:

  1. 如果兩個人都不揭發對方,則由於證據不足,每個人都坐牢一年;
  2. 若一人揭發,而另一人沉默,則揭發者因為立功而立即獲釋,沉默者因不合作而入獄五年;
  3. 若互相揭發,則因證據確實,二者都判刑兩年。

對於任何一個囚徒來說,無論對方採取什麼策略,自己都應該背叛。因為

  • 如果對方選擇合作,那麼自己合作的話就要服刑1年,自己背叛的話,就可以無罪釋放;
  • 如果對方背叛,那麼自己合作的話就要服刑5年,自己背叛的話就只服刑2年。

因此任何囚徒為了自身利益,不管對方採取什麼策略,自己都應該選擇背叛。但是,如果兩者都背叛的話,就都要服刑2年,這不是最優結果。

多次博弈的結論

博弈論專家阿克塞爾羅德邀請全世界的學術同行來設計計算機策略,並在一個重複囚徒困境競賽中互相競爭。參賽的程序的差異廣泛地存在於這些方面:算法的複雜性、最初的對抗、寬恕的能力等等。

阿克塞爾羅德發現,當這些對抗被每個選擇不同策略的參與者一再重複了很長時間之後,從利己的角度來判斷,最終「貪婪」策略趨向於減少,而比較「利他」策略更多地被採用。他用這個博弈來說明,通過自然選擇,一種利他行為的機制可能從最初純粹的自私機制進化而來。

最佳確定性策略被認為是「以牙還牙」,這是阿納托爾·拉波波特(Anatol Rapoport)開發並運用到錦標賽中的方法。它是所有參賽程序中最簡單的,只包含了四行BASIC語言,並且贏得了比賽。

「以牙還牙」策略是:第一次與對方合作,從第二次開始,每一次都用對方前一次對待自己的方式來對待它,也就是:如果前一次對方背叛自己,那麼這一次自己就背叛對方;如果前一次對方與自己合作,那麼這次自己就與對方合作。

更好些的策略是「寬恕地以牙還牙」。當你的對手背叛,在下一回合中你無論如何要以小機率(大約是1%~5%)時而合作一下。這是考慮到偶爾要從循環背叛的受騙中復原。當錯誤傳達被引入博弈時,「寬恕地以牙還牙」是最佳的。這意味著有時你的動作被錯誤地傳達給你的對手:你合作但是你的對手聽說你背叛了。

這個令人驚訝的結果啟發我們,也許最成功的為人處世之道就是:用對方對待你的方式來對待他,另外再加上一點兒寬容。

重複博弈詳解

基本報償表如下:

乙合作乙欺騙
甲合作甲得2分,乙得2分甲得0分,乙得6分
甲欺騙甲得6分,乙得0分甲得0分,乙得0分

用 H 代表合作,用 D(deceive) 代表欺騙。

甲的策略是俠義(一報還一報):

  1. 一開始先合作
  2. 你上次合作我就合作,你上次欺騙我就欺驗

乙的策略是流氓:

  1. 一開始先欺騙
  2. 對方上次合作我就欺騙
  3. 對方上次欺騙我就合作
  4. 對方連續兩次欺騙我就欺騙

各個回合雙方的行為如下:

循 環
┌─┐
↓ ↓
循 環
┌─┐
↓ ↓
循 環
┌─┐
↓ ↓

HDDHDDHDD
DDHDDHDDH

026026026
620620620
  1. 第一回合,甲仁厚玩合作H,乙宰客玩欺騙D
  2. 第二回合,甲報復玩欺騙D,乙仍然宰客玩欺騙D
  3. 第三回合,甲仍報復玩欺騙D,乙發現甲並非傻客,於是玩合作H
  4. 第四回合,甲原諒乙,玩合作H;乙卻因甲上次不合作,回頭玩欺騙D宰客

請註意,此序列呈現一個有趣的規律:就是每三個一組,不斷迴圈重複。於是我們很容易算出,博弈兩方平均每個回合的報償有多少:只要取相繼三個回合,作個簡單平均就夠了。甲得到(0+2+6)/3=2.67,乙得到(6+2+0)/3=2.67。顯然,兩者平分秋色,不相上下,誰也不比誰差,誰也不比誰強。

這種循環重複並不是特例。可以證明,有限自動機玩無限重複博弈,其結果最終都會變成循環重複序列。於是,利用類似的辦法,我們可以針對上貼中列出的七種策略,算出每一對策略相博所產生的的平均報償。這些報償可以寫成一個7×7博弈矩陣,如下表所示(其中一些略去了小數,這不影響下面的討論):

                  乙
     傻客  惡棍  冷血  恕道  俠義  流氓  搖擺
    .---------------------------.
  傻客|4,4|0,6|4,4|4,4|4,4|0,6|0,6|
    |---+---+---+---+---+---+---|
  惡棍|6,0|2,2|2,2|2,2|2,2|3,1|2,2|
    |---+---+---+---+---+---+---|
  冷血|4,4|2,2|4,4|4,4|2,2|3,1|2,2|
    |---+---+---+---+---+---+---|
甲 恕道|4,4|2,2|4,4|4,4|3,3|2,2|2,2|
    |---+---+---+---+---+---+---|
  俠義|4,4|2,2|2,2|3,3|2,2|2,2|2,2|
    |---+---+---+---+---+---+---|
  流氓|6,0|1,3|1,3|2,2|2,2|4,4|2,4|
    |---+---+---+---+---+---+---|
  搖擺|6,0|2,2|2,2|2,2|2,2|4,2|3,3|
    .---------------------------.

上面這個表裡面,有帶圈數字的格子都是平衡點。比如,乙玩惡棍策略時,甲無論玩什麼,都不比當惡棍帶來的好處更多,頂多不致受損而已。因此,甲乙雙方都當惡棍,次次都玩欺騙,便是重複囚犯博弈的平衡點之一,此時各方的報償與一次性博弈相同,都是2。

均衡點

觀察一下上面這個表,我們會發現它有多個平衡點。非重複博弈中的均衡點,惡棍對惡棍,雙方永遠玩欺騙,仍然是無限重複博弈的均衡點。無條件合作的傻客策略,仍然不是重複博弈的均衡點理性的人,決不會當傻客。更重要的是,重複博弈引進了許多新的平衡點,其中有不少平衡點,可以實現合作報償(4,4)。這包括恕道策略對恕道策略,恕道策略對冷血策略,冷血策略對冷血策略,流氓策略對流氓策略等,都可以維持雙方的合作。以流氓對流氓為例:第一回合,雙方耍流氓互宰,發現對方不是好惹的之後,雙方轉入合作心態,此後一直維持合作,這樣無限次重複,其平均報償都是4。

事實上,存在這無窮多對有限自動機策略,可以成為無限重複博弈的平衡點,並同時實現雙方的合作。這就是有名的「大眾定理(Folk Theorem)」,又譯作「無名氏定理」。它之得名,是由於重複博弈促進合作的思想,早就有很多人提出,以致無法追溯到其原創者,於是以「無名氏」名之。

特徵特性

大眾定理說明了行為規則的多樣性:有無窮多種行為規則可以支持合作行為。在正常的平衡狀態中,可觀察到的行為可以完全相同的,此即博弈雙方相互合作,不玩欺騙。但其背後的行為規則卻可能大不相同合作,可以是由於雙方都信奉仁厚的恕道主義,也可能是因為雙方都是理性流氓,還可能是因為雙方都一冷血報復作威脅。這些行為規則上的區別,在正常的平衡狀態中,是看不出來的,只有在非正常情況下,或在與外人的交往中,才會表現出來。

行為規則

為說明此點,構想有兩個相互隔離的社會:一個形成了理性流氓式的行為規則,一個形成仁厚恕道的行為規則,他們各自內部都能維持相互合作,這形成了社會的正常狀態。外人但憑觀察這兩個社會中人們的正常行為,看不出他們有什麼區別。現在假設兩個社會打破隔離,相互接觸,會產生甚麼情況?兩套行為規則間會出現激烈的衝突!初次接觸,流氓主義者將把對方當傻客,大宰其客。恕道主義者假設對方是好人,選擇合作,只是在吃了虧之後,才以回宰其客相回報。流氓主義者見對方回宰,以為對方也是跟自己一樣的流氓,於是轉向合作心態,同時預期對方也選擇合作。但恕道主義者根據「以直報怨」的原則,仍然以宰客回報對方上次的欺騙。流氓主義者一看對方不合作,怒從心起,於是報之以宰客,如此循環往復,雙方永遠無法達成合作。

規則衝突

行為規則的衝突,類似於人文學科裡常說的文化衝突。由於行為規則反映了人們對各自行為的穩定預期,一些博弈論者把不同的行為規則解釋為不同的文化信仰,應當是不無道理的。我覺得,重複博弈理論,為我們科學理解許多文化現象,打開了大門。

正是由於行為規則本身的多樣性和複雜性,所以我對成樸文章中過分抬高「一報還一報(tit for tat)」單一規則,將之推崇為美德的起源,始終抱有疑慮。

參考原作

  1. 行為和行為規則
  2. 自動機與博奕策略
  3. 大眾定理與文化沖突

google 雲端文件 p1,p2