演化博弈的魯棒穩(wěn)定與鎮(zhèn)定

趙 榮, 馮俊娥

(山東大學(xué)數(shù)學(xué)學(xué)院,山東濟(jì)南 250100)

1 引言

博弈論又稱對(duì)策論,主要研究公式化了的激勵(lì)結(jié)構(gòu)間的相互作用,是研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法.博弈論的思想有著源遠(yuǎn)流長(zhǎng)的歷史,可以追溯到兩千多年前我國(guó)的“齊威王田忌賽馬”,一千五百多年前巴比倫猶太教法典中的“婚姻合同問題”等.直至1944年,馮·諾依曼和摩根斯坦出版著作《博弈論和經(jīng)濟(jì)行為》[1],創(chuàng)建了博弈論的一般理論方法,給出了博弈論的一般框架、概念術(shù)語(yǔ)和表示方法,這也被公認(rèn)為博弈論初步形成的標(biāo)志.一般來講,可以將博弈分為兩大類:合作博弈和非合作博弈.對(duì)于非合作博弈,約翰·納什在1951年提出了“Nash均衡”的概念[2].“納什均衡”被譽(yù)為現(xiàn)代博弈論中最重要的概念,隨著博弈論和經(jīng)濟(jì)學(xué)的發(fā)展,納什均衡已成為現(xiàn)代經(jīng)濟(jì)分析的出發(fā)點(diǎn)和關(guān)鍵性概念.關(guān)于合作博弈,羅伊德·沙普利在1962年提出了“Shapley值”這一重要概念[3],對(duì)合作博弈的分配問題做出了重要貢獻(xiàn).

作為一種基本的數(shù)學(xué)工具,矩陣?yán)碚撛跀?shù)學(xué)學(xué)科與其他學(xué)科技術(shù)領(lǐng)域,諸如數(shù)值分析、優(yōu)化理論、微分方程、概率統(tǒng)計(jì)、運(yùn)籌學(xué)、控制論、系統(tǒng)工程等學(xué)科都有廣泛的應(yīng)用,甚至在經(jīng)濟(jì)管理、社會(huì)科學(xué)等領(lǐng)域,矩陣的理論和方法都起著十分重要的作用.同樣地,矩陣方法在博弈論的研究中也起著至關(guān)重要的作用.實(shí)際上,馮·諾依曼就是從矩陣博弈開始研究的[4].近年來,由程代展教授及其團(tuán)隊(duì)創(chuàng)立的矩陣半張量積[5-6],打破了傳統(tǒng)矩陣乘積對(duì)維數(shù)的限制,豐富了現(xiàn)代控制領(lǐng)域的研究方法.目前,矩陣半張量積理論已經(jīng)被成功應(yīng)用于邏輯系統(tǒng)[7]、有限博弈[8]、圖論[9]、有限自動(dòng)機(jī)[10]、生物系統(tǒng)[11]、模糊控制[12-13]等眾多領(lǐng)域.基于矩陣半張量積,有限博弈的相關(guān)研究取得了一系列豐碩的研究成果.諸如,文獻(xiàn)[14]利用半張量積,構(gòu)建了勢(shì)方程,給出了勢(shì)函數(shù)的計(jì)算方法;文獻(xiàn)[15]基于有限博弈的向量空間結(jié)構(gòu)給出了正交分解定理;文獻(xiàn)[16]建立了網(wǎng)絡(luò)演化博弈的代數(shù)模型,進(jìn)而分析了網(wǎng)絡(luò)的動(dòng)態(tài)行為,包括穩(wěn)定性、能控性和一致性等問題;文獻(xiàn)[17]研究了博弈控制理論在多智能體中的應(yīng)用;文獻(xiàn)[18]研究了基于狀態(tài)博弈的學(xué)習(xí)算法設(shè)計(jì)及其應(yīng)用,等.

演化博弈最早是由生物學(xué)家引入用來研究生物系統(tǒng)的進(jìn)化過程的[19-21],文獻(xiàn)[22]曾指出:“博弈論更容易應(yīng)用于生物學(xué),而不是它最初設(shè)計(jì)的經(jīng)濟(jì)行為領(lǐng)域”.這充分說明了演化博弈在生物學(xué)方面有著很強(qiáng)的應(yīng)用背景.在過去的幾十年里,演化博弈的相關(guān)研究吸引了不同學(xué)科領(lǐng)域?qū)W者們的廣泛關(guān)注,例如經(jīng)濟(jì)系統(tǒng)[23]、社會(huì)系統(tǒng)[24]、工程系統(tǒng)[25]等等.對(duì)于演化博弈,其動(dòng)態(tài)過程及穩(wěn)定性是一個(gè)自然而不可回避的問題.在矩陣半張量積的研究框架下,文獻(xiàn)[26]利用Lyapunov函數(shù)對(duì)演化博弈的穩(wěn)定和鎮(zhèn)定問題進(jìn)行了分析,文獻(xiàn)[27]討論了時(shí)滯影響下演化博弈的穩(wěn)定性,文獻(xiàn)[28-29]考慮了隨機(jī)演化博弈的穩(wěn)定和鎮(zhèn)定問題,文獻(xiàn)[30-31]分別研究了網(wǎng)絡(luò)演化博弈和超網(wǎng)絡(luò)演化博弈的演化穩(wěn)定策略.

干擾普遍存在于控制系統(tǒng)以及現(xiàn)實(shí)生活中,抗干擾問題也得到越來越廣泛的關(guān)注.值得注意的是,在博弈的相關(guān)研究中,大多假設(shè)博弈過程在理想的環(huán)境中進(jìn)行.最近,文獻(xiàn)[32-33]考慮了干擾影響下的連續(xù)時(shí)間線性二次博弈,通過ε-Nash均衡來反映干擾對(duì)博弈的影響.文獻(xiàn)[34]研究了干擾影響下離散非線性二次博弈的事件驅(qū)動(dòng)策略設(shè)計(jì).文獻(xiàn)[35]考慮了隨機(jī)干擾對(duì)建筑工程供應(yīng)鏈中博弈動(dòng)態(tài)過程的影響.并且,文獻(xiàn)[32-33]驗(yàn)證了干擾可能會(huì)影響博弈動(dòng)態(tài),最終影響博弈的結(jié)果.因此,簡(jiǎn)單地忽略干擾存在的影響是不合理的.

基于以上討論,本文利用矩陣半張量積工具,研究干擾影響下演化博弈的穩(wěn)定與鎮(zhèn)定問題.本文的主要貢獻(xiàn)如下:1)提出了干擾博弈、控制-干擾博弈、魯棒-Nash均衡等概念,進(jìn)而給出了干擾演化博弈與控制-干擾演化博弈的代數(shù)狀態(tài)空間表示.2)通過構(gòu)造輔助系統(tǒng),將演化博弈的魯棒穩(wěn)定與鎮(zhèn)定問題轉(zhuǎn)化為新系統(tǒng)的集合穩(wěn)定和集合鎮(zhèn)定問題.3)給出了干擾演化博弈及控制-干擾演化博弈魯棒穩(wěn)定及鎮(zhèn)定的充分必要條件,并且設(shè)計(jì)了狀態(tài)反饋控制器以保證魯棒鎮(zhèn)定的實(shí)現(xiàn).

本文其余部分的結(jié)構(gòu)安排如下:第2節(jié)介紹符號(hào)表示、矩陣半張量積的概念和性質(zhì).第3節(jié)是問題描述,具體給出了演化博弈魯棒穩(wěn)定及鎮(zhèn)定的概念.第4節(jié)是本文的主要內(nèi)容,分別討論了干擾演化博弈、控制-干擾演化博弈的代數(shù)狀態(tài)空間表示,給出了魯棒穩(wěn)定及鎮(zhèn)定的充分必要條件,并進(jìn)一步設(shè)計(jì)了狀態(tài)反饋控制器.第5節(jié)通過兩個(gè)例子驗(yàn)證了本文所得結(jié)果的有效性.第6節(jié)對(duì)本文進(jìn)行了總結(jié).

2 預(yù)備知識(shí)

本部分簡(jiǎn)要介紹一些基本知識(shí),包括符號(hào)表示、矩陣半張量積的定義和基本性質(zhì).

2.1 符號(hào)表示

2.2 矩陣半張量積

本小節(jié)簡(jiǎn)要介紹矩陣半張量積的基本定義和相關(guān)性質(zhì).

定義1[5]假設(shè)A ∈Rm×n,B ∈Rp×q,則矩陣A和B的半張量積定義為

其中t=lcm(n,p)是n和p的最小公倍數(shù).

注意到,當(dāng)n=p時(shí),矩陣半張量積就退化為傳統(tǒng)矩陣乘積.在不致混淆的情形下,符號(hào)通常被省略.

引理1[5]下面是關(guān)于矩陣半張量積的一些基本性質(zhì):

3 問題陳述

本節(jié)將具體給出一類干擾影響下演化博弈的穩(wěn)定與鎮(zhèn)定問題的相關(guān)介紹和定義.

3)Ξ={1,2,··· ,m}表示外部干擾的集合.

4)C=(c1,c2,··· ,cn)∈Rn,其中ci:S×Ξ →R是第i個(gè)玩家的支付函數(shù),i ∈N.

這里“有限”是指:1)玩家個(gè)數(shù)n<∞;2)策略個(gè)數(shù)|Si|<∞;3)干擾個(gè)數(shù)|Ξ|<∞.

下面給出魯棒Nash均衡的定義.

定義3 給定一個(gè)干擾博弈G=(N,S,Ξ,C).

設(shè)一個(gè)干擾博弈G=(N,S,Ξ,C)被重復(fù)進(jìn)行,那么在每個(gè)玩家都是理性的前提,每個(gè)玩家都會(huì)根據(jù)已有的信息更新自己的策略,設(shè)法最大化自己的利益.假設(shè)n個(gè)玩家的局勢(shì)演化方程可以表示為

其中:wi(t)∈Dai表示系統(tǒng)(2)的內(nèi)部狀態(tài),i=1,2,··· ,p;ξj(t)∈Dlj表示系統(tǒng)(2)的輸出,j=1,2,··· ,m.

注1需要指出的是,在工程實(shí)踐中,各種擾動(dòng),例如諧波,恒頻波,控制器的增益變化,執(zhí)行器故障和控制器到執(zhí)行器通道中的通信波動(dòng)等都可由外部系統(tǒng)(2)生成[36-37].因此,本文考慮由系統(tǒng)(2)所生成的干擾對(duì)博弈的影響.

接下來,給出上述干擾演化博弈GD魯棒穩(wěn)定的定義.可以表示為

注2在定義4(定義6)中,要求穩(wěn)定(鎮(zhèn)定)的點(diǎn)是魯棒-Nash均衡,不失一般性,也可以給出魯棒穩(wěn)定(鎮(zhèn)定)到任一局勢(shì)的定義.但眾所周知,Nash均衡被認(rèn)為是非合作博弈的“基本解”,在妥協(xié)意義下是每個(gè)玩家的最優(yōu)選擇.因此,本文主要考慮演化博弈魯棒穩(wěn)定(鎮(zhèn)定)到魯棒Nash均衡的情況,對(duì)于一般的收斂性,相關(guān)結(jié)果可以自然推廣.

4 主要內(nèi)容

在本節(jié)中,具體討論在什么條件下干擾演化博弈(控制-干擾演化博弈)可以實(shí)現(xiàn)魯棒穩(wěn)定(鎮(zhèn)定),并設(shè)計(jì)狀態(tài)反饋控制器.

4.1 魯棒穩(wěn)定

首先,利用矩陣半張量積,式(1)和式(2)的代數(shù)形式可以表示為

并且令z(t)=w(t)x(t)∈Δka.進(jìn)而,從式(8)和式(9),

給定一個(gè)集合W ?Δka.稱系統(tǒng)(11)是關(guān)于W集合穩(wěn)定的,如果存在一個(gè)正整數(shù)η,使得z(t;z0)∈W,?z0∈Δka,?t≥η.接下來,將干擾演化博弈的魯棒穩(wěn)定問題轉(zhuǎn)化為系統(tǒng)(11)的集合穩(wěn)定問題.

引理3 干擾演化博弈GD魯棒穩(wěn)定到魯棒Nash均衡s?,當(dāng)且僅當(dāng)系統(tǒng)(11)是關(guān)于Λ集合穩(wěn)定的.

證(必要性) 假設(shè)干擾演化博弈GD可以魯棒穩(wěn)定到魯棒Nash均衡s?,則存在一個(gè)正整數(shù)ρ,使得式(3)成立.根據(jù)式(7),如果w(0)給定,那么{ξ(t)}∞t=0就是已知的.因此,{ξ(t)}∞t=0的任意性就等價(jià)于w(0)的任意性.另外,當(dāng)t≥τ時(shí),w(t)∈Ω,這里τ是系統(tǒng)(9)的過渡周期.因此,令η=max{τ,ρ},則式(3)意味著

即系統(tǒng)(11)是關(guān)于Λ集合穩(wěn)定的.

(充分性) 假設(shè)系統(tǒng)(11)是關(guān)于Λ集合穩(wěn)定的,則式(12)成立.注意到,z(t)=w(t)x(t)是從Δa×Δk到Δka的一一對(duì)應(yīng).從而,令ρ=η,則式(3)成立,即干擾演化博弈GD可以魯棒穩(wěn)定到魯棒Nash均衡s?.

證畢.

基于引理3,得到以下定理:

定理1 干擾演化博弈GD魯棒穩(wěn)定到魯棒Nash均衡s?,當(dāng)且僅當(dāng)存在一個(gè)正整數(shù)η≤ka,使得

證(必要性) 假設(shè)干擾演化博弈GD可以魯棒穩(wěn)定到魯棒Nash均衡s?,則由引理3,存在正整數(shù)η,使得z(t;z0)∈Λ對(duì)所有的z0∈Δka和t≥η成立.從而

根據(jù)引理3,干擾演化博弈GD可以魯棒穩(wěn)定到魯棒Nash均衡s?.證畢.

4.2 魯棒鎮(zhèn)定

對(duì)于有控制玩家的情形,利用矩陣半張量積將式(4)轉(zhuǎn)化為如下代數(shù)形式:

其中“>”指的是兩個(gè)向量對(duì)應(yīng)分量的元素都滿足大于關(guān)系.

證

1)?2):類似于引理3的證明,易知1)與2)是等價(jià)的.

注3根據(jù)定理2可以知道,若集合Λ的最大控制不變子集Im(Λ)=?,那么控制-干擾演化博弈GUD不能被魯棒鎮(zhèn)定到魯棒Nash均衡s?.

5 仿真算例

例1 考慮一個(gè)干擾博弈G=(N,S,Ξ,C),其中:|N| = 2,|Ξ| = 2,|Si| = 3,i ∈N,且ξ= 1,2時(shí)的支付矩陣如表1-2所示.

表1 ξ =1時(shí)的支付矩陣Table 1 Payoffs when ξ =1

假設(shè)重復(fù)進(jìn)行此干擾博弈的動(dòng)態(tài)演化方程為

從而,根據(jù)定理1可知該干擾演化博弈能夠魯棒穩(wěn)定到魯棒Nash均衡s?.

表2 ξ =2時(shí)的支付矩陣Table 2 Payoffs when ξ =2

例2 考慮如下控制-干擾博弈G=(N,S,Ξ,C),其中,N=X ∪U,|X|=2,|U|=1,|Ξ|=2,|Si|=3,i ∈X,|Sj|=2,i ∈U,且ξ=1,2時(shí)的支付矩陣如表3-4所示.

根據(jù)支付信息(表3-4)和定義5,易知s?=(1,1)～δ19是關(guān)于玩家集X的魯棒Nash均衡.

表3 ξ =1時(shí)的支付矩陣Table 3 Payoffs when ξ =1

表4 ξ =2時(shí)的支付矩陣Table 4 Payoffs when ξ =2

設(shè)外部干擾系統(tǒng)仍為例1中所述,控制-干擾演化博弈的局勢(shì)演化方程為

其中:x(t)∈Δ9,ξ(t)∈Δ2,u(t)∈Δ2,且

進(jìn)一步,令z(t)=w(t)x(t)∈Δ36,有如下輔助系統(tǒng):

換言之,控制玩家可以根據(jù)上述所得的狀態(tài)反饋控制器來更新的自己的策略,以實(shí)現(xiàn)該控制-干擾演化博弈魯棒鎮(zhèn)定到s?.

6 結(jié)論

本文研究了演化博弈的魯棒穩(wěn)定與鎮(zhèn)定問題.在干擾演化博弈與控制-干擾演化博弈魯棒穩(wěn)定與鎮(zhèn)定等概念的基礎(chǔ)上,利用矩陣半張量積得到了代數(shù)狀態(tài)空間表示.進(jìn)一步,通過構(gòu)造一個(gè)輔助系統(tǒng),得到了魯棒穩(wěn)定與鎮(zhèn)定的充分必要條件,并且設(shè)計(jì)了狀態(tài)反饋控制器.最后,通過例子驗(yàn)證了所得結(jié)論的有效性.