約翰·納什的均衡理論在經濟理論中是普遍存在的，但一項新的研究表明，通常不可能有效地達成。
所有的游戲都有納什均衡。但參與者能否達到？
1950年，數(shù)學家約翰·納什（John Nash）——后來在書和電影“美麗的心靈”中出現(xiàn)而更知名——寫了一篇只有兩頁的論文，改變了經濟學理論。他的關鍵卻簡單的想法是，任何競爭游戲都有一個均衡狀態(tài)，在均衡狀態(tài)下，每個玩家采取策略集合中的一種策略，且沒有玩家可以通過單方面切換到不同的策略來贏得更多的利益。
納什的均衡概念在1994年獲得諾貝爾經濟學獎，它不僅在經濟學中，而且在心理學，進化生物學和許多其他領域中，為理解戰(zhàn)略行為提供了一個統(tǒng)一的框架。芝加哥大學的另一位經濟學諾貝爾獎得主羅杰·米森（Roger Myerson）寫道：“它對經濟理論的影響與生物科學中DNA雙螺旋的發(fā)現(xiàn)相當?！?/p>
當參與者處于均衡狀態(tài)時，沒有人有理由去偏離這種狀態(tài)?？墒牵瑓⑴c者是如何達到均衡狀態(tài)呢？這就好比，一個滾球在下坡過程中可能會停留在山谷里而不再繼續(xù)，同樣的，并沒有明顯的力量指導參與者走向納什均衡。
斯坦福大學理論計算機科學家Tim Roughgarden說：“它一直是微觀經濟學家的一個刺。他們使用這些均衡概念分析即將處于均衡狀態(tài)的人們，但并不總能令人滿意的解釋為什么人們將走向納什均衡，而不僅僅只是在摸索?！?/p>
如果人們只玩一次游戲，期望他們找到一個均衡點往往是不合理的。這是特別是當每個玩家只知道游戲的不同結果對他自己的價值，而不知道他的同伴的情況，而這在現(xiàn)實世界中是典型的場景。但是，如果人們可以反復執(zhí)行同樣的游戲，也許他們可以從早期的回合中學習，并迅速地將自己轉向均衡策略和狀態(tài)。然而，找到這種有效的學習方法的嘗試往往徒勞無功。
加利福尼亞大學伯克利分校理論計算機科學博士學位的Aviad Rubinstein說：“經濟學家提出了如何快速收斂到均衡狀態(tài)的機制。但是對于每個這樣的機制，你可以建立一些簡單的游戲規(guī)則，卻不能運作。”
現(xiàn)在，海法技術與以色列理工學院的數(shù)學家魯賓斯坦和雅科夫·巴布奇寧科已經對此困局進行解釋。在去年9月發(fā)布的一篇論文中，他們證明，沒有任何適應策略的方法可以應對以往的游戲并使其有效地收斂到納什均衡，無論這個方法多么聰明、符合常識、或富有創(chuàng)造性，甚至連近似的納什均衡都無法達到?！斑@是一個非常徹底的消極結果”，Roughgarden說。
經濟學家經常使用納什均衡分析來證明他們提出的經濟改革是有道理的。但新的結果表明，經濟學家不能相信游戲玩家將達到納什均衡，除非他們可以證明特定游戲的特殊性。希伯來大學的計算機科學家Noam Nisan說：“如果你想弄清楚你的游戲是否容易找到一個均衡點，那么你必須提供理由?！?/p>
多人游戲
在一些簡單的游戲中，很容易發(fā)現(xiàn)納什均衡。例如，如果我喜歡中國菜，而你更喜歡意大利菜，但是我們最強烈的喜好是一起吃飯，兩個明顯的均衡是我們兩個人去中國餐館或我們兩個人去意大利餐廳。即使我們開始只知道自己的喜好而且不能在比賽之前交流策略，我們也并不會因為花太多時間去深入了解彼此的偏好而導致錯過聯(lián)系的機會從而只能孤獨的晚餐，我們很有希望找到一個，或者另一個均衡。
但是想象一下，如果晚餐計劃涉及100人，每個人都決定了他喜歡和什么人共進晚餐，同時沒有人知道其他任何人的喜好。納什在1950年證明，即使像這樣的大型復雜的游戲，也總是存在一個均衡（至少在策略的概念被擴大以允許隨機選擇，比如你有60％概率選擇中國餐館，的情況下是成立的 ）?？上Ъ{什在2015年因車禍而死亡，他沒有給出達到均衡的計算方法。
阿維亞·魯賓斯坦（Aviad Rubinstein）幫助表明，玩家不一定會發(fā)現(xiàn)納什均衡。
Tselil Schramm通過潛入Nash的證明過程，Babichenko和Rubinstein能夠表明，一般來說，玩家無法找到近似納什均衡的路徑，除非他們表達了幾乎所有關于他們各自的喜好。隨著游戲中玩家的數(shù)量的增加，這種溝通所有需求的時間迅速增長到足以令人望而卻步。
例如，在100人的餐廳游戲中，有2100種可能的結果，因此每個玩家必須共享2100種偏好。相比之下，自大爆炸以來已經過去的秒數(shù)只有2^59。
這種通信瓶頸意味著，任意方法都不可能通過從一輪到另一輪的適應策略來指導玩家有效地達到納什均衡，至少對于一些復雜游戲的這樣的（例如具有復雜偏好的100人玩家餐廳游戲）。畢竟，在每一輪中，玩家只會學到一點新信息：其他玩家對某種晚餐安排有多滿意。因此，他們需要2^100輪游戲來知道彼此價值觀（而在此之前中國和意大利餐館可能都已經關門了）。
耶路撒冷希伯來大學游戲理論家塞爾古·哈特（Sergiu Hart）說：“如果這將比宇宙演化花費更長的時間，那當然完全沒有用?！?/p>
玩家為找出納什均衡，有時候需要知道對方所有的價值觀，這看起來很自然。然而在現(xiàn)實中，這往往是難以實現(xiàn)的一點，即使玩家愿意達到一個接近納什均衡且已經足夠好的近似納什均衡。這是新的論文提出的一個重要的發(fā)現(xiàn)。
Babichenko和Rubinstein的結果并不意味著所有（甚至大部分）的游戲都將受到這個限制，也就是說，只有一些游戲會。經濟學家用來建?，F(xiàn)實世界的許多游戲都有額外的構架，從而大大減少了每個玩家必須溝通的信息量。例如，如果我們每個人都選擇我們早上通勤的兩條路線之一，那么你可能不在乎每個路線上有哪些車手 - 你只需要路線上有多少車。這意味著你的收藏偏好將具有很高的對稱性，你可以將其全部內容轉換成兩個選擇好的句子，而不是2^100個。
經濟學家可以使用這樣的論據來證明為什么特定的游戲是可以達到納什均衡的。但本文介紹的新的成果，意味著這種判定必須在一個個具體案例中分別作出，即不存在一個完美論據證明對于所有游戲，達到納什均衡都是可實現(xiàn)的。
隨著文明的發(fā)展，盡管許多游戲可能會被簡化到適合簡單的博弈模型，而在互聯(lián)網時代，從約會網站到在線股票交易，各種新的多人游戲層出不窮。希伯來大學的計算機科學家Noam Nisan說：“在這個時期，我們不可能通過緩慢的人類進化找到容易達到平衡的游戲?！蔽覀冊谠O計新的游戲的時候，如果假設我們會達到一個平衡點，那我們常常就會出錯。
澳大利亞布里斯班昆士蘭大學的經濟學家安德魯·麥克倫南（Andrew McLennan）說，在現(xiàn)實生活中，人們往往不在平衡點玩游戲，這是經濟學家敏銳地認識到的。但是他說，“經濟學沒有什么理論結構來解釋經濟學的精確程度。” 比如巴奇琴科和魯賓斯坦這樣的新計算機理論科學成果，應該可以為以正式的方式來解決這個問題而提供靈感。”
但是這兩個領域有著非常不同的思維方式，這可能會阻礙跨學科交流：經濟學家傾向于尋找簡單的模型來捕捉復雜交互的本質，而理論計算機科學家通常更有興趣了解隨著模型日益復雜化而發(fā)生什么。 “我希望經濟學的同事更加意識到，計算機科學正在做更有趣的事情”麥克倫南說。
可被信任的調解員
在納什的平衡與納什的論文24年后，這個新的研究成果在既有的納什均衡的理論與更一般的均衡概念之間劃出了明顯的分界線。 1974年，另一位經濟學諾貝爾文學家羅伯特·奧曼（Robert Aumann）提出的“相關均衡”假設了一個場景，每個游戲玩家都接受來自信任的調解員（或“相關設備”）的建議，來了解有關策略的效果。如果沒有哪個玩家出于特別動機來曲解他所收到的建議，并且每個玩家都相信其他玩家會遵循他們各自收到的建議，那么調解員的建議就形成了一個相關的均衡。
這可能起初聽起來像一個神秘的構造，但實際上我們一直在使用這種相關的平衡 - 例如，我們拋硬幣來決定我們吃中餐還是意餐，或用交通信號燈來規(guī)范我們中的哪一個將首先通過交叉路口。
羅伯特·奧曼發(fā)明了相關均衡的概念
在這兩個例子中，每個玩家都清楚地知道“調解員”給予另一個玩家的建議，調解者的建議基本上協(xié)調了玩家來達到他們游戲中的納什均衡。但是，當玩家只知道不同的建議之間是如何相互關聯(lián)的，卻不知道其他人正在獲得什么建議時，奧曼表示，相關均衡的集合可以包含多于Nash均衡的組合：既它可以包括不是納什均衡的那些游戲狀況，但有時候會產生比任何納什均衡更積極的社會效果。例如，在一些游戲中，合作對球員的總收益將高于獨立采取行動，調解員有時可以通過隱瞞他給其他玩家的建議來誘騙某個玩家來合作。這個發(fā)現(xiàn)，邁爾森說，是非常意外的。
由線性方程組和不等式的集合表示的一組游戲的相關均衡比 Nash 平衡組更便于用數(shù)學方法處理，在調解員提供許多不同的建議情況下也是如此。 “以一種別致的方式思考，數(shù)學是如此美麗?！边~爾森說。
雖然邁爾森（Nelson）把納什的游戲理論視為“20 世紀杰出的智力進步之一”，但他認為相關平衡可能比納什均衡更為自然。他多次表示：“如果在其他行星上有智慧的生活，那么他們大多數(shù)會在納什均衡之前發(fā)現(xiàn)相關均衡。
在可重復的游戲中，很自然的，玩家會逐漸適應且趨向他們的均衡策略。例如，采取“最小遺憾化”方法，即在每輪之前，玩家以更高的概率去選擇那些他后悔在過去的游戲中沒有發(fā)揮作用的策略。Roughgarden 表示：“遺憾的最小化是一種與現(xiàn)實生活有一定相似之處的方法——留意同時過去運作良好的策略，偶爾嘗試一些新的策略?！?/p>
研究人員已經表明，許多游戲中，最小遺憾化法會迅速地將游戲收斂到相關平衡，令人驚奇的是：如果調解員一直在向玩家提供建議，那么在大約 100 輪之后，這些游戲的歷史看起來基本相同。麻省理工學院理論計算機科學家康斯坦丁諾斯·達斯卡拉斯（Constantinos Daskalakis）表示：“在通過互動過程中，（相關的）設置會以某種方式被隱含地發(fā)現(xiàn)?！?/p>
隨著游戲的繼續(xù)，玩家不一定保持在同一個相關均衡態(tài)上——例如，在 1000 回合之后，他們可能已經漂移到一個新的平衡，所以現(xiàn)在他們的 1000 場比賽的歷史看起來好像被一個不同的調解員影響的。這個過程讓人聯(lián)想到現(xiàn)實生活中的情況，Roughgarden 說，比如社會規(guī)范的逐漸演變。
尼桑說，在納什均衡難以達成的復雜游戲中，相關均衡是替代解決方案概念的“自然主導競爭者”。
邁爾森說，人類在相關均衡之前就提出了納什均衡的觀點，這可能只是一個歷史事故。他說：“人們會認為更早發(fā)展出的思想是更為基礎性的思想，但是在這種情況下，誰又能說什么是基礎性本的想法呢？”
然而，關于游戲快速收斂的結論，并不意味著其中任何一輪的游戲都是蘊含著相關均衡的作用的——相關均衡體現(xiàn)在游戲的長期歷史中。魯賓斯坦指出，這意味著在任何一輪中，最小遺憾法并不總是理性選手的理想選擇。那就留下了“理性玩家會做什么”的問題，而這目前沒有明確的答案。
