基于半張量積方法的時滯演化擁塞博弈鎮(zhèn)定

王桂林,徐 勇

(河北工業(yè)大學 理學院,天津 300401)

0 概述

在現(xiàn)實生活中,很多問題可轉(zhuǎn)化為擁塞博弈。擁塞博弈理論由ROSENTHAL提出,是指玩家爭奪有限資源的一類非合作博弈,其中每個玩家的花費只取決于玩家所選的資源和選擇相同資源的玩家的數(shù)量。ROSENTHAL指出,任意一個擁塞博弈都是一個勢博弈[1],即每一個擁塞博弈都至少有一個純策略納什均衡,玩家無法通過單方面改變自己的策略來降低花費。由此,擁塞博弈理論在許多學者的推動下得以迅速發(fā)展[2-4],并且在交通網(wǎng)絡[5-6]、認知無線電網(wǎng)絡[7-8]以及資源分配問題[9]等諸多領域被廣泛應用。擁塞博弈可被重復進行多次,即為演化擁塞博弈。

近年來,矩陣的半張量積理論得到快速發(fā)展[10],其在布爾網(wǎng)絡、多值邏輯網(wǎng)絡以及博弈論領域已取得諸多成果,形成了多值邏輯網(wǎng)絡的能控性、能觀性[12]、穩(wěn)定性[13]、鎮(zhèn)定性[14]、布爾網(wǎng)絡的同步[15]以及魯棒輸出跟蹤問題[16]等理論。利用半張量積方法,研究人員進一步發(fā)展了網(wǎng)絡演化博弈[17-18]、演化博弈[19-20]、擁塞博弈[21]等理論。文獻[21]利用矩陣的半張量積將經(jīng)典擁塞博弈表示成代數(shù)形式,對于動態(tài)設備系統(tǒng),通過優(yōu)化每個玩家的支付函數(shù)實現(xiàn)全局最優(yōu),并考慮玩家采用串聯(lián)型短視最優(yōu)響應更新規(guī)則的演化動態(tài)會全局收斂到納什均衡。上述半張量積方法的應用均認為博弈的策略更新只依賴于其最后一步,然而在生物系統(tǒng)和經(jīng)濟活動中,每個玩家都能記住過去不止一個時刻的決策行為,在這種情況下,所有玩家的下一步策略選擇都是基于最后有限步的行為。因此,在演化擁塞博弈中考慮所有玩家都能記住最后有限步策略是合理的。

目前,已有許多學者對帶有時滯的演化博弈進行了研究。文獻[22]研究了帶有時滯的演化博弈的動態(tài)變化和穩(wěn)定性,主要考慮兩種時滯(時不變和時變)的局勢軌跡動態(tài),并利用矩陣的半張量積理論將其動態(tài)系統(tǒng)表示成代數(shù)形式,通過分析其狀態(tài)轉(zhuǎn)移矩陣來研究系統(tǒng)穩(wěn)定到納什均衡的條件。文獻[23]對帶有有限步記憶的網(wǎng)絡演化博弈的收斂性問題進行研究,其在一個正確的假設下,通過設計自由控制序列使得帶有有限步記憶的網(wǎng)絡演化博弈全局收斂到納什均衡。此外,時滯現(xiàn)象同樣存在于演化擁塞博弈問題中,目前還沒有相關文獻對該問題進行研究。

本文在文獻[21]的基礎上,利用半張量積的方法,考慮策略更新規(guī)則為并聯(lián)型短視最優(yōu)響應的擁塞博弈的時滯演化過程,并且其時滯是有限步記憶。因為交通系統(tǒng)中的出行者互不相識,所以在遇到擁塞時,所有出行者都有可能更換路徑。如果下一時刻只有一個玩家更新其策略,那么任意給定的初始局勢一定會全局收斂到納什均衡。然而,如果所有玩家在下一時刻同時更新自己的策略,其并不能保證所有初始狀態(tài)時滯演化后的擁塞博弈全局收斂到納什均衡,因此,在擁塞博弈的時滯演化過程中,通過對玩家施加控制來影響博弈過程是非常必要的。本文通過設計開環(huán)控制和狀態(tài)反饋控制,使時滯演化擁塞博弈全局鎮(zhèn)定到納什均衡,從而實現(xiàn)資源花費最小。

1 預備知識

本節(jié)主要介紹矩陣的半張量積理論和演化博弈論的相關符號、概念及性質(zhì)。

A

其中,?表示Kronecker積。由于矩陣的半張量積幾乎保持了傳統(tǒng)矩陣乘積的所有主要性質(zhì),因此在不混淆的情況下,可以省略“”。

命題1設X∈Δk,則有[10]:

命題2設X∈Rm是一列向量,A為任意矩陣[10],則有:

XA=(Im?A)X

命題3設X∈Rm,Y∈Rn是2個列向量[10],則有:

W[m,n]XY=YX

其中,W[m,n]=δmn[1,m+1,…,(n-1)m+1,2,m+2,…,(n-1)m+2,…,m,2m,…,nm]為換位矩陣。

其中,Mf是f的結構矩陣。

2 本文方法

本節(jié)給出經(jīng)典的擁塞博弈,對時滯演化擁塞博弈的動態(tài)系統(tǒng)進行建模,并將其表示成代數(shù)形式,設計開環(huán)控制和狀態(tài)反饋控制,使時滯演化擁塞博弈全局鎮(zhèn)定到納什均衡。

2.1 擁塞博弈

一個擁塞博弈G=(N,P,(Si)i∈N,(Ξj)j∈P),其中:

1)N={1,2,…,n}表示有限的玩家集。

2)P={1,2,…,p}表示有限的所有玩家共享的資源集。

3)Si?P表示玩家i的策略集,其中,si∈Si是i的策略。

令所有資源的花費函數(shù)為:

Ξ=[Ξ1,Ξ2,…,Ξp]

(1)

2.2 時滯演化擁塞博弈的動態(tài)及代數(shù)形式

本文考慮一類演化擁塞博弈,其中所有玩家的策略都帶有時滯,則時滯演化擁塞博弈的動態(tài)方程如下:

xi(t+1)=fi(x1(t-τ+1),x2(t-τ+1),…,

xn(t-τ+1),…,x1(t),x2(t),…,xn(t))

(2)

本文采用的更新規(guī)則是時間并聯(lián)型短視最優(yōu)響應,最優(yōu)響應策略集記作:

如果xi(t)∈Oi(x(t)),則xi(t+1)=xi(t),否則選擇最小下標j,使得xj(t)∈Oi(x(t)),并令xi(t+1)=xj(t)。

整合上述方程,得到如下公式:

x(t+1)=Mx(t-τ+1)x(t-τ+2)…x(t)

(3)

為方便研究,本文將帶時滯的動態(tài)系統(tǒng),即式(3)轉(zhuǎn)換成不帶時滯的動態(tài)系統(tǒng)。令y(t)=x(t-τ+1)x(t-τ+2)…x(t),則有如下公式:

經(jīng)整理得到如下公式:

(4)

注1本文將x(t)稱為策略局勢,將X(t)=(x(t-τ+1),x(t-τ+2),…,x(t))稱為長度為τ的軌跡局勢。

證明(必要性) 假設:

y(t)=x(t-τ+1)x(t-τ+2)…x(t)=

證明(充分性) 假設:

y(t)=x(t-τ+1)x(t-τ+2)…x(t-1)x(t)=

該定理說明,對于不帶時滯的動態(tài)系統(tǒng)(式(4)),納什均衡與不動點是重合的,則式(4)至少有一個不動點。

注2該定理與文獻[24]的不同之處主要有兩點:

1)系統(tǒng)不同,本文的演化動態(tài)系統(tǒng)是帶有時滯的。

2)證明方法不同,本文采用矩陣的半張量積方法。

2.3 控制器設計

y(t+1)=Lu(t-τ+1)y(t-τ+1)u(t-τ+2)

y(t-τ+2)…u(t)y(t)

(5)

其中,L=Mm+1*Mm+2*…*Mn,u(t)∈Δpm。

根據(jù)命題2和命題3,式(5)可轉(zhuǎn)化為如下形式:

y(t+1)=LΦu(t-τ+1)u(t-τ+2)…u(t)

y(t-τ+1)y(t-τ+2)…y(t)

(6)

令z(t)=y(t-τ+1)y(t-τ+2)…y(t),v(t)=u(t-τ+1)u(t-τ+2)…u(t),則式(6)可轉(zhuǎn)化為如下形式:

(7)

考慮時滯演化擁塞博弈的開環(huán)控制,給出以下定理:

(8)

在設計狀態(tài)反饋控制v(t)=Kz(t)時,使得博弈演化過程中的所有狀態(tài)全局鎮(zhèn)定到納什均衡。將式(7)轉(zhuǎn)化為如下形式:

(9)

定理3式(9)能夠通過狀態(tài)反饋控制全局鎮(zhèn)定到納什均衡,當且僅當存在一個邏輯矩陣K和一個整數(shù)γ≥1,使得:

(10)

假設:

(11)

在控制v(t)=Kz(t)下,對任意給定的初始狀態(tài)z(t),有z(t+1)∈Ω1,因此,式(9)能夠通過狀態(tài)反饋控制全局鎮(zhèn)定到納什均衡。

(12)

注3定理3給出了狀態(tài)反饋控制矩陣的設計過程。

3 算例分析

假設τ=2,記x(t)=x1(t)x2(t)x3(t),y(t)=x(t-1)x(t),則采用時間并聯(lián)型的短視最優(yōu)響應得到局勢演化方程的代數(shù)形式如下:

為了使所有的狀態(tài)全部演化到不動點集合Ω,需要設計控制器。假設玩家1是控制玩家,則局勢控制演化方程的代數(shù)形式如下:

此時有:

圖1 例1設計所用的控制序列

[16,6,11,16,6,6,16,16,11,16,11,16,16,6,11,16]z(t)

可以看出,在狀態(tài)反饋控制下,時滯擁塞博弈的所有初始狀態(tài)都演化到不動點Ω1,即時滯演化擁塞博弈全局鎮(zhèn)定到納什均衡。

4 結束語

本文對時滯演化擁塞博弈的控制問題進行研究,提出一種基于半張量積的時滯演化擁塞博弈鎮(zhèn)定方法。將時滯演化擁塞博弈建模成多值邏輯動態(tài)系統(tǒng),利用矩陣的半張量積給出等價的代數(shù)形式。在此基礎上,分析時滯演化擁塞博弈的動態(tài)行為,通過在該博弈中添加可以自由選擇策略的控制玩家研究其鎮(zhèn)定問題。對于給定的任意初始局勢,給出該博弈是否存在控制使得其全局鎮(zhèn)定到納什均衡的充要條件及控制的具體設計過程。在基于半張量積方法的演化擁塞博弈中,仍有一些問題有待解決,如在實際的演化擁塞博弈中,可能存在攻擊玩家干擾其他玩家的策略選擇的情況。因此,帶有攻擊玩家的演化擁塞博弈有待進一步研究。