基于半张量积方法的时滞演化拥塞博弈镇定

王桂林,徐 勇

(河北工业大学 理学院,天津 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 结束语

本文对时滞演化拥塞博弈的控制问题进行研究,提出一种基于半张量积的时滞演化拥塞博弈镇定方法。将时滞演化拥塞博弈建模成多值逻辑动态系统,利用矩阵的半张量积给出等价的代数形式。在此基础上,分析时滞演化拥塞博弈的动态行为,通过在该博弈中添加可以自由选择策略的控制玩家研究其镇定问题。对于给定的任意初始局势,给出该博弈是否存在控制使得其全局镇定到纳什均衡的充要条件及控制的具体设计过程。在基于半张量积方法的演化拥塞博弈中,仍有一些问题有待解决,如在实际的演化拥塞博弈中,可能存在攻击玩家干扰其他玩家的策略选择的情况。因此,带有攻击玩家的演化拥塞博弈有待进一步研究。