網絡演化博弈的邏輯形式

張淑婷 蔣夢涵

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

（1）數量N→∞的局中人位于一個復雜網絡上。

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

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

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

（5）策略更新法則可能受到局中人所在網絡拓撲結構的影響。

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

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

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

二、預備知識

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

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

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

，其中t為n，的最小公倍數。

注1：

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

引理一：設，則存在唯一的邏輯矩陣，使得在向量形式下，，這里稱為的結構矩陣。

三、主要結果

3.1 問題描述

網絡演化博弈的演化過程，通常由演化方程給出，常用的演化方程如下：

（3.11）

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

考慮單個網絡演化方程的具體表現形式為： （3.12）

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

其中 （3.14）

，，

，

綜上所述，每一局勢演化方程均可以由邏輯形式轉化為代數形式，每個玩家的策略演化方程都有其相應的結構矩陣;本文主要是利用矩陣半張量積的方法，研究代數形式的網絡演化方程，并轉化為基于邏輯變量的邏輯運算形式的演化方程。

3.2動態(tài)網絡演化博弈由矩陣形式轉化為邏輯形式

3.2.1布爾網絡相關研究

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

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

（3.21）

使得常用二元邏輯算子：均能夠與矩陣進行一一對應，從而能夠定義該算子的結構矩陣：

其中：，

，，， （3.22）

利用上述結構矩陣建立二元矩陣運算與邏輯運算之間的等價關系：，，，，（3.23）

根據二間的等價關系，表為個結點的布爾網絡在向量形式下的動態(tài)演化方程：

（3.24）

即（3.25）

其中： ，，，。

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

（一）直接法：

1.考慮n=2時，網絡演化方程的代數形式等價于 （3.26）

其中，，

;

結構矩陣的列向量與結構矩陣的列向量對應關系如下：

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

2.考慮n>2時布爾網絡演化方程代數形式

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

（3.27）

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

引理二：設為一個邏輯函數，若f的結構矩陣為Nf，其代數形式為，則可表為，

N1N2分別為f1，f2的結構矩陣。

重復運用引理一，結合矩陣運算與邏輯運算間的等價關系，從而實現布爾網絡演化方程由代數形式到邏輯形式的轉化。

（二）公式法：

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

引理三：

（3.28）

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

在n>2時，重復利用引理二，得到結構矩陣，同樣的結合引理一得到布爾網絡動態(tài)方程的邏輯形式。

3.2.2 對于值邏輯動態(tài)網絡研究

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

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

使得邏輯算子能與矩陣一一對應，從而得到不同算子的結構矩陣。

定義（二） ?i-轉移（算子）“”：，

結構矩陣

考慮將k值邏輯網絡的代數形式轉化為邏輯形式，需運用以下定理：

定理：設為某一邏輯變量yi的邏輯函數，，f的結構矩陣，對Nf分塊：，則，且邏輯函數的結構矩陣為。

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

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

參考文獻

【1】孟敏;基于半張量積的邏輯網絡的理論與應用[D];山東大學;2015年

【2】王麗慶;基于半張量積的概率布爾網絡相關問題研究[D];浙江師范大學;2018年