美國工程院院士深度解析:博弈論與控制面臨哪些挑戰和機遇?
翻譯 | 馮維維
近年來,博弈論相關的概念和工具在控制、多智能體系統和網絡研究中的應用幾乎呈指數增長。
在接受《國家科學評論》(NSR)訪談時,美國國家工程院院士,伊利諾伊大學香檳分校Swanlund講席教授(該校教師最高榮譽)、高等研究中心主任,IEEE控制系統學會和美國自動控制理事會前任主席,國際動態博弈論學會創始主席塔米爾·巴薩(Tamer Basar),談到了最近博弈論在控制和網絡研究中的新興角色、它如何將控制領域的邊界拓展到工程以外的學科,以及未來的機遇和挑戰。
Tamer Basar(Swanlund講席教授、伊利諾斯大學香檳分校高等研究中心主任)
博弈論是什麼及其在控制中的作用
NSR:您能簡單地告訴我們什麼是博弈論、它是做什麼的嗎?
Basar:
博弈論解決的是多個決策者即博弈參與者(某些情況下稱為代理人)之間的策略交互。由一個目標函數刻畫每個參與者在多個可能的博弈結果之間的排序偏好,她要麼試圖最大化目標函數(在此情況下,目標函數是效用函數或效益函數),要麼最小化目標函數(在這種情況下,我們稱目標函數為成本函數或損失函數)。
對非平凡博弈來説,參與者的目標函數取決於至少一位其他參與者的選擇(行為或決策變量),並且通常是所有參與者的選擇,因此參與者不能簡單地獨立於其他人的選擇而優化自己的目標函數。
因此,這使參與者的行動之間產生了耦合,並導致即便在非合作環境下,參與者在決策過程中也綁定在一起。
如果參與者能達成合作協議,形成集體性的、完全可信的行動或決策選擇,讓所有參與者都能儘可能地受益,那麼我們將處於合作博弈論的領域。
如果參與者之間不允許合作,那麼我們就處於非合作博弈論的領域。博弈論,作為一種系統性的方法,首先必須引入一個令人滿意的解概念。
首要地,解應具有這樣的特徵:所有參與者都不能通過單邊行動來提高收益,這就是所謂的非合作均衡或以約翰•納什的名字命名的納什均衡。
60多年前,約翰·納什引入了它,並且證明它存在於有限博弈(即每個參與者只有有限數量的替代方案的博弈)和混合策略中。對任意一個參與者,如果其他參與者按照納什均衡採取行動,這個參與者將無法通過偏離納什均衡來提高自己的收益。
請注意,我們不允許兩個或兩個以上的參與者從解點集體行動,因為這樣的集體行動需要合作,這是不允許在非合作博弈中發生的。
另一個非合作均衡解的概念是斯塔克爾伯格均衡(Stackelberg equilibrium),它實際上先於納什均衡提出。
其中,參與者的決策之間有一個層次,一些參與者被指定為領導者,有能力首先宣佈他們的策略(並承諾執行他們);其餘的參與者被指定為跟隨者,根據領導者的策略決定他們的策略(追隨者之間也存在相互博弈)。
然而,在宣佈策略之前,領導者會預測追隨者的反應,並以一種對自己最有利的方式決定其行動(就其目標函數而言)。
NSR:我們遇到的不同類型的博弈有哪些?
Basar:
我們可以把博弈分為兩大類,即合作博弈和非合作博弈。後一類是更廣泛意義下的控制界所感興趣的,我們可以對它做進一步的分類。
如果參與者的目標函數之和不能在適當的正縮放和/或不依賴於參與者的決策變量的平移後變為零,我們稱這樣的非合作博弈是嚴格的(或真正的)非零和博弈。
如果一個博弈只有兩個參與者,兩個參與者的目標函數之和為零,或者可以通過適當的正縮放和/或不依賴於參與者的決策變量的平移使其為零,我們稱它是零和博弈。
進一步的細分基於參與者可使用的行動方案性質,以及這些行動如何決定結果。如果每個參與者只有數量有限的行動方案,即參與者從有限集合(動作集)中選擇他們的動作,這種博弈就是有限博弈,否則就是無限博弈。
有限博弈也稱為矩陣博弈。如果參與者的動作集是連續的,且其目標函數相對於所有參與者的動作變量是連續的,則無限博弈被稱為連續核博弈。
正如目標函數所捕獲的,如果參與者的行為單獨決定結果,那麼這樣的博弈被認為是確定性博弈;而如果至少一個參與者的目標函數依賴於一個具有潛在概率分佈的附加變量(自然狀態),那麼我們就稱之為隨機博弈。
如果博弈描述(即參與者、目標函數和潛在概率分佈(如果是隨機的)是所有參與者的共同信息,那麼這就是完全信息博弈;否則我們就稱其為不完全信息博弈。
如果參與者只能獲得先驗信息(所有人共享),而不能獲得任何其他參與者的行動信息,我們會稱其為靜態博弈;否則,我們就稱其為動態博弈。如果每個參與者只行動一次,我們稱其為單次博弈;否則將稱其為多次博弈。請注意,單次博弈可能是動態的,多次博弈可能是靜態的。
如果決策過程的演化(由參與者隨時間控制)發生在連續的時間內,通常涉及一個微分方程,這樣的動態博弈就被稱為微分博弈;如果它發生在離散的時間範圍內,則動態博弈有時被稱為離散時間博弈。
NSR:策略的概念在博弈中起着重要作用,特別是在動態博弈中,是這樣嗎?
Basar:
確實如此。在動態博弈中,隨着博弈的進行,參與者獲得關於其他參與者過去行為的信息(完整或部分的),並在選擇自己的行為時使用這些信息。
例如,在有限動態博弈中,博弈過程可用樹結構表示(也稱為擴展式),其中每個節點代表一個參與者及其行動時間,節點的分支顯示該特定參與者可能的行動。
當參與者對其他參與者過去的行動沒有完整的信息時,就形成了參與者的信息集。在擴展式博弈中,參與者決定的不是他們的行動,而是他們的策略,即他們在每個信息集採取的行動。然後,根據策略以及在博弈樹上的位置,他們採取特定的行為。
因此,此時的均衡是定義在策略上而非行動上的。如果非要與控制論相比,那麼,策略就像控制律,或等價地,控制策略,它根據控制者所能獲得的信息,通常包括被控系統的狀態,來生成控制信號(或命令)作為系統的輸入控制。被控系統的狀態信息可以通過完美或含噪信道獲得。
NSR:請問控制和動態博弈之間是否存在關聯?
Basar:
的確有。控制,特別是最優控制,可以看作是單個參與者的動態(或微分)博弈。進一步,由於納什均衡的表徵和計算涉及到每個參與者個體優化問題的解,因此給最優控制開發的工具,如動態規劃或極大值原理,在動態博弈中肯定是有用的。
然而,如果參與者有不同類型的信息,那麼動態博弈的情況就會更加複雜。即使一些參與者具有開環信息,而其他參與者都具有完全信息,不論是動態規劃還是極大值原理,都不能用來構造納什均衡。
對其他類型的信息結構,情況更加複雜。這在目前仍然是一個活躍的研究領域,而且動態博弈中信息結構的複雜性也是我多年來一直很感興趣的問題。
對於零和動態博弈或微分博弈來説,情況更容易處理一些,這導致了魯棒控制的成功,其中系統可能有模型不確定性和/或未知輸入。
基於零和博弈論方法的魯棒控制允許系統的未知信息被視為對手博弈者所控制的輸入,而其目標與控制器完全相反。
這種控制器和虛擬對手之間的直接利益衝突導致了零和動態博弈的形成,其在給定的控制器信息結構下的極大極小解或鞍點解也由對手(進行收益最大化的博弈參與者)共享,從而為系統提供了魯棒控制律。
這種方法已經產生了不同信息結構下線性和非線性系統的最優H∞設計(即H無窮控制),並已經為經濟學家所採用,例如被諾貝爾獎得主拉爾斯·漢森(Lars Hansen)和托馬斯· 薩金特(Thomas Sargent)2008年在普林斯頓大學出版社出版的《魯棒性》(Robustness)一書中採用。
博弈論的歷史演變
NSR:博弈論的起源可以追溯到什麼時候?您可以談談相關歷史嗎?
Basar:
1944年,約翰·馮·諾伊曼和奧斯卡·摩根斯坦合著的《博弈論與經濟行為》(Theory of Games and Economic Behavior)一書的出版,被普遍認為是這一領域的正式起點。此後,博弈論的理論成果不斷增多,應用的範圍和領域也在不斷擴大。
作為對該領域活力的認可,到目前為止,共有10個諾貝爾經濟學獎,其主要工作是博弈論。
1994年,約翰·海薩尼(John Harsanyi)、約翰·納什( John Nash)和萊因哈德·澤爾騰(Reinhard Selten)獲得了第一次博弈論相關的諾獎,以表彰他們“在非合作博弈理論中對均衡的開創性分析”。
2005年,博弈論方面的第二次諾貝爾獎頒給了羅伯特•奧曼(Robert Aumann)和托馬斯•謝林(Thomas Schelling),獲獎理由是“通過博弈論分析加深了我們對沖突和合作的理解”。
2007年,博弈論相關的第三次諾貝爾獎頒給了列昂尼德·赫維奇(Leonid Hurwicz)、埃裏克·馬斯金(Eric Maskin)和羅傑·邁爾森( Roger Myerson),認為他們“為機制設計理論奠定了基礎”。
最近一次是2012年,阿爾文·羅斯(Alvin Roth)和勞埃德·沙普利(Lloyd Shapley)因“關於穩定分配的理論和市場設計的實踐”而獲獎。在這個與博弈論貢獻相關的最高水平獎的名單中,我還應該加入1999年的克拉福德獎(由瑞典皇家科學院設立的生物科學最高獎項),當年該獎項授予約翰·梅納德·史密斯(John Maynard Smith),以及恩斯特·邁爾(Ernst Mayr)和G·威廉姆斯 (G. Williams),因為他們“發展了進化生物學的概念”。
其中,通過其在演化博弈論和進化穩定策略/均衡方面的研究,史密斯這一被公認的貢獻有很強的博弈論基礎。
儘管馮·諾依曼和摩根斯坦1944年的書籍被普遍認為是博弈論科學方法的起點,但博弈論的概念和一些孤立的關鍵結果卻可以追溯到更早,甚至是幾個世紀前。
16年前,即1928年,約翰·馮·諾依曼本人徹底解決了零和博弈中一個懸而未決的基本問題,即證明了每個有限的兩人零和博弈在混合策略下都存在一個鞍點,這就是眾所周知的極小極大定理——這是埃米爾·博雷爾(Emile Borel)八年前猜測為錯誤的結果。
博弈論思考的一些早期痕跡還可見於安德烈·瑪麗·安培(Andre-Marie Ampere,1775-1836)1802年的著作《關於數學的思想》,而他則受到了喬治·路易·布豐(Georges Louis Buffon,1707-1788)1777年著作的影響。
NSR:在此期間,最優控制方面是否有平行發展,對微分博弈論的發展有何影響?
Basar:
事實上,在大約相同的時間範圍內,我們看到理查德·貝爾曼(上世紀50年代)在蘭德公司工作時引入了動態規劃,作為最優控制和更廣泛意義上的多階段決策的主要原則和工具。
20世紀50年代初期,蘭德公司(美國最重要的以軍事為主的綜合性戰略研究機構)吸引並安置了當時最偉大的一些人物,除了貝爾曼之外,還有倫納德·貝爾科維奇(Leonard D. Berkovitz)、大衞·布萊克韋爾(David Blackwell)、喬治·丹茨格(George Dantzig)、温德爾·弗萊明(Wendell Fleming)、M.R.海斯滕斯(M.R. Hestenes)、魯弗斯·伊薩克斯(Rufus Isaacs)、塞繆爾·卡林(Samuel Karlin)、約翰·納什、J.P.拉薩爾(J.P. LaSalle)和勞埃德·沙普利(Lloyd Shapley)(僅列舉其中幾位)。
這些人和其他人奠定了決策論和博弈論的基礎,從而為控制研究增添了動力。
在這種獨特的、非常有益的環境中,貝爾曼早在1949年就開始了多階段決策過程的研究,但更充分的(研究)是在1952年之後—— 一個也許鮮為人知的歷史事實是,貝爾曼在蘭德工作時的早期主題之一就是博弈論(零和與非零和博弈),他與布萊克韋爾、拉薩爾共同撰寫了研究報告。
32年後貝爾曼寫了一本內容翔實且有趣的自傳(《颶風眼》,Eye of the Hurricane,世界科學出版社,新加坡),在1984年3月19日他英年早逝前不久完成的這本書中,貝爾曼洋洋灑灑地描述了蘭德公司的研究環境和他創造“動態規劃”這個術語的原因。
動態規劃在不同類型問題中的應用,以及“動態規劃函數方程”的獲得,促使貝爾曼隨後提出“最優性原理”作為一個統一的原則。這一原則由幾乎同時同樣供職於蘭德公司的伊薩克斯在微分博弈的更廣闊背景下,將其稱為“變遷原則”,這一稱呼抓住了對抗環境下策略性動態決策特性。
事實上,伊薩克斯被認為是在零和框架下競爭性連續時間動態決策中創造了“微分博弈”一詞的人,也有人把最優性原理歸功於他,因為它可以看作是變遷原則的一個特例。由於工作的機密性,多年來伊薩克斯一直未能在公開文獻中公佈他的發現(貝爾曼則可以),直到1965年其書籍《微分博弈》(Differential Games)的出版。
該書引起了研究興趣的躍遷,首先是追逃博弈(更廣泛地,零和微分博弈),後來是上世紀70年代初的非零和微分博弈,由哈佛大學的何毓琦及其合作者領頭。
博弈論研究的挑戰
NSR:您能談談目前博弈論,特別是在動態博弈方面的主要研究領域,以及主要的挑戰是什麼嗎?
Basar:
我談幾個方面,但絕非完整和詳盡。像我之前簡單説過的,信息結構在動態博弈的非合作均衡表徵和計算中所起的作用是目前一個活躍的研究領域,因為其中仍有許多複雜的因素尚未完全得到理解。
這些都與均衡對決策過程中博弈者所獲得信息類型的相關性有關係:誰與誰交流、一個博弈者的行動怎麼從質量和數量上影響其他博弈者接收到的與其決策相關的信息。
顯然,這些問題在單一決策者情況下都不會出現。還有不同參與者的理性問題——有意或無意的理性缺失,即使他們在某種程度上是理性的,其理性的“邊界”是什麼(可能是由於對資源如計算能力或感知能力的約束所導致的限制造成),以及這一切如何影響均衡。還有一個問題是均衡對未被建模的不確定性以及對抗性干預(如加在通信鏈路上的)的魯棒性。
之前我提到過魯棒(H-∞)最優控制成功地與零和微分博弈相聯繫,這對其他學科也有影響,併為與非零和動態博弈建立類似的聯繫提供了相當豐富的路徑。
另一個內容豐富的研究領域是網絡博弈。
廣義上,這裏的背景是存在一個底層的網絡或圖形結構,可能是多層的,約束着參與者之間的交互:由鄰居關係決定誰與誰交流,誰與誰合作,以及哪些參與者的目標或動態是相互耦合的。
另一個高產的研究領域是平均場博弈,涉及到另一種結構特異性,其中參與者的互動不是與其他個體參與者進行,而是與無限數量的參與者對應的整體進行,單個成員的行為對羣體的整體行為只有極小的影響。這是我本人目前感興趣的一個方向。
最後,當前一個日益增長的研究領域涉及到將機器學習,特別是強化學習工具引入博弈論,以解決“無模型”的多智能體決策問題,其中參與者並沒有其他參與者的變化規律或目標函數信息——而其他參與者的行為會影響他們的表現,但會將自己通過觀察所得的數據,比如在決策過程中獲得的“獎勵”,整合到自己的行為生成算法中。
早在2018年1月,NSR就有一個關於“機器學習”的專題(第1期第5卷),我看到了將其中的框架和工具擴展到博弈論框架下多智能體系統研究的巨大潛力。這也是我目前感興趣的領域之一。
如何為博弈論的研究做好準備
NSR:對於這一領域的新入門者,如研究生,您有何建議?在深入研究博弈論,特別是動態博弈之前,他們應該具備什麼背景?
Basar:
首先,強大的數學背景,尤其是實分析,是必須的。其次,深入掌握(確定性的、隨機的,以及最優的)控制論知識是必不可少的,然後才能面對從單一到多個決策者所產生的複雜問題。
當然,作為其中的一部分,還需要紮實的概率、隨機過程、最優化等知識,以及博弈論方面的一些入門知識也是需要的。
最後,根據要進行的研究所涉及的具體應用領域,一些領域的知識也必不可少。當然,更不必説一個研究領域的新入門者還應該熟悉該領域已完成的研究成果以及目前的相關文獻。
【來源:科學網】
聲明:轉載此文是出於傳遞更多信息之目的。若有來源標註錯誤或侵犯了您的合法權益,請作者持權屬證明與本網聯繫,我們將及時更正、刪除,謝謝。 郵箱地址:newmedia@xxcb.cn