基于矩陣方法的Banzhaf值的計(jì)算及應(yīng)用

夏美霞,李海濤,丁雪瑩,劉衍勝

(山東師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,山東濟(jì)南 250014)

1 引言

合作博弈描述了有限的一組玩家N可以通過合作產(chǎn)生一定的收益.在合作博弈中,單點(diǎn)解是為每個(gè)合作博弈分配一個(gè)n維的實(shí)向量的函數(shù),這個(gè)實(shí)向量表示玩家的收益分布.在過去的幾十年,對合作博弈中單點(diǎn)解的研究引起了國內(nèi)外很多學(xué)者的研究興趣.其中,Shapley值和Banzhaf值是最著名的單點(diǎn)解.Shapley值是由Shapley[1]在1953年首次提出.Banzhaf指數(shù)最初由Penrose[2]于1946年引入,后來由Banzhaf[3]于1965年引入投票博弈.在此背景下,Banzhaf指數(shù)被推廣為所有合作博弈的Banzhaf值[4].這兩種單點(diǎn)解將不同的權(quán)重與每個(gè)聯(lián)盟1聯(lián)盟[5]:設(shè)N={1,2,···,n},N中的任意一個(gè)非空子集K稱為一個(gè)聯(lián)盟,空集?為一個(gè)特殊的聯(lián)盟,因此n個(gè)玩家可以形成2n個(gè)聯(lián)盟.聯(lián)系起來,它們分配給每個(gè)玩家的收益都是玩家所屬的任何聯(lián)盟的邊際貢獻(xiàn)2邊際貢獻(xiàn)[5]:合作博弈中,對?i∈N和滿足i∈K的每個(gè)聯(lián)盟K ∈2N,i對聯(lián)盟的邊際貢獻(xiàn)為i=v(K)?v(K{i}).的平均值.Shapley值給出了每個(gè)玩家在隨機(jī)排序中形成大聯(lián)盟的預(yù)期邊際貢獻(xiàn)[6–7].Banzhaf值提供了每個(gè)參與者形成大聯(lián)盟的預(yù)期邊際貢獻(xiàn),其中每個(gè)聯(lián)盟以相同的概率形成.Dubey和Shapley[8]證明了Banzhaf值的一些數(shù)學(xué)性質(zhì).

最近,程代展教授等[9]提出了矩陣半張量積方法(semi-tensor product of matrices),并使用這種方法來研究有限靜態(tài)博弈和有限演化博弈的建模、分析與控制.矩陣半張量積方法的主要特征是將策略局勢轉(zhuǎn)換成邏輯變量,這有利于有限博弈的線性表示.在過去10年,國內(nèi)外很多學(xué)者使用這種方法研究有限博弈,建立了很多優(yōu)秀的研究結(jié)果[10–14].文獻(xiàn)[10]提出了一種用于網(wǎng)絡(luò)演化博弈的建模、分析和控制的矩陣方法.文獻(xiàn)[12]提出了一種具有多面體策略集的線性動(dòng)態(tài)博弈.此外矩陣半張量積方法也被應(yīng)用于布爾網(wǎng)絡(luò)[15–21]、布爾控制網(wǎng)絡(luò)[22–29]、自動(dòng)機(jī)理論[30–31]和移位寄存器[32]等問題的研究.關(guān)于矩陣半張量積方法的綜述,參見文獻(xiàn)[33–37].

目前Banzhaf值已經(jīng)在不同場景中得到了廣泛應(yīng)用,包括聯(lián)盟結(jié)構(gòu)[38–40]、通信情況[41]、層次關(guān)系[42]和鄰近關(guān)系[43]等.Parmigiani等[44]利用微陣列技術(shù)以產(chǎn)生大量關(guān)于人類基因表達(dá)的信息,這些數(shù)據(jù)可用于鑒定導(dǎo)致特定疾病的基因,從基因表達(dá)數(shù)據(jù)的矩陣推斷基因的相互作用以及當(dāng)生物系統(tǒng)的狀況發(fā)生變化時(shí)它們的行為.Moretti等[45]提出了一種基于聯(lián)盟博弈的基因表達(dá)分析的替代方法.該方法的主要優(yōu)點(diǎn)是可以計(jì)算稱為相關(guān)性指數(shù)的數(shù)值指數(shù),該指數(shù)可以反應(yīng)特定疾病中每個(gè)基因的相關(guān)性.需要指出的是,目前關(guān)于Banzhaf值的計(jì)算主要是直接基于定義的求解,因此很難使用計(jì)算機(jī)進(jìn)行輔助求解.

本文利用矩陣半張量積方法研究Banzhaf值計(jì)算問題,并將所得結(jié)果應(yīng)用于生物網(wǎng)絡(luò)中的遺傳疾病基因的相關(guān)性研究中.本文的主要貢獻(xiàn)是利用矩陣半張量積方法將Banzhaf值轉(zhuǎn)化成等價(jià)的代數(shù)形式,并建立了一個(gè)簡捷的計(jì)算方法.相較于定義中直接計(jì)算的方法,本文給出的方法便于使用計(jì)算機(jī)進(jìn)行輔助求解,并且適用于求解任意有限合作博弈的Banzhaf值.由于使用定義計(jì)算Banzhaf值與根據(jù)本文提出的方法計(jì)算Banzhaf值所需的計(jì)算量復(fù)雜度均為O(n2n),所以本文用一臺(tái)配置為因特爾酷睿i7–6500U 2.5 GHz CPU的電腦進(jìn)行MATLAB數(shù)值仿真時(shí),當(dāng)玩家數(shù)超過15時(shí)就無法運(yùn)行了.數(shù)值仿真表明,在MATLAB容許的玩家數(shù)范圍內(nèi),與定義相比,本文給出的計(jì)算Banzhaf值的方法所需要的MATLAB運(yùn)行時(shí)間更短.

本文的剩余部分安排如下:第2節(jié)列出了矩陣半張量積的一些必要的預(yù)備知識;第3節(jié)給出Banzhaf值的等價(jià)代數(shù)形式和計(jì)算方法;第4節(jié)將得到的結(jié)果應(yīng)用于生物遺傳疾病基因的相關(guān)性度量;第5節(jié)給出本文的結(jié)論.

下面給出本文中用到的符號:R表示實(shí)數(shù);1p=為所有p×q維邏輯矩陣的集合,···,p},其中表示單位矩陣Ip的第i列;一個(gè)n×t維邏輯矩陣M=可以簡記為M=δn·[i1i2···it];Coli(M)表示矩陣M的第i列,Col(M)表示了矩陣M的所有列組成的集合,設(shè)M則M ?N:=[Col1(M)?Col1(N)···Colr(M)?Colr(N)],其中?表示矩陣的Kronecker積.

2 預(yù)備知識

本文使用的主要數(shù)學(xué)工具為矩陣半張量積,定義如下所示.

定義1[9]給定兩個(gè)矩陣矩陣M和N的半張量積定義為

其中α為n和p的最小公倍數(shù).

注1矩陣半張量積是普通矩陣乘積的推廣,因此一般省略符號“”.

下面給出換位矩陣的定義:

定義2[9]換位矩陣W[m,n]∈Lmn×mn定義為

引理1[9]設(shè)X為兩個(gè)列向量,則有W[m,n]XY=Y X.

引理2[9]設(shè)f:Dn→D為一個(gè)邏輯映射.則存在唯一的邏輯矩陣Mf∈L2×2n使得

其中Mf稱為f的結(jié)構(gòu)矩陣.

定義3[35](有限)正規(guī)博弈G=(N,S,C)由3部分構(gòu)成,其中N={1,2,···,n}表示有n個(gè)玩家,S=稱為局勢,Si為第i個(gè)玩家的策略集,C={c1,···,cn},ci:S→為第i個(gè)玩家的收益函數(shù).

定義4[35]一個(gè)帶有可轉(zhuǎn)移效用3可轉(zhuǎn)移效用[5]:各個(gè)玩家都用相同的尺度來衡量他們的收益,并且各個(gè)聯(lián)盟的收益都可以用任何方式分配給各玩家.(transferable utility,TU)的n人合作博弈可由二元結(jié)構(gòu)(N,v)表示,其中:N={1,2,···,n}是玩家集,v:2N→為特征函數(shù)4特征函數(shù)[5]:給定N={1,2,···,n},n人合作博弈的特征函數(shù)v是從2N={K|K ?N}到實(shí)數(shù)集的映射.,滿足v(?)=0.

3 主要結(jié)果

本節(jié)給出Banzhaf值的等價(jià)代數(shù)形式和計(jì)算方法.首先回顧Banzhaf值的定義.

設(shè)K ?N,則K是一個(gè)聯(lián)盟,v(K)表示合作博弈中聯(lián)盟K的收益.記

則由式(3),可以找到v的結(jié)構(gòu)向量Mv使得

其中Mv∈

為了方便下面的計(jì)算與應(yīng)用,這里先定義一個(gè)無異議博弈.

定義5[46]一個(gè)在R?N上的無異議博弈(N,uR)定義為

Banzhaf 值提供了每個(gè)參與者形成大聯(lián)盟的預(yù)期邊際貢獻(xiàn),其中每個(gè)聯(lián)盟以相同的概率形成.下面給出Banzhaf值的定義.

定義6[4]給定合作博弈(N,v),其Banzhaf值β是一個(gè)定義在Rn上的向量:

其中:

其中i=1,2,···,n.

下面使用矩陣半張量積方法研究式(5),給出Banzhaf值的等價(jià)代數(shù)形式和計(jì)算方法.

由式(4)和換位矩陣的性質(zhì)可得

其中Mv是v的結(jié)構(gòu)向量.

由于對任意的l=1,···,n,即l∈K時(shí),本文令

其中j ∈{1,2,···,2n?1}.則對于任意的i=1,2,···,n,式(5)可表示為

其中0表示2n?i+1×2n?i維零矩陣.

容易得出

這里Ei是一個(gè)2n維列向量,i=1,2,···,n.

因此式(5)可重新表示為下式

基于以上分析,得到如下計(jì)算Banzhaf值的代數(shù)表示辦法.

定理1給定合作博弈(N,v),其中:N={1,···,n},Mv是v的結(jié)構(gòu)矩陣.則該合作博弈的Banzhaf值可計(jì)算如下:

其中

是一個(gè)2n×n維矩陣.

證由于該合作博弈的Banzhaf值為

由式(7)可得

又通過式(6),可以計(jì)算出

證畢.

例1考慮一個(gè)合作博弈(N,v),其中N={1,2,3},特征函數(shù)的結(jié)構(gòu)矩陣如下:

由式(9)可以得到式(10),因此可以計(jì)算出這個(gè)合作博弈的Banzhaf值為β(v)=MvΨ3=[18 37 1].

因此,可以計(jì)算出這個(gè)合作博弈的Banzhaf值為

例2考慮手套市場博弈[47].假設(shè)玩家集合N={1,···,n}可分為兩個(gè)互不相交的子集L和R.L中的玩家每個(gè)人有一只左手套,R中的玩家每個(gè)人有一只右手套.左右手套兩只搭配起來可以產(chǎn)生價(jià)值1美元,而單獨(dú)一只手套沒有任何價(jià)值.本文可以用n人合作博弈(N,v)來表示這個(gè)問題:v(K)=min{|L ∩K|,|R ∩K|},?K ∈2N.

假設(shè)

當(dāng)n=5時(shí),L={1,2,5},R={3,4};

當(dāng)n=6時(shí),L={2,3,5},R={1,4,6};

當(dāng)n=7時(shí),L={2,6},R={1,3,4,5,7};

當(dāng)n=8時(shí),L={1,2,3},R={4,5,6,7,8};

當(dāng)n=9時(shí),L={1,4,5,6},R={2,3,7,8,9};

當(dāng)n=10時(shí),L={2,3,5,6,8,9,10},R={1,4,7};

當(dāng)n=11時(shí),L={2,4,6,7,9,10,11},R={1,3,5,8};

當(dāng)n=12時(shí),

L={2,6,7,9,10,11},R={1,3,4,5,8,12};

當(dāng)n=13時(shí),

L={1,2,4,6,7,9,10,11},R={3,5,8,12,13};

當(dāng)n=14時(shí),

L={2,4,6,7,9,10,11,14},R={1,3,5,8,12,13}.

本文用一臺(tái)配置為因特爾酷睿i7–6500U 2.5 GHz CPU的電腦進(jìn)行MATLAB數(shù)值仿真,對不同的n分別用定義6和定理1計(jì)算Banzhaf值,并得出所用的運(yùn)行時(shí)間,見表1.表中方法1是用定義6直接計(jì)算,方法2是用定理1提出的代數(shù)表示計(jì)算的,而最后一列就是得出的Banzhaf值.當(dāng)n15時(shí),使用該配置的電腦在這兩種方法下都無法再進(jìn)行MATLAB數(shù)值仿真.

表1 不同玩家數(shù)下計(jì)算Banzhaf值的兩種方法所用MATLAB運(yùn)行時(shí)間比較Table 1 Comparisons of the running time of MATLAB for two methods of calculating Banzhaf value under different number of players

注2經(jīng)過分析作者發(fā)現(xiàn),根據(jù)定義6計(jì)算Banzhaf值與根據(jù)本文提出的定理1計(jì)算Banzhaf 值所需的計(jì)算量復(fù)雜度均為O(n2n).但是,本文建立的代數(shù)表示方法在形式上對Banzhaf值的計(jì)算更加簡潔.并且由于定理1提出的代數(shù)表示方法將子集的信息存儲(chǔ)在矩陣Ψn中,所以通過表1可以看出,與定義6相比,定理1計(jì)算Banzhaf值所需要的MATLAB運(yùn)行時(shí)間更短.

4 應(yīng)用

生命活動(dòng)中,基因表達(dá)發(fā)生改變是一種常見的現(xiàn)象,也是生物學(xué)研究的核心問題.通過對基因差異表達(dá)的研究,可以推斷細(xì)胞分化中基因“開啟”或“關(guān)閉”的機(jī)制,揭示基因與疾病的發(fā)生,發(fā)展,轉(zhuǎn)歸的內(nèi)在聯(lián)系.近年來,一種稱為微陣列技術(shù)的新的研究方法被提出[44],利用該技術(shù)可以產(chǎn)生大量關(guān)于人類基因表達(dá)的信息,可用于鑒定導(dǎo)致特定疾病的基因.然后通過某種判別方法,將基因表達(dá)信息轉(zhuǎn)化為一個(gè)布爾表達(dá)矩陣,稱之為微陣列矩陣,利用該矩陣推斷基因的相互作用以及當(dāng)生物系統(tǒng)的狀況發(fā)生變化時(shí)它們的行為.

N={1,2,···,n}是n個(gè)基因的集合.是來自正常組織的一組細(xì)胞集合,是具有遺傳疾病的組織的細(xì)胞集合.Aij ∈表示在樣本j(j ∈SR∪SD)中基因i的表達(dá)值.SR和SD中樣本的表達(dá)矩陣分別定義為微陣列實(shí)驗(yàn)情況(microarray experiment situation,MES)可表示為一個(gè)5元組E=實(shí)驗(yàn)的目的是將樣本與表達(dá)局勢相關(guān)聯(lián),并根據(jù)某個(gè)判別方法m來判斷SD中樣本的基因關(guān)于SR中樣本的表達(dá)值是否出現(xiàn)異常.本文用“1”表示異常表達(dá)的基因,用“0”表示正常表達(dá)的基因.使用這個(gè)判別方法m可以得出相應(yīng)的布爾表達(dá)矩陣即微陣列矩陣,記為M.

給定一個(gè)微陣列矩陣M=(mij).對于M的一個(gè)列m·j,j=1,···,d,定義了它的支撐為(m·j)={i:mij=1}.注意到對微陣列矩陣的每一列j,至少存在一個(gè)i使得mij≠0.

為了反映特定疾病中每個(gè)基因的相關(guān)性,Moretti等[45]提出了一種基于聯(lián)盟博弈的基因表達(dá)分析的替代方法,利用該方法計(jì)算稱為相關(guān)性指數(shù)的數(shù)值指數(shù).Banzhaf值作為合作博弈的一個(gè)單點(diǎn)解,提供了每個(gè)參與者形成大聯(lián)盟的預(yù)期邊際貢獻(xiàn).基于此,Lucchetti等[46]提出了使用Banzhaf值來度量基因相關(guān)性的方法.但是該文中Banzhaf值的計(jì)算是直接基于定義的求解,很難使用計(jì)算機(jī)進(jìn)行輔助求解.下面本文將得到的Banzhaf值的計(jì)算方法應(yīng)用于生物遺傳疾病基因的相關(guān)性度量.

例3給定一個(gè)n=4的微陣列實(shí)驗(yàn)情況和判別方法m,它對應(yīng)的微陣列矩陣為

下面用Banzhaf值度量基因與腫瘤發(fā)作的相關(guān)性.

顯然M的列對應(yīng)的支撐分別為(m·1)={1,3},(m·2)={3},(m·3)={1,2,4}.

由于微陣列博弈的特征函數(shù)v是根據(jù)基因組的充分性原則,為每個(gè)聯(lián)盟K ∈2N分配由K確定的腫瘤樣本的平均數(shù),計(jì)算的等價(jià)方法是如下無異議博弈的和:

于是M對應(yīng)的v(K)計(jì)算為

因此可以得到

從而可得v的結(jié)構(gòu)矩陣為

由式(9)可以得到

由定理1,可以計(jì)算出這個(gè)合作博弈的Banzhaf值為

因此可以得到確定腫瘤發(fā)作的最重要的基因是基因3,其次是基因1,最后是基因2和基因4.

5 結(jié)論

本文研究了合作博弈的Banzhaf值的求解問題.利用矩陣半張量積方法,給出了合作博弈特征函數(shù)的代數(shù)表示,基于此給出了Banzhaf值的等價(jià)代數(shù)形式和計(jì)算方法.本文還將所得結(jié)果應(yīng)用于生物網(wǎng)絡(luò)中遺傳疾病基因的相關(guān)性問題中,利用Banzhaf值度量與疾病發(fā)作高度相關(guān)的基因.

由于使用定義6計(jì)算Banzhaf值與根據(jù)本文提出的定理1計(jì)算Banzhaf值所需的計(jì)算量復(fù)雜度均為O(n2n),所以本文用一臺(tái)配置為因特爾酷睿i7–6500 U 2.5 GHz CPU的電腦進(jìn)行MATLAB數(shù)值仿真時(shí),當(dāng)玩家數(shù)超過15時(shí)就無法運(yùn)行了.數(shù)值仿真表明,與定義6相比,定理1計(jì)算Banzhaf值所需要的MATLAB運(yùn)行時(shí)間更短.