基于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)中的条件，以增强该多智能体系统模型推广于实际应用的可能性也是我们将要继续完成的工作。