基于半張量積方法的時滯演化擁塞博弈鎮定

王桂林,徐 勇

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

0 概述

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

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

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

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

1 預備知識

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

A

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

命題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 本文方法

本節給出經典的擁塞博弈,對時滯演化擁塞博弈的動態系統進行建模,并將其表示成代數形式,設計開環控制和狀態反饋控制,使時滯演化擁塞博弈全局鎮定到納什均衡。

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的策略。

令所有資源的花費函數為:

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

(1)

2.2 時滯演化擁塞博弈的動態及代數形式

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

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

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

(2)

本文采用的更新規則是時間并聯型短視最優響應,最優響應策略集記作:

如果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)

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

經整理得到如下公式:

(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)=

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

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

1)系統不同,本文的演化動態系統是帶有時滯的。

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。

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

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)可轉化為如下形式:

(7)

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

(8)

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

(9)

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

(10)

假設:

(11)

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

(12)

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

3 算例分析

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

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

此時有:

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

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

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

4 結束語

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