基于STP相關(guān)馬爾可夫型演化博弈穩(wěn)定性研究

李露露, 朱 睿

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230601)

0 引 言

近年來,隨著矩陣在很多領(lǐng)域研究中應(yīng)用越來越廣泛, 普通矩陣的乘法已經(jīng)不能滿足人們的需求。為此,文獻(xiàn)[1-2]經(jīng)過多年的研究,提出了一種新的矩陣相乘方法,即矩陣半張量積(semi-tensor product, STP),打破了傳統(tǒng)矩陣乘法的條件限制。矩陣半張量積的產(chǎn)生使得布爾網(wǎng)絡(luò)的研究有了突破性的進(jìn)展,很好地解決了簡單布爾網(wǎng)絡(luò)的鎮(zhèn)定性、穩(wěn)定性以及控制等問題[3-4]。在簡單布爾網(wǎng)絡(luò)研究的基礎(chǔ)上,利用矩陣半張量積對τ長度信息條件布爾網(wǎng)絡(luò)的研究也取得了一系列成果[5-6]。由于布爾網(wǎng)絡(luò)是邏輯網(wǎng)絡(luò)中的一種形式,許多學(xué)者將矩陣半張量積推廣至邏輯網(wǎng)絡(luò)中進(jìn)行研究并取得了很大的進(jìn)展[7-8]。

在博弈論的有限演化博弈中,每個人可以在其策略集進(jìn)行選擇,許多專家在演化博弈論中應(yīng)用矩陣半張量積,將其演化過程進(jìn)行代數(shù)表達(dá),得到了很多成果[8-9]。文獻(xiàn)[8]首次利用矩陣半張量積將演化博弈進(jìn)行代數(shù)表達(dá),分別給出了其在2種不同情況下優(yōu)化控制的基本結(jié)果與算法,隨后許多學(xué)者研究了網(wǎng)絡(luò)演化博弈的最優(yōu)控制以及反饋控制等[10]。

李雅普諾夫函數(shù)具有的平穩(wěn)性在研究動力系統(tǒng)的分析和控制中應(yīng)用十分廣泛[11]。文獻(xiàn)[12]對一類稱為馬爾可夫型的有限演化博弈的穩(wěn)定性和鎮(zhèn)定問題進(jìn)行研究,構(gòu)造了有限集上的李雅普諾夫函數(shù),但它只針對單個馬爾可夫型演化博弈,并且下一時刻的決策只與前一時刻的決策有關(guān)?，F(xiàn)實生活中,許多實例都是相關(guān)馬爾可夫型演化博弈,如農(nóng)民播撒種子數(shù)量和產(chǎn)量的穩(wěn)定性就是息息相關(guān)的,而且農(nóng)民在做下一時刻的決策時,為了使決策效益更高,往往會參考前幾年的信息,即τ長度信息。根據(jù)以上討論,本文將對帶有τ長度信息的相關(guān)馬爾可夫型演化博弈進(jìn)行研究,給出此類型博弈決策變化的規(guī)律及其穩(wěn)定性。

本文的主要貢獻(xiàn)包括:

(1) 給出帶有τ長度信息的相關(guān)馬爾可夫型演化博弈的李雅普諾夫函數(shù)存在的充分必要條件,進(jìn)而判斷其全局穩(wěn)定性。

(2) 給出了2個k-值邏輯動態(tài)系統(tǒng)的李雅普諾夫函數(shù)的構(gòu)造算法。

1 預(yù)備知識

本節(jié)主要介紹論文中常用的記號、矩陣半張量積的定義和性質(zhì)、演化博弈以及李雅普諾夫函數(shù)的概念,具體細(xì)節(jié)可參考文獻(xiàn)[1-2]。

1.1 常用記號

設(shè)矩陣L∈Mm×n,若Col(L)?Δm,則稱L為邏輯矩陣。

記所有m×n邏輯矩陣的集合為Lm×n。

1.2 矩陣半張量積的概念和性質(zhì)

定義1[1]令A(yù)∈Mm×n,B∈Ma×b,記n和a的最小公倍數(shù)為k=lcm{n,a},則矩陣半張量積定義為:

(1)

定義2[1]換位矩陣W[m,n]∈Mmn×mn,其列是按照索引Id(i,j;m,n)排列的,行是按照索引Id(j,i;n,m)排列的,位于[(I,J),(i,j)]上元素的值為:

當(dāng)m=n時,W[m,n]可簡寫為W[n]。

根據(jù)定義2,W[m,n]還可以寫成如下形式:

(2)

(3)

定理1[1]設(shè)xi∈Δk,i=1,2,…,n,f(x1,x2,x3,…,xn)∈Δk*為一個多值邏輯(向量)函數(shù),則存在唯一的邏輯矩陣Mf∈Lk*×kn,使得在向量形式下,有

(4)

并稱Mf為f的結(jié)構(gòu)矩陣。

1.3 博弈的概念和理論

定義4[12]馬爾可夫型演化博弈的下一時刻的策略選擇僅依賴于當(dāng)前的策略,其演化方程為:

φ(x(t+1))-φ(x(t))≥0,t≥0

(5)

則稱φ(x)為馬爾可夫型演化博弈的李雅普諾夫函數(shù),且當(dāng)φ(x(t+1))=φ(x(t))時,有x(t)=x*。

2 主要結(jié)果

2.1 模型的建立

在現(xiàn)實生活中,許多事件并非獨立存在,并且在演化時,所參考的信息具有一定長度,因此需要尋找和建立新的模型,即帶有τ長度信息的相關(guān)馬爾科夫型演化博弈進(jìn)行描述。相關(guān)馬爾科夫型演化博弈模型代數(shù)表示為:

(6)

其中:x(t)、y(t)為參與者t時刻策略選擇;M1、M2為狀態(tài)轉(zhuǎn)移矩陣;W=diag{w1,w2,…,wkn}。

下面利用李雅普諾夫函數(shù)為判斷其穩(wěn)定性提供理論依據(jù),并給出李雅普諾夫函數(shù)的構(gòu)造算法。

2.2 模型的解決

根據(jù)定理1,李雅普諾夫函數(shù)φ(x)可表示為相應(yīng)的代數(shù)形式:

其中,Vφ∈Rkn稱為φ(x)的結(jié)構(gòu)向量。

定理2當(dāng)2個帶有τ長度信息的相關(guān)演化博弈模型(6)分別具有李雅普諾夫函數(shù)φ1(x)和φ2(x),當(dāng)且僅當(dāng)存在整數(shù)1≤r≤kn和1≤g≤k2τn,使得下列不等式組有解。

(7)

證明對于具有τ長度信息的相關(guān)演化博弈,先將其進(jìn)行變形。

將x(t),…,x(t-τ+1),y(t),…,y(t-τ+1)進(jìn)行替換:

?

?

進(jìn)而,當(dāng)進(jìn)行演化時,可得:

然后有:

(8)

于是,(8)式可變形為:

z(t+1)=Lz(t)

(9)

此時L=K1*K2*…*K2τ。

下面,用φ1(y)和φ2(z)來說明定理1的有效性。

設(shè)φ1(y)、φ2(z)的結(jié)構(gòu)向量分別為Vφ1=[a1,a2,…,akn]、Vφ2=[b1,b2,…,bk2τn];y(t)、z(t)的轉(zhuǎn)移矩陣分別為M2=δkn[j1,…,jkn]、L=δk2τn[i1,…,ik2τn]。

(1) 充分性。由φ1(y)和φ2(z)的代數(shù)形式可得:

φ1(y(t+1))+φ2(z(t+1))=

Vφ1M2Wx(t)+Vφ2Lz(t)=

[ai1wi1+bj1,…,aiknwikn+bj1,ai1wi1+bj2…,aiknwikn+bj2,…,ai1wi1+bjk2τn,…,aiknwikn+bjk2τn]z(t)x(t)。

于是有:

[φ1(y(t+1))+φ2(z(t+1))]-

[φ1(y(t))+φ2(z(t))]=

bj1,ai1wi1+bj2,…,aiknwikn+

bj2,…,ajknwjkn+bj2,…,ai1wi1+

(10)

[φ1(y(t+1))+φ2(z(t+1))]-

[φ1(y(t))+φ2(z(t))]=(aiqwiq+bjq)-(aqwq+bq)>0,

即

φ1(y(t+1))+φ2(z(t+1))>φ1(y(t))+φ2(z(t))。

φ1(y(t+1))+φ2(z(t+1))=φ1(y(t))+φ2(z(t))。

于是有:

因此,函數(shù)φ1(y)和φ2(z)即為滿足定義5的2個李雅普諾夫函數(shù)。

φ1(y(t+1))+φ2(z(t+1))=

φ1(y(t))+φ2(z(t))。

將x(t)、z(t)代入(10)式,可得:

airwir+bjg=arwr+bg。

aiqwiq+bjq>aqwq+bq,

q=1,…,kn,q≠r;p=1,…,k2τn,p≠g。

證畢。

根據(jù)定理2,可以給出帶有τ長度信息的相關(guān)演化博弈的李雅普諾夫函數(shù)φ1和φ2的構(gòu)造算法。具體的計算步驟為:

(1) 計算轉(zhuǎn)移矩陣M和變形后的L,并找到其唯一的不動點。

(2) 解不等式組(8),并得到一組解[bj1,…,bjk2τn],[a1,a2,…,akn]。

(3) 構(gòu)造李雅普諾夫函數(shù),其代數(shù)形式為:

φ1(y)=[a1,a2,…,akn]zx，φ2(z)=[bj1,…,bjk2τn]zx。

不等式組(7)有無窮多個解,因此相關(guān)馬爾可夫型演化博弈的李雅普諾夫函數(shù)是不唯一的。

李雅普諾夫函數(shù)構(gòu)造算法的復(fù)雜度會隨著矩陣維數(shù)的增加而增大。當(dāng)矩陣的維數(shù)非常大時,需要尋找更有效的方法來求解。

2.3 模型的應(yīng)用

中國是農(nóng)業(yè)大國,農(nóng)民人數(shù)眾多,對于農(nóng)民種植來說,如何選擇種子數(shù)目使收益最大至關(guān)重要。農(nóng)民在決定下一年所播撒的種子數(shù)目時,會受到今年和上一年自己的收益和其他農(nóng)民的收益的影響,他們會在所有策略中選擇獲得利益最大的策略進(jìn)行播種。收益是由播撒的種子數(shù)目和產(chǎn)量決定,而農(nóng)民能獲得的產(chǎn)量與今年播撒的種子數(shù)目有關(guān),而與前一年的產(chǎn)量無關(guān)。以參與者是2個農(nóng)民為例,研究參與者的策略隨時間演化的穩(wěn)定性;下面將利用李雅普諾夫函數(shù)對這種穩(wěn)定性進(jìn)行判定。

考慮演化博弈G1和G2,G1={N,S,C},其中,N={1,2}表示參與者,即2個農(nóng)民。S1={1,2}表示第1個農(nóng)民的策略,即第1個農(nóng)民有兩個策略可以選擇:1表示播撒種子2 000粒,2表示播撒種子2 500粒;S2={1,2}表示第2個農(nóng)民的策略即第2個農(nóng)民有兩個策略可以選擇:1表示播撒種子2 350粒,2表示播撒種子2 600 粒;不同策略組合下,2個農(nóng)民的收益見表1所列。

表1 不同策略組合下的收益

策略更新規(guī)則使用確定型的短視最優(yōu)響應(yīng)[9],因此,可以得到不同局勢下的最佳響應(yīng)函數(shù)值,見表2所列。

表2 不同局勢下的最佳響應(yīng)函數(shù)值

G2為產(chǎn)量的博弈,收獲的產(chǎn)量與其播種的種子數(shù)目具有一定的比率關(guān)系,即產(chǎn)量y(t+1)=M2Wx(t),其中W=diag{0.75, 0.85, 0.95, 0.83}。

接下來,將構(gòu)造李雅普諾夫函數(shù),判斷其矩陣的不動點是2個相關(guān)演化博弈的收斂點。

x(t)x(t-1)y(t)y(t-1)=M1x(t)x(t-1)y(t)y(t-1),

x(t)x(t-1)y(t)y(t-1)=M2x(t)x(t-1)y(t)y(t-1)。

于是可得演化方程為:

x(t+1)=Mx(t)x(t-1)y(t)y(t-1)=M1*M2x(t)x(t-1)y(t)y(t-1)=

x(t)x(t-1)y(t)y(t-1)。

(11)

3 結(jié) 論

本文對一類帶有τ長度信息的相關(guān)馬爾可夫型演化博弈的穩(wěn)定性問題進(jìn)行研究,給出李雅普諾夫函數(shù)存在的充分必要條件,并利用構(gòu)造算法定義2個k-值邏輯動態(tài)系統(tǒng)的李雅普諾夫函數(shù),判斷演化博弈的全局穩(wěn)定性;最后結(jié)合具體事例,驗證了理論結(jié)果的正確性。