王桂林,徐 勇

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

0 概述

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

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

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

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

1 預(yù)備知識

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

A

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

命題1設(shè)X∈Δk,則有[10]:

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

XA=(Im?A)X

命題3設(shè)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的結(jié)構(gòu)矩陣。

2 本文方法

本節(jié)給出經(jīng)典的擁塞博弈,對時滯演化擁塞博弈的動態(tài)系統(tǒng)進(jìn)行建模,并將其表示成代數(shù)形式,設(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的策略。

令所有資源的花費(fè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īng),最優(yōu)響應(yīng)策略集記作:

如果xi(t)∈Oi(x(t)),則xi(t+1)=xi(t),否則選擇最小下標(biāo)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))稱為長度為τ的軌跡局勢。

證明(必要性) 假設(shè):

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

證明(充分性) 假設(shè):

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

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

注2該定理與文獻(xiàn)[24]的不同之處主要有兩點(diǎn):

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

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

2.3 控制器設(shè)計

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)

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

(9)

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

(10)

假設(shè):

(11)

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

(12)

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

3 算例分析

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

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

此時有:

圖1 例1設(shè)計所用的控制序列

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

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

4 結(jié)束語

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