約翰·納什的均衡理論在經(jīng)濟(jì)理論中是普遍存在的，但一項(xiàng)新的研究表明榜配，通常不可能有效地達(dá)成。
所有的游戲都有納什均衡吕晌。但參與者能否達(dá)到蛋褥？
1950年，數(shù)學(xué)家約翰·納什（John Nash）——后來(lái)在書和電影“美麗的心靈”中出現(xiàn)而更知名——寫了一篇只有兩頁(yè)的論文睛驳，改變了經(jīng)濟(jì)學(xué)理論烙心。他的關(guān)鍵卻簡(jiǎn)單的想法是膜廊，任何競(jìng)爭(zhēng)游戲都有一個(gè)均衡狀態(tài)，在均衡狀態(tài)下淫茵，每個(gè)玩家采取策略集合中的一種策略爪瓜，且沒(méi)有玩家可以通過(guò)單方面切換到不同的策略來(lái)贏得更多的利益。
納什的均衡概念在1994年獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)匙瘪，它不僅在經(jīng)濟(jì)學(xué)中铆铆，而且在心理學(xué)，進(jìn)化生物學(xué)和許多其他領(lǐng)域中丹喻，為理解戰(zhàn)略行為提供了一個(gè)統(tǒng)一的框架薄货。芝加哥大學(xué)的另一位經(jīng)濟(jì)學(xué)諾貝爾獎(jiǎng)得主羅杰·米森（Roger Myerson）寫道：“它對(duì)經(jīng)濟(jì)理論的影響與生物科學(xué)中DNA雙螺旋的發(fā)現(xiàn)相當(dāng)∽て。”
當(dāng)參與者處于均衡狀態(tài)時(shí)菲驴，沒(méi)有人有理由去偏離這種狀態(tài)荐吵∑锶撸可是，參與者是如何達(dá)到均衡狀態(tài)呢先煎？這就好比贼涩，一個(gè)滾球在下坡過(guò)程中可能會(huì)停留在山谷里而不再繼續(xù)，同樣的薯蝎，并沒(méi)有明顯的力量指導(dǎo)參與者走向納什均衡遥倦。
斯坦福大學(xué)理論計(jì)算機(jī)科學(xué)家Tim Roughgarden說(shuō)：“它一直是微觀經(jīng)濟(jì)學(xué)家的一個(gè)刺。他們使用這些均衡概念分析即將處于均衡狀態(tài)的人們占锯，但并不總能令人滿意的解釋為什么人們將走向納什均衡袒哥，而不僅僅只是在摸索∠裕”
如果人們只玩一次游戲堡称，期望他們找到一個(gè)均衡點(diǎn)往往是不合理的。這是特別是當(dāng)每個(gè)玩家只知道游戲的不同結(jié)果對(duì)他自己的價(jià)值艺演，而不知道他的同伴的情況却紧，而這在現(xiàn)實(shí)世界中是典型的場(chǎng)景。但是胎撤，如果人們可以反復(fù)執(zhí)行同樣的游戲晓殊，也許他們可以從早期的回合中學(xué)習(xí)，并迅速地將自己轉(zhuǎn)向均衡策略和狀態(tài)伤提。然而巫俺，找到這種有效的學(xué)習(xí)方法的嘗試往往徒勞無(wú)功。
加利福尼亞大學(xué)伯克利分校理論計(jì)算機(jī)科學(xué)博士學(xué)位的Aviad Rubinstein說(shuō)：“經(jīng)濟(jì)學(xué)家提出了如何快速收斂到均衡狀態(tài)的機(jī)制肿男。但是對(duì)于每個(gè)這樣的機(jī)制介汹，你可以建立一些簡(jiǎn)單的游戲規(guī)則砚著，卻不能運(yùn)作〕彰粒”
現(xiàn)在稽穆，海法技術(shù)與以色列理工學(xué)院的數(shù)學(xué)家魯賓斯坦和雅科夫·巴布奇寧科已經(jīng)對(duì)此困局進(jìn)行解釋。在去年9月發(fā)布的一篇論文中赶撰，他們證明舌镶，沒(méi)有任何適應(yīng)策略的方法可以應(yīng)對(duì)以往的游戲并使其有效地收斂到納什均衡，無(wú)論這個(gè)方法多么聰明豪娜、符合常識(shí)餐胀、或富有創(chuàng)造性，甚至連近似的納什均衡都無(wú)法達(dá)到瘤载》裨郑“這是一個(gè)非常徹底的消極結(jié)果”，Roughgarden說(shuō)鸣奔。
經(jīng)濟(jì)學(xué)家經(jīng)常使用納什均衡分析來(lái)證明他們提出的經(jīng)濟(jì)改革是有道理的墨技。但新的結(jié)果表明，經(jīng)濟(jì)學(xué)家不能相信游戲玩家將達(dá)到納什均衡挎狸，除非他們可以證明特定游戲的特殊性扣汪。希伯來(lái)大學(xué)的計(jì)算機(jī)科學(xué)家Noam Nisan說(shuō)：“如果你想弄清楚你的游戲是否容易找到一個(gè)均衡點(diǎn)，那么你必須提供理由锨匆≌副穑”
多人游戲
在一些簡(jiǎn)單的游戲中，很容易發(fā)現(xiàn)納什均衡恐锣。例如茅主，如果我喜歡中國(guó)菜，而你更喜歡意大利菜土榴，但是我們最強(qiáng)烈的喜好是一起吃飯诀姚，兩個(gè)明顯的均衡是我們兩個(gè)人去中國(guó)餐館或我們兩個(gè)人去意大利餐廳。即使我們開(kāi)始只知道自己的喜好而且不能在比賽之前交流策略鞭衩，我們也并不會(huì)因?yàn)榛ㄌ鄷r(shí)間去深入了解彼此的偏好而導(dǎo)致錯(cuò)過(guò)聯(lián)系的機(jī)會(huì)從而只能孤獨(dú)的晚餐学搜，我們很有希望找到一個(gè)，或者另一個(gè)均衡论衍。
但是想象一下瑞佩，如果晚餐計(jì)劃涉及100人，每個(gè)人都決定了他喜歡和什么人共進(jìn)晚餐坯台，同時(shí)沒(méi)有人知道其他任何人的喜好炬丸。納什在1950年證明，即使像這樣的大型復(fù)雜的游戲，也總是存在一個(gè)均衡（至少在策略的概念被擴(kuò)大以允許隨機(jī)選擇稠炬，比如你有60％概率選擇中國(guó)餐館焕阿，的情況下是成立的 ）∈灼簦可惜納什在2015年因車禍而死亡暮屡，他沒(méi)有給出達(dá)到均衡的計(jì)算方法。
阿維亞·魯賓斯坦（Aviad Rubinstein）幫助表明毅桃，玩家不一定會(huì)發(fā)現(xiàn)納什均衡褒纲。
Tselil Schramm通過(guò)潛入Nash的證明過(guò)程，Babichenko和Rubinstein能夠表明钥飞，一般來(lái)說(shuō)莺掠，玩家無(wú)法找到近似納什均衡的路徑，除非他們表達(dá)了幾乎所有關(guān)于他們各自的喜好读宙。隨著游戲中玩家的數(shù)量的增加彻秆，這種溝通所有需求的時(shí)間迅速增長(zhǎng)到足以令人望而卻步。
例如结闸，在100人的餐廳游戲中唇兑，有2100種可能的結(jié)果，因此每個(gè)玩家必須共享2100種偏好膀估。相比之下幔亥，自大爆炸以來(lái)已經(jīng)過(guò)去的秒數(shù)只有2^59。
這種通信瓶頸意味著察纯，任意方法都不可能通過(guò)從一輪到另一輪的適應(yīng)策略來(lái)指導(dǎo)玩家有效地達(dá)到納什均衡，至少對(duì)于一些復(fù)雜游戲的這樣的（例如具有復(fù)雜偏好的100人玩家餐廳游戲）针肥。畢竟饼记，在每一輪中，玩家只會(huì)學(xué)到一點(diǎn)新信息：其他玩家對(duì)某種晚餐安排有多滿意慰枕。因此具则，他們需要2^100輪游戲來(lái)知道彼此價(jià)值觀（而在此之前中國(guó)和意大利餐館可能都已經(jīng)關(guān)門了）。
耶路撒冷希伯來(lái)大學(xué)游戲理論家塞爾古·哈特（Sergiu Hart）說(shuō)：“如果這將比宇宙演化花費(fèi)更長(zhǎng)的時(shí)間具帮，那當(dāng)然完全沒(méi)有用博肋。”
玩家為找出納什均衡蜂厅，有時(shí)候需要知道對(duì)方所有的價(jià)值觀匪凡，這看起來(lái)很自然。然而在現(xiàn)實(shí)中掘猿，這往往是難以實(shí)現(xiàn)的一點(diǎn)病游，即使玩家愿意達(dá)到一個(gè)接近納什均衡且已經(jīng)足夠好的近似納什均衡。這是新的論文提出的一個(gè)重要的發(fā)現(xiàn)稠通。
Babichenko和Rubinstein的結(jié)果并不意味著所有（甚至大部分）的游戲都將受到這個(gè)限制衬衬，也就是說(shuō)买猖，只有一些游戲會(huì)。經(jīng)濟(jì)學(xué)家用來(lái)建淖涛荆現(xiàn)實(shí)世界的許多游戲都有額外的構(gòu)架玉控，從而大大減少了每個(gè)玩家必須溝通的信息量。例如狮惜，如果我們每個(gè)人都選擇我們?cè)缟贤ㄇ诘膬蓷l路線之一奸远，那么你可能不在乎每個(gè)路線上有哪些車手 - 你只需要路線上有多少車。這意味著你的收藏偏好將具有很高的對(duì)稱性讽挟，你可以將其全部?jī)?nèi)容轉(zhuǎn)換成兩個(gè)選擇好的句子懒叛，而不是2^100個(gè)。
經(jīng)濟(jì)學(xué)家可以使用這樣的論據(jù)來(lái)證明為什么特定的游戲是可以達(dá)到納什均衡的耽梅。但本文介紹的新的成果薛窥，意味著這種判定必須在一個(gè)個(gè)具體案例中分別作出，即不存在一個(gè)完美論據(jù)證明對(duì)于所有游戲眼姐，達(dá)到納什均衡都是可實(shí)現(xiàn)的诅迷。
隨著文明的發(fā)展，盡管許多游戲可能會(huì)被簡(jiǎn)化到適合簡(jiǎn)單的博弈模型众旗，而在互聯(lián)網(wǎng)時(shí)代罢杉，從約會(huì)網(wǎng)站到在線股票交易，各種新的多人游戲?qū)映霾桓F贡歧。希伯來(lái)大學(xué)的計(jì)算機(jī)科學(xué)家Noam Nisan說(shuō)：“在這個(gè)時(shí)期滩租，我們不可能通過(guò)緩慢的人類進(jìn)化找到容易達(dá)到平衡的游戲±洌”我們?cè)谠O(shè)計(jì)新的游戲的時(shí)候律想，如果假設(shè)我們會(huì)達(dá)到一個(gè)平衡點(diǎn)，那我們常常就會(huì)出錯(cuò)绍弟。
澳大利亞布里斯班昆士蘭大學(xué)的經(jīng)濟(jì)學(xué)家安德魯·麥克倫南（Andrew McLennan）說(shuō)技即，在現(xiàn)實(shí)生活中，人們往往不在平衡點(diǎn)玩游戲樟遣，這是經(jīng)濟(jì)學(xué)家敏銳地認(rèn)識(shí)到的而叼。但是他說(shuō)，“經(jīng)濟(jì)學(xué)沒(méi)有什么理論結(jié)構(gòu)來(lái)解釋經(jīng)濟(jì)學(xué)的精確程度豹悬】辏” 比如巴奇琴科和魯賓斯坦這樣的新計(jì)算機(jī)理論科學(xué)成果，應(yīng)該可以為以正式的方式來(lái)解決這個(gè)問(wèn)題而提供靈感屿衅“Ｄ眩”
但是這兩個(gè)領(lǐng)域有著非常不同的思維方式，這可能會(huì)阻礙跨學(xué)科交流：經(jīng)濟(jì)學(xué)家傾向于尋找簡(jiǎn)單的模型來(lái)捕捉復(fù)雜交互的本質(zhì)，而理論計(jì)算機(jī)科學(xué)家通常更有興趣了解隨著模型日益復(fù)雜化而發(fā)生什么涡尘。 “我希望經(jīng)濟(jì)學(xué)的同事更加意識(shí)到忍弛，計(jì)算機(jī)科學(xué)正在做更有趣的事情”麥克倫南說(shuō)。
可被信任的調(diào)解員
在納什的平衡與納什的論文24年后考抄，這個(gè)新的研究成果在既有的納什均衡的理論與更一般的均衡概念之間劃出了明顯的分界線细疚。 1974年，另一位經(jīng)濟(jì)學(xué)諾貝爾文學(xué)家羅伯特·奧曼（Robert Aumann）提出的“相關(guān)均衡”假設(shè)了一個(gè)場(chǎng)景川梅，每個(gè)游戲玩家都接受來(lái)自信任的調(diào)解員（或“相關(guān)設(shè)備”）的建議疯兼，來(lái)了解有關(guān)策略的效果。如果沒(méi)有哪個(gè)玩家出于特別動(dòng)機(jī)來(lái)曲解他所收到的建議贫途，并且每個(gè)玩家都相信其他玩家會(huì)遵循他們各自收到的建議吧彪，那么調(diào)解員的建議就形成了一個(gè)相關(guān)的均衡。
這可能起初聽(tīng)起來(lái)像一個(gè)神秘的構(gòu)造丢早，但實(shí)際上我們一直在使用這種相關(guān)的平衡 - 例如姨裸，我們拋硬幣來(lái)決定我們吃中餐還是意餐，或用交通信號(hào)燈來(lái)規(guī)范我們中的哪一個(gè)將首先通過(guò)交叉路口怨酝。
羅伯特·奧曼發(fā)明了相關(guān)均衡的概念
在這兩個(gè)例子中傀缩，每個(gè)玩家都清楚地知道“調(diào)解員”給予另一個(gè)玩家的建議，調(diào)解者的建議基本上協(xié)調(diào)了玩家來(lái)達(dá)到他們游戲中的納什均衡农猬。但是赡艰，當(dāng)玩家只知道不同的建議之間是如何相互關(guān)聯(lián)的，卻不知道其他人正在獲得什么建議時(shí)斤葱，奧曼表示慷垮，相關(guān)均衡的集合可以包含多于Nash均衡的組合：既它可以包括不是納什均衡的那些游戲狀況，但有時(shí)候會(huì)產(chǎn)生比任何納什均衡更積極的社會(huì)效果苦掘。例如换帜，在一些游戲中，合作對(duì)球員的總收益將高于獨(dú)立采取行動(dòng)鹤啡，調(diào)解員有時(shí)可以通過(guò)隱瞞他給其他玩家的建議來(lái)誘騙某個(gè)玩家來(lái)合作。這個(gè)發(fā)現(xiàn)蹲嚣，邁爾森說(shuō)递瑰，是非常意外的。
由線性方程組和不等式的集合表示的一組游戲的相關(guān)均衡比 Nash 平衡組更便于用數(shù)學(xué)方法處理隙畜，在調(diào)解員提供許多不同的建議情況下也是如此抖部。 “以一種別致的方式思考，數(shù)學(xué)是如此美麗议惰∩骺牛”邁爾森說(shuō)。
雖然邁爾森（Nelson）把納什的游戲理論視為“20 世紀(jì)杰出的智力進(jìn)步之一”，但他認(rèn)為相關(guān)平衡可能比納什均衡更為自然俯萎。他多次表示：“如果在其他行星上有智慧的生活傲宜，那么他們大多數(shù)會(huì)在納什均衡之前發(fā)現(xiàn)相關(guān)均衡。
在可重復(fù)的游戲中夫啊，很自然的函卒，玩家會(huì)逐漸適應(yīng)且趨向他們的均衡策略。例如撇眯，采取“最小遺憾化”方法报嵌，即在每輪之前，玩家以更高的概率去選擇那些他后悔在過(guò)去的游戲中沒(méi)有發(fā)揮作用的策略熊榛。Roughgarden 表示：“遺憾的最小化是一種與現(xiàn)實(shí)生活有一定相似之處的方法——留意同時(shí)過(guò)去運(yùn)作良好的策略锚国，偶爾嘗試一些新的策略⌒梗”
研究人員已經(jīng)表明血筑，許多游戲中，最小遺憾化法會(huì)迅速地將游戲收斂到相關(guān)平衡营搅，令人驚奇的是：如果調(diào)解員一直在向玩家提供建議云挟，那么在大約 100 輪之后，這些游戲的歷史看起來(lái)基本相同转质。麻省理工學(xué)院理論計(jì)算機(jī)科學(xué)家康斯坦丁諾斯·達(dá)斯卡拉斯（Constantinos Daskalakis）表示：“在通過(guò)互動(dòng)過(guò)程中园欣，（相關(guān)的）設(shè)置會(huì)以某種方式被隱含地發(fā)現(xiàn)⌒菪罚”
隨著游戲的繼續(xù)沸枯，玩家不一定保持在同一個(gè)相關(guān)均衡態(tài)上——例如，在 1000 回合之后赂弓，他們可能已經(jīng)漂移到一個(gè)新的平衡绑榴，所以現(xiàn)在他們的 1000 場(chǎng)比賽的歷史看起來(lái)好像被一個(gè)不同的調(diào)解員影響的。這個(gè)過(guò)程讓人聯(lián)想到現(xiàn)實(shí)生活中的情況盈魁，Roughgarden 說(shuō)翔怎，比如社會(huì)規(guī)范的逐漸演變。
尼桑說(shuō)杨耙，在納什均衡難以達(dá)成的復(fù)雜游戲中赤套，相關(guān)均衡是替代解決方案概念的“自然主導(dǎo)競(jìng)爭(zhēng)者”。
邁爾森說(shuō)珊膜，人類在相關(guān)均衡之前就提出了納什均衡的觀點(diǎn)容握，這可能只是一個(gè)歷史事故。他說(shuō)：“人們會(huì)認(rèn)為更早發(fā)展出的思想是更為基礎(chǔ)性的思想车柠，但是在這種情況下剔氏，誰(shuí)又能說(shuō)什么是基礎(chǔ)性本的想法呢塑猖？”
然而，關(guān)于游戲快速收斂的結(jié)論谈跛，并不意味著其中任何一輪的游戲都是蘊(yùn)含著相關(guān)均衡的作用的——相關(guān)均衡體現(xiàn)在游戲的長(zhǎng)期歷史中羊苟。魯賓斯坦指出，這意味著在任何一輪中币旧，最小遺憾法并不總是理性選手的理想選擇践险。那就留下了“理性玩家會(huì)做什么”的問(wèn)題，而這目前沒(méi)有明確的答案吹菱。
