Werden wir Helden für einen Tag

Home | About | Archive

S4 programming: iterated prisoners' dilemma

Posted on Feb 9, 2012 by Chung-hong Chan

一直好想研究 R 的 Object oriented programming (OOP) 方法。我對 OOP 的認識不深,之前只求其寫過點 Python 的 OOP code 交功課。現在想試下用 R 玩下 OOP 。 R 的 OOP 系統最少有三個,分別是 S3, S4 和 R5 。 S3 遲早會被淘汰, R5 又太新,中間點的 S4 似乎最多人用。以下的 code ,是想模疑 Dawkins 在 Selfish Gene 一書內的電腦模疑比賽。
先要說甚麼是 prisoners' dilemma 。這是 Game theory 的經典遊戲。假設有甲和乙,兩人是同伴,分別被處於在兩個不同的房間,甲和乙不可以溝通。甲和乙可以選擇「合作」和「背叛」。如果甲和乙同時選擇「合作」,雙方各可以獲得三蚊。如果甲和乙同時選擇「背叛」,雙方只可以獲得一蚊。如果甲選「合作」而乙選「背叛」,乙可獲五蚊,而乙無獎。反之亦然。
根據以上的條件, payoff matrix 就是

合作 (0) 背叛 (1)
合作 (0) 3.3 0,5
背叛 (1) 5,0 1,1

由上圖可見,如果雙方同時選合作,所得總和是 3+3 = 6 。其他三格分別只有 5 和 2 。故此,雙方都合作理論上是最有利的。但經濟學理論已經證明,如果雙方無法溝通又或者彼此沒有信任的話,雙方最有可能是會選擇背叛。原因是就一方自己的利益而言,選擇合作有一半機會獲得 0 元,故此期望值是 (1/2*3 + 1/2*0) = 1.5 元。如果選背叛,最少都可以獲得 1 元,期望值是 (1/2*5 + 1/2*1) = 3 。但整體而言此結果最差,因為兩人總共也只可獲得 2 元。現實的例子是,甲店和乙店都是便利店,他們可選擇同時將可樂減至兩元(背叛)。或者達成協定將價錢保持在四元(合作)。如果甲乙店沒有溝通或互不信任,兩店不會突然將價格保持在四元 (如別店沒有保持價格,自店就賣得比人貴,消費者會到別店購買可樂) ,故此只會同時減價。爆發減價戰。
如果只是一次性的 prisoners' dilemma ,結論如上。但如果 prisoners' dilemma 是不停重複發生的,結果又如何?
甲乙雙方選合作和背叛之後派彩,之後又再選合作和背叛,如此類推兩百次之後,以誰人的派彩總數決定勝負。到底要怎樣的策略才最成功?此類問題稱之為 iterated prisoners' dilemma 。策略是要跟據之前的勝負紀錄作出合理的選擇。
當然,你可以根據單次性的 prisoners' dilemma 企硬二百次都選背叛,但這是否最好的策略?
話說當年曾有人舉行比賽,找出最成功的策略。如果有讀過 Selfish Gene 一書,就會知道一種稱成 tit for tat 的策略在兩次比賽中勝出。所謂 tit for tat ,就是「以牙還牙」。先是選合作,如果對上一次對方合作,就繼續合作:如果對方上次背叛,今次就選背叛。這個簡單策略,只會回想上回合的結果,不「記仇」。 Dawkins 根據此結果說明了生物之間合作的原因。
我想模疑的,正是 iterated prisoners' dilemma 。我想證明 tit for tat 是否最成功的策略。
如果你看以下的 code ,先會發現寫了一個叫 agent 的 object 。此物有大家共用的數據儲存位置和 method 。另外,以 inheritance 的方法寫出用其他策略的 agent 。不同 agent 不同之處只是 play 的方法。 ((以下的 S4 code 並不是全然的 OOP ,例如在大亂鬥的一部份,不是 OO 的,因為沒有太大心機寫全 OO 的 code 。亂鬥部份是 hea 寫,是 quick and dirty 的。)) 以下是參加今次比賽的七種 agents:

  1. agent: default 的 agent ,完全沒有記憶,隨機地選擇合作或背叛。
  2. tit4tat: 以牙還牙,只根據上一回合的紀錄作選擇。如上一次被背叛,今次才會選背叛,否則全選合作。
  3. pavlov: 贏谷輸縮。如果上次獲得多於 1 元,就繼續用上次的選擇,否則轉成上次的反面。
  4. grudger: 小器鬼。一開始只選合作。萬一被背叛,以後全選背叛。
  5. devil: 魔鬼。沒有記憶,只會選背叛。
  6. angel: 天使。沒有記憶,只會選合作。
  7. statistician: 統計學家。這個策略我想原來的比賽是沒有的,是我加落去的。策略是最初四回合合作,之後四回背叛。之後分析之前所有記憶中選合作和背叛的回合,並計算合和背叛的平均派彩。之後選用平均派彩數較高的選擇。

根據這次的模疑,最成功至最差勁的策略分別是:

  1. statistician: 3182
  2. tit4tat: 3020
  3. pavlov: 2942
  4. grudger: 2875
  5. devil: 2840
  6. angel: 2112
  7. agent: 2011

這次比賽是由 statistician 勝出。為何 statistician 可勝,原因是它在「捉路」。但當然,它捉到的路也是很 crude 的。
你也可以 reuse 以下的 code 寫自己的 agent 作模疑,或者你可以寫出比 statistician 更厲害的 agent 也說不定。

source code: tit4tat

在 Axelrod 的 The evolution of cooperation 一書講到,成功的策略要有以下四個元素:

  1. Nice: 如果對手沒有背叛,你不會率先背叛。
  2. Retaliating: 並不能全然合作,有時要反擊。
  3. Forgiving: 對手如不再背叛,應該選合作,而不是選擇報仇。
  4. Non-envious: 並不因為對手高分而眼紅。

不知道 statistician 是否符合以上四點。


Powered by Jekyll and profdr theme