張淑婷 蔣夢涵

摘要：網(wǎng)絡(luò)無處不在，遍及人類社會的各個領(lǐng)域，網(wǎng)絡(luò)演化博弈也廣泛應(yīng)用于基因調(diào)控、圖著色、有限自動機、模糊控制等領(lǐng)域。要討論合作的涌現(xiàn)，必須涉及相當(dāng)數(shù)量的個體（局中人），而且合理地認為這些局中人以及他們之間的關(guān)系構(gòu)成一個復(fù)雜網(wǎng)絡(luò)，隨著時間的演化，每個局中人都在和他的鄰居進行博弈，這就稱為演化網(wǎng)絡(luò)博弈，它的定義可以表述為：

（1）數(shù)量N→∞的局中人位于一個復(fù)雜網(wǎng)絡(luò)上。

（2）每個時間演化步，按一定法則選取的一部分局中人以一定頻率匹配進行博弈。

（3）局中人采取的對策可以按一定法則更新，所有局中人的策略更新法則相同。這種法則稱為“策略的策略”。然而，法則更新比博弈頻率慢得多，使得局中人可以根據(jù)上一次更新對策成功與否選擇、調(diào)整下一次的更新。

（4）局中人可以感知環(huán)境、吸取信息，然后根據(jù)自己的經(jīng)驗和信念，在策略更新法則下更新策略。

（5）策略更新法則可能受到局中人所在網(wǎng)絡(luò)拓撲結(jié)構(gòu)的影響。

我們將邏輯動態(tài)系統(tǒng)與布爾網(wǎng)絡(luò)建立聯(lián)系，一個布爾網(wǎng)絡(luò)可以用一個網(wǎng)絡(luò)圖來描述，結(jié)點1，2，......，k在每個時刻t可取不同的邏輯值，每個結(jié)點在t+1時刻的值是它的鄰域結(jié)果在t時刻值的一個邏輯函數(shù)。

本文的主要目的是運用矩陣的半張量積、布爾網(wǎng)絡(luò)、k值網(wǎng)絡(luò)等網(wǎng)絡(luò)演化博弈的有關(guān)知識，來對一些簡單網(wǎng)絡(luò)圖進行建模，運用邏輯動態(tài)系統(tǒng)，找到矩陣L，使得每個玩家利用鄰域信息來更新策略，最后用邏輯函數(shù)形式進行表達。

關(guān)鍵詞：網(wǎng)絡(luò)演化博弈 半張量積 布爾網(wǎng)絡(luò) ?k值網(wǎng)絡(luò) ?動態(tài)方程 ?邏輯形式 ?邏輯算子

二、預(yù)備知識

首先列出本文中用到的記號：

下面對半張量積進行定義：

定義一：兩個矩陣的半張量積定義為：

，其中t為n，的最小公倍數(shù)。

注1：

由于半張量積保留了大部分矩陣的良好性質(zhì)，因此本文在不做特殊說明的情況下，將省略半張量積符號。

引理一：設(shè)，則存在唯一的邏輯矩陣，使得在向量形式下，，這里稱為的結(jié)構(gòu)矩陣。

三、主要結(jié)果

3.1 問題描述

網(wǎng)絡(luò)演化博弈的演化過程，通常由演化方程給出，常用的演化方程如下：

（3.11）

稱之為局勢演化方程，這一系統(tǒng)由所有玩家的策略演化方程組成，其意義是：居中玩家下一時刻的策略僅依賴于當(dāng)前時刻的策略。

考慮單個網(wǎng)絡(luò)演化方程的具體表現(xiàn)形式為： （3.12）

其中為函數(shù)fi的結(jié)構(gòu)矩陣，利用矩陣的半張量積，在式（3.11）中給出的局勢演化方程系統(tǒng)可以表示為： （3.13）

其中 （3.14）

，，

，

綜上所述，每一局勢演化方程均可以由邏輯形式轉(zhuǎn)化為代數(shù)形式，每個玩家的策略演化方程都有其相應(yīng)的結(jié)構(gòu)矩陣;本文主要是利用矩陣半張量積的方法，研究代數(shù)形式的網(wǎng)絡(luò)演化方程，并轉(zhuǎn)化為基于邏輯變量的邏輯運算形式的演化方程。

3.2動態(tài)網(wǎng)絡(luò)演化博弈由矩陣形式轉(zhuǎn)化為邏輯形式

3.2.1布爾網(wǎng)絡(luò)相關(guān)研究

考慮邏輯變量個數(shù)為2時的網(wǎng)絡(luò)演化方程，即基于布爾網(wǎng)絡(luò)演化博弈的演化方程，對其自矩陣形式到邏輯運算形式進行研究。

首先對于邏輯變量與二維向量進行如下等價變換：

（3.21）

使得常用二元邏輯算子：均能夠與矩陣進行一一對應(yīng)，從而能夠定義該算子的結(jié)構(gòu)矩陣：

其中：，

，，， （3.22）

利用上述結(jié)構(gòu)矩陣建立二元矩陣運算與邏輯運算之間的等價關(guān)系：，，，，（3.23）

根據(jù)二間的等價關(guān)系，表為個結(jié)點的布爾網(wǎng)絡(luò)在向量形式下的動態(tài)演化方程：

（3.24）

即（3.25）

其中： ，，，。

基于以上運算間的關(guān)系，本部分下面研究兩種形式（矩陣形式與邏輯運算）轉(zhuǎn)化算法：

（一）直接法：

1.考慮n=2時，網(wǎng)絡(luò)演化方程的代數(shù)形式等價于 （3.26）

其中，，

;

結(jié)構(gòu)矩陣的列向量與結(jié)構(gòu)矩陣的列向量對應(yīng)關(guān)系如下：

基于上述表格，在已知的情況下，返回得到的矩陣信息，利用式（3.22）（3.23）給出的矩陣運算和邏輯運算間的等價關(guān)系，結(jié)合得到的結(jié)構(gòu)矩陣，求得n=2時演化方程的邏輯形式。

2.考慮n>2時布爾網(wǎng)絡(luò)演化方程代數(shù)形式

此時由布爾網(wǎng)絡(luò)動態(tài)演化方程的代數(shù)形式（同上（3.24）（3.25）式），由數(shù)學(xué)歸納法不難得到：令，則有：

（3.27）

重復(fù)進行1.中所述過程，進一步得到從而可以得到演化方程組的代數(shù)形式;為了便于n>2時該演化方程邏輯形式進行求解，本文不加證明地給出兩者間的轉(zhuǎn)化引理：

引理二：設(shè)為一個邏輯函數(shù)，若f的結(jié)構(gòu)矩陣為Nf，其代數(shù)形式為，則可表為，

N1N2分別為f1，f2的結(jié)構(gòu)矩陣。

重復(fù)運用引理一，結(jié)合矩陣運算與邏輯運算間的等價關(guān)系，從而實現(xiàn)布爾網(wǎng)絡(luò)演化方程由代數(shù)形式到邏輯形式的轉(zhuǎn)化。

（二）公式法：

下面n=2以為例，給出由結(jié)構(gòu)矩陣N返回N1N2到的引理（即公式）：

引理三：

（3.28）

且滿足該公式i1i2的是唯一的。

在n>2時，重復(fù)利用引理二，得到結(jié)構(gòu)矩陣，同樣的結(jié)合引理一得到布爾網(wǎng)絡(luò)動態(tài)方程的邏輯形式。

3.2.2 對于值邏輯動態(tài)網(wǎng)絡(luò)研究

相應(yīng)于布爾網(wǎng)絡(luò)邏輯變量的兩種取值，當(dāng)邏輯變量的取值不是非此即彼時，考慮種取值狀態(tài)下，對其代數(shù)形式進行研究。

基于對于值邏輯網(wǎng)絡(luò)研究，首先定義k值邏輯變量與向量之間的等價變換： （3.29）

使得邏輯算子能與矩陣一一對應(yīng)，從而得到不同算子的結(jié)構(gòu)矩陣。

定義（二） ?i-轉(zhuǎn)移（算子）“”：，

結(jié)構(gòu)矩陣

考慮將k值邏輯網(wǎng)絡(luò)的代數(shù)形式轉(zhuǎn)化為邏輯形式，需運用以下定理：

定理：設(shè)為某一邏輯變量yi的邏輯函數(shù)，，f的結(jié)構(gòu)矩陣，對Nf分塊：，則，且邏輯函數(shù)的結(jié)構(gòu)矩陣為。

重復(fù)運用以上定理，研究k值邏輯變量的邏輯形式，使得最終返回到該動態(tài)網(wǎng)絡(luò)演化方程的邏輯形式。

基于對以上相關(guān)網(wǎng)絡(luò)不同形式轉(zhuǎn)化的研究，針對所給代數(shù)矩陣L，在博弈中使得每個玩家能夠利用鄰域信息來更新策略，最后由布爾網(wǎng)絡(luò)及k值網(wǎng)絡(luò)的動力學(xué)代數(shù)方程返回到邏輯函數(shù)形式以進行表達。

參考文獻

【1】孟敏;基于半張量積的邏輯網(wǎng)絡(luò)的理論與應(yīng)用[D];山東大學(xué);2015年

【2】王麗慶;基于半張量積的概率布爾網(wǎng)絡(luò)相關(guān)問題研究[D];浙江師范大學(xué);2018年