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 预备知识

本节主要介绍矩阵的半张量积理论和演化博弈论的相关符号、概念及性质。

令$\mathcal{M} $_m×n表示m×n的实矩阵的集合, C_col(A)表示矩阵A的列的集合, C_colⁱ(A)是矩阵A的第i列, $\mathcal{D}$_k:={1, 2, …, k}, k≥2, δ_kⁱ表示单位矩阵I_k的第i列, Δ_k:={δ_kⁱ|i=1, 2, …, k}。如果C_col(L)⊂Δ_m, 则称矩阵L=δ_m[i₁, i₂, …, i_n]∈$\mathcal{M}$_m×n为逻辑矩阵, $\mathcal{L}$_m×n表示m×n维逻辑矩阵的集合。

定义1  令A∈$\mathcal{M}$_m×n, B∈$\mathcal{M}$_p×q, n和p的最小公倍数为t=lcm{n, p}, 则A和B的半张量积为^[10]:

$ \mathit{\boldsymbol{A}} \ltimes \mathit{\boldsymbol{B}}: = (\mathit{\boldsymbol{A}} \otimes {\mathit{\boldsymbol{I}}_{t/n}})(\mathit{\boldsymbol{B}} \otimes {\mathit{\boldsymbol{I}}_{t/p}}) \in {\mathcal{M}_{mt/n \times qt/p}} $

其中, ⊗表示Kronecker积。由于矩阵的半张量积几乎保持了传统矩阵乘积的所有主要性质, 因此在不混淆的情况下, 可以省略“⋉”。

定义2  令A∈$\mathcal{M}$_p×n, B∈$\mathcal{M}$_q×n, 则矩阵A和B的Khatri-Rao积为^[10]:

$ \begin{array}{*{20}{l}} {\mathit{\boldsymbol{A}} * \mathit{\boldsymbol{B}} = [C_{{\rm{col}}}^1(\mathit{\boldsymbol{A}}) \ltimes C_{{\rm{col}}}^1(\mathit{\boldsymbol{B}}),}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} C_{{\rm{col}}}^2(\mathit{\boldsymbol{A}}) \ltimes C_{{\rm{col}}}^2(\mathit{\boldsymbol{B}}), \cdots ,C_{{\rm{col}}}^n(\mathit{\boldsymbol{A}}) \ltimes C_{{\rm{col}}}^n(\mathit{\boldsymbol{B}})]} \end{array} $

命题1  设X∈Δ_k, 则有^[10]:

$ {\mathit{\boldsymbol{X}}^2} = \mathit{\boldsymbol{O}}_k^R\mathit{\boldsymbol{X}} $

其中, O_k^R:=δ_k²[1, k+2, 2k+3, …, k²]∈$\mathcal{L}$_k²×k为k维降阶矩阵。

命题2  设X∈R^m是一列向量, A为任意矩阵^[10], 则有:

$ \mathit{\boldsymbol{X}} \times \mathit{\boldsymbol{A}} = ({\mathit{\boldsymbol{I}}_m} \ltimes \mathit{\boldsymbol{A}})\mathit{\boldsymbol{X}} $

命题3  设X∈R^m, Y∈Rⁿ是2个列向量^[10], 则有:

$ {\mathit{\boldsymbol{W}}_{[m,n]}}\mathit{\boldsymbol{XY}} = \mathit{\boldsymbol{YX}} $

其中, W_{[m, n]}=δ_mn[1, m+1, …, (n-1)m+1, 2, m+2, …, (n-1)m+2, …, m, 2m, …, nm]为换位矩阵。

引理1  设f:$\mathcal{D}$kn→$\mathcal{D}$k是k值逻辑函数, 则存在唯一的Mf∈$\mathcal{L}$k×kn[10], 使得:

$ f({x_1},{x_2}, \cdots ,{x_n}) = {\mathit{\boldsymbol{M}}_f} \ltimes _{i = 1}^n{x_i} $

其中, M_f是f的结构矩阵。

定义3  给定一个有限博弈G=(N, S, C), 局势s_*=(s_*¹, s_*², …, s_*ⁿ)称为一个纳什均衡^[11], 如果c_i(s_*¹, s_*², …, s_*ⁿ)≤c_i(s_*¹, …, s_*^i-1, sⁱ, s_*ⁱ⁺¹, …, s_*ⁿ), 则有sⁱ∈Sⁱ, i=1, 2, …, n。其中, C表示玩家的花费。

2 本文方法

本节给出经典的拥塞博弈, 对时滞演化拥塞博弈的动态系统进行建模, 并将其表示成代数形式, 设计开环控制和状态反馈控制, 使时滞演化拥塞博弈全局镇定到纳什均衡。

2.1 拥塞博弈

一个拥塞博弈G=(N, P, (Sⁱ)_i∈N, (Ξ_j)_j∈P), 其中:

1) N={1, 2, …, n}表示有限的玩家集。

2) P={1, 2, …, p}表示有限的所有玩家共享的资源集。

3) Sⁱ⊂P表示玩家i的策略集, 其中, sⁱ∈Sⁱ是i的策略。

4) Ξ_j表示资源j∈P的花费, 其只依赖于局势中选取资源j的玩家数量, 局势记作s=(s¹, s², …, sⁿ), 局势的集合为$S = \prod\limits_{i = 1}^n {{S^i}} $。

令所有资源的花费函数为:

$ \Xi = \left[ {\begin{array}{*{20}{l}} {{\Xi _1},{\Xi _2}, \cdots ,{\Xi _p}]} \end{array}} \right. $

(1)

其中, Ξ_j=[ξ₁^j, ξ₂^j, …, ξ_n^j], j=1, 2, …, p, ξ_k^j表示有k个玩家选取资源j的花费, 则玩家i的花费函数为:

$ {c_i}(s) = \sum\limits_{j = {s^i}} {{\Xi _j}} ({k_j}(s)),i = 1,2, \cdots ,n $

2.2 时滞演化拥塞博弈的动态及代数形式

本文考虑一类演化拥塞博弈, 其中所有玩家的策略都带有时滞, 则时滞演化拥塞博弈的动态方程如下:

$ \begin{array}{*{20}{l}} {{x_i}(t + 1) = {f_i}({x_1}(t - \tau + 1),{x_2}(t - \tau + 1), \cdots ,}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {x_n}(t - \tau + 1), \cdots ,{x_1}(t),{x_2}(t), \cdots ,{x_n}(t))} \end{array} $

(2)

其中, i=1, 2, …, n, x_i(l)∈P是玩家i在时刻l的策略, l=t-τ+1, t-τ+2, …, t, f_i:$\mathcal{D}$_p^τn→$\mathcal{D}$_p是p值逻辑函数, 它由策略更新规则决定。

本文采用的更新规则是时间并联型短视最优响应, 最优响应策略集记作:

$ {O_i}(x(t)) = \mathop { {\rm{argmin}} }\limits_{{x_i}{\kern 1pt} \in {\kern 1pt} {\kern 1pt} P} \{ {c_i}({x^i},{x^{ - i}})\} $

如果x_i(t)∈O_i(x(t)), 则x_i(t+1)=x_i(t), 否则选择最小下标j, 使得x_j(t)∈O_i(x(t)), 并令x_i(t+1)=x_j(t)。

将时滞演化拥塞博弈的动态方程转化为代数形式, 根据引理1, 令$x=\ltimes _{i=1}^{n}{{x}_{i}}$, 则时滞演化拥塞博弈的动态方程如下:

$ \begin{array}{*{20}{l}} {{x_i}(t + 1) = {\mathit{\boldsymbol{M}}_i}x(t - \tau + 1)x(t - \tau + 2) \cdots x(t)}\\ {i = 1,2, \cdots ,n} \end{array} $

其中, M_i∈$\mathcal{L}$_p×p^τn是f_i的结构矩阵。

整合上述方程, 得到如下公式:

$ x(t + 1) = \mathit{\boldsymbol{M}}x(t - \tau + 1)x(t - \tau + 2) \cdots x(t) $

(3)

其中, M=M₁*M₂*…*M_n∈$\mathcal{L}$_pⁿ×p^τn, *表示Khatri-Rao积。

为方便研究, 本文将带时滞的动态系统, 即式(3)转换成不带时滞的动态系统。令y(t)=x(t-τ+1)x(t-τ+2)…x(t), 则有如下公式:

$ \begin{array}{l} \begin{array}{*{20}{l}} {y(t + 1) = x(t - \tau + 2)x(t - \tau + 3) \cdots x(t)x(t + 1) = }\\ {x(t - \tau + 2)x(t - \tau + 3) \cdots x(t)\mathit{\boldsymbol{M}}y(t) = } \end{array}\\ \begin{array}{*{20}{l}} {({\mathit{\boldsymbol{I}}_{p(\tau - 1)n}} \otimes \mathit{\boldsymbol{M}})x(t - \tau + 2)x(t - \tau + 3) \cdots x(t)}\\ {x(t - \tau + 1)x(t - \tau + 2) \cdots x(t - 1)x(t) = } \end{array}\\ \begin{array}{*{20}{l}} {({\mathit{\boldsymbol{I}}_{p(\tau - 1)n}} \otimes \mathit{\boldsymbol{M}}){\mathit{\boldsymbol{W}}_{[{p^n},p(\tau - 1)n]}}x(t - \tau + 1)}\\ {O_{p(\tau - 1)n}^Rx(t - \tau + 2)x(t - \tau + 3) \cdots x(t - 1)x(t) = } \end{array}\\ ({\mathit{\boldsymbol{I}}_{p(\tau - 1)n}} \otimes \mathit{\boldsymbol{M}}){\mathit{\boldsymbol{W}}_{[{p^n},p(\tau - 1)n]}}({\mathit{\boldsymbol{I}}_{{p^n}}} \otimes \mathit{\boldsymbol{O}}_{p(\tau - 1)n}^R)y(t) \end{array} $

经整理得到如下公式:

$ y(t + 1) = \mathit{\boldsymbol{\tilde M}}y(t) $

(4)

其中, $\mathit{\boldsymbol{\widetilde M}} = \left( {{\mathit{\boldsymbol{I}}_{p\left( {\tau - 1} \right)n}} \otimes \mathit{\boldsymbol{M}}} \right){\mathit{\boldsymbol{W}}_{\left[ {{p^n}, {p^{\left( {\tau - 1} \right)n}}} \right]}}\left( {{\mathit{\boldsymbol{I}}_{{p^n}}} \otimes O_{{p^{\left( {\tau - 1} \right)n}}}^R} \right)$。显然, 拥塞博弈的时滞演化动态方程式(2)的代数表示式(3)与式(4)是等价的。

注1  本文将x(t)称为策略局势, 将X(t)=(x(t-τ+1), x(t-τ+2), …, x(t))称为长度为τ的轨迹局势。

对于时滞演化拥塞博弈(式(3)), 可以用不带时滞的动态系统的状态转移矩阵$\mathit{\boldsymbol{\widetilde M}}$的元素来描述纳什均衡, 从而得到定理1。

定理1  考虑不带时滞的系统(式(4)), δpτnb是纳什均衡的充要条件为$\mathit{\boldsymbol{\widetilde M}}$的对角线元素$\mathit{\boldsymbol{\widetilde m}}$bb=1(不动点)。

证明(必要性)  假设:

$ \begin{array}{l} y(t) = x(t - \tau + 1)x(t - \tau + 2) \cdots x(t) = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \ltimes _{i = 1}^n{x_i}(t - \tau + 1) \ltimes _{i = 1}^n{x_i}(t - \tau + 2) \cdots \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \ltimes _{i = 1}^n{x_i}(t) = \delta _{{p^{\tau n}}}^b \end{array} $

是一个纳什均衡, 则对于每个玩家i∈N, 都有xi(l)∈Oi(x(l)), l=t-τ+1, t-τ+2, …, t。因此, y(t+1)=$\mathit{\boldsymbol{\widetilde M}}$y(t)=$\mathit{\boldsymbol{\widetilde M}}$δpτnb=Ccolb($\mathit{\boldsymbol{\widetilde M}}$)=δpτnb, δpτnb是系统式(4)的不动点, 即($\widetilde m$)bb=1。

证明(充分性)  假设:

$ \begin{array}{l} y(t) = x(t - \tau + 1)x(t - \tau + 2) \cdots x(t - 1)x(t) = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \ltimes _{i = 1}^n{x_i}(t - \tau + 1) \ltimes _{i = 1}^n{x_i}(t - \tau + 2) \cdots \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \ltimes _{i = 1}^n{x_i}(t) = \delta _{{p^{\tau n}}}^b \end{array} $

不是纳什均衡, 则至少存在一个玩家i, 使得xi(l)∉Oi(x(l)), l=t-τ+1, t-τ+2, …, t。因此, y(t+1)=$\mathit{\boldsymbol{\widetilde M}}$y(t)=$\mathit{\boldsymbol{\widetilde M}}$δpτnb=Ccolb($\mathit{\boldsymbol{\widetilde M}}$)≠δpτnb, 这表明δpτnb不是不动点, 即$\widetilde m$bb≠1, 矛盾。证毕。

该定理说明, 对于不带时滞的动态系统(式(4)), 纳什均衡与不动点是重合的, 则式(4)至少有一个不动点。

注2  该定理与文献[24]的不同之处主要有两点:

1) 系统不同, 本文的演化动态系统是带有时滞的。

2) 证明方法不同, 本文采用矩阵的半张量积方法。

2.3 控制器设计

本文考虑通过添加控制玩家来研究时滞演化拥塞博弈的镇定性。不失一般性, 假设玩家1~玩家m是控制玩家, 其他n-m个玩家是正常玩家, 则记$y\left( t \right)=\ltimes _{j=m+1}^{n}{{x}_{j}}\left( t \right), u\left( t \right)=\ltimes _{i=1}^{m}{{u}_{i}}\left( t \right)$。根据式(3), 引入控制玩家后, τ时滞的演化控制拥塞博弈的动态方程如下:

$ \begin{array}{*{20}{l}} {y(t + 1) = \mathit{\boldsymbol{L}}u(t - \tau + 1)y(t - \tau + 1)u(t - \tau + 2)}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} y(t - \tau + 2) \cdots u(t)y(t)} \end{array} $

(5)

其中, L=M_m+1*M_m+2*…*M_n, u(t)∈Δ_p^m。

根据命题2和命题3, 式(5)可转化为如下形式:

$ \begin{array}{*{20}{l}} {y(t + 1) = \mathit{\boldsymbol{L \boldsymbol{\varPhi} }}u(t - \tau + 1)u(t - \tau + 2) \cdots u(t)}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} y(t - \tau + 1)y(t - \tau + 2) \cdots y(t)} \end{array} $

(6)

其中, $\mathit{\boldsymbol{L \boldsymbol{\varPhi} = L}}\prod\limits_{j = 1}^{\tau - 1} {\left( {{\mathit{\boldsymbol{I}}_{{p^{jm}}}} \otimes {\mathit{\boldsymbol{W}}_{\left[ {{p^m}, {p^{j\left( {n - m} \right)}}} \right]}}} \right)} $。

令z(t)=y(t-τ+1)y(t-τ+2)…y(t), v(t)=u(t-τ+1)u(t-τ+2)…u(t), 则式(6)可转化为如下形式:

$ z(t + 1) = \mathit{\boldsymbol{\tilde L}}v(t)z(t) $

(7)

其中, $\mathit{\boldsymbol{\widetilde L}}$=(Ip(τ-1)(n-m)⊗LΦ)W[pτn, p(τ-1)(n-m)](Ip(τ-1)m+n⊗Op(τ-1)(n-m)R)。

引理2  对于式(7), 状态δpτnj从状态δpτni可达的充要条件为Ccolb($\mathit{\boldsymbol{\widetilde L}}$)=δpτ(n-m)j[25]。

在设计开环控制和状态反馈控制时, 使系统中的所有状态全局镇定到纳什均衡点集, 记为Ω。由于时滞演化拥塞博弈至少有一个纳什均衡, 因此将每一个纳什均衡点δpτnj分解成δpmi1δpn-mk1δpmi2δpn-mk2…δpmiτδpn-mkτ, 对任意给定的初始状态δpτ(n-m)l, 选取任意的控制δpmi1δpmi2…δpmiτ=δpτmi∈Δpτm, 只要保证z(t+1)=δpτ(n-m)k=δpn-mk1δpn-mk2…δpn-mkτ即可。时滞演化拥塞博弈经过有限次演化之后, 不论初始状态是什么, 所有状态最终定会进入不动点或简单极限环。为了使式(7)中的所有状态全局镇定到纳什均衡, 只需对简单极限环中的局势施加控制即可。鉴于极限环的特点, 控制极限环中的一个局势即可。

考虑时滞演化拥塞博弈的开环控制, 给出以下定理:

定理2  式(7)中的所有状态全局镇定到纳什均衡, 当且仅当存在控制v(t), 使得对极限环中的任意初始状态z(t)=δpτ(n-m)l时, 有如下公式:

$ {C_{{\rm{col}}{\kern 1pt} l}}(\mathit{\boldsymbol{\tilde L}}v(t)) \in {\varOmega _1} $

(8)

其中, Ω1={δpτ(n-m)k|δpmiδpτ(n-m)k=δpτnj∈Ω}。

证明  由式(7)可知, 对极限环中的任意初始状z(t)=δpτ(n-m)l, 通过设计控制v(t), 使得z(t+1)∈Ω1。z(t+1)∈Ω1与Ccoll($\mathit{\boldsymbol{\widetilde L}}$v(t))∈Ω1是等价的。证毕。

在设计状态反馈控制v(t)=Kz(t)时, 使得博弈演化过程中的所有状态全局镇定到纳什均衡。将式(7)转化为如下形式:

$ z(t + 1) = \mathit{\boldsymbol{\tilde L}}z(t)v(t) $

(9)

其中, $\mathit{\boldsymbol{\overline L}} = \mathit{\boldsymbol{\widetilde L}}{\mathit{\boldsymbol{W}}_{\left[ {{p^{\tau \left( {n - m} \right)}}, {p^{\tau m}}} \right]}}$。

记Ω1的γ步可达集为Eγ(Ω1), 定义一步可达集E(Ω1)={δpτ(n-m)i|col(Ω1)⊂col(${\mathit{\boldsymbol{\overline L}} _i}$), i=1, 2, …, pτ(n-m)。

定理3  式(9)能够通过状态反馈控制全局镇定到纳什均衡, 当且仅当存在一个逻辑矩阵K和一个整数γ≥1, 使得:

$ {C_{{\rm{col}}}}({(\mathit{\boldsymbol{\bar L}}({\mathit{\boldsymbol{I}}_{{p^{\tau (n - m)}}}} \otimes \mathit{\boldsymbol{K}})\mathit{\boldsymbol{O}}_{{p^{\tau (n - m)}}}^R)^\gamma }) \in {\varOmega _1} $

(10)

证明(充分性)  假设式(10)成立, 通过构建状态反馈控制使得式(9)全局镇定到纳什均衡。将$\mathit{\boldsymbol{\overline L}} $分为p^τ(n-m)块$\mathit{\boldsymbol{\overline L}} $₁, $\mathit{\boldsymbol{\overline L}} $₂, …, $\mathit{\boldsymbol{\overline L}} $_p^τ(n-m), $\mathit{\boldsymbol{\overline L}} $_i∈$\mathcal{L}$_{p^τ(n-m)×p^τm}。

假设:

$ \overline {{E_w}({\varOmega _1})} = {E_w}({\varOmega _1})\backslash {E_{w - 1}}({\varOmega _1}),w = 1,2, \cdots ,\gamma $

(11)

其中, $\overline {{E_0}\left( {{\mathit{\Omega }_\mathit{1}}} \right)} = {\mathit{\Omega }_\mathit{1}}$。

记K=[δpτmα1, δpτmα2, …, δpτmαpτ(n-m)]∈$\mathcal{L}$pτm×pτ(n-m), 当δpτ(n-m)Λ∈Ω1时, 有Ccoli($\mathit{\boldsymbol{\overline L}} $Λ)∈Ω1, i=1, 2, …, pτm, 因此, αΛ列所选的控制是δpτmi, i=1, 2, …, pτm。当δpτ(n-m)Λ∉Ω1时, 一定存在唯一的$\overline {{E_w}\left( {{\mathit{\Omega }_1}} \right)} $使得δpτ(n-m)Λ∈$\overline {{E_w}\left( {{\mathit{\Omega }_1}} \right)} $, w=1, 2, …, γ, 则有Ccoli($\mathit{\boldsymbol{\overline L}} $Λ)∈ $\overline {{E_{w - 1}}\left( {{\mathit{\Omega }_1}} \right)} $, i=1, 2, …, pτm, αΛ列所选的控制为δpτmi, i=1, 2, …, pτm, Λ=1, 2, …, pτ(n-m), 构建的状态反馈控制矩阵为K=[δpτmα1, δpτmα2, …, δpτmαpτ(n-m)]。

在控制v(t)=Kz(t)下, 对任意给定的初始状态z(t), 有z(t+1)∈Ω₁, 因此, 式(9)能够通过状态反馈控制全局镇定到纳什均衡。

证明(必要性)  假设式(9)能够通过状态反馈控制v(t)=Kz(t), K∈$\mathcal{L}$_{p^τm×p^τ(n-m)}全局镇定到纳什均衡, 则式(9)和控制v(t)=Kz(t)变成如下形式:

$ z(t + 1) = \mathit{\boldsymbol{\bar L}}z(t)\mathit{\boldsymbol{K}}z(t) = \mathit{\boldsymbol{\bar L}}({\mathit{\boldsymbol{I}}_{{p^{\tau (n - m)}}}} \otimes \mathit{\boldsymbol{K}})\mathit{\boldsymbol{O}}_{{p^{\tau (n - m)}}}^Rz(t) $

(12)

对任意给定的初始状态z(t), 在控制v(t)=Kz(t)下, 有z(t+1)∈Ω₁, 且z(t+1)∈Ω₁与C_col(${\left( {\mathit{\boldsymbol{\overline L}} \left( {{\mathit{\boldsymbol{I}}_{{p^{\tau \left( {n - m} \right)}}}} \otimes \mathit{\boldsymbol{K}}} \right)K_{{p^{\tau \left( {n - m} \right)}}}^R} \right)^\gamma }$)∈Ω₁是等价的。证毕。

注3  定理3给出了状态反馈控制矩阵的设计过程。

3 算例分析

例1  考虑交通系统中的时滞演化拥塞博弈。令N={1, 2, 3}表示3个玩家(即3辆大货车), P={1, 2}表示2个资源(即2条路)。3辆货车同时从A点运货到B点, 并且共享2条路, 可以看出, 选同一条路的货车数越多, 每一辆货车花费的时间就越多。根据式(1), 设所有资源的花费为Ξ=10131551223。

假设τ=2, 记x(t)=x₁(t)x₂(t)x₃(t), y(t)=x(t-1)x(t), 则采用时间并联型的短视最优响应得到局势演化方程的代数形式如下:

$ y(t + 1) = \mathit{\boldsymbol{\tilde M}}y(t) $

其中, $\mathit{\boldsymbol{\widetilde M}}$=δ₆₄[8, 16, 24, 32, 40, 48, 56, 64, 8, 16, 24, 28, 40, 46, 56, 58, 8, 16, 24, 28, 40, 48, 55, 59, 8, 12, 20, 28, 40, 42, 51, 57, 8, 16, 24, 32, 40, 46, 55, 61, 8, 14, 24, 26, 38, 46, 53, 57, 8, 16, 23, 27, 39, 45, 55, 57, 8, 10, 19, 25, 37, 41, 49, 57]。

由$\mathit{\boldsymbol{\widetilde M}}$得到时滞演化拥塞博弈的不动点集合Ω={δ₆₄²⁸, δ₆₄⁴⁶, δ₆₄⁵⁵}以及长度为3的简单极限环{δ₆₄⁸, δ₆₄⁵⁷, δ₆₄⁶⁴}、{δ₆₄¹⁰, δ₆₄¹⁶, δ₆₄⁵⁸}、{δ₆₄¹⁹, δ₆₄²⁴, δ₆₄⁵⁹}、{δ₆₄³⁷, δ₆₄⁴⁰, δ₆₄⁶¹}。其他所有状态3步演化到不动点或者3步演化到简单极限环。

为了使所有的状态全部演化到不动点集合Ω, 需要设计控制器。假设玩家1是控制玩家, 则局势控制演化方程的代数形式如下:

$ z(t + 1) = \mathit{\boldsymbol{\tilde L}}v(t)z(t) $

其中, z(t)=y(t-1)y(t), v(t)=u(t-1)u(t), $\mathit{\boldsymbol{\tilde L}}$=δ₁₆[4, 8, 12, 16, 4, 8, 12, 16, 4, 8, 12, 16, 4, 8, 12, 16, 4, 8, 12, 16, 4, 6, 12, 14, 4, 8, 11, 15, 4, 6, 11, 13, 4, 8, 12, 16, 4, 6, 12, 14, 4, 8, 11, 15, 4, 6, 11, 13, 4, 6, 11, 13, 2, 6, 9, 13, 3, 5, 11, 13, 1, 5, 9, 13]。

在考虑开环控制时, 将不动点局势进行分解, 则可选的控制有{δ₄¹, δ₄², δ₄³, δ₄⁴}、Ω₁={δ₁₆⁶, δ₁₆¹¹, δ₁₆¹⁶}。由定理2可知, 当环中的初始状态为z(t)∈{δ₁₆⁴, δ₁₆⁸, δ₁₆¹²}时, 取控制v(t)=δ₄¹, 有col_l($\mathit{\boldsymbol{\tilde L}}$v(t))∈Ω₁, l=4, 8, 12。当环中的初始状态z(t)∈{δ₁₆¹⁴, δ₁₆¹⁵}, 取控制为v(t)=δ₄²或v(t)=δ₄³, 有C_coll($\mathit{\boldsymbol{\tilde L}}$v(t))∈Ω₁, l=14, 15。综上, 对于博弈中的所有初始状态都能全局镇定到纳什均衡。

然后设计状态反馈控制v(t)=Kz(t), K=[δ₄^α₁, δ₄^α₂, …, δ₄^α₁₆]。由式(9)可得:

$ \begin{array}{l} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \mathit{\boldsymbol{\bar L}} = [4,4,4,4,8,8,8,6,12,12,12,11,16,16,\\ \begin{array}{*{20}{l}} {16,13,4,4,4,2,8,6,6,6,12,12,12,9,16,14,14,13,}\\ {4,4,4,3,8,8,8,5,12,11,11,11,16,15,15,13,4,4,}\\ {\left. {4,1,8,6,6,5,12,11,11,9,16,13,13,13} \right]}。\end{array} \end{array} $

由定理3, 将$\mathit{\boldsymbol{\overline L}} $分为如下16块:

$ \begin{array}{*{20}{l}} {{{\mathit{\boldsymbol{\bar L}}}_1} = {\delta _{16}}[4,4,4,4],{{\mathit{\boldsymbol{\bar L}}}_2} = {\delta _{16}}[8,8,8,6]}\\ {{{\mathit{\boldsymbol{\bar L}}}_3} = {\delta _{16}}[12,12,12,11],{{\mathit{\boldsymbol{\bar L}}}_4} = {\delta _{16}}[16,16,16,13]}\\ {{{\mathit{\boldsymbol{\bar L}}}_5} = {\delta _{16}}[4,4,4,2],{{\mathit{\boldsymbol{\bar L}}}_6} = {\delta _{16}}[8,6,6,6]}\\ {{{\mathit{\boldsymbol{\bar L}}}_7} = {\delta _{16}}[12,12,12,9],{{\mathit{\boldsymbol{\bar L}}}_8} = {\delta _{16}}[16,14,14,13]}\\ {{{\mathit{\boldsymbol{\bar L}}}_9} = {\delta _{16}}[4,4,4,3],{{\mathit{\boldsymbol{\bar L}}}_{10}} = {\delta _{16}}[8,8,8,5]}\\ {{{\mathit{\boldsymbol{\bar L}}}_{11}} = {\delta _{16}}[12,11,11,11],{{\mathit{\boldsymbol{\bar L}}}_{12}} = {\delta _{16}}[16,15,15,13]}\\ {{{\mathit{\boldsymbol{\bar L}}}_{13}} = {\delta _{16}}[4,4,4,1],{{\mathit{\boldsymbol{\bar L}}}_{14}} = {\delta _{16}}[8,6,6,5]}\\ {{{\mathit{\boldsymbol{\bar L}}}_{15}} = {\delta _{16}}[12,11,11,9],{{\mathit{\boldsymbol{\bar L}}}_{16}} = {\delta _{16}}[16,13,13,13]} \end{array} $

对于{δ₁₆⁶, δ₁₆¹¹, δ₁₆¹⁶}∈Ω₁, 可以得到C_coli($\mathit{\boldsymbol{\overline L}} $₆)∈Ω₁, i=2, 3, 4, C_coli($\mathit{\boldsymbol{\overline L}} $₁₁)∈Ω₁, i=2, 3, 4, C_col1($\mathit{\boldsymbol{\overline L}} $₁₆)∈Ω₁, 因此, α₆和α₁₁列可选的控制是δ₄²、δ₄³、δ₄⁴, α₁₆列可选的控制是δ₄¹。

对于{δ₁₆¹, δ₁₆², δ₁₆³, δ₁₆⁴, δ₁₆⁵, δ₁₆⁷, δ₁₆⁸, δ₁₆⁹, δ₁₆¹⁰, δ₁₆¹², δ₁₆¹³, δ₁₆¹⁴, δ₁₆¹⁵}∉Ω₁, 根据式(14)可得如下公式:

$ \begin{array}{l} \overline {{E_1}({\varOmega _1})} = {E_1}({\varOmega _1})\backslash {\varOmega _1} = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \{ \delta _{16}^2,\delta _{16}^3,\delta _{16}^4,\delta _{16}^8,\delta _{16}^{14},\delta _{16}^{15},\delta _{16}^{12}\} \\ \overline {{E_2}({\varOmega _1})} = {E_2}({\varOmega _1})\backslash {E_1}({\varOmega _1}) = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \{ \delta _{16}^1,\delta _{16}^5,\delta _{16}^7,\delta _{16}^9,\delta _{16}^{10},\delta _{16}^{13}\} \end{array} $

此时有:

$ \begin{array}{l} {C_{{\rm{col}}{\kern 1pt} {\rm{4}}}}({{\mathit{\boldsymbol{\bar L}}}_2}) \in \overline {{E_0}({\Omega _1})} \\ {C_{{\rm{col}}{\kern 1pt} {\rm{4}}}}({{\mathit{\boldsymbol{\bar L}}}_3}) \in \overline {{E_0}({\Omega _1})} \\ \begin{array}{*{20}{l}} {{C_{{\rm{ col}}{\kern 1pt} {\kern 1pt} i}}({{\mathit{\boldsymbol{\bar L}}}_4}) \in \overline {{E_0}({\Omega _1})} ,i = 1,2,3}\\ {{C_{{\rm{col}}{\kern 1pt} {\rm{1}}}}({{\mathit{\boldsymbol{\bar L}}}_8}) \in \overline {{E_0}({\Omega _1})} }\\ {{C_{{\rm{col}}{\kern 1pt} {\rm{1}}}}({{\mathit{\boldsymbol{\bar L}}}_{12}}) \in \overline {{E_0}({\Omega _1})} } \end{array}\\ \begin{array}{*{20}{l}} {{C_{{\rm{ col}}{\kern 1pt} {\kern 1pt} i}}({{\mathit{\boldsymbol{\bar L}}}_{14}}) \in \overline {{E_0}({\Omega _1})} ,i = 2,3}\\ {{C_{{\rm{ col}}{\kern 1pt} {\kern 1pt} i}}({{\mathit{\boldsymbol{\bar L}}}_{15}}) \in \overline {{E_0}({\Omega _1})} ,i = 2,3}\\ {{C_{{\rm{ col}}{\kern 1pt} {\kern 1pt} i}}({{\mathit{\boldsymbol{\bar L}}}_1}) \in \overline {{E_1}({\Omega _1})} ,i = 1,2,3,4} \end{array}\\ \begin{array}{*{20}{l}} {{C_{{\rm{col}}{\kern 1pt} {\rm{4}}}}({{\mathit{\boldsymbol{\bar L}}}_5}) \in \overline {{E_1}({\Omega _1})} }\\ {{C_{{\rm{ col}}{\kern 1pt} {\kern 1pt} i}}({{\mathit{\boldsymbol{\bar L}}}_7}) \in \overline {{E_1}({\Omega _1})} ,i = 1,2,3}\\ {{C_{{\rm{col}}{\kern 1pt} {\rm{4}}}}({{\mathit{\boldsymbol{\bar L}}}_9}) \in \overline {{E_1}({\Omega _1})} }\\ {{C_{{\rm{ col}}{\kern 1pt} {\kern 1pt} i}}({{\mathit{\boldsymbol{\bar L}}}_{10}}) \in \overline {{E_1}({\Omega _1})} ,i = 1,2,3}\\ {{C_{{\rm{ col}}{\kern 1pt} {\kern 1pt} i}}({{\mathit{\boldsymbol{\bar L}}}_{13}}) \in \overline {{E_1}({\Omega _1})} ,i = 1,2,3} \end{array} \end{array} $

因此, α₂、α₃、α₅、α₉列可选的控制是δ₄⁴, α₈、α₁₂列可选的控制是δ₄¹, α₁₄、α₁₅列可选的控制是δ₄²和δ₄³, α₄、α₇、α₁₀、α₁₃列可选的控制是δ₄¹、δ₄²、δ₄³, α₁列可选的控制是δ₄¹、δ₄²、δ₄³、δ₄⁴, 具体镇定过程如图 1所示。

任取K=[δ₄¹, δ₄⁴, δ₄⁴, δ₄², δ₄⁴, δ₄², δ₄³, δ₄¹, δ₄⁴, δ₄³, δ₄³, δ₄¹, δ₄³, δ₄², δ₄³, δ₄¹], 由式(12)可得下式:

$ \begin{array}{*{20}{l}} {z(t + 1) = {{[\mathit{\boldsymbol{\bar L}}({\mathit{\boldsymbol{I}}_{16}} \otimes \mathit{\boldsymbol{K}})\mathit{\boldsymbol{O}}_{16}^R]}^2}z(t) = }\\ {[16,6,11,16,6,6,16,16,11,16,11,16,16,6,11,16]z(t)} \end{array} $

可以看出, 在状态反馈控制下, 时滞拥塞博弈的所有初始状态都演化到不动点Ω₁, 即时滞演化拥塞博弈全局镇定到纳什均衡。

4 结束语

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