DeepMind於Nature子刊發文提出非對稱博弈的降維方法

選自DeepMind

作者：Karl Tuyls、Marc Lanctot、Julian Perolat

機器之心編譯

參與：劉曉坤、黃小天、路雪

近日，DeepMind 在 Scientific Report 上發表論文《Symmetric Decomposition of Asymmetric Games》，表明一個非對稱博弈可以分解為多個對稱博弈，從而將博弈降維，並且非對稱博弈和對稱變體的納什均衡也有非常簡單的對應關係。

隨著 AI 系統在現實世界中扮演的角色越來越重要，理解不同系統之間如何交互變得非常關鍵。

DeepMind 最新在 Scientific Report 上發表了一篇論文《Symmetric Decomposition of Asymmetric Games》，使用了博弈論的一個分支來解決這個問題。具體來說，DeepMind 研究者檢驗了兩個智能系統在非對稱博弈遊戲（asymmetric game，包括 Leduc 撲克和多種棋牌遊戲）的特定類型情景下的行為和反應。非對稱博弈還可以自然地對現實世界場景建模，例如自動拍賣，其中買家和賣家以不同的動機行動。研究結果給出了對這些場景的新洞察，揭示了一種非常簡單的分析方法。雖然 DeepMind 的興趣主要在於如何將該理論應用到多個 AI 系統的交互中，但研究者相信這些結果還可以應用到經濟學、進化生物學和經驗博弈論（empirical game theory）等。

該方法被證明在數學上是很簡單的，允許對非對稱博弈進行快速、直接的分析。

博弈論是一種數學理論，用於分析競爭環境中決策者使用的策略，可以在多種情景中應用於人類、動物和計算機。博弈論在研究多智能體環境中很常用，多智能體環境中的系統數量超過一個，例如多個家庭機器人協作打掃房子。傳統上通常使用簡單的對稱博弈遊戲來分析多智能體系統的演化動態，例如「囚徒困境」，其中每個玩家都有相同的可選動作。雖然這些博弈遊戲可以為多智能體系統的工作方式提供有用的洞察，並告訴我們如何讓所有玩家取得想要的結果——即納什均衡，但是它們無法對所有情景建模。

DeepMind 的新技術允許快速、簡單地在更加複雜的非對稱博弈中發現可用於實現納什均衡的策略（非對稱博弈遊戲中每個玩家都有不同的策略、目標和獎勵）。可以通過「性別大戰」（一個博弈論研究中常用的協調博弈遊戲）的例子展示這些博弈和用於分析它們的新技術。

在性別大戰中，兩個玩家需要在一個晚上協商去看歌劇還是看電影。兩個玩家中，一個略微更喜歡歌劇，另一個更喜歡電影。這個博弈是非對稱的，因為雖然兩個玩家的可選策略是相同的，但是基於玩家偏好，選項所對應的獎勵是不同的。為了維持他們的友誼，或者說均衡，兩個玩家需要選擇相同的選項，如果選擇了不同的選項則收益為零。

該遊戲有三個均衡：(i) 兩個玩家都決定去歌劇院，(ii) 兩人都決定去看電影，(iii) 最後的混合選擇，其中每個玩家選擇自己偏好的活動的比例為五分之三。最後一個「不穩定」選擇可以用 DeepMind 的方法，通過將非對稱博弈簡化或分解成對稱博弈而被迅速發現。這些分解出的對稱博弈遊戲本質上把每個玩家的獎勵表作為一個獨立的對稱雙人博弈，其均衡點與原來的非對稱博弈一致。

下圖為兩個分解出的簡單對稱博弈遊戲繪製了納什均衡，我們可以快速發現非對稱博弈 (a) 中的最優策略。也可以反過來操作，使用非對稱博弈發現對稱博弈中的均衡。

紅點表示納什均衡。我們可以輕鬆地從兩個分解出的對稱博弈遊戲 (b) 和 (c) 的繪圖中得出非對稱博弈 (a)。以上所有圖中，x 軸對應於玩家 1 選擇歌劇的概率，y 軸對應於玩家 2 選擇歌劇的概率。

這一方法也適用於其他遊戲，包括論文中詳述的 Leduc 撲克。在所有這些情景中，該方法被證明在數學上是簡單的，可以快速而直接地分析非對稱博弈，我們希望這也有助於我們理解不同的動態系統，包括多智能體環境。

論文：Symmetric Decomposition of Asymmetric Games

我們提出了關於雙人非對稱博弈遊戲的新理論洞察，允許優雅地將非對稱博弈遊戲分解為兩個單人對稱博弈遊戲。具體來說，我們展示了如何通過預見和研究構成非對稱博弈的收益表（A 和 B），將非對稱雙矩陣博弈 (A,B) 分解為它的對稱變體，即兩個獨立的、單人的對稱博弈。我們揭示了雙人非對稱博弈與其單人對稱博弈之間形式上的多種令人驚訝的關係，促進了對原始非對稱博弈進行分析的便利性（因為分解可以降維）。主要的研究成果揭示了，如果 (x,y) 是非對稱博弈 (A,B) 的納什均衡，則 y 是由收益表 A 決定的對稱博弈遊戲的納什均衡，x 是由收益表 B 決定的對稱博弈遊戲的納什均衡，反之亦然。並且兩個單人對稱博弈的納什均衡的組合構成了非對稱博弈的納什均衡。通過在多個標準實例中檢驗更簡單的對稱博弈遊戲的演化動態，我們展示了這些形式關係如何幫助發現和分析非對稱博弈的納什結構。

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

?------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！