game theory -5168 │愛情公寓交友網站與聊天室

還沒登入愛情公寓嗎？還沒加入愛情公寓嗎？馬上進入公寓和 10,549,330 個住戶交朋友～

紅包抽抽樂！小資變土豪！

素人也能成為明日之星！

移除此區廣告請加入VIP

檔案狀態:

住戶編號:2044027

5168 的日記本

快速選單

pareto ^^ 《前一篇

後一篇》 c'est superbe

回應

給他日記貼紙

給他愛的鼓勵

檢舉

篇名: game theory
作者: 5168	日期: 2011.01.16　　天氣: 　心情:

羅伯特·阿克塞爾羅德在其著作《合作的進化》中，探索了經典囚徒困境情景的一個擴展，並把它稱作「重複的囚徒困境」（IPD）。在這個博弈中，參與者必須反覆地選擇他們彼此相關的策略，並且記住他們以前的對抗。阿克塞爾羅德邀請全世界的學術同行來設計計算機策略，並在一個重複囚徒困境競賽中互相競爭。參賽的程序的差異廣泛地存在於這些方面：演算法的複雜性、最初的對抗、寬恕的能力等等。
阿克塞爾羅德發現，當這些對抗被每個選擇不同策略的參與者一再重複了很長時間之後，從利己的角度來判斷，最終「貪婪」策略趨向於減少，而比較「利他」策略更多地被採用。他用這個博弈來說明，通過自然選擇，一種利他行為的機制可能從最初純粹的自私機制進化而來。
最佳確定性策略被認為是「以牙還牙」，這是阿納托爾·拉波波特（Anatol Rapoport）開發並運用到錦標賽中的方法。它是所有參賽程序中最簡單的，只包含了四行BASIC語言，並且贏得了比賽。這個策略只不過是在重複博弈的開頭合作，然後，採取你的對手前一回合的策略。更好些的策略是「寬恕地以牙還牙」。當你的對手背叛，在下一回合中你無論如何要以小機率（大約是1%-5%）時而合作一下。這是考慮到偶爾要從循環背叛的受騙中復原。當錯誤傳達被引入博弈時，「寬恕地以牙還牙」是最佳的。這意味著有時你的動作被錯誤地傳達給你的對手：你合作但是你的對手聽說你背叛了。
通過分析高分策略，阿克塞爾羅德指定了策略獲得成功的幾個必要條件。
友善：最重要的條件是策略必須「友善」，這就是說，不要在對手背叛之前先背叛。幾乎所有的高分策略都是友善的。因此，完全自私的策略僅僅出於自私的原因，也永遠不會首先打擊其對手。
報復：但是，阿克斯洛德主張，成功的策略必須不是一個盲目樂觀者。要始終報復。一個非報復策略的例子是始終合作。這是一個非常糟糕的選擇，因為「下流」策略將殘酷地剝削這樣的傻瓜。
寬恕：成功策略的另一個品質是必須要寬恕。雖然它們不報復，但是如果對手不繼續背叛，它們會一再退卻到合作。這停止了報復和反報復的長期進行，最大化了得分點數。
不嫉妒：最後一個品質是不嫉妒，就是說不去爭取得到高於對手的分數（對於「友善」的策略來說這也是不可能的，也就是說「友善」的策略永遠無法得到高於對手的分數）。
因此，阿克塞爾羅德得到一種給人以烏托邦印象的結論，認為自私的個人為了其自私的利益會趨向友善、寬恕和不嫉妒。阿克塞爾羅德關於重複囚徒困境的研究的重要結論之一，是友善的傢伙能先完成交易。
重新考慮經典的囚徒困境一節中給定的軍備競賽模型：結論是，只是理性策略增進了軍事力量，似乎兩個國家都寧可花費其GDP在槍炮而不是黃油上。有趣的是，企圖說明對抗國家實際上以這種方式（在「重複囚徒困境假定」下的不同時期，軍費支出在「高」和「低」之間反覆）競賽的嘗試，卻經常表明假定的軍備競賽並沒有如預想的那樣出現。（例如希臘人和土耳其人的軍費支出，看來並不像遵循「以牙還牙」的重複囚徒困境式的軍備競賽，卻更可能是被其國內的政策所驅使。）這可能是一次性博弈和重複性博弈中的理性行為不同的例子。
對一次性囚徒困境博弈來說，最佳（點數最大化的）策略是簡單地背叛；正如前面解釋的，無論對手的行動可能是什麼，這都是真實的。但是，在重複的囚徒困境博弈中，最佳策略依賴於可能的對手的策略，和他們怎樣對背叛和合作作出反應。例如，考慮這樣一個人群，那裡每個人每次都背叛，除了一個人是遵循以牙還牙策略。這個人處於一種輕微的不利地位，因為第一回合的損失。在這樣的人群中，對這個人來說最佳策略就是每次都背叛。在一個有一定的百分比的總背叛者而剩下的則是以牙還牙者的人群中，對個人來說的最佳策略依賴於這個百分比和博弈的長度。
一般有兩種方法得到最佳策略：
貝葉斯納什均衡：如果對抗策略的統計分布能被確定（例如，50％以牙還牙，50％一直合作），就能從數學上獲得最佳的相對策略[4]。
已經有了人群的蒙特卡羅模擬，在這裡低分個人消失了，高分個人一再被生產出來（一種獲得最佳策略的天才演算法）。決賽人群中的演算法合成通常依賴於初賽人群中的演算法合成。
儘管以牙還牙始終被認為是最可靠的基本策略，但是在重複囚徒困境的20周年紀念賽中，來英國南安普敦大學的一個小組（由尼古拉斯·詹寧斯（Nicholas Jennings）[1] 領導，包括了拉蒂普·達什（Rajdeep Dash）、薩瓦帕里·拉姆瓊（Sarvapali Ramchurn）、亞歷克斯·羅傑斯（Alex Rogers）斯和皮魯克里士南·維特林根（Perukrishnen Vytelingum））介紹了一個新的策略，這個策略證明了它比以牙還牙更成功。這個策略依賴於程序之間的合作，為單一程序中獲得了最高的點數。南安普敦大學提交了60個程序參與競賽，這些程序的開頭被設計成通過一組5到10個的動作去彼此識別。一旦這些識別被作出，一個程序將總是合作，其他程序則總是背叛，保證背叛者得到最大的點數。如果程序識別出它在操作一個非南安普敦參與者，這程序將持續地背叛，企圖去最小化競爭程序的得分。結果[5]，這個策略以獲得前3位結束了競賽，也得到了大量接近底部的位置。雖然這個策略顯著地證明了比以牙還牙有效，但是這是因為利用了下述事實：在這個特殊的競賽中，多重通道是被允許的。在一方只能控制單一參與者的競賽中，以牙還牙確實是更好的策略。
如果重複囚徒困境將被精確地重複N次，已知N是一個常數，那麼會產生另一個有趣的事實。納什均衡就是每次都背叛。這很容易用歸納法證明。你也可以在最後的回合背叛，既然你的對手將沒有機會懲罰你。因此，你們都將在最後的回合背叛。這時，你可以在倒數第二回合中背叛，既然最後一回無論你做什麼，你的對手都將背叛。依此類推。為了合作以保持請求，這時未來必須對兩個參與者來說是不確定的。一個解決方案是讓博弈總次數N變成隨機的。對未來的預期必須是無法確定的長度。
另一個單獨的案例是「永不停止」的囚徒困境。這個博弈被重複很多次，而且你的分數是一個平均數（當然是用計算機計算的）。
囚徒困境博弈是某些人類合作和信任理論的基礎。假定囚徒困境能夠模擬需要信任的兩人之間的交流，群體的合作行為可以用有多個參與者的、重複博弈的變體來模擬。這從而引起了許許多多學者經久不衰的興趣。1975年，格羅夫曼（Grofman）和普爾（Pool）估計，致力於這方面研究的學術文章，數量超過2000篇。

標籤:

瀏覽次數:73 人氣指數:73 累積鼓勵:0

切換閱讀模式

回應

給他日記貼紙

給他愛的鼓勵

檢舉

給本文愛的鼓勵：