機器之心

選自TowardsDataScience

作者：Jesus Rodriguez

機器之心編譯

參與：魔王、杜偉

隨著人工智能的發(fā)展，博弈論迎來了復興。關(guān)于博弈論，數(shù)據(jù)科學家需要了解哪些經(jīng)典思想和新思路呢？本文作者就這些問題一一展開了分析。通過此文，相信讀者會對博弈論的概念和分類有更清晰的理解。

博弈論是最讓人著迷的數(shù)學領(lǐng)域之一，它影響了多個不同領(lǐng)域，如經(jīng)濟學、社會科學、生物學，顯然還有計算機科學。博弈論的定義有很多，但我認為以下這個定義非常有幫助，盡管它過分簡潔：

博弈論是具備激勵機制的概率。

游戲在人工智能發(fā)展過程中起到關(guān)鍵作用。對于初學者而言，游戲環(huán)境在強化學習或模仿學習等領(lǐng)域中逐漸成為流行的訓練機制。理論上，任何多智能體 AI 系統(tǒng)都要經(jīng)歷玩家之間的游戲化交互。構(gòu)建游戲原則的數(shù)學分支正是博弈論。在人工智能語境和深度學習系統(tǒng)語境下，要想使多智能體環(huán)境具備一些必備的重要能力，博弈論必不可少。在多智能體環(huán)境中，不同的 AI 程序需要交互或競爭才能達成目標。

博弈論的歷史與計算機科學史密不可分。目前博弈論領(lǐng)域中的許多研究可以追溯至阿蘭·圖靈、馮·諾伊曼這些計算機科學先驅(qū)的工作。因電影《美麗心靈》而聞名于世的納什均衡（Nash equilibrium）是現(xiàn)代系統(tǒng)中很多 AI 交互的基礎(chǔ)。但是，利用博弈論原則多次建模 AI 宇宙超出了納什均衡的范疇。想理解如何利用博弈論構(gòu)建 AI 系統(tǒng)，最好先理解我們在社會或經(jīng)濟互動中常遇到的博弈類型。

我們每天參與數(shù)百種基于游戲動態(tài)（game dynamics）的交互。但是，游戲化環(huán)境的架構(gòu)與此完全不同，其激勵和參與者目的也不相同。如何將這些原則應用到 AI 智能體建模中呢？這個難題推動 AI 研究某些領(lǐng)域的發(fā)展，如多智能體強化學習。

顯然，游戲是博弈論最具可見性的實體，但它遠遠不是應用博弈論概念的唯一空間。也就是說，還有很多其他領(lǐng)域也受到博弈論和 AI 的共同影響。大多數(shù)需要多個「參與者」合作或競爭才能完成任務(wù)的場景都可以利用 AI 技術(shù)進行游戲化和改進。盡管之前的陳述是一種泛化，但我認為它傳達出了一個信息：博弈論和 AI 是一種思考和建模軟件系統(tǒng)的方式，而不只是一種技術(shù)。

利用博弈論的 AI 場景應包含不止一個參與者。例如，Salesforce Einstein 這類銷售預測優(yōu)化 AI 系統(tǒng)就不是應用博弈論原則的完美場景。但是，在多智能體環(huán)境中，博弈論又有明顯不同。

在 AI 系統(tǒng)中建構(gòu)游戲動態(tài)需要兩步：

參與者設(shè)計：博弈論可用來優(yōu)化參與者的決策，以獲得最大效用；

機制設(shè)計：逆博弈論（inverse game theory）主要為一組智能參與者設(shè)計游戲。拍賣就是機制設(shè)計的經(jīng)典案例。

那么 AI 時代的數(shù)據(jù)科學家又需要了解哪些博弈呢？這些博弈彼此之間是否存在著聯(lián)系呢？本文作者、Invector Labs 首席科學家兼執(zhí)行合伙人 Jesus Rodriguez 對此發(fā)表了自己的看法。

本文作者 Jesus Rodriguez。

數(shù)據(jù)科學家應該知道的 5 種博弈

假設(shè)我們正在構(gòu)建一個需要多個智能體互相合作競爭才能完成特定目標的 AI 系統(tǒng)，即博弈論的經(jīng)典場景。自 20 世紀 40 年代誕生以來，博弈論專注于建模最常見的交互模式，現(xiàn)在我們每天在多智能體 AI 系統(tǒng)中看到的就是它們。理解環(huán)境中不同類型的游戲動態(tài)是設(shè)計高效游戲化 AI 系統(tǒng)的關(guān)鍵元素。從較高層次來看，五元素標準有助于理解 AI 環(huán)境中的游戲動態(tài)，即對稱 vs 非對稱、完美信息 vs 非完美信息、合作 vs 非合作、同時 vs 序列和零和 vs 非零和。下面將一一展開介紹。

作者提出的五元素標準。

對稱 vs 非對稱

最簡單的一種博弈分類方式是根據(jù)對稱性進行分類。在對稱博弈環(huán)境里，每個玩家具備同樣的目標，結(jié)果僅取決于策略。國際象棋就是一種經(jīng)典的對稱博弈。我們在現(xiàn)實世界中遇到的很多場景缺少對稱的數(shù)學優(yōu)雅性，因為參與者通常目標不同，甚至還存在沖突。商務(wù)談判則屬于非對稱博弈，參與各方目標不同，并從不同的角度來評估結(jié)果（例如，贏得合同 vs 最小化投資）。

完美信息 vs 不完美信息

另一種重要的博弈分類方式基于可獲取信息類型。完美信息博弈指每個玩家都能夠看到其他玩家的行動，例如國際象棋。在很多現(xiàn)代交互的環(huán)境中，每個玩家的行動是對別人隱藏的，博弈論將這些場景歸類為不完美信息博弈。從撲克等紙牌游戲到自動駕駛汽車，不完美游戲博弈就在我們身邊。

合作 vs 非合作

在合作博弈環(huán)境中，不同的參與者可以通過結(jié)盟來最大化最終結(jié)果。合同談判通常被認為是合作博弈。在非合作博弈環(huán)境中，參與者禁止結(jié)盟。戰(zhàn)爭是非合作博弈的終極案例。

同時 vs 序列

在序列博弈環(huán)境中，每個玩家了解對手之前的動作。棋盤游戲本質(zhì)上最具序列博弈屬性。在同時博弈場景中，雙方可以同時行動，例如證券交易。

零和 vs 非零和

零和游戲指一方有得其他方必有失，例如棋盤游戲。非零和游戲中，多個玩家可以從其他玩家的動作中獲益。經(jīng)濟交互中多個參與者合作擴大市場規(guī)模就是非零和博弈。

納什均衡

對稱博弈統(tǒng)治 AI 世界，其中大多數(shù)基于 20 世紀最著名的數(shù)學理論之一：納什均衡。納什均衡以美國數(shù)學家 John Forbes Nash 命名。本質(zhì)上，納什均衡描述了這樣的場景：每個玩家選擇一個策略，當一個玩家不改變策略時，沒有玩家能從改變策略中獲益。

已故美國數(shù)學家、經(jīng)濟學家 John Nash。

納什均衡是一個優(yōu)美且強大的數(shù)學模型，它可以解決很多博弈論問題，但在一些對稱博弈環(huán)境中捉襟見肘。對于初學者而言，納什方法假設(shè)玩家具備無限的計算能力，而現(xiàn)實環(huán)境中幾乎不存在這種情況。

此外，很多納什均衡模型無法解釋風險概念（常見于大多數(shù)非對稱博弈場景，如經(jīng)濟市場）。因此，很多非對稱博弈場景很難利用納什均衡實現(xiàn)。在多智能體 AI 系統(tǒng)中這一點尤為重要，這需要在解決方案的數(shù)學優(yōu)雅性和實現(xiàn)的可行性中找到合適的平衡。

博弈論中正在影響機器學習的新想法

多智能體 AI 系統(tǒng)是 AI 生態(tài)系統(tǒng)中最讓人著迷的領(lǐng)域之一。多智能體系統(tǒng)等領(lǐng)域的近期進展擴展了博弈論的邊界，它依賴該領(lǐng)域中最復雜的思想。作者在下文又列舉了出現(xiàn)在現(xiàn)代機器學習中的博弈論子領(lǐng)域的示例。

平均場博弈

平均場博弈（Mean Field-Games，MFG）是博弈論中比較新的領(lǐng)域。MFG 理論誕生于 2006 年，是 Minyi Huang、Roland Malhamé、Peter Caines、Jean-Michel Lasry 和菲爾茲獎得主 Pierre-Louis Lions 發(fā)表的一系列獨立論文中的一篇。

從概念上看，MFG 包含的方法和技術(shù)用于研究由「理性博弈方」組成的大群體下的微分博弈。這些智能體不光對自己的狀態(tài)（如財富、資產(chǎn)）有偏好，對群體中其他智能體的分布也存在偏好。MFG 理論為這些系統(tǒng)研究泛化納什均衡。

經(jīng)典的案例是如何讓幾個魚群以比較協(xié)調(diào)的方式沿相同方向游動。理論上，這種現(xiàn)象很難解釋，不過它基于這一事實：魚對最鄰近魚群的行為有反應。具體而言，每條魚并不關(guān)心其他魚，但是它關(guān)心附近作為一個整體統(tǒng)一移動的魚群。如果我們用數(shù)學術(shù)語表述的話，魚對魚群的反應是哈密頓-雅可比-貝爾曼方程（Hamilton-Jacobi-Bellman equation，簡稱 HJB 方程）。而整個魚群的行動是所有魚的動作集合，這對應了福克-普朗克方程（Fokker-Planck-Kolmogorov equation）。平均場博弈理論是這兩個公式的結(jié)合體。

平均場博弈中的魚群統(tǒng)一游動經(jīng)典案例。

隨機博弈

隨機博弈可以追溯至 1950 年代，由諾貝爾經(jīng)濟學獎獲得者 Lloyd Shapley 提出。從概念上來看，隨機博弈由有限數(shù)量的玩家在有限狀態(tài)空間中執(zhí)行，在每個狀態(tài)中，每個玩家從有限多的動作中選擇一個；最終動作組合決定了每個玩家的獎勵和下一個狀態(tài)的概率分布。

已故數(shù)學家、隨機博弈概念提出者 Lloyd Shapley。

隨機博弈的經(jīng)典形式是哲學家晚餐問題：有 n + 1 位哲學家 (n ≥ 1) 坐在圓桌旁，圓桌中間有一碗米飯，任意兩位相鄰的哲學家之間有一根筷子，筷子在兩人可及范圍內(nèi)。由于桌子是圓的，因此筷子的數(shù)量與哲學家人數(shù)一樣。為了吃到碗中的米飯，每位哲學家需要拿到可及范圍內(nèi)的兩根筷子。如果一位科學家吃到了，那么他的兩位鄰座就不能同時吃到。哲學家的生活很簡單，只有思考和吃飯，為了生存，哲學家必須一次次地思考和吃飯。該任務(wù)就是設(shè)計一個使所有哲學家生存下去的機制。

隨機博弈中的哲學家晚餐經(jīng)典案例。

演化博弈

演化博弈論（Evolutionary Game Theory，EGT）從達爾文進化論中獲得靈感。EGT 的起源可以追溯至 1973 年的 John Maynard Smith 和 George R. Price，也可以作為策略來分析，該數(shù)學標準可用于預測競爭策略的結(jié)果。

從概念上看，EGT 是博弈論概念在如下場景中的應用：通過選擇和復制的進化過程，隨著時間的變化，智能體群體使用不同策略來創(chuàng)建穩(wěn)定的解決方案。EGT 的主要思想是很多行為涉及群體中多個智能體的交互，任意一個智能體的成果都離不開其策略與其他智能體策略之間的交互。經(jīng)典博弈論專注于靜態(tài)策略（即策略不隨時間變化），而演化博弈論專注于策略隨時間的變化，以及在進化過程中最成功的動態(tài)策略。

EGT 的經(jīng)典案例是鷹鴿博弈，即讓鷹和鴿子圍繞可共用資源競賽。在該游戲中，每位選手嚴格遵循以下策略中的一個或全部：

鷹：發(fā)起攻擊行為，在受傷或?qū)κ趾笸酥敖^不停下。

鴿：如果對手發(fā)起攻擊行為，直接撤退。

如果我們假設(shè)存在如下情況：1）當兩個個體都發(fā)起攻擊行為時，戰(zhàn)斗最終走向結(jié)束，二者具備同等受傷概率；2）戰(zhàn)斗成本將個體的健康度降低了某個常量 C；3）當鷹鴿相遇時，鴿子直接逃跑，鷹獲取資源；4）兩只鴿子遇到資源并平分資源，則鷹鴿博弈的健康情況如下所示：

逆博弈論

很多案例不需要優(yōu)化參與者的策略，而是圍繞理智參與者的行為設(shè)計游戲，這就是逆博弈論。拍賣被認為是逆博弈論中的主要案例。

總之，隨著人工智能的發(fā)展，博弈論正在復興。阿蘭·圖靈或馮·諾伊曼等計算機科學界傳奇人物提出的博弈論原則現(xiàn)在已經(jīng)是全球某些最智能系統(tǒng)的核心，人工智能近期進展也有助于推動博弈論研究的發(fā)展。隨著 AI 繼續(xù)進化，我們將看到更多博弈論新想法找到融入主流深度學習系統(tǒng)的方式。

原文鏈接：https://towardsdatascience.com/a-crash-course-in-game-theory-for-machine-learning-classic-and-new-ideas-50e33ba2636d

本文為機器之心編譯，轉(zhuǎn)載請聯(lián)系本公眾號獲得授權(quán)。

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

加入機器之心（全職記者 / 實習生）：hr@jiqizhixin.com

投稿或?qū)で髨蟮溃篶ontent@jiqizhixin.com

廣告 & 商務(wù)合作：bd@jiqizhixin.com

原標題：《博弈論速成指南：那些融入深度學習的經(jīng)典想法和新思路》

閱讀原文