王 博 劉驚雷

(煙臺大學(xué)計算機(jī)與控制工程學(xué)院 山東煙臺 264005) (bob8190@163.com)

在布爾Game中比較有名的2個均衡解為純策略納什均衡(pure Nash equilibrium, PNE)和核(core)，但是均衡解不一定是最優(yōu)解.PNE和核都是策略組合的集合，不同的是PNE是非合作Game下的均衡，而核是在合作Game下通過聯(lián)盟達(dá)到的一種均衡.PNE特征是沒有Agent會因為單獨地脫離這個PNE而獲得更好的收益；而核的特征是Agent中的聯(lián)盟不會因為共同地脫離而都取得更好的收益.以著名的囚徒困境為例來說明這2種均衡解，假設(shè)2個小偷共謀闖入民宅作案后，被警察逮捕，被分別單獨審訊，警察對每個犯罪嫌疑人都給出如下的判罰規(guī)則：若小偷1和2都坦白了罪行，則兩人各被判刑3年；若兩者一方坦白，一方抵賴，則抵賴者被判5年，而坦白者因如實交代有功，減刑3年，立即釋放；若兩人都抵賴，則警方證據(jù)不足，因私闖民宅，各被判刑1年.不同的策略對應(yīng)的效應(yīng)如表1所示：

Table 1 Strategy Table for the Prisoner’s Dilemma表1 囚徒困境的策略表

表1中第1列的序數(shù)對的第1個序數(shù)為小偷1的策略，第2個序數(shù)為小偷2的策略，以“0”表示抵賴，“1”表示坦白.表1中第2列的序數(shù)對分別對應(yīng)于小偷1的效用和小偷2的效用.可以明顯地看出囚徒困境問題存在一個PNE，就是策略組合(1,1)，因為在該策略組合下任一小偷單獨改變自己的策略都不會獲得更高的收益.即使2個嫌犯可以聯(lián)盟合作，該問題也不存在核，因為即使對于屬于PNE的策略組合(1,1)來說，當(dāng)小偷1和小偷2聯(lián)盟來改變策略時，他們卻能獲得更好的收益，因此該問題沒有核解.

本文主要研究以布爾Game為輸入的核求解的問題.事實上布爾Game的核求解問題就是合作Game以布爾Game為框架的求解問題.Dunne等人使用非合作布爾Game的表示方法表示了合作布爾Game，本文也采用這樣的布爾Game的表示方式，它們的Agent都是由命題公式來代表目標(biāo)，并且這些Agent都控制一組決策變量，合作布爾Game的不同之處在于包含了成本[3].

目前，布爾Game已經(jīng)著重從知識表示的角度和純策略納什均衡的角度進(jìn)行了大量的研究，而在計算以核為解的表示和算法問題上研究不多.現(xiàn)在有2種現(xiàn)有的方法可以應(yīng)用在這個計算問題上：1)把布爾Game轉(zhuǎn)換成正則形式的Game是可用的，這樣就能容易地解出正則形式的Game.但是，這樣的轉(zhuǎn)換在決策變量的數(shù)量上是指數(shù)級的.尤其是需要計算整個效用矩陣的方法可能只適用于Agent和行動的數(shù)量足夠小時.避免使用所有收益矩陣中條目的方法可能更加適用于布爾Game.2)布爾Game中隱藏著很多圖結(jié)構(gòu)，通過這些圖的結(jié)構(gòu)可以提高布爾Game的求解效率，也能迅速地得出Game中的聯(lián)盟結(jié)構(gòu)并以此來求核.通常，計算布爾Game的核的問題可以看做策略組合的產(chǎn)生和對比測試的問題，即產(chǎn)生策略然后檢測這個策略是否與后面的定義5所描述的一致.因此核求解的算法主要通過簡化生成過程或測試過程來在一定程度上降低算法復(fù)雜度.在布爾Game的相關(guān)研究方面，本文的主要貢獻(xiàn)在于：

1) 給出了布爾Game解的PNE、核和約束滿足問題(CSP)三者之間的關(guān)系，即布爾Game滿足核的賦值，一定是PNE，但不一定滿足CSP(參見第2節(jié)的例1).反之，布爾Game中的策略組合一旦滿足CSP，就一定是核，進(jìn)而一定是PNE.

2) 將布爾Game中的決策變量看作超圖中的頂點，Agent目標(biāo)中包含的決策變量看作超圖中的超邊，構(gòu)成布爾Game的超圖結(jié)構(gòu).通過超圖的超樹分解算法求核，即求解布爾Game的約束可滿足問題的解(參見5.3節(jié)的命題3).

3) 使用Agent之間存在的依賴關(guān)系，即一個Agent的目標(biāo)中的決策變量依賴于另一個Agent所控制的決策變量.以Agent為頂點、以相關(guān)Agent為邊構(gòu)成的有向依賴圖，根據(jù)穩(wěn)定集將圖分解，得到規(guī)模上更小的子圖，這一定程度地降低了核求解的時間復(fù)雜度，簡化了布爾Game的核求解問題.

1 相關(guān)工作

本節(jié)從布爾Game框架的提出發(fā)展以及布爾Game的求解2方面，簡要地描述布爾Game研究的相關(guān)工作.Harrenstein等人于2001年首先提出了二元偏好的雙人零和Game上的布爾Game的模型，并在布爾Game的確定性上進(jìn)行了邏輯描述[1].Dunne等人主要給出了以布爾Game的形式表示的一些Game實例在決策問題上的計算復(fù)雜性[4].Bonzon等人將布爾Game擴(kuò)展為多Agent參與的未必是零和博弈的框架，并且描述了納什均衡和劣勢策略，并對相關(guān)問題的計算復(fù)雜性進(jìn)行了研究[2].Dunne等人提出了一種表示合作Game的新模型，即合作布爾Game.此模型是在原有的布爾Game上添加了成本，使得Agent的目的除了達(dá)成自己的目標(biāo)外，還要使成本最小化[3].Bonzon等人通過優(yōu)先化的目標(biāo)和命題化的CP-nets中表達(dá)Agent的偏好，擴(kuò)展了二元的偏好關(guān)系，并給出了納什均衡在布爾Game中的語義描述和確定了一些問題的計算復(fù)雜度[5].后來又提出布爾Game可以用來分析聯(lián)盟的形成，而且證明了如果聯(lián)盟能夠保證聯(lián)盟成員的所有目標(biāo)都得到滿足，那么布爾Game中的聯(lián)盟就是高效的[6].Wooldridge等人在合作布爾Game上應(yīng)用稅收方案促使整個Game達(dá)到穩(wěn)定狀態(tài)，并提出了一個合適的稅收方案的方法[7].

Clercq等人給出了布爾Game擴(kuò)展為Agent之間相互不確定彼此目標(biāo)的模型，使用了概率論中的不確定量度在語義上定義了不完全信息的布爾Game，并給出了這些語義的語法特征[8].Harrenstein等人研究了在帶成本的布爾Game中轉(zhuǎn)換的效果，Agent在成本上主要是為了追求某個目標(biāo)的滿意，其次是為了將他們的決策成本降到最低[9].引入并定義了迭代布爾Game，研究了其決策問題的計算復(fù)雜性[10]，又有不嚴(yán)格的準(zhǔn)備方案可以通過適當(dāng)?shù)募顧C(jī)制來消除.除了考慮在Game中不受限制地控制Agent的成本功能外，還研究了幾種機(jī)制，即使是在稅收或補(bǔ)貼不可能的情況下，允許Agent組成聯(lián)盟，并消除Game中的不良結(jié)果[11].之后通過用可能的邏輯來代替?zhèn)鹘y(tǒng)邏輯的使用，以一種自然的方式來解決一些不切實際的假設(shè)，運用可能性邏輯設(shè)置了2種不同的環(huán)境，并通過一個面向談判的程序說明了如何讓掌握較多知識的Agent獲得比其他一般的Agent更多有價值的結(jié)果[12].在國內(nèi)也有一些關(guān)于Game聯(lián)盟的研究有助于求核，楊威等人在協(xié)作感知系統(tǒng)的多目標(biāo)非線性優(yōu)化問題上，基于聯(lián)盟博弈理論構(gòu)建了一個不可轉(zhuǎn)移支付的聯(lián)盟構(gòu)造博弈模型，提出了一種分布式多目標(biāo)聯(lián)盟構(gòu)造算法DMCF[13].徐廣斌等人基于DP算法來求最優(yōu)聯(lián)盟的問題，提出了CCDP算法[14].

在布爾Game解的計算問題上,Bonzon等人定義了布爾Game中的Agent之間的依賴關(guān)系圖，給出了在無環(huán)依賴關(guān)系圖求PNE的算法，而且證明了這種依賴圖簡化了純策略納什均衡的計算[15].Sauro和Villata引入了穩(wěn)定聯(lián)盟和Δ-約簡，提出了基于二者的算法，并通過實驗展示了它們有效地改善了核的計算[16].Dunne等人定義了k界納什均衡的概念：沒有Agent可以通過改變小于k個決策變量來阻塞當(dāng)前策略組合而更加受益，而且證明了布爾Game在納什均衡相關(guān)的計算問題上，比一般的表示Game的框架要容易得多[17].Clercq等人提出了一種基于析取回答集編程的求解純策略納什均衡的方法，并通過實驗驗證了該方法的有效性[18].2017年他們又給出了求一般布爾Game均衡解的方法.該方法基于析取回答集編程(ASP)并解出任何布爾Game的解，而且還擴(kuò)展到了對帶約束和成本的布爾Game求解[19].

本文則研究和計算了布爾Game核的求解問題，與已有的求核算法的主要區(qū)別在于:

1) 對比于Sauro等人的包含成本的求核方法，本文的布爾Game沒有添加成本，是更加一般化的布爾Game.而且根據(jù)布爾Game的核與約束滿足問題之間的關(guān)系，運用了布爾Game的超圖形式簡化了求解約束滿足解的過程.

2) 對比于Clercq等人提出的判斷布爾Game中是否存在核的方法，本文研究的是求布爾Game中的所有核.總的來說本文吸取了Bonzon等人的穩(wěn)定集的概念[15]，將其求納什均衡的方法擴(kuò)展到布爾Game的核求解中，通過Agent間的依賴關(guān)系得到穩(wěn)定集，再以穩(wěn)定集分解布爾Game，從而簡化了部分核的求解過程，提高了求解效率.

2 布爾Game的相關(guān)定義

本節(jié)對布爾Game的相關(guān)概念進(jìn)行形式化描述，并統(tǒng)一了第3～5節(jié)中所用到的標(biāo)記.

布爾Game是一種邏輯推理的框架，它通過使用命題公式來使Agent的理性行為形式化.本文給出如下定義:

定義1. 布爾Game.布爾Game是一個四元組G=(N,V,π,Φ).其中，N={1,2,…,n}表示n個Agent的集合;V={p1,p2,…}是一組原子命題，即決策變量的集合;π:V→N為控制賦值函數(shù)；Φ={φ1,φ2,…,φn}表示Agent所對應(yīng)的目標(biāo)公式.

控制賦值函數(shù)π將每一個決策變量映射到控制這個決策變量的Agent上.Agenti控制的所有決策變量記作πi={p∈V|π-1(p)=i}.每個決策變量有且只有一個Agent控制，即{π1,π2,…,πn}是決策變量集V的一個劃分.上述中控制的意思是只有Agenti才可以設(shè)置πi中每個決策變量的真值.

定義2. 策略組合.給定布爾GameG=(N,V,π,Φ).G中的Agenti上所有策略的集合Si={si∈2πi}，那么GameG中所有的策略組合S=S1×S2×…×Si×Si+1×…×Sn.對于?i，si∈Si，G的一個策略組合s=(s1,s2,…,si,si+1,…,sn).一個策略組合也稱作一組賦值.

定義2中，2πi表示πi上解釋的集合.si是Agenti的策略，即i控制的所有決策變量πi上的一個解釋，s是所有決策變量V上的一個解釋，即s∈2V.

定義3. 效用函數(shù).給定一個布爾GameG=(N,V,π,Φ).對于每個Agenti∈N和G的每個策略組合s，效用函數(shù)ui被定義為ui(s)=1當(dāng)且僅當(dāng)sφi，否則ui(s)=0.

定義5. 核core(G).策略組合s∈S被聯(lián)盟C?N(C≠?)阻塞，如果存在一個策略組合s′∈S使得：

于是布爾Game的核core(G)就包含不受任何非空的聯(lián)盟C?N阻塞的策略組合s.

定義5也蘊(yùn)含著core(G)不會受單獨的Agent阻塞，所以每個核都是PNE.

例1. 給定一個布爾GameG1=(N,V,π,Φ)，其中N={1,2,3}，V={p1,p2,p3}.而且π1={p1}，π2={p2}，π3={p3}，即Agent 1控制p1，Agent 2控制p2，Agent 3控制p3.Agent 1，2和3的目標(biāo)分別是φ1=p1∨(p1∧p2∧p3)=1，φ2=p1?(p2?p3)=1和φ3=(p1∧p2∧p3)∨(p1∧p2∧p3)=1.

3 約束可滿足問題下的布爾Game

3.1 約束滿足問題

定義6. 約束滿足問題(CSP).可通過三元組I=(X,Y,C)來表示.其中，X是一個有限的變量集合，Y表示有限的值域集合，C={C1,C2,…,Cm}表示由m個約束組成的約束集合.對于每個約束Ci(1≤i≤m)，由二元組(Si,ri)表示.其中，Si?X是約束的范圍，它是一個長度為li的變量集合；ri是li個變量Si在值域Y上的關(guān)系，被稱作約束關(guān)系.而CSP的解為一組滿足所有約束的在X上的賦值.

定義7. 布爾Game的約束滿足問題表示.給定一個布爾GameG=(N,V,π,Φ).布爾Game的約束滿足問題表示CSP(G)=(V,{0,1},C)，其中?i∈N,Ci=(RV(i),φi=1)，RV(i)表示Agenti的相關(guān)變量，其具體介紹參見定義11.

通過定義7可知，在布爾GameG中，Agenti的策略Si就是約束Ci的待定解集，只有滿足約束關(guān)系ri的才是約束Ci的解，在布爾Game層次上就是Agenti為了滿足目標(biāo)所采取的策略.

例2. 對于例1的布爾GameG1中的約束滿足問題CSP(G1)可表示為X={p1,p2,p3}，Y={0,1}，C={((p1,p2,p3),φ1=1),((p1,p2,p3),φ2=1),((p1,p2,p3),φ3=1)}，而CSP(G1)的解為使φ1∧φ2∧φ3=1的賦值集合.

3.2 布爾Game的超圖表示

超樹樹寬是專門為超圖設(shè)計的一種環(huán)性的度量.約束可滿足問題在結(jié)構(gòu)上最合適的表示方式之一是與之相對應(yīng)的超圖[20].因此在CSP下的布爾Game可以通過超圖結(jié)構(gòu)表示.

定義8. 超圖.超圖表示為H=(P,HE)，其中P是頂點集，HE={e≠?|e?P}是超邊的集合，即每條超邊是頂點集P的非空子集.

對于一個CSPI=(X,Y,C)，它相對應(yīng)的超圖表示為H(I)=(P,HE)，其中P=X，并且HE={var(S)|(S,r)∈C}，var(S)表示在約束C的約束范圍S中的變量集合.那么給定一個布爾GameG=(N,V,π,Φ).根據(jù)定義7，G的超圖表示為H(G)=(V,RV).其中布爾Game中的決策變量的集合V視為超圖中的頂點集；RV是所有Agent的相關(guān)變量的集合，它被看做超圖中的超邊的集合.

對于布爾GameG的連接樹J(G)，因為它屬于寬度為1的超樹分解，所以它的每個節(jié)點中都只有一條超邊.而連接樹中頂點的連接條件為：當(dāng)2條超邊h1和h2共同包含一個決策變量v時，在J(G)中h1和h2就可以被連通，而且v也一定會出現(xiàn)在連通h1和h2唯一路徑上的每個節(jié)點中.換言之，在J(G)中包含v的所有節(jié)點可以誘導(dǎo)一棵J(G)的(連通)子樹.

例3. 給定布爾GameG3，其中有一組AgentN={1,2,3}和一組決策變量V={p1,p2,p3,p4}.其中Agent 1控制p1，Agent 2控制p2，Agent 3控制p3和p4.Agent 1的目標(biāo)是使公式φ1=p1?p3為真，而Agent 2和Agent 3的目標(biāo)分別是使φ2=p2∧(p1∧p4)和φ3=(p3∨p1)→p2為真.那么該布爾Game的超圖如圖1所示，表示為H(G3)=(V,HE)，其中V={p1,p2,p3,p4}，HE={e1,e2,e3}，e1={p1,p3}，e2={p1,p2,p4}，e3={p1,p2,p3}.這是一個無環(huán)超圖，所以根據(jù)連接樹中頂點的連接條件可以得到一個超樹分解，即連接樹J(G3)，如圖2所示，對于根節(jié)點φ3，(φ3)={p1,p2,p3}，λ(φ3)={e3}.

Fig. 1 The hypergraph structure of G3圖1 G3的超圖結(jié)構(gòu)

Fig. 2 The join tree J(G3)圖2 連接樹J(G3)

4 Agent間的依賴關(guān)系

定義11. 相關(guān)變量，相關(guān)Agent.給定布爾GameG=(N,V,π,Φ).Agenti的相關(guān)變量RV(i)為φi中不能繼續(xù)約簡的原子變量的集合.i的相關(guān)AgentRA(i)={π-1(p)∈N|p∈RV(i)}.Agent上的依賴關(guān)系圖是有向圖DG=(N,R)，其中?i,j∈N，如果j∈RA(i)，那么有向邊(i,j)∈R.

Agenti的相關(guān)Agent是控制著Agenti的相關(guān)變量的一組Agent集合.布爾Game的依賴關(guān)系圖為圖(N,R)，其中頂點集合N對應(yīng)于Agent的集合，并且R是所有有向邊(i,j)的集合，其中?i,j∈N，j∈RA(i)，即Agenti依賴于Agentj，R也是一種在N上的二元關(guān)系.R上的傳遞閉包記作TC，TC(i,j)表示在關(guān)系R上Agenti和Agentj之間是否存在一條路徑，那么TC(i)就表示Agenti直接或間接依賴的Agent的集合.若依賴關(guān)系圖DG上的一組Agent穩(wěn)定，需要在關(guān)系R上閉合[15].

定義12. 穩(wěn)定集.給定布爾GameG=(N,V,π,Φ).對于B?N，B是穩(wěn)定集當(dāng)且僅當(dāng)R(B)?B，即?i∈B，對于任意的Agentj使得(i,j)∈R，同時j∈B.

穩(wěn)定集就是N的子集B，其中B中的Agent不依賴于B以外任何的Agent.R(B)表示?i∈B，RA(i)?R(B).即集合B中所有Agent的相關(guān)Agent的集合.所以穩(wěn)定集B的R(B)運算時在B上是閉合的.穩(wěn)定集的概念最早是由Neumann等人于1953年提出的，它是一種策略標(biāo)準(zhǔn)，但是與本文中穩(wěn)定集的概念是不同的[22].

引理1. 令C?2N，若存在布爾GameG使得C在G上是穩(wěn)定的，需要滿足以下4個性質(zhì):

1) ?∈C;

2)N∈C；

3) 若B,B′∈C，則B∪B′∈C；

4) 若B,B′∈C，則B∩B′∈C.

通過引理1可知，穩(wěn)定集在交、并運算上是閉合的.

命題1. 給定布爾GameG=(N,V,π,Φ)，?i∈N，TC(i)一定是穩(wěn)定集.

證明. 假設(shè)TC(i)不是穩(wěn)定集，那么一定?j∈TC(i)依賴于TC(i)以外的Agentk∈N，但是因為TC(i)是i所依賴的所有的Agent集合，若j依賴于k，則k∈TC(i).這與假設(shè)矛盾，所以命題成立.

證畢.

通過定義13可以看出，布爾Game在穩(wěn)定集B上的映射GB中，Agent的目標(biāo)是不包含穩(wěn)定集以外的Agent所控制的決策變量，因此映射GB也是一個布爾Game.

如果布爾GameG上在B的映射GB的一個策略組合sB不是GB上的納什均衡，那么在G中以sB為基礎(chǔ)的任一策略組合s都不是G中的納什均衡[15].同樣地，本文將這樣的結(jié)論推廣到核的求解上.

命題2. 給定布爾GameG=(N,V,π,Φ)和一個穩(wěn)定集B，如果s∈core(G)，那么sB∈core(GB)，其中sB?s，即sB是s在B控制決策變量上的映射.

證畢.

例4. 給定一個布爾GameG2={N,V,π,Φ}，其中N={1,2,3}，V={p1,p2,p3}，πi={pi}，φ1=p2，φ2=p1∨p2并且φ3=p1∧p2∧p3.于是對于相關(guān)變量，RV(1)={p2}，RV(2)={p1,p2}，RV(3)={p1,p2,p3}.而RA(1)={2}，RA(2)={1,2}，RA(3)={1,2,3}.于是G2的依賴關(guān)系圖可以表示為：DG(G2)=(N,R)，其中R={(1,2),(2,1),(2,2),(3,1),(3,2),(3,3)}.所以G2的依賴關(guān)系圖如圖3所示：

Fig. 3 The dependencies between Agents of G2圖3 布爾Game G2的Agent依賴關(guān)系

圖3中從Agent 3到Agent 1有一個箭頭，表示3依賴于1，即Agent 1是Agent 3的相關(guān)Agent.在G2中集合{1,2}是在R上除空集和N外唯一的穩(wěn)定集.

5 布爾Game的核求解

本節(jié)對基于超樹分解的無環(huán)布爾Game的可滿足核的求解算法以及通過穩(wěn)定集分解布爾Game的求核算法，進(jìn)行了具體的算法描述和分析.

5.1 基于超樹分解的布爾Game求核算法

通過第3節(jié)引入的在CSP下的布爾Game，本節(jié)采用超圖的超樹分解算法得到超樹，即Gottlob等人提出的det-k-decomp算法[23].該算法可以在多項式時間內(nèi)判斷一個寬度為k的超樹分解是否存在，而且如果存在這樣的有界超樹，可以通過遞歸構(gòu)造出一個寬度為k的超樹分解.因為本文研究的是超圖上無環(huán)的布爾Game，所以需要構(gòu)造一個寬度為1的超樹分解，即一個連接樹.得到的超樹通過類數(shù)據(jù)庫內(nèi)連接查詢的方式，求解滿足布爾Game的約束滿足問題的核，參見算法1.

算法1.traverseJoinTree(J(G),G,RV,S).

輸入：布爾GameG=(N,V,π,Φ)、G中所有Agent的相關(guān)變量集RV；

輸出：布爾Game約束滿足問題下的解S.

①J(G)←det-k-decomp()；

②p←J(G)的根節(jié)點；

③ if(public←(RV(p)∩CV))≠?

④Sp←Spublic×2RV(p)-public；

⑤ else

⑥Sp←2p；

⑦ end if

⑧Ss←?；

⑨ for eachs∈Sp

⑩ ifsφp

第1步，算法1的行①～⑦，在遞歸的過程中獲得當(dāng)前結(jié)點的待驗證策略集合Sp.Sp的存儲結(jié)構(gòu)類似于數(shù)據(jù)庫的表，由決策變量和其對應(yīng)的賦值組成，決策變量相當(dāng)于數(shù)據(jù)表中的屬性行，決策變量上的賦值相當(dāng)于字段.該過程是依據(jù)引理2執(zhí)行的.首先將J(G)的根節(jié)點賦值給中間變量p.CV是已生成并測試過的決策變量的集合.在生成當(dāng)前結(jié)點的待驗證策略之前，可以通過判斷CV和RV(p)是否存在交集來減少該結(jié)點生成的待驗證策略集的大小.CV和RV(p)存在交集就意味著當(dāng)前結(jié)點中的一部分決策變量已經(jīng)參與過生成待驗證策略.所以可以在之前求得的結(jié)點目標(biāo)可滿足的解的基礎(chǔ)上，只是生成在RV(p)中未和CV相交的部分決策變量.而因為連接樹的構(gòu)成特點，若之前的結(jié)點已經(jīng)生成過策略，當(dāng)前結(jié)點的決策變量和之前的結(jié)點的決策變量之間一定存在交集.具體過程可以參見5.4節(jié)的例5.

引理2. 一個合取范式是重言式，當(dāng)且僅當(dāng)它的每一個簡單析取范式都是重言式.

對于布爾GameG的約束滿足問題CSP(G)，根據(jù)引理2，對φ1∧φ2∧…∧φn=1的求解，可以轉(zhuǎn)化為對每個Agent的目標(biāo)單獨求可滿足解，最后通過內(nèi)連接操作合并得到所有目標(biāo)的解，即求得約束解的核.

算法1的目的是求解布爾Game的約束滿足問題，即求φ1∧φ2∧…∧φn=1的解.通過建立布爾GameG上通過建立布爾GameG上的超圖結(jié)構(gòu)，然后超樹分解得到連接樹J(G)，在G的連接樹J(G)上遞歸地遍歷求得所有Agent都可滿足的解.

5.2 基于穩(wěn)定集的布爾Game分解求核算法

一般的窮舉方法的求核算法是在所有Agent上生成所有的策略組合，然后調(diào)用函數(shù)1判斷每個策略組合s是否滿足核的定義.由于一般的窮舉算法的時間復(fù)雜度是指數(shù)級的，所以在較大規(guī)模的布爾Game上求解是相當(dāng)消耗時間的.所以本節(jié)根據(jù)穩(wěn)定集分解布爾Game，可以將布爾Game的規(guī)?？s小，提高運算效率.

根據(jù)命題2的逆否命題，即如果sB?core(GB)，那么s?core(G)，可以通過穩(wěn)定集分解布爾Game為規(guī)模更小的在原始布爾Game上的映射.通過這樣的方法可以提前排除很多不必要的策略上的測試，產(chǎn)生待檢測的子策略組合，從而縮小測試的策略范圍.接下來根據(jù)命題2、命題1和定義12來設(shè)計算法2.

算法2的目的是通過穩(wěn)定集分解布爾Game得到一些規(guī)模更小的布爾Game，然后從規(guī)模最小的布爾Game開始，在具有包含和被包含關(guān)系的布爾Game上迭代求核.這樣就降低了核求解過程的策略測試范圍，以此來提高求解布爾Game的核的效率.因為一個布爾Game可能存在很多規(guī)模不一的穩(wěn)定集，所以算法2按照穩(wěn)定集間的包含關(guān)系從規(guī)模最小的非空穩(wěn)定集分解布爾Game，最后求得原布爾Game的核.算法2的詳細(xì)描述如下：

算法2. 基于穩(wěn)定集的布爾Game分解求核算法.

輸入：布爾GameG=(N,V,π,Φ)、G中Agent間的依賴關(guān)系圖DG=(N,R)；

輸出：G的核core(G).

②TC←warshall(DG)；

③ for eachi∈N

⑤ end for

⑦Bpre←?；

⑧core(G)←?；

⑨ for eachB∈TC

⑩ ifBpre?B

第1步，在算法2的行①～⑥，先通過warshall算法求解布爾Game上存在的關(guān)系R的傳遞閉包的關(guān)系矩陣TC[24].然后根據(jù)命題1和引理1，由TC得到所有穩(wěn)定集，對于TC(i)，其中i∈N.將這些穩(wěn)定集和全集N寫入穩(wěn)定集的集合.得到的穩(wěn)定集的集合按照從小到大的次序排序.

函數(shù)1.isCore(G,s).

輸入：布爾GameG=(N,V,π,Φ)、G的一個策略組合s；

輸出：布爾變量flagCore.

①C←?；

② fori←1 to |N|

④C←C∪{i};

⑤ end if

⑥ end for

⑦SC←{s-C}×2πC；

⑧flagCore←true；

⑨ for eachs′∈SC

⑩ ifs′?s

函數(shù)1的功能是檢測布爾GameG中的一個策略組合是否符合核的定義，即對于當(dāng)前策略組合，是否存在一個聯(lián)盟所引起的另一個策略組合阻塞當(dāng)前策略組合，若沒有聯(lián)盟阻塞當(dāng)前策略組合，則該策略組合就是核，否則就不屬于核.下面是對函數(shù)1的具體描述.2πC表示在聯(lián)盟C上生成的策略組合，s-C表示聯(lián)盟C以外的Agent的策略組合.首先生成聯(lián)盟C，構(gòu)成聯(lián)盟的原則是目標(biāo)未滿足的Agent可以構(gòu)成聯(lián)盟；然后改變聯(lián)盟C中Agent的策略，而保持C以外的Agent的策略不變，通過和2πC的笛卡爾積，構(gòu)成新的策略組合SC；最后檢測SC中是否存在策略組合s′阻塞s，即s′是否使聯(lián)盟C的效用相對s得到提高，若SC中不存在一個s′阻塞s，那么s就是布爾GameG的核，否則不屬于核.

5.3 算法理論分析

命題3. 如果布爾GameG的策略組合Ss是CSP(G)的解集，那么Ss?core(G).

證明.s∈Ss為布爾GameG的核，即s∈core(G)，C?N是任意的一個聯(lián)盟，S是G上的所有的策略組合.假設(shè)存在一個策略組合s′∈S，使聯(lián)盟C以外的所有Agent在s和s′執(zhí)行相同的決策，并且聯(lián)盟C內(nèi)的Agent在s′所得的收益比在s中的收益多.但是因為s是CSP(G)的解，也就是對于每個Agent的目標(biāo)都會被滿足，即φ1∧φ2∧…∧φn=1.而且本文的布爾GameG的收益是二元的，即非1即0.所以聯(lián)盟C內(nèi)的Agent在s′所得的收益最多和在s中的收益一樣多，結(jié)論與假設(shè)和核的定義相互矛盾，因此Ss?core(G).

證畢.

一般求核問題可以看做產(chǎn)生策略和比較測試的過程，即先產(chǎn)生策略然后再比較檢測該策略是否符合φ3∧φ1=1，如定義5所述.而算法1根據(jù)命題3，可以不必考慮比較檢測的步驟,因此大大縮短了算法的時間復(fù)雜度.同樣地，算法1也同樣適用于布爾Game求純策略納什均衡.

定理1. 在最壞情況下，算法1的時間復(fù)雜度為O(|N|×2k)，其中k表示布爾Game目標(biāo)中決策變量的最大值.

證明. 直觀來看，在布爾GameG的超圖結(jié)構(gòu)的超樹分解J(G)中，每個結(jié)點都需要生成它們的策略，即在每個Agent目標(biāo)上生成策略，因為只有根結(jié)點能生成所有的策略，其他結(jié)點生成的策略是在之前結(jié)點的基礎(chǔ)上完成的，所以第1個結(jié)點中目標(biāo)的決策變量數(shù)在算法的運行效率上起決定性作用.那么最壞的情況就是根結(jié)點的目標(biāo)中決策變量數(shù)最大且每個結(jié)點都包含這樣的決策變量數(shù)k時，此時每個結(jié)點生成策略的時間復(fù)雜度是2k.最后需要在所有結(jié)點上生成策略，于是算法的復(fù)雜度為|N|×2k.

證畢.

定理2. 在最壞情況下，函數(shù)1的時間復(fù)雜度為O(2|VC|)，其中|VC|表示該策略中可以組成聯(lián)盟中的決策變量數(shù).

證明. 函數(shù)1的關(guān)鍵步驟是對新生成的帶聯(lián)盟的策略組合集SC進(jìn)行逐個檢測，而SC的個數(shù)就是2|VC|.所以在最壞情況下需遍歷完整個SC，所以函數(shù)1的時間復(fù)雜度為O(2|VC|).

證畢.

5.4 算法求解實例

例5. 給定一個布爾GameG4=(N,V,π,Φ)，其中N={1,2,3,4}，V={a,b,c,d,e,f}，π1={a,b}，π2={c,d}，π3={e}，π4={f}.φ1=(a∧b)∨c，φ2=b?(c?d)，φ3=(a→b)∧e，φ4=(c∧d∧f)∨(c∧d∧f).

根據(jù)例5描述,由定義7，G4可以被表示為CSP(G4)=(V,{0,1},C)，其中V={a,b,c,d,e,f}，C={C1,C2,C3,C4}而C1={(a,b,c),φ1=1}，C2={(b,c,d),φ2=1}，C3={(a,b,e),φ3=1}，C4={(c,d,f),φ4=1}.對于CSP(G4)的超圖表示H(G4)如圖4所示：

Fig. 4 The hypergraph structure of G4圖4 G4的超圖結(jié)構(gòu)

把每個Agent的目標(biāo)所包含的決策變量視作一條超邊，那么可以得到與HG4相對應(yīng)的超樹分解.因為HG4是無環(huán)超圖，它的超樹分解就是它所對應(yīng)的連接圖JT(G4)，如圖5所示.

Fig. 5 The join tree on H(G4)圖5 H(G4)生成的連接樹

下面求解G4的屬于約束滿足解的核.根據(jù)算法1得到圖6的執(zhí)行過程,圖6是從左到右執(zhí)行的.詳細(xì)描述如下：根據(jù)命題3，可以得到滿足布爾GameG4中的φ1∧φ2∧φ3∧φ4=1的賦值一定是G4的核.1)根據(jù)G4的連接樹結(jié)構(gòu)，得到r3={(0,0,1),(0,1,1),(1,1,1)}，即滿足φ3=1的賦值.2)生成和測試φ3的子結(jié)點φ1，根據(jù)命題3，在以上的結(jié)果中只需以r3的結(jié)果為基礎(chǔ)連續(xù)生成和測試，那么生成決策變量a,b,c的策略是(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,1,0),(1,1,1).3)經(jīng)過測試得到滿足的策略集{(0,0,0,1),(0,0,1,1),(0,1,0,1),(0,1,1,1),(1,1,0,1),(1,1,1,1)}.同理，每個結(jié)點都需要在之前求得的結(jié)果上生成策略并進(jìn)行測試，這在很大程度上降低了生成策略和測試的時間.每個結(jié)點都遍歷過后得到滿足φ1∧φ2∧φ3∧φ4=1的策略，也是G4的核，對應(yīng)于a，b，c，d，e，f為{(0,0,1,0,1,0)}.

abc φ3cφ1dφ2fφ40000001111100101100001000111111100100000100010101100111101010010101100110010

Fig. 6 Truth table of the process of algorithm 1
圖6 算法1 執(zhí)行過程的真值表

下面根據(jù)算法2求解布爾Game的全部核.根據(jù)Agent間的依賴圖獲得穩(wěn)定集，得到小規(guī)模的布爾Game，在小規(guī)模的布爾Game中排除一些不是核的解.如圖7所示，

RA

(1)={1,2}，

RA

(2)={1,2}.當(dāng)

B

1

={1,2}時，

R

(

B

1

)={1,2}?

B

，所以

B

1

={1,2}是穩(wěn)定集.同理，集合

B

2

={1,2,3}和

B

3

={1,2,4}是穩(wěn)定集.所以

G

4

所有穩(wěn)定集的集合

從小到大為{

B

1

,

B

2

,

B

3

,

N

}.

Fig. 7 Dependency graph among Agent of G4圖7 G4中Agent間的依賴圖

s-C)是否優(yōu)于(0,0,0,0).比較得出(0,0,0,1)?(0,0,0,0)，于是(0,0,0,0)被聯(lián)盟C阻塞了，所以(0,0,0,0)不是GB1的核.和上述過程相同，對于其他的策略也需要被檢驗是否被某個聯(lián)盟阻塞，進(jìn)而得到核.于是最后得到GB1的核core(GB1)={(0,0,1,0),(0,1,1,1),(1,0,1,0),(1,1,0,0),(1,1,1,1)}.

Table 2 The First Process of Algorithm 2表2 算法2的第1步執(zhí)行過程

因為B1?B2，所以求解G4映射在B2上的子布爾GameGB2的核.此時根據(jù)命題2，通過core(GB1)×2π3得到GB2需要判斷的策略集，2π3是π3上的解釋.與求GB1的核的過程相同，遍歷所有策略，在每個策略上生成聯(lián)盟，再檢測聯(lián)盟是否阻塞該策略,具體的執(zhí)行過程如表3所示.最后得到GB2的核為core(GB2)={(0,0,1,0,1),(0,1,1,1,1),(1,0,1,0,0),(1,0,1,0,1),(1,1,0,0,1),(1,1,1,1,1)}.

Table 3 The Second Process of Algorithm 2表3 算法2 的第2步執(zhí)行過程

因為B2B3且B2?N，所以最后求解布爾GameG的核.與求GB1的核的過程相同，通過core(GB2)×2f得到在G上的待驗證策略集.然后遍歷所有策略，在每個策略上生成聯(lián)盟，再檢測聯(lián)盟是否阻塞該策略.具體的執(zhí)行過程如表4所示.最終求得的布爾GameG的核對應(yīng)于(a,b,c,d,e,f)為core(G)={(0,0,1,0,1,0),(0,1,1,1,1,0),(0,1,1,1,1,1),(1,0,1,0,0,0),(1,0,1,0,1,0),(1,1,0,0,1,0),(1,1,0,0,1,1),(1,1,1,1,1,0),(1,1,1,1,1,1)}.

Table 4 The Last Process of Algorithm 2表4 算法2的最后一步執(zhí)行過程

6 實驗分析

本節(jié)對算法1、算法2和已有的求核算法進(jìn)行實驗對比，并進(jìn)行相應(yīng)的分析，來證明本文提出算法的有效性.由于布爾Game是新興的框架，在實際中應(yīng)用不多，數(shù)據(jù)較缺乏，所以本節(jié)采用隨機(jī)生成的布爾Game來模擬數(shù)據(jù)，以此來驗證本文給出的算法的效率.

6.1 隨機(jī)生成布爾Game

本節(jié)構(gòu)建了一個隨機(jī)生成的布爾Game模型[19]，該模型可以根據(jù)需要構(gòu)建適用于算法1的無環(huán)超圖的布爾Game，也可以構(gòu)造無特殊結(jié)構(gòu)的布爾Game.

通過以下8個參數(shù)的約束下隨機(jī)生成布爾Game：

1) Agent的數(shù)量|N|;

2) 每個Agent控制決策變量的數(shù)量b;

3) 目標(biāo)中二元運算符(∨和∧)的最大值m;

4) 目標(biāo)存在一個合取運算符的概率p(相反的是析取運算符);

5) 目標(biāo)中決策變量取非的概率n;

6) 每個Agent是否包含至少一個自己所控制的變量(默認(rèn)為否，以s表示);

7) 是否附加超圖無環(huán)的約束(默認(rèn)為否，以0表示);

8) 為保證每次運行程序時得到的布爾Game相同，設(shè)置seed.

按上述約束，設(shè)置參數(shù)|N|=5，b=2，m=3，p=0.5，n=0.5，seed=1，其他取默認(rèn)值，生成的隨機(jī)的布爾Game的數(shù)據(jù)格式如下：

①bgAgent 5

②a1p1p20

③a2p3p40

④a3p5p60

⑤a4p7p80

⑥a5p9p100

⑦ 1 (-p6& (p7;(p7;p9)))

⑧ 2 (-p8&p6)

⑨ 3 (p6;-p2)

⑩ 4 (p5;(p10;p7))

數(shù)據(jù)的行①以bg來表示一個布爾Game的開始，后面表示Agent的個數(shù).行②～⑥格式相同，其中p1,p2,…,p10表示決策變量，a表示一個Agent的開始的標(biāo)識，以行②為例，Agent 1控制的決策變量為p1和p2，最后都以0為該Agent的結(jié)束標(biāo)識.而行⑦～格式相同，以行⑦為例開頭的數(shù)字1表示Agent 1，后面便是Agent 1的目標(biāo)，其中，“-”表示取否，“;”表示析取，“&”表示合取，即Agent的目標(biāo)為p6∧(p7∨(p7∨p9)).

這里考慮的二元運算符只有合取和析取.因為根據(jù)蘊(yùn)含等值等式A→B?A∨B和等價等值式A?B?(A→B)∧(B→A)?(A∧B)∨(A∧B)，可以將目標(biāo)中的蘊(yùn)含符和等價符轉(zhuǎn)換為只包含析取和合取的命題公式.為了使得隨機(jī)布爾Game具有多樣性，這里通過設(shè)置參數(shù)m把不同Agent的目標(biāo)的長度設(shè)置一定的差異，并且對于每個Agent目標(biāo)中的二元運算符的數(shù)量都在[1，m]區(qū)間.

6.2 實驗環(huán)境和評估標(biāo)準(zhǔn)

本文的實驗的環(huán)境為：計算機(jī)操作系統(tǒng)是Windows7 64 b，硬件內(nèi)存為8 GB DDR 3，主頻為3.2 GHz的i5-4700英特爾處理器.程序的實現(xiàn)通過C++程序語言實現(xiàn).實驗的數(shù)據(jù)是根據(jù)6.1節(jié)描述隨機(jī)生成的模擬數(shù)據(jù).

本文以算法的運行時間為算法效率優(yōu)劣的評估標(biāo)準(zhǔn),分別設(shè)置2組實驗，即對算法1和算法2進(jìn)行實驗.1)在超圖無環(huán)的布爾Game上對算法1和可滿足性問題的窮舉算法進(jìn)行實驗對比，來驗證算法1的相對效率和影響算法效率的因素.2)在一般布爾Game上運用本文提出的算法2和一般的窮舉算法進(jìn)行實驗對比，和檢驗不同參數(shù)對算法效率的影響.考慮到實驗中影響實驗結(jié)果的變量比較多，所以采用控制變量法進(jìn)行實驗對比.本實驗的主要自變量為Agent的數(shù)量|N|、決策變量的數(shù)量|V|以及每個目標(biāo)中存在的二元運算符的個數(shù).為了降低特殊布爾Game對算法的影響和方便觀察實驗結(jié)果，每個自變量對應(yīng)因變量的取值為不同的100個布爾Game運行時間的中位數(shù)的對數(shù)，時間的單位為毫秒(ms).而且為了防止程序運行時間過長，設(shè)置超時時間為5 min，無論是否求得核，只要超過5 min就終止程序.

6.3 布爾Game的約束滿足求解實驗

Fig. 8 Experiment of solving core of Boolean games with a constraint satisfaction solution圖8 無環(huán)布爾Game求可滿足核的實驗

本節(jié)在存在約束滿足解的無環(huán)布爾Game的數(shù)據(jù)集上進(jìn)行實驗，實驗結(jié)果如圖8所示.該實驗對一般的窮舉法、NashEvaluation算法[25]和算法1進(jìn)行比較.這里的NashEvaluation算法是通過多次遍歷超圖的超樹分解，最后通過半連接操作求得約束滿足解的算法.以Agent的數(shù)量為自變量進(jìn)行3組實驗，每組實驗分設(shè)不同的決策變量數(shù)和最多二元運算符數(shù)，縱向?qū)Ρ冗@2個參數(shù)對算法的影響.通過每個Agenti控制相同的決策變量數(shù)目|πi|來決定總的決策變量數(shù)|V|，目標(biāo)φi中的決策變量數(shù)可以通過二元運算符的個數(shù)得到.分別設(shè)置(2,3)，(2,6)，(4,6)三組參數(shù)對進(jìn)行實驗，以參數(shù)對(2,3)為例，其中參數(shù)2表示每個Agent控制的決策變量數(shù)為2個，參數(shù)3表示每個Agent目標(biāo)中最多包含的二元運算符的數(shù)目為3個.

通過圖8的實驗結(jié)果可以得出，在存在約束滿足解的無環(huán)布爾Game中，算法1明顯比一般的窮舉法高效得多.窮舉法和算法1的運行時間都隨著Agent的數(shù)量的增加而增加，窮舉法的運算時間變化比較劇烈的原因是它需要窮舉出所有的策略組合，而這樣的過程所耗的時間是指數(shù)級增長的.當(dāng)決策變量的個數(shù)達(dá)到40時，窮舉法就超出了5 min.反觀算法1的曲線比較平滑，圖8的(a)和(b)可以看出，算法1的時間復(fù)雜度和所有決策變量的數(shù)目的關(guān)系不大，而與目標(biāo)中二元運算符的數(shù)目有關(guān)，即包含決策變量最多的目標(biāo)有關(guān)系.所以一旦固定了二元運算符的數(shù)量，算法1就只受到Agent個數(shù)的影響，這也從實驗的角度驗證了定理1的正確性.與窮舉法對比，算法1的效率較高是因為它考慮了每個Agent目標(biāo)之間的關(guān)系，即不同Agent之間的相關(guān)變量存在相交的部分，而且通過超樹分解，將所有的決策變量分解為更小的組，從而大大降低了策略生成的次數(shù).

在NashEvaluation算法和算法1的比較中，可以發(fā)現(xiàn)本文提出的算法1比NashEvaluation算法更高效.這是因為NashEvaluation算法對超樹進(jìn)行了3次遍歷并進(jìn)行了半連接處理；而算法1只是對超樹進(jìn)行了一次的遍歷，因為在這個過程中，每個結(jié)點被遍歷時都是在先前結(jié)點計算得到的解上計算，這在一定程度上減少了策略的檢測個數(shù).而且可以發(fā)現(xiàn)，在中小規(guī)模的布爾Game中2個算法的效率相差不大，而在大規(guī)模的布爾Game求解中算法1相對較好.從圖8的(a),(b)和(c)可以看到，NashEvaluation算法和算法1一樣，都是受m和Agent個數(shù)N的影響比較大.需要說明的是圖8中縱坐標(biāo)中SCBG是“求解布爾Game的核”的縮寫.

6.4 基于穩(wěn)定集分解的布爾Game求核實驗

本節(jié)在不存在任何限制的布爾Game的數(shù)據(jù)集上進(jìn)行實驗，測試算法2的效率.這里只在每個Agent上控制2個決策變量，目標(biāo)中包含3個二元操作符的布爾Game上進(jìn)行實驗測試.

通過圖9可得，對于2個算法，當(dāng)Agent個數(shù)增加到30個，相應(yīng)的決策變量數(shù)就增加到了60個，這時布爾Game的核的求解就到了一定的界限.但在30個Agent之前，算法2所達(dá)到的效果還是相對明顯的，在一定程度上提高了計算核的效率.所以算法2只是適用于Agent的個數(shù)和決策變量的數(shù)目不太多的情況下，雖然在通過Agent間的依賴關(guān)系分解了原始布爾Game，但在局部的子布爾Game的求核算法中仍然是指數(shù)級的.對于剩余的待檢測策略，在比較的過程中，每個策略需要的對比次數(shù)至少是2|V|.所以該算法只能適用于中小規(guī)模的無約束滿足解的布爾Game求核.

Fig. 9 Experiment of solving core of general Boolean games圖9 一般布爾Game求核實驗

6.5 實驗結(jié)論

通過6.3節(jié)、6.4節(jié)的實驗分析，可以得出本文給出的算法1適用于求解超圖無環(huán)布爾Game的約束滿足解，算法1受Agent和對應(yīng)相關(guān)變量(目標(biāo)中的決策變量)的影響比較大，而跟整個決策變量集的大小無關(guān).當(dāng)相關(guān)變量數(shù)固定時，算法1與Agent數(shù)屬于線性關(guān)系；當(dāng)Agent數(shù)固定時，算法1與最大相關(guān)變量是指數(shù)關(guān)系.實驗證明這種將布爾Game的決策變量集通過目標(biāo)分解的方法，大大降低了生成策略組合的過程，從而提高了求核的效率.并且在與NashEvaluation算法的比較中，算法1在大規(guī)模的布爾Game的可滿足核的求解上相對高效.

算法2適用于中小規(guī)模的布爾Game，規(guī)模是指布爾Game的Agent數(shù)量和決策變量數(shù)的大小.通過穩(wěn)定集分解布爾Game的方法，在一定程度上降低了求核的運行時間，但是也存在弊端，就是當(dāng)布爾Game規(guī)模過大時，被分解得到的子布爾Game規(guī)模雖然相對于較小，但規(guī)模相對于一般問題還是過大.所以該算法對于中小規(guī)模的布爾Game是適用的.

7 結(jié)論和未來工作

本文主要研究了2個問題:1)求解布爾Game的可滿足性問題的解；2)求解布爾Game的所有核.在問題1上引入約束滿足問題的超圖表示，對于有無環(huán)超圖的布爾Game，利用超樹分解來降低求可滿足解的可行空間，給出了基于超樹分解的求布爾Game可滿足解的算法，該算法在很大程度上縮小了問題的規(guī)模，提高了求解效率.在問題2上通過Agent間的依賴關(guān)系圖得到穩(wěn)定集，利用穩(wěn)定集分解布爾Game來降低求核的可行空間，給出了基于穩(wěn)定集分解的布爾Game求核算法，提高了求解核的效率.最后以隨機(jī)生成的布爾Game實驗驗證了上述2種算法的有效性.

本文的未來工作包括：

1) 將Agent間的依賴關(guān)系加入到布爾Game的超樹分解中，將超圖的結(jié)構(gòu)更接近于布爾Game，研究該結(jié)構(gòu)的核求解問題，找到高效率的核求解算法.

2) 在布爾Game的超圖表示中，研究在超圖的超樹分解的樹寬大于等于2時，布爾Game的核求解方法.

3) 在執(zhí)行決策變量時將單個Agent的操作細(xì)分化，將稅收、決策變量的約束關(guān)系、成本加入到布爾Game中，使得更貼近現(xiàn)實中的博弈.

WangBo, born in 1994. Master candidate. His main research interests include computation of a core on Boolean games.

LiuJinglei, born in 1970. PhD, professor, and master supervisor. His main research interests include artificial intelligent and theoretical computer science.