基于STP相关马尔可夫型演化博弈稳定性研究

李露露, 朱 睿

(合肥工业大学 数学学院,安徽 合肥 230601)

0 引 言

近年来,随着矩阵在很多领域研究中应用越来越广泛, 普通矩阵的乘法已经不能满足人们的需求。为此,文献[1-2]经过多年的研究,提出了一种新的矩阵相乘方法,即矩阵半张量积(semi-tensor product, STP),打破了传统矩阵乘法的条件限制。矩阵半张量积的产生使得布尔网络的研究有了突破性的进展,很好地解决了简单布尔网络的镇定性、稳定性以及控制等问题[3-4]。在简单布尔网络研究的基础上,利用矩阵半张量积对τ长度信息条件布尔网络的研究也取得了一系列成果[5-6]。由于布尔网络是逻辑网络中的一种形式,许多学者将矩阵半张量积推广至逻辑网络中进行研究并取得了很大的进展[7-8]。

在博弈论的有限演化博弈中,每个人可以在其策略集进行选择,许多专家在演化博弈论中应用矩阵半张量积,将其演化过程进行代数表达,得到了很多成果[8-9]。文献[8]首次利用矩阵半张量积将演化博弈进行代数表达,分别给出了其在2种不同情况下优化控制的基本结果与算法,随后许多学者研究了网络演化博弈的最优控制以及反馈控制等[10]。

李雅普诺夫函数具有的平稳性在研究动力系统的分析和控制中应用十分广泛[11]。文献[12]对一类称为马尔可夫型的有限演化博弈的稳定性和镇定问题进行研究,构造了有限集上的李雅普诺夫函数,但它只针对单个马尔可夫型演化博弈,并且下一时刻的决策只与前一时刻的决策有关。现实生活中,许多实例都是相关马尔可夫型演化博弈,如农民播撒种子数量和产量的稳定性就是息息相关的,而且农民在做下一时刻的决策时,为了使决策效益更高,往往会参考前几年的信息,即τ长度信息。根据以上讨论,本文将对带有τ长度信息的相关马尔可夫型演化博弈进行研究,给出此类型博弈决策变化的规律及其稳定性。

本文的主要贡献包括:

(1) 给出带有τ长度信息的相关马尔可夫型演化博弈的李雅普诺夫函数存在的充分必要条件,进而判断其全局稳定性。

(2) 给出了2个k-值逻辑动态系统的李雅普诺夫函数的构造算法。

1 预备知识

本节主要介绍论文中常用的记号、矩阵半张量积的定义和性质、演化博弈以及李雅普诺夫函数的概念,具体细节可参考文献[1-2]。

1.1 常用记号

设矩阵L∈Mm×n,若Col(L)⊂Δm,则称L为逻辑矩阵。

记所有m×n逻辑矩阵的集合为Lm×n。

1.2 矩阵半张量积的概念和性质

定义1[1]令A∈Mm×n,B∈Ma×b,记n和a的最小公倍数为k=lcm{n,a},则矩阵半张量积定义为:

(1)

定义2[1]换位矩阵W[m,n]∈Mmn×mn,其列是按照索引Id(i,j;m,n)排列的,行是按照索引Id(j,i;n,m)排列的,位于[(I,J),(i,j)]上元素的值为:

当m=n时,W[m,n]可简写为W[n]。

根据定义2,W[m,n]还可以写成如下形式:

(2)

(3)

定理1[1]设xi∈Δk,i=1,2,…,n,f(x1,x2,x3,…,xn)∈Δk*为一个多值逻辑(向量)函数,则存在唯一的逻辑矩阵Mf∈Lk*×kn,使得在向量形式下,有

(4)

并称Mf为f的结构矩阵。

1.3 博弈的概念和理论

定义4[12]马尔可夫型演化博弈的下一时刻的策略选择仅依赖于当前的策略,其演化方程为:

φ(x(t+1))-φ(x(t))≥0,t≥0

(5)

则称φ(x)为马尔可夫型演化博弈的李雅普诺夫函数,且当φ(x(t+1))=φ(x(t))时,有x(t)=x*。

2 主要结果

2.1 模型的建立

在现实生活中,许多事件并非独立存在,并且在演化时,所参考的信息具有一定长度,因此需要寻找和建立新的模型,即带有τ长度信息的相关马尔科夫型演化博弈进行描述。相关马尔科夫型演化博弈模型代数表示为:

(6)

其中:x(t)、y(t)为参与者t时刻策略选择;M1、M2为状态转移矩阵;W=diag{w1,w2,…,wkn}。

下面利用李雅普诺夫函数为判断其稳定性提供理论依据,并给出李雅普诺夫函数的构造算法。

2.2 模型的解决

根据定理1,李雅普诺夫函数φ(x)可表示为相应的代数形式:

其中,Vφ∈Rkn称为φ(x)的结构向量。

定理2当2个带有τ长度信息的相关演化博弈模型(6)分别具有李雅普诺夫函数φ1(x)和φ2(x),当且仅当存在整数1≤r≤kn和1≤g≤k2τn,使得下列不等式组有解。

(7)

证明对于具有τ长度信息的相关演化博弈,先将其进行变形。

将x(t),…,x(t-τ+1),y(t),…,y(t-τ+1)进行替换:

⋮

⋮

进而,当进行演化时,可得:

然后有:

(8)

于是,(8)式可变形为:

z(t+1)=Lz(t)

(9)

此时L=K1*K2*…*K2τ。

下面,用φ1(y)和φ2(z)来说明定理1的有效性。

设φ1(y)、φ2(z)的结构向量分别为Vφ1=[a1,a2,…,akn]、Vφ2=[b1,b2,…,bk2τn];y(t)、z(t)的转移矩阵分别为M2=δkn[j1,…,jkn]、L=δk2τn[i1,…,ik2τn]。

(1) 充分性。由φ1(y)和φ2(z)的代数形式可得:

φ1(y(t+1))+φ2(z(t+1))=

Vφ1M2Wx(t)+Vφ2Lz(t)=

[ai1wi1+bj1,…,aiknwikn+bj1,ai1wi1+bj2…,aiknwikn+bj2,…,ai1wi1+bjk2τn,…,aiknwikn+bjk2τn]z(t)x(t)。

于是有:

[φ1(y(t+1))+φ2(z(t+1))]-

[φ1(y(t))+φ2(z(t))]=

bj1,ai1wi1+bj2,…,aiknwikn+

bj2,…,ajknwjkn+bj2,…,ai1wi1+

(10)

[φ1(y(t+1))+φ2(z(t+1))]-

[φ1(y(t))+φ2(z(t))]=(aiqwiq+bjq)-(aqwq+bq)>0,

即

φ1(y(t+1))+φ2(z(t+1))>φ1(y(t))+φ2(z(t))。

φ1(y(t+1))+φ2(z(t+1))=φ1(y(t))+φ2(z(t))。

于是有:

因此,函数φ1(y)和φ2(z)即为满足定义5的2个李雅普诺夫函数。

φ1(y(t+1))+φ2(z(t+1))=

φ1(y(t))+φ2(z(t))。

将x(t)、z(t)代入(10)式,可得:

airwir+bjg=arwr+bg。

aiqwiq+bjq>aqwq+bq,

q=1,…,kn,q≠r;p=1,…,k2τn,p≠g。

证毕。

根据定理2,可以给出带有τ长度信息的相关演化博弈的李雅普诺夫函数φ1和φ2的构造算法。具体的计算步骤为:

(1) 计算转移矩阵M和变形后的L,并找到其唯一的不动点。

(2) 解不等式组(8),并得到一组解[bj1,…,bjk2τn],[a1,a2,…,akn]。

(3) 构造李雅普诺夫函数,其代数形式为:

φ1(y)=[a1,a2,…,akn]zx，φ2(z)=[bj1,…,bjk2τn]zx。

不等式组(7)有无穷多个解,因此相关马尔可夫型演化博弈的李雅普诺夫函数是不唯一的。

李雅普诺夫函数构造算法的复杂度会随着矩阵维数的增加而增大。当矩阵的维数非常大时,需要寻找更有效的方法来求解。

2.3 模型的应用

中国是农业大国,农民人数众多,对于农民种植来说,如何选择种子数目使收益最大至关重要。农民在决定下一年所播撒的种子数目时,会受到今年和上一年自己的收益和其他农民的收益的影响,他们会在所有策略中选择获得利益最大的策略进行播种。收益是由播撒的种子数目和产量决定,而农民能获得的产量与今年播撒的种子数目有关,而与前一年的产量无关。以参与者是2个农民为例,研究参与者的策略随时间演化的稳定性;下面将利用李雅普诺夫函数对这种稳定性进行判定。

考虑演化博弈G1和G2,G1={N,S,C},其中,N={1,2}表示参与者,即2个农民。S1={1,2}表示第1个农民的策略,即第1个农民有两个策略可以选择:1表示播撒种子2 000粒,2表示播撒种子2 500粒;S2={1,2}表示第2个农民的策略即第2个农民有两个策略可以选择:1表示播撒种子2 350粒,2表示播撒种子2 600 粒;不同策略组合下,2个农民的收益见表1所列。

表1 不同策略组合下的收益

策略更新规则使用确定型的短视最优响应[9],因此,可以得到不同局势下的最佳响应函数值,见表2所列。

表2 不同局势下的最佳响应函数值

G2为产量的博弈,收获的产量与其播种的种子数目具有一定的比率关系,即产量y(t+1)=M2Wx(t),其中W=diag{0.75, 0.85, 0.95, 0.83}。

接下来,将构造李雅普诺夫函数,判断其矩阵的不动点是2个相关演化博弈的收敛点。

x(t)x(t-1)y(t)y(t-1)=M1x(t)x(t-1)y(t)y(t-1),

x(t)x(t-1)y(t)y(t-1)=M2x(t)x(t-1)y(t)y(t-1)。

于是可得演化方程为:

x(t+1)=Mx(t)x(t-1)y(t)y(t-1)=M1*M2x(t)x(t-1)y(t)y(t-1)=

x(t)x(t-1)y(t)y(t-1)。

(11)

3 结 论

本文对一类带有τ长度信息的相关马尔可夫型演化博弈的稳定性问题进行研究,给出李雅普诺夫函数存在的充分必要条件,并利用构造算法定义2个k-值逻辑动态系统的李雅普诺夫函数,判断演化博弈的全局稳定性;最后结合具体事例,验证了理论结果的正确性。