機(jī)器之心

選自TowardsDataScience

作者：Jesus Rodriguez

機(jī)器之心編譯

參與：魔王、杜偉

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

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

博弈論是具備激勵(lì)機(jī)制的概率。

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

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

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

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

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

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

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

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

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

本文作者 Jesus Rodriguez。

數(shù)據(jù)科學(xué)家應(yīng)該知道的 5 種博弈

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

作者提出的五元素標(biāo)準(zhǔn)。

對(duì)稱(chēng) vs 非對(duì)稱(chēng)

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

完美信息 vs 不完美信息

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

合作 vs 非合作

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

同時(shí) vs 序列

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

零和 vs 非零和

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

納什均衡

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

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

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

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

博弈論中正在影響機(jī)器學(xué)習(xí)的新想法

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

平均場(chǎng)博弈

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

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

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

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

隨機(jī)博弈

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

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

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

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

演化博弈

演化博弈論（Evolutionary Game Theory，EGT）從達(dá)爾文進(jìn)化論中獲得靈感。EGT 的起源可以追溯至 1973 年的 John Maynard Smith 和 George R. Price，也可以作為策略來(lái)分析，該數(shù)學(xué)標(biāo)準(zhǔn)可用于預(yù)測(cè)競(jìng)爭(zhēng)策略的結(jié)果。

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

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

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

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

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

逆博弈論

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

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

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

本文為機(jī)器之心編譯，轉(zhuǎn)載請(qǐng)聯(lián)系本公眾號(hào)獲得授權(quán)。

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

加入機(jī)器之心（全職記者 / 實(shí)習(xí)生）：hr@jiqizhixin.com

投稿或?qū)で髨?bào)道：content@jiqizhixin.com

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

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

閱讀原文