张淑婷 蒋梦涵

摘要：网络无处不在，遍及人类社会的各个领域，网络演化博弈也广泛应用于基因调控、图着色、有限自动机、模糊控制等领域。要讨论合作的涌现，必须涉及相当数量的个体（局中人），而且合理地认为这些局中人以及他们之间的关系构成一个复杂网络，随着时间的演化，每个局中人都在和他的邻居进行博弈，这就称为演化网络博弈，它的定义可以表述为：

（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年