王桂林,徐 勇

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

0 引言

擁塞問題起源于交通工程,由于缺乏管理機(jī)構(gòu)有效的集中調(diào)控,加之出行者的個人自主行為,目標(biāo)在于最小化自己的花費,因此,采用博弈論來研究這類問題是十分必要的。Rosenthal首次提出擁塞博弈[1],并且指出擁塞博弈一定存在納什均衡?；谄淞己眯再|(zhì),生活中很多的擁塞問題均可采用擁塞博弈得以解決,比如交通網(wǎng)絡(luò)問題[2]、認(rèn)知無線電網(wǎng)絡(luò)問題[3-4]、以及資源分配問題[5-6]等。

近年來,程代展教授提出矩陣的半張量積理論,為演化博弈論的研究提供了良好的工具。利用矩陣的半張量積理論,將演化博弈建模成邏輯動態(tài)系統(tǒng),并將其表示成代數(shù)形式,通過分析狀態(tài)轉(zhuǎn)移矩陣的結(jié)構(gòu)來分析玩家的策略行為。在此基礎(chǔ)上,已有學(xué)者研究了演化博弈的穩(wěn)定性與鎮(zhèn)定性[7]、公共物品演化博弈的策略最優(yōu)[8]等理論。在生物系統(tǒng)和經(jīng)濟(jì)行為中,因玩家數(shù)目龐大,故玩家只與其鄰居玩家進(jìn)行博弈,此博弈可用網(wǎng)絡(luò)拓?fù)鋱D直觀表示玩家之間的關(guān)系,諸多學(xué)者在網(wǎng)絡(luò)演化博弈的領(lǐng)域得到了許多理論結(jié)果。比如,網(wǎng)絡(luò)演化博弈的分析控制[9]、帶時滯的網(wǎng)絡(luò)演化博弈的控制[10-11]、以及網(wǎng)絡(luò)演化博弈的策略一致性[12]等。擁塞博弈也可以被重復(fù)進(jìn)行,稱之為演化擁塞博弈。文獻(xiàn)[13]研究了演化擁塞博弈的收斂速度,證明演化擁塞博弈的納什均衡點是不動點。文獻(xiàn)[14]利用矩陣的半張量積將經(jīng)典擁塞博弈表示成代數(shù)形式,針對動態(tài)設(shè)備系統(tǒng),通過優(yōu)化每個玩家的支付函數(shù)來實現(xiàn)全局最優(yōu),得到玩家采用串聯(lián)型短視最優(yōu)響應(yīng)更新規(guī)則的演化動態(tài)一定會全局收斂到納什均衡。另外,矩陣的半張量積理論在布爾(控制)網(wǎng)絡(luò)的應(yīng)用也十分廣泛,得到了布爾(控制)網(wǎng)絡(luò)的集控性[15]、能觀性[16]、穩(wěn)定性[17]、以及切換布爾網(wǎng)絡(luò)的鎮(zhèn)定性[18]等理論。

在社會網(wǎng)絡(luò)中,玩家在進(jìn)行演化博弈時可能會存在攻擊玩家干擾其他正常玩家的策略選擇,該攻擊玩家可能會不考慮其他玩家的利益。此時,隨之而來的問題就是如何保證其他正常玩家的利益。所以,在演化博弈中,可以施加魯棒控制器來影響博弈的演化過程,從而使得系統(tǒng)中的可行狀態(tài)能收斂到納什均衡[19]。因為在系統(tǒng)中,可能會存在一些不合理的策略局勢,比如,文獻(xiàn)[20]圖1的棋盤中,根據(jù)象棋的規(guī)則,局勢C2→B3是不可行的。在布爾網(wǎng)絡(luò)[21-22]、網(wǎng)絡(luò)演化博弈[23]等領(lǐng)域的魯棒性問題都已被研究,但是在演化擁塞博弈領(lǐng)域還沒有相關(guān)的研究文獻(xiàn)。

本文利用矩陣的半張量積方法,考慮帶有攻擊玩家和可行狀態(tài)受限集的擁塞博弈演化過程魯棒性問題。由于在實際的擁塞問題中,所有玩家在下一時刻都可能進(jìn)行策略更新,所以本文采用并聯(lián)型短視最優(yōu)響應(yīng)策略更新規(guī)則。然而對于可行狀態(tài)受限集中的所有初始狀態(tài),要使得帶有攻擊玩家的演化擁塞博弈直接魯棒可達(dá)納什均衡是不容易的,為此,通過施加魯棒控制器來影響博弈進(jìn)程是非常必要的。本文通過設(shè)計開環(huán)控制和狀態(tài)反饋控制,使得帶有攻擊玩家的演化擁塞博弈中的可行狀態(tài)受限集中的所有初始狀態(tài)魯棒可達(dá)納什均衡。本文的主要貢獻(xiàn)如下:1)將半張量積的方法應(yīng)用于帶攻擊玩家和可行狀態(tài)受限集的演化擁塞博弈的研究;2)給出了設(shè)計控制的方法,使帶攻擊玩家的演化擁塞博弈中的可行狀態(tài)受限集中的所有初始狀態(tài)魯棒可達(dá)納什均衡。

1 預(yù)備知識

首先定義一些概念：

2)Dk:={1,2,…,k},k≥2。

4)Col(A)表示矩陣A的列的集合,Coli(A)表示矩陣A的第i列。

5)Lm×n表示m×n維邏輯矩陣的集合,L=δk[i1,i2,…,in]是結(jié)構(gòu)矩陣。

6)A和B的布爾乘積可定義為A×BB=(aij×Bbij)=(aij)∧(bij)。

然后介紹一些關(guān)于半張量積以及博弈論的定義及性質(zhì)。

定義1[7]矩陣Am×n和矩陣Bp×q的半張量積是

其中,t是n和p的最小公倍數(shù),?表示Kronecker積。

定義2[24]矩陣Ap×n和Bq×n的Khatri-Rao積為

性質(zhì)1[24](偽交換性) 設(shè)X∈Rp是一列向量,B為任意矩陣,那么

性質(zhì)2[24]設(shè)X∈Rm,Y∈Rn是兩個列向量,那么

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]為換位矩陣。

性質(zhì)3[24]設(shè)X∈Δk,那么

引理1[24]令f(x1,x2,…,xn):Dn→D是邏輯變量x1,x2,…,xn的邏輯函數(shù),則

其中,Mf是f的結(jié)構(gòu)矩陣。

2 主要結(jié)果

本節(jié)首先給出經(jīng)典的擁塞博弈;然后建模演化擁塞博弈的動態(tài)系統(tǒng),并將其表示成代數(shù)形式;最后建模帶攻擊玩家和控制玩家的演化擁塞博弈的動態(tài)系統(tǒng),設(shè)計開環(huán)控制和狀態(tài)反饋控制,使得帶攻擊玩家和可行狀態(tài)受限集的演化擁塞博弈魯棒可達(dá)納什均衡。

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)

則玩家i的花費函數(shù)為

2.2 演化擁塞博弈的動態(tài)系統(tǒng)及代數(shù)形式

首先給出演化擁塞博弈的動態(tài)方程

xi(t+1)=fi(x1(t),x2(t),…,xn(t)),i=1,2,…,n

(2)

本文采取的策略更新規(guī)則是并聯(lián)型短視最優(yōu)響應(yīng)。最優(yōu)響應(yīng)集

則玩家i在時刻t+1的策略選擇為

(3)

然后將演化擁塞博弈的動態(tài)系統(tǒng)(2)表示成代數(shù)形式

xi(t+1)=Mix(t),i=1,2,…,n

(4)

將系統(tǒng)(4)中的方程整合得到

x(t+1)=Mx(t)

其中,M=M1*M2*…*Mn∈Ll×l,“*”是Khatri-Rao積。

注1:文獻(xiàn)[13]已證明演化擁塞博弈至少有一個納什均衡點。

2.3 帶攻擊玩家和可行狀態(tài)受限集的演化擁塞博弈的魯棒性分析

這一部分主要考慮通過添加控制玩家來研究帶攻擊玩家和可行狀態(tài)受限集的演化擁塞博弈的魯棒性。不失一般性,假設(shè)玩家1,玩家2,…,玩家q是攻擊玩家,玩家q+1,玩家q+2,…,玩家m是控制玩家,其他n-m個玩家是正常玩家。

根據(jù)式(2),帶攻擊玩家和控制玩家的演化擁塞博弈動態(tài)方程為

xi(t+1)=fi(ξ1(t),…,ξq(t),uq+1(t),…,um(t),xm+1(t),…,xn(t)),i=m+1,…,n

(5)

將(5)轉(zhuǎn)化成代數(shù)形式并相乘得

z(t+1)=Lξ(t)u(t)z(t)

(6)

假設(shè)正常玩家的策略局勢集都取自于可行狀態(tài)受限集：

(7)

下面介紹帶有攻擊玩家和可行狀態(tài)受限集的演化擁塞博弈魯棒可達(dá)納什均衡的定義。記納什均衡點集Ω。

定義4帶有攻擊玩家和可行狀態(tài)受限集Γz的演化擁塞博弈魯棒可達(dá)納什均衡,如果對于任意的初始狀態(tài)z(0)∈Γz,在任意ξ(t)下,存在控制u(t),使得

接下來,設(shè)計開環(huán)控制和狀態(tài)反饋控制,使得系統(tǒng)(6)Γz中的所有狀態(tài)魯棒可達(dá)納什均衡。

先考慮開環(huán)控制,給出定理1。

接下來設(shè)計狀態(tài)反饋控制,形式如式(8)：

(8)

假設(shè)gi的結(jié)構(gòu)矩陣是Ki,i=q+1,q+2,…,m,則狀態(tài)反饋控制式(8)可表示成代數(shù)形式

u(t)=Kz(t)

將(6)變?yōu)?/p>

(9)

定理2系統(tǒng)(9)Γz中的所有狀態(tài)能夠通過狀態(tài)反饋控制魯棒可達(dá)納什均衡,當(dāng)且僅當(dāng)存在一個整數(shù)σ滿足1≤σ

(10)

證明:(充分性)假設(shè)式(10)成立,在任意的ξ(t)下,通過構(gòu)建狀態(tài)反饋控制矩陣K使得系統(tǒng)(9)魯棒可達(dá)納什均衡。

(11)

(必要性)假設(shè)系統(tǒng)(9)Γz中的所有狀態(tài)能夠通過狀態(tài)反饋控制u(t)=Kz(t)魯棒可達(dá)納什均衡,則系統(tǒng)(9)和控制u(t)=Kz(t)變成

(12)

注2:狀態(tài)反饋控制的設(shè)計重點在于增益矩陣K的設(shè)計。設(shè)計過程為

3 算例分析

考慮4個玩家N={1,2,3,4},5個資源P={1,2,3,4,5}組成的擁塞博弈。4個玩家的策略集

由式(1),設(shè)所有資源的花費為

Ξ=[2,3,5,7,3,5,6,9,2,4,6,10,3,6,7,8,2,5,7,9]

根據(jù)策略更新規(guī)則(3),擁塞博弈的演化動態(tài)的代數(shù)形式表示為

x(t+1)=Mx(t)

其中,M=δ54[45,24,18,53,14,26,27,24,27,15,24,15,23,14,23,24,24,24,18,24,18,26,14,26,27,24,27,45,24,18,15,45,18,9,6,9,15,24,15,15,15,15,6,6,6,18,24,15,17,14,14,9,6,6],x(t)=x1(t)x2(t)x3(t)x4(t)。

現(xiàn)在考慮帶有攻擊玩家的演化擁塞博弈。在演化擁塞博弈中,假設(shè)玩家1是攻擊玩家,玩家2是控制玩家,玩家3和玩家4是正常玩家。令ξ(t)=x1(t),u(t)=x2(t),z(t)=x3(t)x4(t)。得到帶攻擊玩家的演化擁塞博弈的代數(shù)形式

z(t+1)=Lξ(t)u(t)z(t)

(13)

其中,L=δ9[9,6,9,8,5,8,9,6,9,6,6,6,5,5,5,6,6,6,9,6,9,8,5,8,9,6,9,9,6,9,9,6,9,9,6,9,6,6,6,6,6,6,6,6,6,9,6,6,8,5,5,9,6,6]。

接下來設(shè)計狀態(tài)反饋控制u(t)=Kz(t),K=δ3[α1,α2,α3,α4,α5,α6,α7,α8,α9],使得帶攻擊玩家和可行狀態(tài)受限集的演化擁塞博弈魯棒可達(dá)納什均衡。

將式(13)轉(zhuǎn)換成

則有

R11=δ9[9,6,9],R32=δ9[9,6,0],R53=δ9[0,0,5],R74=δ9[9,6,9],R95=δ9[9,6,0]

K=δ3[α1,α2,1,α4,3,α6,α7,α8,1]

圖1 可行狀態(tài)受限集Γz的魯棒控制過程

4 結(jié)論

本文研究帶攻擊玩家和可行狀態(tài)受限集的演化擁塞博弈的魯棒控制問題。首先,將帶攻擊玩家和控制玩家的演化擁塞博弈建模成多值邏輯動態(tài)系統(tǒng),利用矩陣的半張量積,給出等價的代數(shù)形式。在此基礎(chǔ)上,分析博弈的動態(tài)行為。然后,對于給定可行狀態(tài)受限集的任意初始局勢,給出了該博弈是否存在控制使得其魯棒可達(dá)納什均衡的充要條件,并給出了控制的具體設(shè)計過程。需要指出的是,在基于半張量積方法的的帶攻擊玩家的演化擁塞博弈中,仍然有一些問題有待研究。比如,在實際帶攻擊玩家的演化擁塞博弈中,在攻擊玩家和正常玩家進(jìn)行決策時,可能會記住過去不止一個時刻的決策行為,所以帶有攻擊玩家的時滯演化擁塞博弈有待進(jìn)一步研究。