網(wǎng)絡(luò)演化博弈的邏輯形式

張淑婷 蔣夢(mèng)涵

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

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

（2）每個(gè)時(shí)間演化步，按一定法則選取的一部分局中人以一定頻率匹配進(jìn)行博弈。

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

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

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

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

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

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

二、預(yù)備知識(shí)

首先列出本文中用到的記號(hào)：

下面對(duì)半張量積進(jìn)行定義：

定義一：兩個(gè)矩陣的半張量積定義為：

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

注1：

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

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

三、主要結(jié)果

3.1 問題描述

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

（3.11）

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

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

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

其中 （3.14）

，，

，

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

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

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

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

首先對(duì)于邏輯變量與二維向量進(jìn)行如下等價(jià)變換：

（3.21）

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

其中：，

，，， （3.22）

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

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

（3.24）

即（3.25）

其中： ，，，。

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

（一）直接法：

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

其中，，

;

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

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

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

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

（3.27）

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

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

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

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

（二）公式法：

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

引理三：

（3.28）

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

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

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