一个想法：走向“纳什均衡”是普遍存在的大趋势
?作者 | coolmud
單位 | 中國移動(dòng)研究院
研究方向 | 博弈論、機(jī)器學(xué)習(xí)
“納什均衡”（Nash Equilibrium）是博弈（game）中一種特別狀態(tài)：每個(gè)玩家單方面改變自己的策略（strategy）都不會(huì)有更好的收益。因此，所有玩家都會(huì)固守自己的策略，否則“不一定損人但一定不利己”，從而使得這個(gè)均衡狀態(tài)具備一定的穩(wěn)定性。1951 年，約翰·納什就在數(shù)學(xué)上證明了均衡點(diǎn)存在。不過，雖然我們能體會(huì)玩家們不愿意離開均衡點(diǎn)，迄今為止卻很少在現(xiàn)實(shí)世界中找到納什均衡的存在，也找不到把玩家們推向均衡點(diǎn)的力量。事實(shí)上，玩家們實(shí)在沒有理由主動(dòng)去找均衡點(diǎn)而因此被困住。更重要的是，就算本著“公心”，在均衡點(diǎn)所有玩家收益總和還往往不是最高的。話句話說，在現(xiàn)實(shí)世界，無論是人類社會(huì)，還是廣泛大自然，一個(gè)博弈要走向納什均衡，要么有個(gè)超越于普通玩家的“協(xié)調(diào)者”在主動(dòng)促成，要么是玩家們普遍的、不自覺的、簡(jiǎn)單的行為導(dǎo)致。?
我們先來排除協(xié)調(diào)者的可能性。首先協(xié)調(diào)者也沒有動(dòng)機(jī)搞什么“高大上”的納什均衡，因?yàn)榫退闼苋淌懿皇亲罡叩氖找婵偤?#xff0c;也未必喜歡過于穩(wěn)定而失去改變的能力。其次就是，協(xié)調(diào)者未必做得到。在玩家數(shù)量很多、策略數(shù)量也很多的情況下，協(xié)調(diào)者如何能夠通悉所有玩家的收益情況？采用何種高效的算法？哪來的算力？要知道數(shù)學(xué)上可沒有非常高效的算法，尤其是多人博弈。最后就是，回到剛才說的，就算協(xié)調(diào)者計(jì)算出均衡點(diǎn)，要為數(shù)眾多的玩家通通欣然接受照做其策略也是一個(gè)大工程。因此，協(xié)調(diào)者的意愿不太可能是推動(dòng)納什均衡的動(dòng)力。?
剩下的可能就是，在沒有協(xié)調(diào)者的情況下， 玩家們的行為導(dǎo)致博弈走向均衡。假如真是這樣，這種行為應(yīng)該是玩家們普遍具備的，也應(yīng)該是玩家本能驅(qū)動(dòng)或者大自然規(guī)律強(qiáng)制的。因此，這個(gè)行為最終也應(yīng)該是簡(jiǎn)單的，簡(jiǎn)單到每個(gè)玩家只需要看到自己的收益情況就能不斷調(diào)整自身策略，而不需要考慮其他眾多玩家的策略、收益情況，更不用關(guān)心均衡點(diǎn)在哪里。另外，簡(jiǎn)單意味著玩家們行為只需要極少的計(jì)算，最好是丁點(diǎn)都沒有。?
而本文的主要觀點(diǎn)就是，在現(xiàn)實(shí)世界玩家這種行為是普遍存在的，所以博弈走向納什均衡是普遍存在的趨勢(shì)。這種行為就是“平滑地、等比例地壓制零遺憾策略”。
論文標(biāo)題：
Geometrical regret matching: A new dynamics to Nash equilibrium
論文地址：
https://doi.org/10.1063/5.0012735
論文代碼：
https://github.com/lansiz/eqpt
“平滑地、等比例地壓制零遺憾策略”
這句話我們可以拆開來講。先說說“零遺憾（regret）的策略”。假設(shè)某玩家具備三個(gè)策略 (A, B, C)，且該玩家使用純策略獲得的收益分別為20、-30、50，表示為 [20, -30, 50]。又假設(shè)在某次博弈中該玩家采用了混合策略，例如?(0.6, 0.3, 0.1)，那么玩家得到的收益是把混合策略當(dāng)做概率分布進(jìn)行計(jì)算：
當(dāng)然，大家如果把上述混合策略當(dāng)做股票投資組合 (60%, 30%, 10%)，可能比較有感。現(xiàn)在，看到 8 的收益，該玩家肯定最遺憾沒有“滿倉”策略 C、能掙 50，其次是比較遺憾沒有滿倉策略 A、能掙 20，最不遺憾滿倉策略 B、掙負(fù) 30。可以看到，遺憾的程度剛好跟收益數(shù)值順序一致，因此我們決定用純策略收益來度量玩家對(duì)三個(gè)策略的遺憾程度，即 ：。
同時(shí)出于后續(xù)的數(shù)學(xué)處理目的，我們希望把遺憾值控制在非負(fù)數(shù)范圍內(nèi)，也就是把 -30 換成 0，即零遺憾。那么就有：。然而，因?yàn)槭找鏀?shù)值是在實(shí)數(shù)范圍內(nèi)的，換負(fù)數(shù)為零的方法會(huì)輕易導(dǎo)致所有策略都是零遺憾，例如 。同樣出于數(shù)學(xué)目的，我們把純策略收益減去混合策略收益以保證至少有一個(gè)策略有正遺憾值：
這樣我們得到了三個(gè)策略的遺憾值 <12, 0, 42>，其中策略 B 是零遺憾策略。剛才說到混合策略可以看作概率分布，因此零遺憾實(shí)質(zhì)是標(biāo)注了不高于期望收益的策略。?
現(xiàn)在可以說說“平滑地、等比例地壓制零遺憾策略”了。?
回顧本文的目的，我們是希望，當(dāng)所有玩家都迭代地、“平滑地、等比例地壓制零遺憾策略”，博弈就奔赴均衡點(diǎn)。以上述初始混合策略 (0.6, 0.3, 0.1) 為例，為了滿足“平滑地”、“等比例地”，我們這樣設(shè)計(jì)那個(gè)玩家的混合策略調(diào)整方法：
上式中，我們實(shí)際上把 (0.6, 0.3, 0.1) 和 <12, 0, 42> 當(dāng)作了三維向量。如下圖所示，調(diào)整后的混合策略也是一個(gè)三維向量。相比向量 (0.6, 0.3, 0.1)，新的混合策略跟遺憾向量 <12, 0, 42> 的角度減小了，也就是被推向了遺憾向量。減小的角度受到正實(shí)參數(shù) r 的控制，r 越小，角度變化越小。
下邊紅色箭頭是調(diào)整后的混合策略
最重要的是，這種混合策略調(diào)整方法會(huì)同比例壓制所有零遺憾策略，因?yàn)樯鲜街蟹帜敢话闶谴笥?1 的實(shí)數(shù)。舉一個(gè)四個(gè)策略的例子可能更明顯：當(dāng)混合策略為?(0.6, 0.2, 0.1, 0.1)?、遺憾值為 (40, 0, 0,?20)?時(shí)，策略 B 和 C 對(duì)應(yīng)比重都被同一個(gè)大于 1 的分母除，因此同比例減小了。?
然后，我們可以采用極微小的參數(shù) r 來實(shí)現(xiàn)迭代調(diào)整的平滑。?
下文我們將演示，當(dāng)所有玩家都按照上述方法迭代混合策略時(shí)，博弈將向均衡點(diǎn)演進(jìn)。不過，在此之前，我們要解答本文最重要的一個(gè)問題：為什么“平滑地、等比例地壓制不高于期望收益的策略”在現(xiàn)實(shí)世界是普遍存在的玩家行為？在市場(chǎng)中這個(gè)行為應(yīng)該不難解釋，符合玩家們“趨利避害”的本能習(xí)慣。在自然選擇過程中，可以解釋為，一個(gè)種群中采用劣勢(shì)策略的個(gè)體數(shù)量被大自然逐漸消減。這其中，“等比例壓制”是相對(duì)最苛刻的要求，需要玩家或者環(huán)境精確地執(zhí)行。不得不承認(rèn)，這個(gè)要求可能影響本文觀點(diǎn)可信度。
均衡點(diǎn)逼近演示
從上面例子看到，無論是雙人博弈，還是多人博弈，每個(gè)玩家只需知道自己的混合策略向量和純策略收益向量，就能進(jìn)行前述的策略調(diào)整。這個(gè)不可不謂簡(jiǎn)單，計(jì)算量并不大。但是，這時(shí)必須有個(gè)系統(tǒng)，對(duì)所有玩家提供它們各自的純策略收益向量。準(zhǔn)確地說，對(duì)任意玩家的任意混合策略 ，這個(gè)系統(tǒng)都能允許玩家獲知收益 和純策略收益向量 ，并且 必須為 和 的內(nèi)積，即 。
舉個(gè)例子。市場(chǎng)中，一個(gè)玩家以 (0.6, 0.3, 0.1) 的資金組合，分別獲得了 [12, -9, 5] 的收益，因此容易計(jì)算出純策略收益向量 [20, -30, 50]。這其中，市場(chǎng)本身必須對(duì)所有玩家提供上述信息。同此理，在自然選擇中，大自然也扮演這樣的系統(tǒng)。本質(zhì)上，這個(gè)系統(tǒng)為每個(gè)玩家提供了一個(gè)函數(shù)，這函數(shù)必須同時(shí)輸入其他玩家們的混合策略，計(jì)算后向該玩家提供信息。這個(gè)系統(tǒng)將承擔(dān)主要的計(jì)算量。
下面進(jìn)入演示環(huán)節(jié)。先是雙人博弈的演示，然后是多人博弈。
為了演示雙人博弈收斂到均衡點(diǎn)，我們就采用大家熟知的矩陣博弈中的 bimatrix 作為上述系統(tǒng)。綜合前述的種種機(jī)制，我們可以這樣實(shí)現(xiàn)雙人博弈逼近均衡點(diǎn)的算法：
vertices payoff就是純策略收益向量；max操作是對(duì)兩個(gè)向量對(duì)等元素的逐個(gè)比較，并最終返回一個(gè)向量。
在上述算法會(huì)把混合策略的調(diào)整歷史記錄下來形成軌跡。對(duì)于 3×3 的雙人博弈，軌跡肯定在二維的probability simplex上。為了直觀，我們把simplex轉(zhuǎn)換成平面上的等邊三角形。
下面是三個(gè)典型示例的運(yùn)行結(jié)果：
這個(gè)博弈只有一個(gè)均衡點(diǎn)，而且在均衡點(diǎn)兩個(gè)玩家都會(huì)使用純策略。
這個(gè)博弈只有一個(gè)均衡點(diǎn)，而且在均衡點(diǎn)兩個(gè)玩家都會(huì)使用帶有兩個(gè)策略的混合策略。黑色叉叉是真實(shí)的均衡點(diǎn)。
有兩個(gè)均衡點(diǎn)，每個(gè)均衡點(diǎn)的混合策略都使用兩個(gè)策略。收斂到哪個(gè)均衡點(diǎn)取決于初始混合策略。
對(duì)于非 3×3 博弈，例如 60×40，因?yàn)榛旌喜呗韵蛄砍^三維，一定要可視化的話可以用 PCA 方法（主成分分析）減少維數(shù)到三維。例如：
一個(gè)60x40博弈
下面的示例演示了均衡點(diǎn)與初始混合策略是無關(guān)的。無論是什么初始策略，都會(huì)收斂到某個(gè)均衡點(diǎn)：
接著是多人博弈的演示。在本文使用的數(shù)學(xué)中，雙人博弈只是多人的一種特例。因?yàn)樵谶@兩種博弈中，前述的信息提供系統(tǒng)都是以一個(gè)多變量聯(lián)合概率分布為計(jì)算基礎(chǔ)的，只不過雙人博弈是兩個(gè)變量的聯(lián)合概率分布。
下面是一個(gè)多人博弈的示例：
這個(gè)博弈有6個(gè)玩家，每個(gè)玩家可以使用3個(gè)策略。
更代碼多示例、詳細(xì)數(shù)學(xué)機(jī)制見后文的“參考材料”。代碼可以下載運(yùn)行，有詳細(xì)的操作方法。這里建議對(duì)多人博弈用好點(diǎn)的計(jì)算機(jī)運(yùn)算。不然要等很久。
一個(gè)缺陷：混合策略“轉(zhuǎn)圈圈”
就雙人博弈而言，如果對(duì)隨機(jī)生成的 3×3 或 4×4?博弈運(yùn)行前述算法，會(huì)發(fā)現(xiàn)大約 25% 的博弈只有使用三個(gè)策略的均衡點(diǎn)可以作為收斂目標(biāo)。這時(shí)候，混合策略軌跡就會(huì)轉(zhuǎn)圈，而且轉(zhuǎn)圈軌跡還不經(jīng)過均衡點(diǎn)：
轉(zhuǎn)圈的3x3
轉(zhuǎn)圈的60x40
多人博弈就更嚴(yán)重了，大概率發(fā)生轉(zhuǎn)圈。
轉(zhuǎn)圈的成因見：
https://github.com/lansiz/eqpt#important-the-cyclic-strategy-path-issue
軌跡轉(zhuǎn)圈會(huì)嚴(yán)重影響逼近均衡點(diǎn)的精度。這個(gè)問題目前沒有辦法解決。軌跡轉(zhuǎn)圈可以簡(jiǎn)單理解為算法不斷努力試圖找到通向均衡點(diǎn)路徑卻始終沒有路徑可及、只能周而復(fù)始嘗試。因此，博弈雖然沒有最終逼近均衡點(diǎn)，但與走向納什均衡的動(dòng)力并不矛盾。
結(jié)論
納什均衡可能是普遍存在的大趨勢(shì)。這個(gè)趨勢(shì)后面的驅(qū)動(dòng)力就是玩家長(zhǎng)期的行為習(xí)慣或者環(huán)境影響。這些驅(qū)動(dòng)力因?yàn)楹?jiǎn)單所以普遍存在、因?yàn)橘N近本能而難于抗拒。
我們現(xiàn)在能夠想象到，納什均衡的穩(wěn)定性不但在于玩家喜歡呆在那里，還在于就算玩家偏離了均衡點(diǎn)也會(huì)被拉回均衡點(diǎn)。從這個(gè)意義上講，納什均衡像一個(gè)旋渦，玩家們被裹挾其中而不自知。
附1. 與納什均衡存在性證明的關(guān)系
附2. 與“Regret Matching”方法的關(guān)系
附3. 隨機(jī)生成“五人博弈”策略軌跡圖（近500個(gè)示例圖，40M）
網(wǎng)盤鏈接：
https://pan.baidu.com/s/12qzbApmndik3yhTCsjHOCA
提取碼：
6666
更多閱讀
#投 稿?通 道#
?讓你的文字被更多人看到?
如何才能讓更多的優(yōu)質(zhì)內(nèi)容以更短路徑到達(dá)讀者群體，縮短讀者尋找優(yōu)質(zhì)內(nèi)容的成本呢？答案就是：你不認(rèn)識(shí)的人。
總有一些你不認(rèn)識(shí)的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學(xué)者和學(xué)術(shù)靈感相互碰撞，迸發(fā)出更多的可能性。?
PaperWeekly 鼓勵(lì)高校實(shí)驗(yàn)室或個(gè)人，在我們的平臺(tái)上分享各類優(yōu)質(zhì)內(nèi)容，可以是最新論文解讀，也可以是學(xué)術(shù)熱點(diǎn)剖析、科研心得或競(jìng)賽經(jīng)驗(yàn)講解等。我們的目的只有一個(gè)，讓知識(shí)真正流動(dòng)起來。
📝?稿件基本要求：
? 文章確系個(gè)人原創(chuàng)作品，未曾在公開渠道發(fā)表，如為其他平臺(tái)已發(fā)表或待發(fā)表的文章，請(qǐng)明確標(biāo)注?
? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發(fā)送，要求圖片清晰，無版權(quán)問題
? PaperWeekly 尊重原作者署名權(quán)，并將為每篇被采納的原創(chuàng)首發(fā)稿件，提供業(yè)內(nèi)具有競(jìng)爭(zhēng)力稿酬，具體依據(jù)文章閱讀量和文章質(zhì)量階梯制結(jié)算
📬?投稿通道：
? 投稿郵箱：hr@paperweekly.site?
? 來稿請(qǐng)備注即時(shí)聯(lián)系方式（微信），以便我們?cè)诟寮x用的第一時(shí)間聯(lián)系作者
? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿
△長(zhǎng)按添加PaperWeekly小編
🔍
現(xiàn)在，在「知乎」也能找到我們了
進(jìn)入知乎首頁搜索「PaperWeekly」
點(diǎn)擊「關(guān)注」訂閱我們的專欄吧
·
總結(jié)
以上是生活随笔為你收集整理的一个想法：走向“纳什均衡”是普遍存在的大趋势的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
