论文部分内容阅读
摘要:网络无处不在,遍及人类社会的各个领域,网络演化博弈也广泛应用于基因调控、图着色、有限自动机、模糊控制等领域。要讨论合作的涌现,必须涉及相当数量的个体(局中人),而且合理地认为这些局中人以及他们之间的关系构成一个复杂网络,随着时间的演化,每个局中人都在和他的邻居进行博弈,这就称为演化网络博弈,它的定义可以表述为:
(1)数量N→∞的局中人位于一个复杂网络上。
(2)每个时间演化步,按一定法则选取的一部分局中人以一定频率匹配进行博弈。
(3)局中人采取的对策可以按一定法则更新,所有局中人的策略更新法则相同。这种法则称为“策略的策略”。然而,法则更新比博弈频率慢得多,使得局中人可以根据上一次更新对策成功与否选择、调整下一次的更新。
(4)局中人可以感知环境、吸取信息,然后根据自己的经验和信念,在策略更新法则下更新策略。
(5)策略更新法则可能受到局中人所在网络拓扑结构的影响。
我们将逻辑动态系统与布尔网络建立联系,一个布尔网络可以用一个网络图来描述,结点1,2,......,k在每个时刻t可取不同的逻辑值,每个结点在t+1时刻的值是它的邻域结果在t时刻值的一个逻辑函数。
本文的主要目的是运用矩阵的半张量积、布尔网络、k值网络等网络演化博弈的有关知识,来对一些简单网络图进行建模,运用逻辑动态系统,找到矩阵L,使得每个玩家利用邻域信息来更新策略,最后用逻辑函数形式进行表达。
关键词:网络演化博弈 半张量积 布尔网络 k值网络 动态方程 逻辑形式 逻辑算子
二、预备知识
首先列出本文中用到的记号:
下面对半张量积进行定义:
定义一:两个矩阵的半张量积定义为:
,其中t为n,的最小公倍数。
注1:
由于半张量积保留了大部分矩阵的良好性质,因此本文在不做特殊说明的情况下,将省略半张量积符号。
引理一:设,则存在唯一的逻辑矩阵,使得在向量形式下,,這里称为的结构矩阵。
三、主要结果
3.1 问题描述
网络演化博弈的演化过程,通常由演化方程给出,常用的演化方程如下:
(3.11)
称之为局势演化方程,这一系统由所有玩家的策略演化方程组成,其意义是:居中玩家下一时刻的策略仅依赖于当前时刻的策略。
考虑单个网络演化方程的具体表现形式为: (3.12)
其中为函数fi的结构矩阵,利用矩阵的半张量积,在式(3.11)中给出的局势演化方程系统可以表示为: (3.13)
其中 (3.14)
,,
,
综上所述,每一局势演化方程均可以由逻辑形式转化为代数形式,每个玩家的策略演化方程都有其相应的结构矩阵;本文主要是利用矩阵半张量积的方法,研究代数形式的网络演化方程,并转化为基于逻辑变量的逻辑运算形式的演化方程。
3.2动态网络演化博弈由矩阵形式转化为逻辑形式
3.2.1布尔网络相关研究
考虑逻辑变量个数为2时的网络演化方程,即基于布尔网络演化博弈的演化方程,对其自矩阵形式到逻辑运算形式进行研究。
首先对于逻辑变量与二维向量进行如下等价变换:
(3.21)
使得常用二元逻辑算子:均能够与矩阵进行一一对应,从而能够定义该算子的结构矩阵:
其中:,
,,, (3.22)
利用上述结构矩阵建立二元矩阵运算与逻辑运算之间的等价关系:,,,,(3.23)
根据二间的等价关系,表为个结点的布尔网络在向量形式下的动态演化方程:
(3.24)
即(3.25)
其中: ,,,。
基于以上运算间的关系,本部分下面研究两种形式(矩阵形式与逻辑运算)转化算法:
(一)直接法:
1.考虑n=2时,网络演化方程的代数形式等价于 (3.26)
其中,,
;
结构矩阵的列向量与结构矩阵的列向量对应关系如下:
基于上述表格,在已知的情况下,返回得到的矩阵信息,利用式(3.22)(3.23)给出的矩阵运算和逻辑运算间的等价关系,结合得到的结构矩阵,求得n=2时演化方程的逻辑形式。
2.考虑n>2时布尔网络演化方程代数形式
此时由布尔网络动态演化方程的代数形式(同上(3.24)(3.25)式),由数学归纳法不难得到:令,则有:
(3.27)
重复进行1.中所述过程,进一步得到从而可以得到演化方程组的代数形式;为了便于n>2时该演化方程逻辑形式进行求解,本文不加证明地给出两者间的转化引理:
引理二:设为一个逻辑函数,若f的结构矩阵为Nf,其代数形式为,则可表为,
N1N2分别为f1,f2的结构矩阵。
重复运用引理一,结合矩阵运算与逻辑运算间的等价关系,从而实现布尔网络演化方程由代数形式到逻辑形式的转化。
(二)公式法:
下面n=2以为例,给出由结构矩阵N返回N1N2到的引理(即公式):
引理三:
(3.28)
且满足该公式i1i2的是唯一的。
在n>2时,重复利用引理二,得到结构矩阵,同样的结合引理一得到布尔网络动态方程的逻辑形式。
3.2.2 对于值逻辑动态网络研究
相应于布尔网络逻辑变量的两种取值,当逻辑变量的取值不是非此即彼时,考虑种取值状态下,对其代数形式进行研究。
基于对于值逻辑网络研究,首先定义k值逻辑变量与向量之间的等价变换: (3.29)
使得逻辑算子能与矩阵一一对应,从而得到不同算子的结构矩阵。
定义(二) i-转移(算子)“”:,
结构矩阵
考虑将k值逻辑网络的代数形式转化为逻辑形式,需运用以下定理:
定理:设为某一逻辑变量yi的逻辑函数,,f的结构矩阵,对Nf分块:,则,且逻辑函数的结构矩阵为。
重复运用以上定理,研究k值逻辑变量的逻辑形式,使得最终返回到该动态网络演化方程的逻辑形式。
基于对以上相关网络不同形式转化的研究,针对所给代数矩阵L,在博弈中使得每个玩家能够利用邻域信息来更新策略,最后由布尔网络及k值网络的动力学代数方程返回到逻辑函数形式以进行表达。
参考文献
【1】孟敏;基于半张量积的逻辑网络的理论与应用[D];山东大学;2015年
【2】王丽庆;基于半张量积的概率布尔网络相关问题研究[D];浙江师范大学;2018年
(1)数量N→∞的局中人位于一个复杂网络上。
(2)每个时间演化步,按一定法则选取的一部分局中人以一定频率匹配进行博弈。
(3)局中人采取的对策可以按一定法则更新,所有局中人的策略更新法则相同。这种法则称为“策略的策略”。然而,法则更新比博弈频率慢得多,使得局中人可以根据上一次更新对策成功与否选择、调整下一次的更新。
(4)局中人可以感知环境、吸取信息,然后根据自己的经验和信念,在策略更新法则下更新策略。
(5)策略更新法则可能受到局中人所在网络拓扑结构的影响。
我们将逻辑动态系统与布尔网络建立联系,一个布尔网络可以用一个网络图来描述,结点1,2,......,k在每个时刻t可取不同的逻辑值,每个结点在t+1时刻的值是它的邻域结果在t时刻值的一个逻辑函数。
本文的主要目的是运用矩阵的半张量积、布尔网络、k值网络等网络演化博弈的有关知识,来对一些简单网络图进行建模,运用逻辑动态系统,找到矩阵L,使得每个玩家利用邻域信息来更新策略,最后用逻辑函数形式进行表达。
关键词:网络演化博弈 半张量积 布尔网络 k值网络 动态方程 逻辑形式 逻辑算子
二、预备知识
首先列出本文中用到的记号:
下面对半张量积进行定义:
定义一:两个矩阵的半张量积定义为:
,其中t为n,的最小公倍数。
注1:
由于半张量积保留了大部分矩阵的良好性质,因此本文在不做特殊说明的情况下,将省略半张量积符号。
引理一:设,则存在唯一的逻辑矩阵,使得在向量形式下,,這里称为的结构矩阵。
三、主要结果
3.1 问题描述
网络演化博弈的演化过程,通常由演化方程给出,常用的演化方程如下:
(3.11)
称之为局势演化方程,这一系统由所有玩家的策略演化方程组成,其意义是:居中玩家下一时刻的策略仅依赖于当前时刻的策略。
考虑单个网络演化方程的具体表现形式为: (3.12)
其中为函数fi的结构矩阵,利用矩阵的半张量积,在式(3.11)中给出的局势演化方程系统可以表示为: (3.13)
其中 (3.14)
,,
,
综上所述,每一局势演化方程均可以由逻辑形式转化为代数形式,每个玩家的策略演化方程都有其相应的结构矩阵;本文主要是利用矩阵半张量积的方法,研究代数形式的网络演化方程,并转化为基于逻辑变量的逻辑运算形式的演化方程。
3.2动态网络演化博弈由矩阵形式转化为逻辑形式
3.2.1布尔网络相关研究
考虑逻辑变量个数为2时的网络演化方程,即基于布尔网络演化博弈的演化方程,对其自矩阵形式到逻辑运算形式进行研究。
首先对于逻辑变量与二维向量进行如下等价变换:
(3.21)
使得常用二元逻辑算子:均能够与矩阵进行一一对应,从而能够定义该算子的结构矩阵:
其中:,
,,, (3.22)
利用上述结构矩阵建立二元矩阵运算与逻辑运算之间的等价关系:,,,,(3.23)
根据二间的等价关系,表为个结点的布尔网络在向量形式下的动态演化方程:
(3.24)
即(3.25)
其中: ,,,。
基于以上运算间的关系,本部分下面研究两种形式(矩阵形式与逻辑运算)转化算法:
(一)直接法:
1.考虑n=2时,网络演化方程的代数形式等价于 (3.26)
其中,,
;
结构矩阵的列向量与结构矩阵的列向量对应关系如下:
基于上述表格,在已知的情况下,返回得到的矩阵信息,利用式(3.22)(3.23)给出的矩阵运算和逻辑运算间的等价关系,结合得到的结构矩阵,求得n=2时演化方程的逻辑形式。
2.考虑n>2时布尔网络演化方程代数形式
此时由布尔网络动态演化方程的代数形式(同上(3.24)(3.25)式),由数学归纳法不难得到:令,则有:
(3.27)
重复进行1.中所述过程,进一步得到从而可以得到演化方程组的代数形式;为了便于n>2时该演化方程逻辑形式进行求解,本文不加证明地给出两者间的转化引理:
引理二:设为一个逻辑函数,若f的结构矩阵为Nf,其代数形式为,则可表为,
N1N2分别为f1,f2的结构矩阵。
重复运用引理一,结合矩阵运算与逻辑运算间的等价关系,从而实现布尔网络演化方程由代数形式到逻辑形式的转化。
(二)公式法:
下面n=2以为例,给出由结构矩阵N返回N1N2到的引理(即公式):
引理三:
(3.28)
且满足该公式i1i2的是唯一的。
在n>2时,重复利用引理二,得到结构矩阵,同样的结合引理一得到布尔网络动态方程的逻辑形式。
3.2.2 对于值逻辑动态网络研究
相应于布尔网络逻辑变量的两种取值,当逻辑变量的取值不是非此即彼时,考虑种取值状态下,对其代数形式进行研究。
基于对于值逻辑网络研究,首先定义k值逻辑变量与向量之间的等价变换: (3.29)
使得逻辑算子能与矩阵一一对应,从而得到不同算子的结构矩阵。
定义(二) i-转移(算子)“”:,
结构矩阵
考虑将k值逻辑网络的代数形式转化为逻辑形式,需运用以下定理:
定理:设为某一逻辑变量yi的逻辑函数,,f的结构矩阵,对Nf分块:,则,且逻辑函数的结构矩阵为。
重复运用以上定理,研究k值逻辑变量的逻辑形式,使得最终返回到该动态网络演化方程的逻辑形式。
基于对以上相关网络不同形式转化的研究,针对所给代数矩阵L,在博弈中使得每个玩家能够利用邻域信息来更新策略,最后由布尔网络及k值网络的动力学代数方程返回到逻辑函数形式以进行表达。
参考文献
【1】孟敏;基于半张量积的逻辑网络的理论与应用[D];山东大学;2015年
【2】王丽庆;基于半张量积的概率布尔网络相关问题研究[D];浙江师范大学;2018年