DeepMind SR論文：非對稱博弈的對稱分解

編者按：隨著人工智慧系統不斷落地，開始在現實生活中扮演重要角色，理解不同系統間的相互作用也成了一件重要的事。近日，DeepMind在Nature旗下的刊物Scientific Reports上發表了一篇新論文：Symmetric Decomposition of Asymmetric Games（非對稱博弈的對稱分解），介紹了團隊在多智能系統上的一些進展，即結合博弈論和納什均衡考察同一系統中多智能體間的相互作用。據介紹，這個成果不僅會對遊戲建模產生影響，它對經濟理論、進化生物學等其他學科也可能有一定的借鑒意義。

以下是論智概括、注釋的論文內容，如有錯誤，歡迎指出。

論文概述

一直以來，我們對分析多智能體系統中的戰略交互和納什均衡演化動態十分感興趣。在過去，這種戰略交互一般基於單個群體複製動態模型，它們一般受限於對稱性，即在統一的研究條件下，每個個體在執行什麼策略和獲得什麼收益上是完全一致的。例如，Walsh等人之前引入了一個經驗博弈論的方法（heuristic payoff table method，也稱啟發式收益表法），能展現複雜多智能體系統中各智能體之間的相互作用，現在這已被其他人擴展並應用到了德州撲克和多機器人系統中。類似的方法也被應用於人類合作、語言和複雜社會問題的建模，但它們的前提都是對稱博弈，即每個智能體是可以互相替換的，它們有完全相同的策略集合。

論智註：囚徒困境是對稱博弈的一個經驗案例。兩個共犯入獄，在無法溝通的情況下：互不揭發，各判1年；一方揭發，揭發者立即獲釋，沉默者10年；互相揭發，各判8年。兩人可選擇的策略和相應獎勵是完全一致的，所以是對稱的。

換言之，如果涉及不同角色的交互（如買賣雙方），即不同智能體可以根據不同行動選擇策略，獲得獎勵的評價也不同，那麼這些方法都是行不通的，它們無法直接適用於非對稱博弈情景。如博弈論中的最後通牒博弈、性別戰博弈，以及「貓捉老鼠」型桌游Scotland Yard。

論智註：

最後通牒博弈（Ultimatum Game）：兩人共分一筆錢，由提議者提出分配方案，回應者執行贊成/否決權，他們雙方的關係是不對稱的。（如果有多個分錢人，那就是「海盜分金」）

性別戰博弈（Battle of the Sexes）：夫妻倆都很想看電視，但丈夫偏好球賽，妻子偏好電視劇，他們有相同的利益，又有相悖的利益結果。

對於這種涉及多個智能體的非對稱博弈，之前已經一些人提出過很多方法，但他們的做法大多是先把非對稱博弈轉化為對稱博弈，再在新建立的策略和獎勵機制下進行分析。這是可行的，但僅限於簡單問題，如之前提到的Scotland Yard，它包含一個特工、5個警察和1個罪犯，又有多重遊戲規則限制，在重建它的評價機制前，把這樣一個複雜情景分解成只包含單一個體的對稱情景是不現實的。因此，本文提出的方法既不需要重建新的博弈，又有理論支撐，我們發現了非對稱博弈和納什均衡之間存在的一些微妙關係。

本文的主要創新在於分析非對稱博弈中的對稱因素，對於這些部分，我們能用複製動態模型的方法進行處理，而事實上我們也發現這些對稱因素的納什均衡和整個非對稱博弈的納什均衡正相關，這就提供了一個分析方法。需要注意的是，這些對稱因素是「種間」的，不是「種內」的，因為我們考察的是不同角色間的相互作用，也就是真正的不對稱對局。

本文的主要結論之一是在完全支持策略前提下，x策略（玩家1）和y策略（玩家2）的混合納什均衡構成了原始非對稱博弈的納什均衡，這時玩家1的對稱因素被定義在玩家2的收益上，反之亦然。換句話說，就是在完全支持策略前提下，非對稱博弈的納什均衡是兩個子對稱博弈的納什均衡的成對組合。

具體方法

對於非對稱博弈，現在最直接和最經典的做法是把智能體分開處理：根據玩家分配群體，然後讓兩個群體中的智能體相互對抗。這樣做的前提是假設這些玩家都是獨立的個體，它們不需要理解其他玩家的思路和做法。當然，在現實中這種假設局限性很大，因為要考慮到對抗性思維，一個棋手可以擅長執白，但他也要會執黑先行。

定義：假設這是一個包含兩個玩家的正則形式博弈（Normal form game，NFG），G=(S1, S2, A, B)。S1和S2分別是玩家1和玩家2的純策略集合，A和B是相應的收益。兩個玩家同時選擇各自的純策略（行動）。

如上表所示，玩家1和玩家2的收益可用矩陣（A,B）來表示，它的橫向數據表示玩家1的策略，縱向數據表示玩家2的策略。這個聯合策略的結果決定了兩個玩家的收益。

當S1=S2、A=B時，玩家1和玩家2可以互換，這時我們稱它是一個對稱博弈。如果兩個條件中至少有一個不符合，那它就是非對稱博弈。根據古典博弈論的思想，每個參與博弈的玩家都是理性的，他們會在推測對方做法的前提下爭取己方收益的最大化。這時，我們就能用納什均衡（NE）來判斷玩家選擇的合理性。

論智註：納什均衡是一種博弈結果，它有兩個前提：參與者獨立、互不溝通；預測其他人策略，並以此為基礎選擇自己的最優解。註：納什均衡為個體最優反應，而非整體最優決策，例如囚徒困境的納什均衡是雙方都認罪。

設ΔS1、ΔS2是混合策略集合，那麼兩個玩家的策略元組(x, y)∈ΔS1×ΔS2，即分布在純策略集（動作集）上。其中策略x是?|S1|、策略y是?|S2|的向量，表示玩家選擇這個策略的概率。xTAy和xTBy分別是兩名玩家的收益。已知在納什均衡中，雙方都已經單方面做出了最佳選擇，那麼我們可得：

定義：如果（x,y）是一個納什均衡，那它應該滿足：

如果策略集中只有一個必定選擇的策略，那它是純策略納什均衡；如果每個策略都有被選中的概率，那它是一個混合策略納什均衡。在演化博弈論中，博弈通常作為對個體的單獨微觀刻畫，換句話說，就是每個玩家都在獨立進行博弈，並且需要一個獨立的收益來定義博弈。在這種情況下，我們可得：

定義：在一個單一主體的博弈中，如果策略x是一個納什均衡，那他應該滿足：

這是一個單一玩家情景，所以x∈NE(A)。

模仿者動態（Replicator Dynamics）

模仿者動態在本質上是動態描述，它概括了策略的比例動態變化，用生物學現象說明，就是「適者生存」。它的動態複製機制如下：

這個公式比較了一個策略所獲得的收益與整個群體的平均收益。如果策略的分數高於平均水平，那麼它將能夠複製後代，如果分數低於平均水平，其它在群體中的佔比將減少，並有可能瀕臨「滅絕」。

進化穩定策略（Evolutionarily stable stragegy，ESS）

正如之前假設的，我們的單個簡單智能體現在在玩「單機遊戲」，放眼整個系統，即是一堆智能體正在獨立做相同的活動。如果這時群體中出現了一小部分突變者，它佔比小，無法影響大多數個體的選擇，這時該策略是穩定的，我們就稱它為ESS。而這部分突變者只有兩條路：被同化，或者在進化過程中消失。

非對稱的模仿者動態

以上假設都還是基於對稱博弈，現在我們把它們擴展到非對稱博弈。如下圖所示，在這個博弈中，兩名玩家有相同的策略集，即出門玩耍。但他們又有不同的收益：玩家1想去看歌劇，玩家2卻想去看電影。

根據模仿者動態，我們能得到這樣一對公式：

相對對稱模仿者動態（Symmetric Counterpart Replicator Dynamics）

這是我們提出的一個新概念，即非對稱模仿者動態中的相對對稱模仿者動態。我們把收益表A和B看做是隸屬兩個獨立博弈的收益，它們不再耦合。在第一個博弈中，所有玩家根據y選擇策略，即玩家2的原始策略和模仿者動態分布；在第二個博弈中，所有玩家根據x選擇策略，即玩家1的原始策略和模仿者動態分布。這時，我們能把公式調整為：

一般結論

綜合全文，我們得出的主要結論是：

當x和y條件相同時，如果 (x, y)?∈?NE(A,B)，那麼x?∈?NE(BΤ)、y?∈?NE(A)。

當x和y條件相同時，如果x?∈?NE(BΤ)、y?∈?NE(A)，那麼(x,y)?∈?NE(A,B)

定理1

如果策略x和y構成非對稱博弈G=(S1 , S2 , A, B)的納什均衡，xi>0，yj>0，|S1| = |S2|=n，則認為x是單群體博弈BT的納什均衡，y是單群體博弈AT的納什均衡。反之亦然。

推論1

非對稱博弈中的相對對稱模仿者動態的納什均衡的組合，可以構成原非對稱博弈的總的納什均衡。

定理2

當x是單群體博弈BT的納什均衡，y是單群體博弈AT的納什均衡，且Ix=Iy時，策略x和策略y對非對稱博弈G=(S1 , S2 , A, B)的納什均衡提供了同樣的支持（Ix=Iy）。

推論2

在非對稱博弈G=(S1 , S2 , A, B)中，策略x和策略y可依靠各自子策略集（S1和S2）中具有相同概率的策略，形成一個純策略納什均衡。當且僅當y和x在由收益A和B定義的這兩個博弈中也是嚴格的純策略納什均衡。

推論3

當且僅當在非對稱博弈G=(S1 , S2 , A, B)中，S1 , S2是兩個具有相同指標策略的ESS，（x,y）是局部漸進穩定的均衡，策略y在由A定義的博弈中、策略x在由B定義的博弈中才是嚴格的純策略納什均衡。

關於以上推論，DeepMind在論文中列出了推理細節，此處因篇幅原因不具體說明，感興趣的讀者可以前往原文閱讀。

實驗例證

在這一節中，我們將結合可視化工具說明非對稱博弈和對稱博弈模型之間的理論聯繫，以及它將如何改變多智能體博弈分析。圖中用矢量場表示平衡的動態變化，結合表示軌跡的線條和表示趨勢的箭頭，我們能對模仿者動態建立更深的了解。

需要注意的是，這個可視化工具一般只針對一個玩家，當同時呈現雙人非對稱博弈的演化動態來分析其均衡結構時，因為兩個玩家的動態是內在耦合的且是高維的，所以會很複雜。DeepMind在文中介紹了改進做法，考慮了其他玩家在其各自的策略中的誘導動態，具體可查看論文。

實驗1 性別戰博弈

之前提到了，性別戰博弈的雙方有共同的利益訴求，但有相悖的利益結果，即有相同的策略集，但相應的收益不同。以之前兩人看歌劇和看電影的案例為例，下圖是兩名玩家在博弈過程中的進化動態。其中x軸對應玩家1願意去看歌劇的概率，y軸對應玩家2看歌劇的概率。藍色箭頭展示了這一動態中的矢量場，黑線則是相應軌跡。

我們現在用這個博弈來說明定理1。假設定理1成立，那我們可以計算中兩名玩家的收益表。其中第一個博弈有一個((2/5,3/5),(2/5,3/5))的混合策略納什均衡，第二個博弈有一個((3/5,2/5),(3/5,2/5))的混合策略納什均衡。

下圖中的（b）和（c）是兩個博弈的演化動態，可以發現，兩個均衡點（紅點）位置的組合和整個非對稱博弈的均衡點一致。

實驗2 性別戰博弈的延伸

為了證明非對稱博弈中的這些定理，包括策略的排列，這裡我們對性別戰博弈做了一點延伸。具體來說，這同樣是兩個玩家博弈，但除了看歌劇和看電影，玩家2現在多了第三種選擇：在收音機上聽音樂會。

要注意，這時兩個玩家的策略集是不同的，除了出門，玩家2現在還可以宅家。如果我們要進行類似的分析，我們就需要兩個不對稱的模仿者動態方程，而用不對稱的模仿者動態來描述動態演化將是十分複雜的，因為它是高維的，還不能通過映射玩家的策略來完成。換句話說，這時靜態圖只能假設一個固定策略，而無法描述策略演變。

這裡我們採用的方法是設置一個虛擬策略D，來保證兩名玩家在策略集上有相同的數量，這是我們使用定理的前提。

這時博弈1、博弈2的收益是{(x=(0.6,0.4,0)，y=(0.4,0,0.6))，(x=(0,1,0)，y=(0,0,1))，(x=(1,0,0)，y=(1,0,0)))}。

現在我們再來分析這個不對稱博弈。我們找到了博弈1的納什均衡點(1, 0, 0)、(0.4, 0.6, 0)和(0, 1, 0)，以及博弈2的納什均衡點(0, 0, 1)、(0.6, 0.4, 0)、(0, 1, 0)和(1,0,0)。根據這兩個獨立的納什均衡，再加上剩餘的納什均衡，我們能得出原不對稱博弈的納什均衡。

具體而言，通過應用定理2，我們發現(x =(0.6,0.4,0)，y =(0.4,0.6,0))可以轉換為(x =(0.6,0.4,0)，y=(0.4,0,0.6))，因為我們為第二個玩家排列了第二個和第三個動作，我們需要再次交換這些動作。此外，我們還發現了(x =(0,1,0)，y =(0,1,0))可以轉換為(x =(0,1,0))，y =(0,0,1 ))，因為我們為第二個玩家排列了行動2和3。結合這些數據，現在我們已經找到了原始不對稱博弈的所有納什均衡。

DeepMind還在實驗3中介紹了在撲克遊戲中的一些推理應用，此處不再詳談。

小結

這項研究揭示了研究多個智能體之間不對稱相互作用的新亮點，並為分析非對稱博弈提供了便利、徹底的新方法，在現實場景中，訓練多個智能體研究交互、進化、學習是非常常見的研究方法，它不限於博弈建模，在經濟學、生物學、語言、遊戲和人工智慧中都有廣泛應用。因此，這項成果可能將惠及以上諸多領域。

原文地址：www.nature.com/articles/s41598-018-19194-4#Sec13

博客地址：deepmind.com/blog/game-theory-insights-asymmetric-multi-agent-games/

如發現錯誤，歡迎留言指出，小編將不勝感謝。

推薦閱讀：