基于STP相關馬爾可夫型演化博弈穩定性研究

李露露, 朱 睿

(合肥工業大學 數學學院,安徽 合肥 230601)

0 引 言

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

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

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

本文的主要貢獻包括:

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

(2) 給出了2個k-值邏輯動態系統的李雅普諾夫函數的構造算法。

1 預備知識

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

1.1 常用記號

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

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

1.2 矩陣半張量積的概念和性質

定義1[1]令A∈Mm×n,B∈Ma×b,記n和a的最小公倍數為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)]上元素的值為:

當m=n時,W[m,n]可簡寫為W[n]。

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

(2)

(3)

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

(4)

并稱Mf為f的結構矩陣。

1.3 博弈的概念和理論

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

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

(5)

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

2 主要結果

2.1 模型的建立

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

(6)

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

下面利用李雅普諾夫函數為判斷其穩定性提供理論依據,并給出李雅普諾夫函數的構造算法。

2.2 模型的解決

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

其中,Vφ∈Rkn稱為φ(x)的結構向量。

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

(7)

證明對于具有τ長度信息的相關演化博弈,先將其進行變形。

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

?

?

進而,當進行演化時,可得:

然后有:

(8)

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

z(t+1)=Lz(t)

(9)

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

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

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

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

φ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))。

于是有:

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

φ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。

證畢。

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

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

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

(3) 構造李雅普諾夫函數,其代數形式為:

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

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

李雅普諾夫函數構造算法的復雜度會隨著矩陣維數的增加而增大。當矩陣的維數非常大時,需要尋找更有效的方法來求解。

2.3 模型的應用

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

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

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

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

表2 不同局勢下的最佳響應函數值

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

接下來,將構造李雅普諾夫函數,判斷其矩陣的不動點是2個相關演化博弈的收斂點。

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 結 論

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