基于NE結果的多智能體系統模型及其能控性

國俊豪，紀志堅

(青島大學自動化學院，山東 青島 266071)

0 引言

博弈論主要研究的是個體所做決策如何影響其他個體決策，其中最核心的概念是納什均衡(Nash Equilibrium)，納什均衡是指在個體之間在相互作用中達到一種均衡狀態，在此狀態下不會有個體通過單方面改變策略來增加收益。它有助于解釋人們是如何做出復雜決策的，并廣泛應用于國際關系的處理以及心理學的研究。在生活中，我們不難發現肯德基和麥當勞的選址位置總是相近的，也就是說肯德基的附近幾乎也會存在一家麥當勞。再比如星巴克附近總會有好幾家咖啡店，這是因為每家店的決策者總會選擇最優的地理位置，以獲得最大的客流量，因此同一類型的商家會出現在相近的地方，而不是分散開來，便利不同位置的顧客。從經濟學的角度來看，一旦有一家偏離了最優位置，收益就會減少，因此達到了納什均衡。我們用圖1a表示上述情況，L1,L2附近有4條街道，L3,L4附近有兩條街道，其中L1,L2,L3,L4表示不同店鋪。由于納什均衡的存在，L1,L2都期望有四條街的客流量，因而都期望能在四條街的中心位置。同理L3,L4為了同時擁有第5條街和第6條街的客流量，最終也開在了相近的位置。如圖1b所示，L1,L2均與街道F1,F2,F3,F4相連接，因此有相同的選址。

圖1 等鄰居模型的圖論描述

基于上述情景，可以看到進行博弈并期望達到納什均衡的是Li,i=1,2,3,4，因此Li做出的決策對整個系統的狀態具有決定性的影響，我們將其稱作領導者，并在本文中只考慮領導者之間的博弈；客流量的多少取決于領導者的決策是否使自己受益，因此在這種情況下，將客流量視作跟隨者。在這里，領導者i的決策用rj(i)表示。在博弈論中，類似的情況還有很多，比如著名的囚徒困境，兩個囚徒會聽到警察所提供的相同的判刑規則，這時我們將進行博弈的囚徒們建模為領導者，警察(或警察提供的規則)為跟隨者，此時領導者們的跟隨者鄰居是相同的，所以囚徒們做出相同的決策，即都選擇了坦白罪行，并獲得了同樣的處罰，達到納什均衡的結果。

上述實際問題可以從圖論的角度進行刻畫，因此可以讓每個智能體遵循預先設定的協議，然而智能體顯著的特點是高智商性，因此智能體可以通過博弈來決策自己的行為。本文考慮既能夠遵循預先設定的協議又能自主做出決策的智能體。基于如上所述，本文建立了一類新的模型——等鄰居模型，即在領導者—跟隨者架構下，如果不同的領導者含有相同的鄰居集合(如上述情景所示，這里的鄰居僅由跟隨者構成)，則這些領導者會有相同的決策，否則領導者做出不同的決策。在此模型下，由領導者自身的決策所形成的納什均衡能否改變系統的狀態是本文研究的主要問題，即對基于納什均衡的多智能體系統的能控性研究。與現有的對能控性問題的研究方法不同，我們不是從能控的秩判據等角度考慮問題，而是研究等鄰居模型與常用模型之間的能控性關系，來得到等鄰居模型能控的條件。

到目前為止，在研究系統的能控性時[1-7]，大部分內容是通過如式(1)所示的這類系統得到信息拓撲結構與系統的能控性之間的關系：

(1)

A,B分別為系統矩陣和輸入矩陣。值得注意的是，這些研究成果雖然均是基于系統(1)這樣的形式得到的，但是基于輸入矩陣的不同，得到的能控性結論也不同。因此，如果模型之間不能等價轉換，或者不清楚兩個模型等價的條件，那么在一個固定模型下得到的那些研究成果的價值也會減少。例如，在運用一些結論或者引理時，需要特別考慮該結論是在什么模型下產生的，如文獻[8]中所得到的能控圖、條件能控圖、不能控圖的劃分標準是在廣播控制下成立的，在其他模型下并不成立，所謂的廣播控制是指在不存在智能體—智能體通信的前提下，不加區別地向所有智能體發送相同的信號，從而控制多智能體系統；領導者—跟隨者網絡的可控性首先在文獻[9]中提出，Tanner等人在他們的模型下使用系統矩陣的頻譜分析來描述可控性；對于多領導者的情形，文獻[10]做了深入討論。在Tanner模型下，得到了關于能控性的大量研究結果，如在文獻[11]中提出了一個幾乎等價劃分的充要條件，闡明了拉普拉斯矩陣L與一般拉普拉斯矩陣Lπ的關系；文獻[12]研究了多智能體系統在等價劃分下的能控性問題。在多智能體系統中添加博弈的思想是十分重要的，張人仁[13]等人研究的是當一個宏觀觀測器給予決策后，剩下的智能體試圖優化各自的目標函數以達到可能的納什均衡；馬晶瑩[14]等人研究了通過博弈來決定自己行為而不遵循任何預先設定的協議的智能體。而本文結合圖論以及多智能體系統的分布式協議研究了多智能體能夠自主地做出決策的情況。

在物理系統的數學建模中，人們總是面臨一個兩難的境地：建立一個精確的模型會使得操作困難，但是，如果建立一個相對容易操作的模型又會使實用性降低。綜合考慮，我們發現一方面每個個體都有自己的選擇、都有自己的算計、都期望自己利益最大化，因此多個個體構成的多智能體系統，有考慮博奕和納什均衡的必要性，這是實際需求的驅使；另一方面，多智能體網絡系統的根本特點是包含了圖拓撲結構和分布式協議。結合以上兩方面，本文建立了領導者—跟隨者框架下的等鄰居模型。該模型首次將納什均衡與圖的拓撲結構建立聯系，使得納什均衡的結果更具直觀性：具體來說，本文建立的這類模型，是模擬了當不同的領導者含有相同的鄰居集合時，他們會做出相同的決策的情況，無論哪一個領導者改變自己的決策都會使自己的收益減少，因此領導者的決策是否相同，可以從圖的拓撲結構上分析他們是否有相同的鄰居集；其次，該模型更具有實際應用價值，更便于問題的處理；不僅如此，我們發現該模型能夠轉化為常見模型的形式，因此，在研究其能控性問題時，我們不是從能控的秩判據等角度考慮問題，而是研究等鄰居模型與常用模型之間的能控性關系，來得到等鄰居模型能控的條件。

1 預備知識

本文將智能體視為頂點,智能體間的通信(或敏感關系)視為邊,則整個系統的通信關系可用一個圖G描述,稱G為系統的信息拓撲。若智能體之間的通信是雙向的,則用無向圖表示;否則,視為有向圖。本文研究連通的沒有權重的無向圖。若系統的信息拓撲不隨時間變化,即智能體之間的邊不會隨時間的變化增加或減少,則稱為固定拓撲。本文研究固定拓撲結構下的能控性問題。

一個無向圖G由頂點集V(G)和邊集E(G)?V(G)×V(G)組成。若圖G為具有n個頂點的有限圖,則可以將V(G)和E(G)分別表示為V(G)={1,2,…,n},E(G)={(i,j)|i,j∈V(G)}。頂點i的鄰居集合定義為N(i)={j∈V(G)|(i,j)∈E(G)}。如果圖G中任2個不同的頂點i,j間都存在1條道路,則稱圖G是連通的。圖的鄰接矩陣定義為A(G)=[aij]n×n,其中

引理1[15]n維連續時間線性時不變系統(1)完全能控的充分必要條件為矩陣A不存在與B正交的非零左特征向量，即對矩陣A的所有特征值λi,i=1,2,…,n,使得同時滿足

αTA=λiαT,αTB=0

的左特征向量αT=0。

引理2[15]對n維連續時間線性時不變系統(1),構造能控性判別矩陣:Q=[BABA2B…An-1B],則系統完全能控的充分必要條件為rank(Q)=n。

2 等鄰居模型

2.1 等鄰居模型

在等鄰居模型下，根據協議能夠彼此之間進行博弈后做出自己決策的智能體稱為領導者，我們將領導者i的決策用ri表示；僅僅遵循預先設定好的協議而無法進行博弈的智能體稱為跟隨者，跟隨者的狀態受到領導者的影響。值得注意的是：同一個領導者可以有多個不同的決策，這與廣播控制的控制輸入不同；如果不同的領導者含有相同的鄰居集合NF(i)，且NF(i)?VF,則這些領導者會做出相同的決策。

我們假定領導者的所有決策均不相等，這保證了同一領導者不會做出相同的決策。此時，n個智能體中的前m個智能體i表示為

(2)

(3)

即m個跟隨者遵循式(3)，剩下的n-m個領導者用式(4)表示

(4)

其中,ui為跟隨者遵循的協議，rj表示領導者i與彼此之間進行博弈后做出的決策。結合店鋪選址問題，可以發現如果領導者i1與i2滿足NF(i1)=NF(i2)時，則有rj(i1)=rj(i2)。

我們發現考慮能進行博弈的智能體依舊可以寫成如式(1)的形式，進而研究線性系統的能控性問題，如圖2c所示。

則上述問題可以轉換成

(5)

其中，L為拉普拉斯矩陣，B=[bij]∈Rn×(n-m)是二元矩陣，當節點i∈V與節點j∈VF有連接時，bij=1，否則bij=0，其中，VF是跟隨者的集合。例如圖2c中的節點1,2,4的跟隨者鄰居均為節點5,因此做出相同的決策r5,領導者節點1,3有相同的跟隨者鄰居6，因此也有相同的決策r6。值得注意的是，該模型說明同一領導者可以同時做出不同決策，這也是符合實際的，例如商家選址時所做的決策并非只受一類鄰居的影響，因此可以做出不同的決策。另外，在此模型中，基于納什均衡的存在，存在不同領導者自主做出相同的決策的情況。

通過對基于博弈的多智能體系統模型的轉換，可以看到這與常見的模型存在形式上的相似性，于是下面介紹了常見的模型，并從模型角度研究等鄰居模型的能控性。

2.2 常用模型[16]

在這類模型下，圖2中的部分節點(領導者)會被施加外部控制信號，而剩余節點(跟隨者)將會被該類節點及其自身拓撲結構控制，如圖2a所示。其中每一個跟隨者的狀態由式(6)決定

圖2 三類模型在同一拓撲結構下的表示

(6)

每一個領導者的狀態j∈VL由式(7)決定

(7)

向量x=[x1,…,xn]T∈Rn表示系統中所有的狀態，向量u=[u1,…,un-m]T∈Rn-m表示系統中的控制輸入，且這些控制輸入不相同。因此可將(6)和(7)表達成如式(8)的形式。

(8)

2.3 Tanner模型[17]

求得跟隨者的動力學方程為

(9)

在此類模型下，僅僅考慮領導者與跟隨者之間的連邊向跟隨者節點注入的控制信號，而不考慮領導者節點的狀態。

通過具體的例子，分析上述三類模型的不同：

如圖2所示，假定系統中只有兩個領導者。在由6個點構成的固定拓撲結構下，選擇節點5和6作為領導者，它們有相同的拉普拉斯矩陣，所以在不同的模型下，我們只需要考慮它們的輸入矩陣。由上述定義，分別得到他們的輸入矩陣

結果表明，這三類模型的輸入矩陣的形式(維數,符號)并不相同。

綜上所述，等鄰居模型與常見模型的區別在于領導者個體能否通過博弈自主做出決策，我們考慮的是跟隨者鄰居相同的那部分領導者會做出相同的決策，以便達到納什均衡的狀態。特別地，我們發現等鄰居模型在形式上可以與系統(1)進行轉化，而系統(1)是多智能體系統的根本特點，因此我們研究不同模型與等鄰居模型的關系來得到在這類新模型下系統能控的條件。

3 主要結果

本文首次研究遵循一定協議并能自主做出決策的智能體。在此類系統下，能研究的問題很多，比如一致性問題、包圍控制問題、事件誘導控制等問題，而本文僅考慮系統的狀態是否可以通過領導者自主做出的決策來驅動任意給定的初始狀態到達任意的期望狀態，我們通過能控性的概念進行研究。

定義1(領導者—跟隨者架構下的納什均衡狀態)在等鄰居模型下，每個領導者都期望做出使自己利益最大化的決策，基于納什均衡的存在，進行博弈的領導者做出的決策相等，即rj(i1)=rj(i2)=…=rj(ik),其中ik表示領導者，此時系統形成的狀態我們稱為領導者—跟隨者架構下的納什均衡狀態。

定義2系統(2)(3)(4)被稱為能控的，如果對于任意給定的初始狀態x(0)和終點狀態x(T),都存在領導者策略r(t),t∈[0,T],在此策略下，系統存在唯一的領導者—跟隨者架構下的納什均衡狀態x*(t)=x(T)。

假設1假設在多智能體網絡系統中總是存在唯一的領導者—跟隨者架構下的納什均衡狀態，此時領導者所做決策滿足等鄰居模型的條件。

由于等鄰居模型可以化為常見模型的形式，我們很自然地從研究不同模型之間的關系入手，研究在等鄰居模型下的能控性問題。由于一般模型中領導者不能自主做出決策，但是存在控制輸入u，因此在研究兩者的關系時，假定等鄰居模型中的決策r與這里的u等價；另外，等鄰居模型中，決定決策r是否相等的因素是跟隨者，因此等鄰居模型中的跟隨者在一般模型中表示的是領導者的角色。因此，在定理1中，我們提到的“在同一拓撲結構下”意思是每個智能體的連接方式均相等，而且需要將領導者跟隨者的角色互換，從而研究兩類模型的關系。如圖2所示，a,c即表示“同一拓撲結構”，雖然在a中，選擇節點5,6為領導者，在c中，選擇節點1,2,3,4為領導者，但是c中的領導者所做決策取決于節點5,6，因此在研究不同模型的關系時，我們稱節點5,6為領導者。此時稱a,c有相同的領導者5,6，也有相同的跟隨者1,2,3,4。

上述引理反映了智能體之間變換序號對整個系統的動力學方程的影響，即系統矩陣左乘并右乘對應的置換矩陣P,則輸入矩陣需要左乘對應的置換矩陣P。其實，改變節點的編號，圖并不會發生實質改變，只是“人為定義的名稱”發生了改變。在(L,M)下，并不能保證前m個序號為跟隨者，而在Tanner模型中，一般令前m個智能體為跟隨者。因此，研究不同模型下的智能體狀態時，可運用該引理使之對應。

引理4[18](L,M)是不可控的，當且僅當L(G)的特征向量中對應于領導者的位置的元素均為零。

定理1(L,M)模型與Tanner模型、等鄰居模型在同一拓撲結構下，有如下關系：

1)在一階系統下，(L,M)與(Lf,Lfl)等價。即(L,M)能控的充分必要條件是Tanner模型能控；

2)若假設1成立：

(1)當|VL|=1時，不妨設該領導者為n,若dn=n-1，則(L,M)能控的充分必要條件為(L,B)能控；若dn

(2)當|VL|>1時，若存在|N(p)|≠0,vip≠0,p∈VL,N(p)?VL,使得|N(p)|≠λi,i=1,2,…,n，則(L,M)是能控的，當且僅當(L,B)能控。

證明 1)要證(L,M)與Tanner模型等價，只要證明在相同的拓撲結構下，當選擇相同的領導者時，兩模型有相同的能控性。

(2)當|VL|>1時，在上述條件下，若(L,M)不能控，則(L,B)不能控，其證明與(1)類似，在此省略。下面只需要證明若(L,M)能控，則(L,B)能控。

在研究(L,M)與等鄰居模型的關系時，我們得到兩模型能控性相同的充分必要條件，當該充分必要條件不成立時，我們發現兩個模型的能控性并不相同。如圖3a所示，選擇領導者集合為VL={6,7,8},此時不存在|N(p)|≠0,vip≠0,p∈VL,N(p)?VL,使得|N(p)|≠λi,i=1,2,…,8。此時，兩個模型的輸入矩陣分別為

計算得rank[Q(M)]=8,rank[Q(B)]=7,因此具有不同的能控性。因此，正是這個限制條件的存在，在一定程度上也會限制該多智能體系統模型推廣于實際應用。

例1如圖3b所示，其拉普拉斯矩陣及其特征值和特征向量分別為

圖3 選擇6,7,8為領導者的八點圖

推論1在定理1的2)(2)的條件下，(L,B)不能控的充分必要條件為存在L的一個特征向量vi,使vi對應的領導者的位置全為零。

證明：在定理1的2)(2)的條件下,(L,B)與(L,M)有相同的能控性，因此由引理4可得該結論成立。

4 結論和展望

本文基于納什均衡得到的結果建立了一類新的模型，即等鄰居模型，并分析了在這類模型下多智能體系統的能控性問題。我們先研究了一般性模型與Tanner模型之間的關系，發現在一階積分器下，兩個模型是等價的，即具有相同的能控性，進而我們研究了等鄰居模型與一般性模型的能控性關系，得到了等鄰居模型在固定條件下能夠與其他模型產生相同能控性的結論。接下來，我們計劃進一步研究在一般性的模型下得到的結論能否應用到等鄰居模型，或者添加合適的條件使得原有的研究成果在等鄰居模型下成立。另外，弱化定理1 2)中的條件，以增強該多智能體系統模型推廣于實際應用的可能性也是我們將要繼續完成的工作。