帶攻擊玩家的演化擁塞博弈的魯棒性分析

王桂林,徐 勇

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

0 引言

擁塞問題起源于交通工程,由于缺乏管理機構(gòu)有效的集中調(diào)控,加之出行者的個人自主行為,目標(biāo)在于最小化自己的花費,因此,采用博弈論來研究這類問題是十分必要的。Rosenthal首次提出擁塞博弈[1],并且指出擁塞博弈一定存在納什均衡?；谄淞己眯再|(zhì),生活中很多的擁塞問題均可采用擁塞博弈得以解決,比如交通網(wǎng)絡(luò)問題[2]、認知無線電網(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)濟行為中,因玩家數(shù)目龐大,故玩家只與其鄰居玩家進行博弈,此博弈可用網(wǎng)絡(luò)拓撲圖直觀表示玩家之間的關(guān)系,諸多學(xué)者在網(wǎng)絡(luò)演化博弈的領(lǐng)域得到了許多理論結(jié)果。比如,網(wǎng)絡(luò)演化博弈的分析控制[9]、帶時滯的網(wǎng)絡(luò)演化博弈的控制[10-11]、以及網(wǎng)絡(luò)演化博弈的策略一致性[12]等。擁塞博弈也可以被重復(fù)進行,稱之為演化擁塞博弈。文獻[13]研究了演化擁塞博弈的收斂速度,證明演化擁塞博弈的納什均衡點是不動點。文獻[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ò)中,玩家在進行演化博弈時可能會存在攻擊玩家干擾其他正常玩家的策略選擇,該攻擊玩家可能會不考慮其他玩家的利益。此時,隨之而來的問題就是如何保證其他正常玩家的利益。所以,在演化博弈中,可以施加魯棒控制器來影響博弈的演化過程,從而使得系統(tǒng)中的可行狀態(tài)能收斂到納什均衡[19]。因為在系統(tǒng)中,可能會存在一些不合理的策略局勢,比如,文獻[20]圖1的棋盤中,根據(jù)象棋的規(guī)則,局勢C2→B3是不可行的。在布爾網(wǎng)絡(luò)[21-22]、網(wǎng)絡(luò)演化博弈[23]等領(lǐng)域的魯棒性問題都已被研究,但是在演化擁塞博弈領(lǐng)域還沒有相關(guān)的研究文獻。

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

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)受限集的演化擁塞博弈魯棒可達納什均衡。

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:文獻[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)受限集的演化擁塞博弈魯棒可達納什均衡的定義。記納什均衡點集Ω。

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

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

先考慮開環(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āng)且僅當(dāng)存在一個整數(shù)σ滿足1≤σ

(10)

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

(11)

(必要性)假設(shè)系統(tǒng)(9)Γz中的所有狀態(tài)能夠通過狀態(tài)反饋控制u(t)=Kz(t)魯棒可達納什均衡,則系統(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)受限集的演化擁塞博弈魯棒可達納什均衡。

將式(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)受限集的任意初始局勢,給出了該博弈是否存在控制使得其魯棒可達納什均衡的充要條件,并給出了控制的具體設(shè)計過程。需要指出的是,在基于半張量積方法的的帶攻擊玩家的演化擁塞博弈中,仍然有一些問題有待研究。比如,在實際帶攻擊玩家的演化擁塞博弈中,在攻擊玩家和正常玩家進行決策時,可能會記住過去不止一個時刻的決策行為,所以帶有攻擊玩家的時滯演化擁塞博弈有待進一步研究。