囚徒困境(Prisoner's Dilemma)

囚徒困境是博弈論的非零和博弈中具代表性的例子,反映個人最佳選擇並非團體最佳選擇。雖然困境本身只屬模型性質,但現實中的價格競爭、環境保護等方面,也會頻繁出現類似情況。

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

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

囚徒困境的主旨為,囚徒們雖然彼此合作,堅不吐實,可為全體帶來最佳利益(無罪開釋),但在資訊不明的情況下,因為出賣同夥可為自己帶來利益(縮短刑期),也因為同夥把自己招出來可為他帶來利益,因此彼此出賣雖違反最佳共同利益,反而是自己最大利益所在。這種情況被稱為是『納許平衡』。

納許平衡又稱為非合作賽局平衡,是博弈論的一個重要概念,以約翰·納許命名。納許平衡定義為:如果某情況下無一參與者可以獨自行動而增加收益,則此策略組合被稱為納許平衡點。

Update 20150523:

納許於2015年05月23日於New Jersey高速公路發生車禍喪命,得年86歲,讓我們一起為這位偉大的數學家/經濟學家哀悼。新聞備份

另一個囚徒困境的例子

某個案子的兩個嫌疑犯被分開審訊,警官分別告訴兩個囚犯,如果你招供,而對方不招供,則你將被立即釋放,而對方將被判刑十年;如果兩人均招供,將均被判刑兩 年。如果兩人均不招供,將最有利,只被判刑半年。 於是,兩人同時陷入招供還是不招供的兩難處境。 但兩人無法溝通,於是從各自的利益角度出發,都依據各自的理性而選擇了招供, 這種情況就稱為納許平衡點。

用程序來描述的話,變成:

用表格來描述的話,變成:(蠻像數位電子學裡面的TTL真值表)

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

兩個囚犯符合自己利益的選擇是坦白招供,原本對雙方都有利的策略不招供從而均被判刑半年就不會出現。事實上,這樣兩人都選擇坦白的策略以及因此被判兩年的結局被稱作是「納許平衡」(也叫非合作均衡),換言之,在此情況下,無一參與者可以「獨自行動」(即單方面改變決定)而增加收穫。

「認罪減刑」之不可行

囚徒困境的結論是許多國家中認罪減刑(英文:plea bargain)被禁止的原因之一。囚徒困境帶來的結論是:如果有二個罪犯,其中一人犯罪而另外一人是無辜的,犯罪者會為了減刑坦白一切甚至冤枉清白者(單獨背叛)。最糟糕的情況是,如果他們二人都被判入獄,坦白的犯罪者刑期少,堅持無罪的冤枉者刑期反而更多。

那麼,如果在競爭的次數是『有限次』甚至是『無限次』的情況之下,要怎麼樣才可以逃避『納許平衡』,在競爭中取得領先(贏家)呢?再另外一篇『以牙還牙』中我們再來討論。

2008 年有人跳出來打破這個理論

MIT的一位計算機科學博士生的博士論文獲得2008年度美國計算機協會學位論文獎——認為經濟學家的推測是錯誤的,找到納許平衡點是幾乎不可能的事。 目前擔任MIT電機工程和計算機科學系助理教授的Constantinos Daskalakis與 UC伯克利的Christos Papadimitriou、英國利物浦大學的Paul Goldberg合作,證明對某些博弈來說,窮全世界所有計算機之力,在整個宇宙壽命的時間內也計算不出納許平衡點。Daskalakis相信,計算機找不到,人類也不可能找到。

  1. 參考:賽局理論(Game Theory)
  2. 參考:零和與非零合?以牙還牙(Tit for tat)
理論 Theory 方法論 Methodology 囚徒困境 納許平衡 納許均衡 以牙還牙