基于事件驅(qū)動控制的混雜動態(tài)博弈系統(tǒng)的納什均衡分析

陳向勇 曹進德 趙 峰 姜曉偉

(1.臨沂大學(xué)自動化與電氣工程學(xué)院,山東臨沂 276005;2.東南大學(xué)數(shù)學(xué)學(xué)院,江蘇南京 211189;3.中國地質(zhì)大學(xué)復(fù)雜系統(tǒng)先進控制與智能自動化湖北省重點實驗室;自動化學(xué)院,湖北武漢 430074)

1 引言

20世紀60年代中期,諾貝爾獎獲得者澤爾騰將納什均衡概念引入動態(tài)分析,開創(chuàng)了動態(tài)博弈的研究.經(jīng)過近六十年發(fā)展,一系列重要成果被提出,比如,屬于連續(xù)動態(tài)博弈范疇的微分對策[1]已被成功應(yīng)用于飛行器追逃控制、多目標協(xié)同作戰(zhàn)等方面;源于棋牌游戲的事件動態(tài)博弈[2]在2007年被首次提出并實現(xiàn)了對邏輯層面有限階段動態(tài)博弈的分析和求解[3].

近年來,混雜動態(tài)博弈已經(jīng)成為新的研究熱點.它源于作戰(zhàn)行動和棋牌游戲,描述的是兩個非合作智能主體之間事件動態(tài)博弈和微分對策相互作用的多階段博弈過程.然而,邏輯狀態(tài)演化的引入使得系統(tǒng)結(jié)構(gòu)復(fù)雜度變高,導(dǎo)致傳統(tǒng)的博弈模型無法準確地描述系統(tǒng)的內(nèi)在結(jié)構(gòu)和演化特征,對其進行建模和求解變得非常困難,如何建立更有效描述混雜動態(tài)博弈演化過程的數(shù)學(xué)模型成為首要解決的問題.其中,徐等首次通過一個空戰(zhàn)實例介紹了基于事件觸發(fā)的混雜動態(tài)博弈問題的內(nèi)容與處理方法[4].此后,針對階段數(shù)較少的混雜動態(tài)博弈,陳等建立了基于Lanches-ter方程的狀態(tài)空間表述模型,分別對連續(xù)最優(yōu)策略和事件變招策略的求解[5-6].針對邏輯層面的有限動態(tài)博弈,程代展教授給出了演化博弈的代數(shù)狀態(tài)空間描述和博弈策略的矩陣表示[7-8].2019年,借鑒混雜動態(tài)系統(tǒng)的思想,文獻[9]首次提出了博弈切換演化動力學(xué)框架(圖1a所示),即不同博弈模式對應(yīng)不同環(huán)境狀態(tài),個體行為和當前時間進行博弈共同決定下一時間進行的博弈,并研究了網(wǎng)絡(luò)結(jié)構(gòu)群體合作演化行為.以上研究結(jié)果都為混雜動態(tài)博弈系統(tǒng)的分析和控制提供了較好的基礎(chǔ)模型.

當前,人工智能在圍棋、星際爭霸等博弈場景的應(yīng)用[10-11],為動態(tài)博弈問題的求解帶來便利并取得算法方面的進步,使得博弈系統(tǒng)的策略集和階段數(shù)逐漸龐大,呈現(xiàn)出規(guī)模大和結(jié)構(gòu)復(fù)雜度高的特點.特別在博弈演化過程中,預(yù)測結(jié)果千變?nèi)f化,導(dǎo)致傳統(tǒng)的博弈理論無法準確分析其演化規(guī)律.因此,眾多研究者開始重新審視復(fù)雜動態(tài)博弈中納什均衡的意義和作用,并對博弈從初始狀態(tài)到均衡的動態(tài)演化過程及參與者的運動規(guī)律進行深入探索.其中,演化穩(wěn)定策略[12-13]為復(fù)雜博弈均衡解的研究實現(xiàn)了突破.文獻[14-15]對多階段演化博弈中的有限理性問題進行了理論分析和應(yīng)用驗證,實現(xiàn)了對傳統(tǒng)博弈問題參與者“理性”基礎(chǔ)的修正.文獻[16]給出多階段有限博弈的均衡分析和一致性預(yù)測成立條件.文獻[17]針對具有大策略集的多階段博弈給出期望條件,實現(xiàn)了均衡的存在性分析和求解.文獻[18-19]針對復(fù)雜動態(tài)博弈的演化特點,利用事件樹給出了激勵均衡、完美子博弈強均衡和開環(huán)反饋納什均衡的概念和性質(zhì).這都為混雜動態(tài)博弈均衡問題的分析提供理論借鑒.

另一方面,復(fù)雜博弈均衡的求解在智能優(yōu)化算法方面[20]取得了進步.針對非合作博弈系統(tǒng),提出時變納什均衡和廣義納什均衡等概念,設(shè)計了有效求解的分布式智能優(yōu)化方法[21-23].由此,上述研究成果已經(jīng)在大規(guī)模復(fù)雜博弈的均衡求解方面發(fā)揮了作用.然而,混雜動態(tài)博弈的均衡解需要在多階段演化后通過動態(tài)調(diào)整才能達到,而且參與者對保證利益最大化行動的理解存在較大差異,而針對混雜動態(tài)博弈均衡的存在性分析、性質(zhì)分類等研究成果較少.

受上述分析的啟發(fā),本文研究了基于事件驅(qū)動控制的混雜動態(tài)博弈系統(tǒng)的納什均衡分析問題.首先,分析了事件驅(qū)動機制對混雜動態(tài)博弈過程的影響,進而,在進行狀態(tài)空間描述的基礎(chǔ)上,給出了混雜動態(tài)博弈的納什均衡的定義,并建立了對應(yīng)博弈系統(tǒng)的策略型模型.其次,結(jié)合Lanchester方程,分別討論了兩類混雜動態(tài)博弈系統(tǒng)的均衡問題,包括事件驅(qū)動策略設(shè)計和固定的情況,獲得了均衡解存在的必要條件.最后,數(shù)值模擬進行了應(yīng)用分析,驗證了所取得結(jié)果的合理性,并總結(jié)了混雜動態(tài)博弈研究的未來工作.

2 模型描述和基礎(chǔ)知識

圖1展示了非合作動態(tài)博弈雙方的混雜動態(tài)演化過程,其中,X和Y為博弈雙方的決策者,從圖1不難看出,混雜動態(tài)博弈的演化過程包含兩個層面,一是決策者的變招X和Y發(fā)生在離散時刻,每次變招都是根據(jù)博弈雙方觀察和探測的態(tài)勢信息確立的,都會改變對陣的形勢,引起連續(xù)系統(tǒng)的結(jié)構(gòu)性變化,表現(xiàn)為事件驅(qū)動的邏輯狀態(tài)變化.另一層面就是雙方連續(xù)動態(tài)的博弈過程,具體是根據(jù)決策者的指令和系統(tǒng)的結(jié)構(gòu)特征而不斷調(diào)整連續(xù)控制輸入,來改變各單元狀態(tài)量,但是博弈雙方的態(tài)勢不會發(fā)生改變,屬于系統(tǒng)結(jié)構(gòu)不變情況下的連續(xù)控制過程,如此構(gòu)成了混合動態(tài)博弈的演化過程.由此,依據(jù)文獻[4-5]的建模原則,可得

圖1 混雜動態(tài)博弈系統(tǒng)演化結(jié)構(gòu)圖Fig.1 Evolution structure of hybrid dynamic games system

其中:x和y是X和Y的狀態(tài)向量;t ∈[0,T],T是終端時刻;Ex和Ey分別是雙方引起系統(tǒng)結(jié)構(gòu)變化的事件驅(qū)動控制策略;U和V是連續(xù)控制輸入向量.進而,定義如下的性能指標函數(shù):

其中:Φ(x(T),y(T))為與終端狀態(tài)向量有關(guān)的連續(xù)函數(shù);h(x,y,Ex,Ey,U,V)為連續(xù)函數(shù).由此構(gòu)成了混合動態(tài)博弈系統(tǒng)的狀態(tài)空間描述的一般形式.

由此,設(shè)博弈雙方在tk(1 ≤k<∞)時進行引起系統(tǒng)結(jié)構(gòu)變化的事件驅(qū)動變招,其中tk ∈[t0,tf],t0≤t1≤···≤tk≤···≤tf,t0為初始時刻,tf為終端時刻,可確定策略集為U={U1,U2,··· ,Uk,},V={V1,V2,··· ,Vk},Ex={Ex1,Ex2,··· ,Exk},Ey={Ey1,Ey2,··· ,Eyk}.定義博弈雙方在確定連續(xù)控制和事件變招策略集后的對陣態(tài)勢集合為S={s0,s1,··· ,sk,sf},s0={sx0,sy0}為初始態(tài)勢,演化穩(wěn)定結(jié)局為sf={sxf,syf},對應(yīng)的sq(q=1,2,··· ,k)為演化過程中雙方確定策略后的態(tài)勢,由此可以得到

由此,可以用一個七元數(shù)組建立混雜動態(tài)博弈系統(tǒng)的策略型模型

其中:P={X,Y}是博弈雙方的決策者集合,決策雙方對應(yīng)的狀態(tài)向量一般定義為x={x1,x2,··· ,xn}和y={y1,y2,··· ,ym};S={s0,s1,··· ,sk,sf}為態(tài)勢集合,C={U,V}為連續(xù)控制策略集合;E={EX,EY}為雙方根據(jù)態(tài)勢制定的事件驅(qū)動策略;Σ:s×(E×C)→s為態(tài)勢轉(zhuǎn)移函數(shù)集合;R是由博弈雙方制定的演化規(guī)則,包括行動集、信息集和預(yù)先制定的規(guī)則等;J為性能指標函數(shù).

本文主要是針對所建立基于事件驅(qū)動控制的混雜動態(tài)博弈系統(tǒng),對其納什均衡進行分析.根據(jù)博弈論和微分對策理論,當混雜動態(tài)博弈的事件觸發(fā)次數(shù)較少和策略集合較小時,可知博弈的納什均衡需要滿足

注1式(4)中給出的納什均衡的定義是按照傳統(tǒng)博弈論和微分對策的基礎(chǔ)理論所提出的.由于本文研究的混雜動態(tài)博弈主要是由事件驅(qū)動控制和連續(xù)微分對策相互作用所組成的,而每一次變招的發(fā)生都和系統(tǒng)的結(jié)構(gòu)特性、參數(shù)和性能指標等有著緊密的聯(lián)系,因此在每一次事件驅(qū)動策略不變的連續(xù)博弈演化中,納什均衡解都是存在的.

3 主要結(jié)果

本節(jié)重點考慮事件驅(qū)動控制策略和連續(xù)控制策略對混雜動態(tài)博弈演化的影響,將分別對事件驅(qū)動的混雜動態(tài)博弈的均衡問題和事件策略固定的混雜動態(tài)博弈系統(tǒng)的均衡問題進行分析.

3.1 事件驅(qū)動控制的混雜動態(tài)博弈的納什均衡

針對系統(tǒng)(1)和性能指標(2),設(shè)博弈雙方的連續(xù)控制輸入量是固定量,則混雜動態(tài)博弈的納什均衡問題轉(zhuǎn)化為求解最佳事件驅(qū)動策略(E?x,E?y)使得

其中:αji>0為Y方第j個單元對X方第i個單元的損耗系數(shù);βij>0為X方第i個單元對Y方第j個單元的損耗系數(shù);ηi和θj分別為終端狀態(tài)所對應(yīng)的重要性加權(quán)因子;ψji ∈{0,1}和φij ∈{0,1}是事件驅(qū)動變量.特別是,當在tq時刻發(fā)生變招時會引起對應(yīng)值的選取,則對應(yīng)的事件驅(qū)動策略的表達式為

其中:ψjqi為事件驅(qū)動策略確定后Y方第jq個單元會對陣X方的第i個單元;同樣,φiq′j表示X方第iq′個單元會對陣Y方第j個單元;{1q,··· ,nq}∈{1,··· ,n}表示Y方在tq時刻變招發(fā)生后的選擇的對陣方式;同樣{1q′,··· ,mq′}∈{1,··· ,m}表示X方在tq時刻變招發(fā)生后的選擇的對陣方式.

注2以上討論的模型(6)屬于系統(tǒng)(1)的范疇,可以改寫成其中α和β為對應(yīng)αji>0和βij>0的系數(shù)矩陣.同樣,對應(yīng)的性能指標(7)屬于指標(2)的范疇.

注3因為ψjqi和φiq′j都是0-1型事件驅(qū)動變量.根據(jù)Lanchester方程的基礎(chǔ)理論,當上述的矩陣中列和條件被滿足時,表示博弈雙方在選擇對陣單元的時候必須集中全部力量攻擊對方.

由此,根據(jù)動態(tài)博弈求解均衡的極大極小值原理,可以得到上述博弈系統(tǒng)均衡存在的必要條件.

定理1 設(shè)上述混雜動態(tài)博弈系統(tǒng)的伴隨函數(shù)為λ={λ1,··· ,λm},μ={μ1,··· ,μn},對應(yīng)系統(tǒng)的Hamilton函數(shù)為

注4此定理的具體證明過程可參考文獻[6]給出的定理證明.

3.2 事件策略固定的混雜動態(tài)博弈的納什均衡

針對系統(tǒng)(1)和性能指標(2),設(shè)博弈雙方事件驅(qū)動策略是固定不變的,則混雜動態(tài)博弈的均衡問題轉(zhuǎn)化為求解最優(yōu)控制策略(U?,V ?)使得

注6根據(jù)Lanchester方程的基礎(chǔ)理論,當上述的矩陣中列和和行和條件被滿足時,所表示的物理含義是指博弈雙方在對陣選擇中己方的一個單元只能選擇對陣對方的一個單元.

由此,針對博弈雙方的連續(xù)控制輸入ui(t)∈[u?,

其中:u?,u?,v?,v?,M0和N0為非負實數(shù),q=1,··· ,k.

證 根據(jù)式(15)可知

注9本部分討論的事件驅(qū)動策略是不變的,但是變招時刻是需要計算出來,根據(jù)文獻[5]提供的計算步驟,可以從終端時刻開始往前逐級求取每一時間區(qū)間[tq?1,tq]內(nèi)的最優(yōu)連續(xù)控制策略,在此基礎(chǔ)上,利用靜態(tài)優(yōu)化方法可以求得變招時刻以及最終整個混雜博弈系統(tǒng)的納什均衡.

注10如果變招時刻也是固定,這樣整個混雜動態(tài)博弈系統(tǒng)就被劃分為k+1個微分對策子系統(tǒng),只需要按照微分對策原理,求出每一時間段內(nèi)的子博弈系統(tǒng)的納什均衡并將其整合,所對應(yīng)的結(jié)果就是整個混雜博弈系統(tǒng)的納什均衡結(jié)果.

3.3 應(yīng)用例子

近年來,Lanchester方程已被成功應(yīng)用于市場競爭、公共交通投資、人口預(yù)測模型等[24-25].文獻[5-6]也給出了兩類基于Lanchester方程的混雜動態(tài)博弈系統(tǒng)模型.由此,本文針對與系統(tǒng)模型(6)和模型(16)有關(guān)的應(yīng)用例子進行均衡分析.

例1 設(shè)系統(tǒng)的連續(xù)控制輸入量全為0,考慮如下混雜動態(tài)博弈模型

設(shè)系統(tǒng)狀態(tài)的初始值為x10=100,y10=30,y20=30,終端時間為T=0.489.首先根據(jù)定理1可以求出納什均衡解滿足的條件為

進而,根據(jù)文獻[6]的理論結(jié)果,可知,對于Ex在tq=0.384時刻會發(fā)生一次變招,對應(yīng)的事件驅(qū)動策略為

則基于系統(tǒng)(21)和性能指標(22)的事件驅(qū)動的混雜動態(tài)博弈系統(tǒng)的納什均衡滿足

例2 在例1的基礎(chǔ)上,保持系統(tǒng)模型不變,但性能指標為

由此,按照已取得的理論分析結(jié)果,可以求出在博弈演化時間段內(nèi)沒有新的變招發(fā)生,則對應(yīng)博弈系統(tǒng)的納什均衡滿足

注11從例1和例2可以看出,上述事件驅(qū)動的混雜動態(tài)博弈系統(tǒng)納什均衡的存在性與模型的系數(shù)和性能指標的重要性因子有關(guān)系.

則按照本文的理論分析結(jié)果和文獻[5]的基本理論,可以得到變招時刻為t1=2.5,對應(yīng)博弈系統(tǒng)的納什均衡解(U?,V ?)需要滿足

注12從例3可以看出,在事件驅(qū)動策略固定的前提下,混雜博弈系統(tǒng)的納什均衡的存在性與變招發(fā)生的時刻以及最優(yōu)連續(xù)控制輸入有關(guān)系.

4 結(jié)論和展望

本文對基于事件驅(qū)動的混雜動態(tài)博弈系統(tǒng)的均衡問題進行了研究.在建立系統(tǒng)的狀態(tài)空間模型和策略型表達式的基礎(chǔ)上,分析了事件驅(qū)動控制在混雜動態(tài)博弈演化中的作用和意義,給出了傳統(tǒng)意義上的納什均衡的定義.進而,針對事件驅(qū)動變化的混雜動態(tài)博弈系統(tǒng)和事件策略固定的混雜動態(tài)博弈系統(tǒng),分別對納什均衡的存在性進行了分析,展示出混雜動態(tài)博弈系統(tǒng)在一定條件下納什均衡的特點.最后通過應(yīng)用分析展示了分析結(jié)果的可行性.

然而,混雜動態(tài)博弈的研究尚處于起步階段.本文的主要研究也主要是結(jié)合Lanchester方程,在一定假設(shè)條件的基礎(chǔ)上對兩類特殊的混雜動態(tài)博弈系統(tǒng)的均衡問題進行研究.僅僅考慮了理性的博弈決策方遵守一致預(yù)測的情況,沒有給出一般性的結(jié)論.基于此,針對于混雜動態(tài)博弈系統(tǒng)的建模、分析、控制和應(yīng)用問題,未來的研究工作具體包括:

1) 如何較好地描述內(nèi)在演化規(guī)律和結(jié)構(gòu)特征并建立模型是混雜動態(tài)博弈首要解決的問題.近年來,網(wǎng)絡(luò)科學(xué)的發(fā)展及不對稱博弈方向的深入研究,為探討具有大策略集和多階段數(shù)的混雜動態(tài)博弈的演化特征提供了啟發(fā)和借鑒.一方面,針對連續(xù)動態(tài)博弈,文獻[26]建立了基于Lanchester方程的兩階段攻防對抗博弈系統(tǒng)的網(wǎng)絡(luò)化模型.針對邏輯層面的動態(tài)博弈,文獻[27]給出了考慮每個節(jié)點的演化方程,建立了表述其演化特征的邏輯動態(tài)模型,給出了切換拓撲的網(wǎng)絡(luò)演化博弈的代數(shù)空間描述.2020 年,梅森·波特指出多層時序網(wǎng)絡(luò)已成為未來網(wǎng)絡(luò)科學(xué)的研究熱點之一[28].由此,網(wǎng)絡(luò)科學(xué)的發(fā)展為探討更復(fù)雜的混雜動態(tài)博弈系統(tǒng)的內(nèi)在規(guī)律和演化特征并建立更準確的模型提供了啟發(fā)和借鑒.

2) 博弈分析的目的是預(yù)測博弈的結(jié)果.由于大策略集和多階段數(shù)的影響,混雜動態(tài)博弈對陣局勢更為重要,納什均衡的達到應(yīng)當是在多次博弈后通過動態(tài)調(diào)整才能達到的,具有“相對性”和“動態(tài)性”.同時,在多階段演化中,博弈決策雙方產(chǎn)生不理性決策,使得傳統(tǒng)的一致預(yù)測條件不再成立,這就需要給出“理性”決策主體一致性預(yù)測成立條件,這樣才能混雜動態(tài)博弈研究目的與任務(wù),這是實現(xiàn)混雜博弈控制的基本條件,也是設(shè)計最優(yōu)策略求解的關(guān)鍵前提.

3) 混雜動態(tài)博弈典型特點就是具有較大的策略集和階段數(shù),這必然會給最優(yōu)策略的設(shè)計和求解帶來極大的困難,因此需要通過網(wǎng)絡(luò)節(jié)點評估和拓撲結(jié)構(gòu)分析,研究給出網(wǎng)絡(luò)演化莫模型中重要節(jié)點的判別條件,設(shè)計消除失效策略的剪枝搜索方法并對大策略集空間簡化,是混雜動態(tài)博弈理論研究的另一關(guān)鍵突破.同時,需要注意的時,在混雜動態(tài)博弈的網(wǎng)絡(luò)演化中,網(wǎng)絡(luò)中多個個體之間需要互相通信和信息交互,這樣才能夠?qū)崿F(xiàn)博弈態(tài)勢的監(jiān)測和獲取.當出現(xiàn)不完全的不對稱信息時,博弈雙方的決策狀態(tài)會受到影響,從理論角度,就需要對衡量博弈雙方獲得信息的能力進行量化并在模型中體現(xiàn),而從算法角度,就需要對演化穩(wěn)定策略的求解進行算法設(shè)計,當前,分布式優(yōu)化[31-32]和強化學(xué)習(xí)技術(shù)[33]為復(fù)雜博弈問題的研究提供了算法方面的借鑒,但這也對本文研究的混雜動態(tài)博弈在理論和算法學(xué)方面的研究提出了新挑戰(zhàn).

4) 混雜動態(tài)博弈的理論體系的完善離不開應(yīng)用驗證.現(xiàn)代物流系統(tǒng)[29-30]規(guī)模大且結(jié)構(gòu)度復(fù)雜,是以離散事件為主的復(fù)雜的連續(xù)-離散事件相統(tǒng)一的混雜動態(tài)系統(tǒng).特別是,物流供需博弈演化具有混雜動態(tài)特性,考慮供應(yīng)量、需求量、供需速度、物流供需信息因素的影響,構(gòu)建以需求方和供給方為決策主體、以利益最大化為供需目的的網(wǎng)絡(luò)化混雜動態(tài)博弈模型;實現(xiàn)物流供需博弈系統(tǒng)的分析和求解,進而,通過建立網(wǎng)絡(luò)演化仿真平臺,實現(xiàn)對物流供需博弈的求解和應(yīng)用驗證,不斷豐富和更新混雜動態(tài)博弈系統(tǒng)分析和控制的理論和方法體系.