無名氏定理：修訂版本之間的差異
（→一次性博弈） |
（→重複博弈詳解） |
||
| （未顯示同用戶所作出之12次版本） | |||
| 第 2 行： | 第 2 行： | ||
英語為 folk theorems ，中文又譯為大眾定理。 | 英語為 folk theorems ，中文又譯為大眾定理。 | ||
| − | + | 單憑理性計算，有限次重複博弈，是解決個體理性與集體理性之間矛盾的方法。只要博弈人具有足夠的耐心(貼現因子足夠大)，那麼在滿足博弈人個人理性約束的前提下，博弈人之間就總有多種可能達成合作均衡。 | |
「無名氏定理」之得名，是由於重複博弈促進合作的思想，早就有很多人提出，以致無法追溯到其原創者，於是以「無名氏」名之。數學中，「無名氏定理」一詞通常表示人們普遍同意，且已經經過討論卻未曾發表的定理。為了讓名字更直白一些，Roger Myerson 推薦把這類定理叫做「一般可行性定理」(英語：general feasibility theorem)。 | 「無名氏定理」之得名，是由於重複博弈促進合作的思想，早就有很多人提出，以致無法追溯到其原創者，於是以「無名氏」名之。數學中，「無名氏定理」一詞通常表示人們普遍同意，且已經經過討論卻未曾發表的定理。為了讓名字更直白一些，Roger Myerson 推薦把這類定理叫做「一般可行性定理」(英語：general feasibility theorem)。 | ||
==一次性博弈與重複博弈== | ==一次性博弈與重複博弈== | ||
| − | === | + | ===一次性博弈=== |
兩個共謀犯罪的人被關入監獄，被隔離審訊： | 兩個共謀犯罪的人被關入監獄，被隔離審訊： | ||
#如果兩個人都不揭發對方，則由於證據不足，每個人都坐牢一年； | #如果兩個人都不揭發對方，則由於證據不足，每個人都坐牢一年； | ||
| 第 16 行： | 第 16 行： | ||
*如果對方背叛，那麼自己合作的話就要服刑5年，自己背叛的話就只服刑2年。 | *如果對方背叛，那麼自己合作的話就要服刑5年，自己背叛的話就只服刑2年。 | ||
因此任何囚徒為了自身利益，不管對方採取什麼策略，自己都應該選擇背叛。但是，如果兩者都背叛的話，就都要服刑2年，這不是最優結果。 | 因此任何囚徒為了自身利益，不管對方採取什麼策略，自己都應該選擇背叛。但是，如果兩者都背叛的話，就都要服刑2年，這不是最優結果。 | ||
| − | === | + | ===多次博弈的結論=== |
博弈論專家阿克塞爾羅德邀請全世界的學術同行來設計計算機策略，並在一個重複囚徒困境競賽中互相競爭。參賽的程序的差異廣泛地存在於這些方面：算法的複雜性、最初的對抗、寬恕的能力等等。 | 博弈論專家阿克塞爾羅德邀請全世界的學術同行來設計計算機策略，並在一個重複囚徒困境競賽中互相競爭。參賽的程序的差異廣泛地存在於這些方面：算法的複雜性、最初的對抗、寬恕的能力等等。 | ||
| 第 28 行： | 第 28 行： | ||
這個令人驚訝的結果啟發我們，也許最成功的為人處世之道就是：用對方對待你的方式來對待他，另外再加上一點兒寬容。 | 這個令人驚訝的結果啟發我們，也許最成功的為人處世之道就是：用對方對待你的方式來對待他，另外再加上一點兒寬容。 | ||
| − | === | + | ===重複博弈詳解=== |
基本報償表如下： | 基本報償表如下： | ||
| 第 36 行： | 第 36 行： | ||
<tr><td>甲欺騙</td><td>甲得6分，乙得0分</td><td>甲得0分，乙得0分</td></tr> | <tr><td>甲欺騙</td><td>甲得6分，乙得0分</td><td>甲得0分，乙得0分</td></tr> | ||
</table> | </table> | ||
| + | |||
| + | 用 H 代表合作，用 D(deceive) 代表欺騙。 | ||
| + | |||
| + | 甲的策略是俠義(一報還一報)： | ||
| + | #一開始先合作 | ||
| + | #你上次合作我就合作，你上次欺騙我就欺驗 | ||
| + | 乙的策略是流氓： | ||
| + | #一開始先欺騙 | ||
| + | #對方上次合作我就欺騙 | ||
| + | #對方上次欺騙我就合作 | ||
| + | #對方連續兩次欺騙我就欺騙 | ||
| + | '''各個回合雙方的行為如下：''' | ||
| + | |||
| + | <table class=nicetable> | ||
| + | <tr><th colspan=2></th><th colspan=3>循 環<br/>┌─┐<br/>↓ ↓</th><th colspan=3>循 環<br/>┌─┐<br/>↓ ↓</th><th colspan=3>循 環<br/>┌─┐<br/>↓ ↓</th></tr> | ||
| + | <tr><th rowspan=2>行<br/>為</th><th>甲</th><th>H</th><th>D</th><th>D</th><th>H</th><th>D</th><th>D</th><th>H</th><th>D</th><th>D</th></tr> | ||
| + | <tr><th>乙</th><th>D</th><th>D</th><th>H</th><th>D</th><th>D</th><th>H</th><th>D</th><th>D</th><th>H</th></tr> | ||
| + | <tr><th rowspan=2>報<br/>償</th><th>甲</th><th>0</th><th>2</th><th>6</th><th>0</th><th>2</th><th>6</th><th>0</th><th>2</th><th>6</th></tr> | ||
| + | <tr><th>乙</th><th>6</th><th>2</th><th>0</th><th>6</th><th>2</th><th>0</th><th>6</th><th>2</th><th>0</th></tr> | ||
| + | </table> | ||
| + | #第一回合，甲仁厚玩合作H，乙宰客玩欺騙D | ||
| + | #第二回合，甲報復玩欺騙D，乙仍然宰客玩欺騙D | ||
| + | #第三回合，甲仍報復玩欺騙D，乙發現甲並非傻客，於是玩合作H | ||
| + | #第四回合，甲原諒乙，玩合作H;乙卻因甲上次不合作，回頭玩欺騙D宰客 | ||
| + | … | ||
| + | |||
| + | 請註意，此序列呈現一個有趣的規律：就是每三個一組，不斷迴圈重複。於是我們很容易算出，博弈兩方平均每個回合的報償有多少：只要取相繼三個回合，作個簡單平均就夠了。甲得到(0+2+6)/3=2.67，乙得到(6+2+0)/3=2.67。顯然，兩者平分秋色，不相上下，誰也不比誰差，誰也不比誰強。 | ||
| + | |||
| + | 這種循環重複並不是特例。可以證明，有限自動機玩無限重複博弈，其結果最終都會變成循環重複序列。於是，利用類似的辦法，我們可以針對上貼中列出的七種策略，算出每一對策略相博所產生的的平均報償。這些報償可以寫成一個7×7博弈矩陣，如下表所示(其中一些略去了小數，這不影響下面的討論)： | ||
| + | : 乙 | ||
| + | : 傻客 惡棍 冷血 恕道 俠義 流氓 搖擺 | ||
| + | : ．－－－－－－－－－－－－－－－－－－－－－－－－－－－． | ||
| + | : 傻客｜４，４｜０，６｜４，４｜４，４｜４，４｜０，６｜０，６｜ | ||
| + | : ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜ | ||
| + | : 惡棍｜６，０｜２，２｜２，２｜２，２｜２，２｜３，１｜２，２｜ | ||
| + | : ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜ | ||
| + | : 冷血｜４，４｜２，２｜４，４｜４，４｜２，２｜３，１｜２，２｜ | ||
| + | : ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜ | ||
| + | :甲 恕道｜４，４｜２，２｜４，４｜４，４｜３，３｜２，２｜２，２｜ | ||
| + | : ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜ | ||
| + | : 俠義｜４，４｜２，２｜２，２｜３，３｜２，２｜２，２｜２，２｜ | ||
| + | : ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜ | ||
| + | : 流氓｜６，０｜１，３｜１，３｜２，２｜２，２｜４，４｜２，４｜ | ||
| + | : ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜ | ||
| + | : 搖擺｜６，０｜２，２｜２，２｜２，２｜２，２｜４，２｜３，３｜ | ||
| + | : ．－－－－－－－－－－－－－－－－－－－－－－－－－－－． | ||
| + | 上面這個表裡面，有帶圈數字的格子都是平衡點。比如，乙玩惡棍策略時，甲無論玩什麼，都不比當惡棍帶來的好處更多，頂多不致受損而已。因此，甲乙雙方都當惡棍，次次都玩欺騙，便是重複囚犯博弈的平衡點之一，此時各方的報償與一次性博弈相同，都是2。 | ||
| + | |||
| + | '''均衡點''' | ||
| + | |||
| + | 觀察一下上面這個表，我們會發現它有多個平衡點。非重複博弈中的均衡點，惡棍對惡棍，雙方永遠玩欺騙，仍然是無限重複博弈的均衡點。無條件合作的傻客策略，仍然不是重複博弈的均衡點理性的人，決不會當傻客。更重要的是，重複博弈引進了許多新的平衡點，其中有不少平衡點，可以實現合作報償(4,4)。這包括恕道策略對恕道策略，恕道策略對冷血策略，冷血策略對冷血策略，流氓策略對流氓策略等，都可以維持雙方的合作。以流氓對流氓為例:第一回合，雙方耍流氓互宰，發現對方不是好惹的之後，雙方轉入合作心態，此後一直維持合作，這樣無限次重複，其平均報償都是4。 | ||
| + | |||
| + | 事實上，存在這無窮多對有限自動機策略，可以成為無限重複博弈的平衡點，並同時實現雙方的合作。這就是有名的「大眾定理(Folk Theorem)」，又譯作「無名氏定理」。它之得名，是由於重複博弈促進合作的思想，早就有很多人提出，以致無法追溯到其原創者，於是以「無名氏」名之。 | ||
| + | |||
| + | '''特徵特性''' | ||
| + | |||
| + | 大眾定理說明了行為規則的多樣性:有無窮多種行為規則可以支持合作行為。在正常的平衡狀態中，可觀察到的行為可以完全相同的，此即博弈雙方相互合作，不玩欺騙。但其背後的行為規則卻可能大不相同合作，可以是由於雙方都信奉仁厚的恕道主義，也可能是因為雙方都是理性流氓，還可能是因為雙方都一冷血報復作威脅。這些行為規則上的區別，在正常的平衡狀態中，是看不出來的，只有在非正常情況下，或在與外人的交往中，才會表現出來。 | ||
| + | |||
| + | '''行為規則''' | ||
| + | |||
| + | 為說明此點，構想有兩個相互隔離的社會：一個形成了理性流氓式的行為規則，一個形成仁厚恕道的行為規則，他們各自內部都能維持相互合作，這形成了社會的正常狀態。外人但憑觀察這兩個社會中人們的正常行為，看不出他們有什麼區別。現在假設兩個社會打破隔離，相互接觸，會產生甚麼情況？兩套行為規則間會出現激烈的衝突！初次接觸，流氓主義者將把對方當傻客，大宰其客。恕道主義者假設對方是好人，選擇合作，只是在吃了虧之後，才以回宰其客相回報。流氓主義者見對方回宰，以為對方也是跟自己一樣的流氓，於是轉向合作心態，同時預期對方也選擇合作。但恕道主義者根據「以直報怨」的原則，仍然以宰客回報對方上次的欺騙。流氓主義者一看對方不合作，怒從心起，於是報之以宰客，如此循環往復，雙方永遠無法達成合作。 | ||
| + | |||
| + | '''規則衝突''' | ||
| + | |||
| + | 行為規則的衝突，類似於人文學科裡常說的文化衝突。由於行為規則反映了人們對各自行為的穩定預期，一些博弈論者把不同的行為規則解釋為不同的文化信仰，應當是不無道理的。我覺得，重複博弈理論，為我們科學理解許多文化現象，打開了大門。 | ||
| + | |||
| + | 正是由於行為規則本身的多樣性和複雜性，所以我對成樸文章中過分抬高「一報還一報(tit for tat)」單一規則，將之推崇為美德的起源，始終抱有疑慮。 | ||
| + | |||
| + | '''參考原作''' | ||
| + | #[http://www.yhcw.net/yuner/articles/prison1.html 行為和行為規則] | ||
| + | #[http://www.yhcw.net/yuner/articles/prison2.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年，自己背叛的話，就可以無罪釋放；
- 如果對方背叛，那麼自己合作的話就要服刑5年，自己背叛的話就只服刑2年。
因此任何囚徒為了自身利益，不管對方採取什麼策略，自己都應該選擇背叛。但是，如果兩者都背叛的話，就都要服刑2年，這不是最優結果。
多次博弈的結論
博弈論專家阿克塞爾羅德邀請全世界的學術同行來設計計算機策略，並在一個重複囚徒困境競賽中互相競爭。參賽的程序的差異廣泛地存在於這些方面：算法的複雜性、最初的對抗、寬恕的能力等等。
阿克塞爾羅德發現，當這些對抗被每個選擇不同策略的參與者一再重複了很長時間之後，從利己的角度來判斷，最終「貪婪」策略趨向於減少，而比較「利他」策略更多地被採用。他用這個博弈來說明，通過自然選擇，一種利他行為的機制可能從最初純粹的自私機制進化而來。
最佳確定性策略被認為是「以牙還牙」，這是阿納托爾·拉波波特(Anatol Rapoport)開發並運用到錦標賽中的方法。它是所有參賽程序中最簡單的，只包含了四行BASIC語言，並且贏得了比賽。
「以牙還牙」策略是:第一次與對方合作，從第二次開始，每一次都用對方前一次對待自己的方式來對待它，也就是：如果前一次對方背叛自己，那麼這一次自己就背叛對方；如果前一次對方與自己合作，那麼這次自己就與對方合作。
更好些的策略是「寬恕地以牙還牙」。當你的對手背叛，在下一回合中你無論如何要以小機率(大約是1%~5%)時而合作一下。這是考慮到偶爾要從循環背叛的受騙中復原。當錯誤傳達被引入博弈時，「寬恕地以牙還牙」是最佳的。這意味著有時你的動作被錯誤地傳達給你的對手：你合作但是你的對手聽說你背叛了。
這個令人驚訝的結果啟發我們，也許最成功的為人處世之道就是：用對方對待你的方式來對待他，另外再加上一點兒寬容。
重複博弈詳解
基本報償表如下：
| 乙合作 | 乙欺騙 | |
| 甲合作 | 甲得2分，乙得2分 | 甲得0分，乙得6分 |
| 甲欺騙 | 甲得6分，乙得0分 | 甲得0分，乙得0分 |
用 H 代表合作，用 D(deceive) 代表欺騙。
甲的策略是俠義(一報還一報)：
- 一開始先合作
- 你上次合作我就合作，你上次欺騙我就欺驗
乙的策略是流氓：
- 一開始先欺騙
- 對方上次合作我就欺騙
- 對方上次欺騙我就合作
- 對方連續兩次欺騙我就欺騙
各個回合雙方的行為如下：
| 循 環 ┌─┐ ↓ ↓ | 循 環 ┌─┐ ↓ ↓ | 循 環 ┌─┐ ↓ ↓ | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 行 為 | 甲 | H | D | D | H | D | D | H | D | D |
| 乙 | D | D | H | D | D | H | D | D | H | |
| 報 償 | 甲 | 0 | 2 | 6 | 0 | 2 | 6 | 0 | 2 | 6 |
| 乙 | 6 | 2 | 0 | 6 | 2 | 0 | 6 | 2 | 0 | |
- 第一回合，甲仁厚玩合作H，乙宰客玩欺騙D
- 第二回合，甲報復玩欺騙D，乙仍然宰客玩欺騙D
- 第三回合，甲仍報復玩欺騙D，乙發現甲並非傻客，於是玩合作H
- 第四回合，甲原諒乙，玩合作H;乙卻因甲上次不合作，回頭玩欺騙D宰客
…
請註意，此序列呈現一個有趣的規律：就是每三個一組，不斷迴圈重複。於是我們很容易算出，博弈兩方平均每個回合的報償有多少：只要取相繼三個回合，作個簡單平均就夠了。甲得到(0+2+6)/3=2.67，乙得到(6+2+0)/3=2.67。顯然，兩者平分秋色，不相上下，誰也不比誰差，誰也不比誰強。
這種循環重複並不是特例。可以證明，有限自動機玩無限重複博弈，其結果最終都會變成循環重複序列。於是，利用類似的辦法，我們可以針對上貼中列出的七種策略，算出每一對策略相博所產生的的平均報償。這些報償可以寫成一個7×7博弈矩陣，如下表所示(其中一些略去了小數，這不影響下面的討論)：
- 乙
- 傻客 惡棍 冷血 恕道 俠義 流氓 搖擺
- ．－－－－－－－－－－－－－－－－－－－－－－－－－－－．
- 傻客｜４，４｜０，６｜４，４｜４，４｜４，４｜０，６｜０，６｜
- ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜
- 惡棍｜６，０｜２，２｜２，２｜２，２｜２，２｜３，１｜２，２｜
- ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜
- 冷血｜４，４｜２，２｜４，４｜４，４｜２，２｜３，１｜２，２｜
- ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜
- 甲 恕道｜４，４｜２，２｜４，４｜４，４｜３，３｜２，２｜２，２｜
- ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜
- 俠義｜４，４｜２，２｜２，２｜３，３｜２，２｜２，２｜２，２｜
- ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜
- 流氓｜６，０｜１，３｜１，３｜２，２｜２，２｜４，４｜２，４｜
- ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜
- 搖擺｜６，０｜２，２｜２，２｜２，２｜２，２｜４，２｜３，３｜
- ．－－－－－－－－－－－－－－－－－－－－－－－－－－－．
上面這個表裡面，有帶圈數字的格子都是平衡點。比如，乙玩惡棍策略時，甲無論玩什麼，都不比當惡棍帶來的好處更多，頂多不致受損而已。因此，甲乙雙方都當惡棍，次次都玩欺騙，便是重複囚犯博弈的平衡點之一，此時各方的報償與一次性博弈相同，都是2。
均衡點
觀察一下上面這個表，我們會發現它有多個平衡點。非重複博弈中的均衡點，惡棍對惡棍，雙方永遠玩欺騙，仍然是無限重複博弈的均衡點。無條件合作的傻客策略，仍然不是重複博弈的均衡點理性的人，決不會當傻客。更重要的是，重複博弈引進了許多新的平衡點，其中有不少平衡點，可以實現合作報償(4,4)。這包括恕道策略對恕道策略，恕道策略對冷血策略，冷血策略對冷血策略，流氓策略對流氓策略等，都可以維持雙方的合作。以流氓對流氓為例:第一回合，雙方耍流氓互宰，發現對方不是好惹的之後，雙方轉入合作心態，此後一直維持合作，這樣無限次重複，其平均報償都是4。
事實上，存在這無窮多對有限自動機策略，可以成為無限重複博弈的平衡點，並同時實現雙方的合作。這就是有名的「大眾定理(Folk Theorem)」，又譯作「無名氏定理」。它之得名，是由於重複博弈促進合作的思想，早就有很多人提出，以致無法追溯到其原創者，於是以「無名氏」名之。
特徵特性
大眾定理說明了行為規則的多樣性:有無窮多種行為規則可以支持合作行為。在正常的平衡狀態中，可觀察到的行為可以完全相同的，此即博弈雙方相互合作，不玩欺騙。但其背後的行為規則卻可能大不相同合作，可以是由於雙方都信奉仁厚的恕道主義，也可能是因為雙方都是理性流氓，還可能是因為雙方都一冷血報復作威脅。這些行為規則上的區別，在正常的平衡狀態中，是看不出來的，只有在非正常情況下，或在與外人的交往中，才會表現出來。
行為規則
為說明此點，構想有兩個相互隔離的社會：一個形成了理性流氓式的行為規則，一個形成仁厚恕道的行為規則，他們各自內部都能維持相互合作，這形成了社會的正常狀態。外人但憑觀察這兩個社會中人們的正常行為，看不出他們有什麼區別。現在假設兩個社會打破隔離，相互接觸，會產生甚麼情況？兩套行為規則間會出現激烈的衝突！初次接觸，流氓主義者將把對方當傻客，大宰其客。恕道主義者假設對方是好人，選擇合作，只是在吃了虧之後，才以回宰其客相回報。流氓主義者見對方回宰，以為對方也是跟自己一樣的流氓，於是轉向合作心態，同時預期對方也選擇合作。但恕道主義者根據「以直報怨」的原則，仍然以宰客回報對方上次的欺騙。流氓主義者一看對方不合作，怒從心起，於是報之以宰客，如此循環往復，雙方永遠無法達成合作。
規則衝突
行為規則的衝突，類似於人文學科裡常說的文化衝突。由於行為規則反映了人們對各自行為的穩定預期，一些博弈論者把不同的行為規則解釋為不同的文化信仰，應當是不無道理的。我覺得，重複博弈理論，為我們科學理解許多文化現象，打開了大門。
正是由於行為規則本身的多樣性和複雜性，所以我對成樸文章中過分抬高「一報還一報(tit for tat)」單一規則，將之推崇為美德的起源，始終抱有疑慮。
參考原作
google 雲端文件 p1,p2
