布尔Game的核求解算法
2018-08-06刘惊雷
王 博 刘惊雷
(烟台大学计算机与控制工程学院 山东烟台 264005) (bob8190@163.com)
在布尔Game中比较有名的2个均衡解为纯策略纳什均衡(pure Nash equilibrium, PNE)和核(core)，但是均衡解不一定是最优解.PNE和核都是策略组合的集合，不同的是PNE是非合作Game下的均衡，而核是在合作Game下通过联盟达到的一种均衡.PNE特征是没有Agent会因为单独地脱离这个PNE而获得更好的收益；而核的特征是Agent中的联盟不会因为共同地脱离而都取得更好的收益.以著名的囚徒困境为例来说明这2种均衡解，假设2个小偷共谋闯入民宅作案后，被警察逮捕，被分别单独审讯，警察对每个犯罪嫌疑人都给出如下的判罚规则：若小偷1和2都坦白了罪行，则两人各被判刑3年；若两者一方坦白，一方抵赖，则抵赖者被判5年，而坦白者因如实交代有功，减刑3年，立即释放；若两人都抵赖，则警方证据不足，因私闯民宅，各被判刑1年.不同的策略对应的效应如表1所示：
Table 1 Strategy Table for the Prisoner’s Dilemma表1 囚徒困境的策略表
表1中第1列的序数对的第1个序数为小偷1的策略，第2个序数为小偷2的策略，以“0”表示抵赖，“1”表示坦白.表1中第2列的序数对分别对应于小偷1的效用和小偷2的效用.可以明显地看出囚徒困境问题存在一个PNE，就是策略组合(1,1)，因为在该策略组合下任一小偷单独改变自己的策略都不会获得更高的收益.即使2个嫌犯可以联盟合作，该问题也不存在核，因为即使对于属于PNE的策略组合(1,1)来说，当小偷1和小偷2联盟来改变策略时，他们却能获得更好的收益，因此该问题没有核解.
本文主要研究以布尔Game为输入的核求解的问题.事实上布尔Game的核求解问题就是合作Game以布尔Game为框架的求解问题.Dunne等人使用非合作布尔Game的表示方法表示了合作布尔Game，本文也采用这样的布尔Game的表示方式，它们的Agent都是由命题公式来代表目标，并且这些Agent都控制一组决策变量，合作布尔Game的不同之处在于包含了成本[3].
目前，布尔Game已经着重从知识表示的角度和纯策略纳什均衡的角度进行了大量的研究，而在计算以核为解的表示和算法问题上研究不多.现在有2种现有的方法可以应用在这个计算问题上：1)把布尔Game转换成正则形式的Game是可用的，这样就能容易地解出正则形式的Game.但是，这样的转换在决策变量的数量上是指数级的.尤其是需要计算整个效用矩阵的方法可能只适用于Agent和行动的数量足够小时.避免使用所有收益矩阵中条目的方法可能更加适用于布尔Game.2)布尔Game中隐藏着很多图结构，通过这些图的结构可以提高布尔Game的求解效率，也能迅速地得出Game中的联盟结构并以此来求核.通常，计算布尔Game的核的问题可以看做策略组合的产生和对比测试的问题，即产生策略然后检测这个策略是否与后面的定义5所描述的一致.因此核求解的算法主要通过简化生成过程或测试过程来在一定程度上降低算法复杂度.在布尔Game的相关研究方面，本文的主要贡献在于：
1) 给出了布尔Game解的PNE、核和约束满足问题(CSP)三者之间的关系，即布尔Game满足核的赋值，一定是PNE，但不一定满足CSP(参见第2节的例1).反之，布尔Game中的策略组合一旦满足CSP，就一定是核，进而一定是PNE.
2) 将布尔Game中的决策变量看作超图中的顶点，Agent目标中包含的决策变量看作超图中的超边，构成布尔Game的超图结构.通过超图的超树分解算法求核，即求解布尔Game的约束可满足问题的解(参见5.3节的命题3).
3) 使用Agent之间存在的依赖关系，即一个Agent的目标中的决策变量依赖于另一个Agent所控制的决策变量.以Agent为顶点、以相关Agent为边构成的有向依赖图，根据稳定集将图分解，得到规模上更小的子图，这一定程度地降低了核求解的时间复杂度，简化了布尔Game的核求解问题.
1 相关工作
本节从布尔Game框架的提出发展以及布尔Game的求解2方面，简要地描述布尔Game研究的相关工作.Harrenstein等人于2001年首先提出了二元偏好的双人零和Game上的布尔Game的模型，并在布尔Game的确定性上进行了逻辑描述[1].Dunne等人主要给出了以布尔Game的形式表示的一些Game实例在决策问题上的计算复杂性[4].Bonzon等人将布尔Game扩展为多Agent参与的未必是零和博弈的框架，并且描述了纳什均衡和劣势策略，并对相关问题的计算复杂性进行了研究[2].Dunne等人提出了一种表示合作Game的新模型，即合作布尔Game.此模型是在原有的布尔Game上添加了成本，使得Agent的目的除了达成自己的目标外，还要使成本最小化[3].Bonzon等人通过优先化的目标和命题化的CP-nets中表达Agent的偏好，扩展了二元的偏好关系，并给出了纳什均衡在布尔Game中的语义描述和确定了一些问题的计算复杂度[5].后来又提出布尔Game可以用来分析联盟的形成，而且证明了如果联盟能够保证联盟成员的所有目标都得到满足，那么布尔Game中的联盟就是高效的[6].Wooldridge等人在合作布尔Game上应用税收方案促使整个Game达到稳定状态，并提出了一个合适的税收方案的方法[7].
Clercq等人给出了布尔Game扩展为Agent之间相互不确定彼此目标的模型，使用了概率论中的不确定量度在语义上定义了不完全信息的布尔Game，并给出了这些语义的语法特征[8].Harrenstein等人研究了在带成本的布尔Game中转换的效果，Agent在成本上主要是为了追求某个目标的满意，其次是为了将他们的决策成本降到最低[9].引入并定义了迭代布尔Game，研究了其决策问题的计算复杂性[10]，又有不严格的准备方案可以通过适当的激励机制来消除.除了考虑在Game中不受限制地控制Agent的成本功能外，还研究了几种机制，即使是在税收或补贴不可能的情况下，允许Agent组成联盟，并消除Game中的不良结果[11].之后通过用可能的逻辑来代替传统逻辑的使用，以一种自然的方式来解决一些不切实际的假设，运用可能性逻辑设置了2种不同的环境，并通过一个面向谈判的程序说明了如何让掌握较多知识的Agent获得比其他一般的Agent更多有价值的结果[12].在国内也有一些关于Game联盟的研究有助于求核，杨威等人在协作感知系统的多目标非线性优化问题上，基于联盟博弈理论构建了一个不可转移支付的联盟构造博弈模型，提出了一种分布式多目标联盟构造算法DMCF[13].徐广斌等人基于DP算法来求最优联盟的问题，提出了CCDP算法[14].
在布尔Game解的计算问题上,Bonzon等人定义了布尔Game中的Agent之间的依赖关系图，给出了在无环依赖关系图求PNE的算法，而且证明了这种依赖图简化了纯策略纳什均衡的计算[15].Sauro和Villata引入了稳定联盟和Δ-约简，提出了基于二者的算法，并通过实验展示了它们有效地改善了核的计算[16].Dunne等人定义了k界纳什均衡的概念：没有Agent可以通过改变小于k个决策变量来阻塞当前策略组合而更加受益，而且证明了布尔Game在纳什均衡相关的计算问题上，比一般的表示Game的框架要容易得多[17].Clercq等人提出了一种基于析取回答集编程的求解纯策略纳什均衡的方法，并通过实验验证了该方法的有效性[18].2017年他们又给出了求一般布尔Game均衡解的方法.该方法基于析取回答集编程(ASP)并解出任何布尔Game的解，而且还扩展到了对带约束和成本的布尔Game求解[19].
本文则研究和计算了布尔Game核的求解问题，与已有的求核算法的主要区别在于:
1) 对比于Sauro等人的包含成本的求核方法，本文的布尔Game没有添加成本，是更加一般化的布尔Game.而且根据布尔Game的核与约束满足问题之间的关系，运用了布尔Game的超图形式简化了求解约束满足解的过程.
2) 对比于Clercq等人提出的判断布尔Game中是否存在核的方法，本文研究的是求布尔Game中的所有核.总的来说本文吸取了Bonzon等人的稳定集的概念[15]，将其求纳什均衡的方法扩展到布尔Game的核求解中，通过Agent间的依赖关系得到稳定集，再以稳定集分解布尔Game，从而简化了部分核的求解过程，提高了求解效率.
2 布尔Game的相关定义
本节对布尔Game的相关概念进行形式化描述，并统一了第3～5节中所用到的标记.
布尔Game是一种逻辑推理的框架，它通过使用命题公式来使Agent的理性行为形式化.本文给出如下定义:
定义1. 布尔Game.布尔Game是一个四元组G=(N,V,π,Φ).其中，N={1,2,…,n}表示n个Agent的集合;V={p1,p2,…}是一组原子命题，即决策变量的集合;π:V→N为控制赋值函数；Φ={φ1,φ2,…,φn}表示Agent所对应的目标公式.
控制赋值函数π将每一个决策变量映射到控制这个决策变量的Agent上.Agenti控制的所有决策变量记作πi={p∈V|π-1(p)=i}.每个决策变量有且只有一个Agent控制，即{π1,π2,…,πn}是决策变量集V的一个划分.上述中控制的意思是只有Agenti才可以设置π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. 效用函数.给定一个布尔GameG=(N,V,π,Φ).对于每个Agenti∈N和G的每个策略组合s，效用函数ui被定义为ui(s)=1当且仅当sφi，否则ui(s)=0.
定义5. 核core(G).策略组合s∈S被联盟C⊆N(C≠∅)阻塞，如果存在一个策略组合s′∈S使得：
于是布尔Game的核core(G)就包含不受任何非空的联盟C⊆N阻塞的策略组合s.
定义5也蕴含着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的目标分别是φ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上的关系，被称作约束关系.而CSP的解为一组满足所有约束的在X上的赋值.
定义7. 布尔Game的约束满足问题表示.给定一个布尔GameG=(N,V,π,Φ).布尔Game的约束满足问题表示CSP(G)=(V,{0,1},C)，其中∀i∈N,Ci=(RV(i),φi=1)，RV(i)表示Agenti的相关变量，其具体介绍参见定义11.
通过定义7可知，在布尔GameG中，Agenti的策略Si就是约束Ci的待定解集，只有满足约束关系ri的才是约束Ci的解，在布尔Game层次上就是Agenti为了满足目标所采取的策略.
例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的超图表示
超树树宽是专门为超图设计的一种环性的度量.约束可满足问题在结构上最合适的表示方式之一是与之相对应的超图[20].因此在CSP下的布尔Game可以通过超图结构表示.
定义8. 超图.超图表示为H=(P,HE)，其中P是顶点集，HE={e≠∅|e⊆P}是超边的集合，即每条超边是顶点集P的非空子集.
对于一个CSPI=(X,Y,C)，它相对应的超图表示为H(I)=(P,HE)，其中P=X，并且HE={var(S)|(S,r)∈C}，var(S)表示在约束C的约束范围S中的变量集合.那么给定一个布尔GameG=(N,V,π,Φ).根据定义7，G的超图表示为H(G)=(V,RV).其中布尔Game中的决策变量的集合V视为超图中的顶点集；RV是所有Agent的相关变量的集合，它被看做超图中的超边的集合.
对于布尔GameG的连接树J(G)，因为它属于宽度为1的超树分解，所以它的每个节点中都只有一条超边.而连接树中顶点的连接条件为：当2条超边h1和h2共同包含一个决策变量v时，在J(G)中h1和h2就可以被连通，而且v也一定会出现在连通h1和h2唯一路径上的每个节点中.换言之，在J(G)中包含v的所有节点可以诱导一棵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的目标是使公式φ1=p1↔p3为真，而Agent 2和Agent 3的目标分别是使φ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}.这是一个无环超图，所以根据连接树中顶点的连接条件可以得到一个超树分解，即连接树J(G3)，如图2所示，对于根节点φ3，(φ3)={p1,p2,p3}，λ(φ3)={e3}.
Fig. 1 The hypergraph structure of G3图1 G3的超图结构
Fig. 2 The join tree J(G3)图2 连接树J(G3)
4 Agent间的依赖关系
定义11. 相关变量，相关Agent.给定布尔GameG=(N,V,π,Φ).Agenti的相关变量RV(i)为φi中不能继续约简的原子变量的集合.i的相关AgentRA(i)={π-1(p)∈N|p∈RV(i)}.Agent上的依赖关系图是有向图DG=(N,R)，其中∀i,j∈N，如果j∈RA(i)，那么有向边(i,j)∈R.
Agenti的相关Agent是控制着Agenti的相关变量的一组Agent集合.布尔Game的依赖关系图为图(N,R)，其中顶点集合N对应于Agent的集合，并且R是所有有向边(i,j)的集合，其中∀i,j∈N，j∈RA(i)，即Agenti依赖于Agentj，R也是一种在N上的二元关系.R上的传递闭包记作TC，TC(i,j)表示在关系R上Agenti和Agentj之间是否存在一条路径，那么TC(i)就表示Agenti直接或间接依赖的Agent的集合.若依赖关系图DG上的一组Agent稳定，需要在关系R上闭合[15].
定义12. 稳定集.给定布尔GameG=(N,V,π,Φ).对于B⊆N，B是稳定集当且仅当R(B)⊆B，即∀i∈B，对于任意的Agentj使得(i,j)∈R，同时j∈B.
稳定集就是N的子集B，其中B中的Agent不依赖于B以外任何的Agent.R(B)表示∀i∈B，RA(i)⊆R(B).即集合B中所有Agent的相关Agent的集合.所以稳定集B的R(B)运算时在B上是闭合的.稳定集的概念最早是由Neumann等人于1953年提出的，它是一种策略标准，但是与本文中稳定集的概念是不同的[22].
引理1. 令C⊆2N，若存在布尔GameG使得C在G上是稳定的，需要满足以下4个性质:
1) ∅∈C;
2)N∈C；
3) 若B,B′∈C，则B∪B′∈C；
4) 若B,B′∈C，则B∩B′∈C.
通过引理1可知，稳定集在交、并运算上是闭合的.
命题1. 给定布尔GameG=(N,V,π,Φ)，∀i∈N，TC(i)一定是稳定集.
证明. 假设TC(i)不是稳定集，那么一定∃j∈TC(i)依赖于TC(i)以外的Agentk∈N，但是因为TC(i)是i所依赖的所有的Agent集合，若j依赖于k，则k∈TC(i).这与假设矛盾，所以命题成立.
证毕.
通过定义13可以看出，布尔Game在稳定集B上的映射GB中，Agent的目标是不包含稳定集以外的Agent所控制的决策变量，因此映射GB也是一个布尔Game.
如果布尔GameG上在B的映射GB的一个策略组合sB不是GB上的纳什均衡，那么在G中以sB为基础的任一策略组合s都不是G中的纳什均衡[15].同样地，本文将这样的结论推广到核的求解上.
命题2. 给定布尔GameG=(N,V,π,Φ)和一个稳定集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.于是对于相关变量，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的依赖关系图可以表示为：DG(G2)=(N,R)，其中R={(1,2),(2,1),(2,2),(3,1),(3,2),(3,3)}.所以G2的依赖关系图如图3所示：
Fig. 3 The dependencies between Agents of G2图3 布尔Game G2的Agent依赖关系
图3中从Agent 3到Agent 1有一个箭头，表示3依赖于1，即Agent 1是Agent 3的相关Agent.在G2中集合{1,2}是在R上除空集和N外唯一的稳定集.
5 布尔Game的核求解
本节对基于超树分解的无环布尔Game的可满足核的求解算法以及通过稳定集分解布尔Game的求核算法，进行了具体的算法描述和分析.
5.1 基于超树分解的布尔Game求核算法
通过第3节引入的在CSP下的布尔Game，本节采用超图的超树分解算法得到超树，即Gottlob等人提出的det-k-decomp算法[23].该算法可以在多项式时间内判断一个宽度为k的超树分解是否存在，而且如果存在这样的有界超树，可以通过递归构造出一个宽度为k的超树分解.因为本文研究的是超图上无环的布尔Game，所以需要构造一个宽度为1的超树分解，即一个连接树.得到的超树通过类数据库内连接查询的方式，求解满足布尔Game的约束满足问题的核，参见算法1.
算法1.traverseJoinTree(J(G),G,RV,S).
输入：布尔GameG=(N,V,π,Φ)、G中所有Agent的相关变量集RV；
输出：布尔Game约束满足问题下的解S.
①J(G)←det-k-decomp()；
②p←J(G)的根节点；
③ if(public←(RV(p)∩CV))≠∅
④Sp←Spublic×2RV(p)-public；
⑤ else
⑥Sp←2p；
⑦ end if
⑧Ss←∅；
⑨ for eachs∈Sp
⑩ ifsφp
第1步，算法1的行①～⑦，在递归的过程中获得当前结点的待验证策略集合Sp.Sp的存储结构类似于数据库的表，由决策变量和其对应的赋值组成，决策变量相当于数据表中的属性行，决策变量上的赋值相当于字段.该过程是依据引理2执行的.首先将J(G)的根节点赋值给中间变量p.CV是已生成并测试过的决策变量的集合.在生成当前结点的待验证策略之前，可以通过判断CV和RV(p)是否存在交集来减少该结点生成的待验证策略集的大小.CV和RV(p)存在交集就意味着当前结点中的一部分决策变量已经参与过生成待验证策略.所以可以在之前求得的结点目标可满足的解的基础上，只是生成在RV(p)中未和CV相交的部分决策变量.而因为连接树的构成特点，若之前的结点已经生成过策略，当前结点的决策变量和之前的结点的决策变量之间一定存在交集.具体过程可以参见5.4节的例5.
引理2. 一个合取范式是重言式，当且仅当它的每一个简单析取范式都是重言式.
对于布尔GameG的约束满足问题CSP(G)，根据引理2，对φ1∧φ2∧…∧φn=1的求解，可以转化为对每个Agent的目标单独求可满足解，最后通过内连接操作合并得到所有目标的解，即求得约束解的核.
算法1的目的是求解布尔Game的约束满足问题，即求φ1∧φ2∧…∧φn=1的解.通过建立布尔GameG上通过建立布尔GameG上的超图结构，然后超树分解得到连接树J(G)，在G的连接树J(G)上递归地遍历求得所有Agent都可满足的解.
5.2 基于稳定集的布尔Game分解求核算法
一般的穷举方法的求核算法是在所有Agent上生成所有的策略组合，然后调用函数1判断每个策略组合s是否满足核的定义.由于一般的穷举算法的时间复杂度是指数级的，所以在较大规模的布尔Game上求解是相当消耗时间的.所以本节根据稳定集分解布尔Game，可以将布尔Game的规模缩小，提高运算效率.
根据命题2的逆否命题，即如果sB∉core(GB)，那么s∉core(G)，可以通过稳定集分解布尔Game为规模更小的在原始布尔Game上的映射.通过这样的方法可以提前排除很多不必要的策略上的测试，产生待检测的子策略组合，从而缩小测试的策略范围.接下来根据命题2、命题1和定义12来设计算法2.
算法2的目的是通过稳定集分解布尔Game得到一些规模更小的布尔Game，然后从规模最小的布尔Game开始，在具有包含和被包含关系的布尔Game上迭代求核.这样就降低了核求解过程的策略测试范围，以此来提高求解布尔Game的核的效率.因为一个布尔Game可能存在很多规模不一的稳定集，所以算法2按照稳定集间的包含关系从规模最小的非空稳定集分解布尔Game，最后求得原布尔Game的核.算法2的详细描述如下：
算法2. 基于稳定集的布尔Game分解求核算法.
输入：布尔GameG=(N,V,π,Φ)、G中Agent间的依赖关系图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上存在的关系R的传递闭包的关系矩阵TC[24].然后根据命题1和引理1，由TC得到所有稳定集，对于TC(i)，其中i∈N.将这些稳定集和全集N写入稳定集的集合.得到的稳定集的集合按照从小到大的次序排序.
函数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
函数1的功能是检测布尔GameG中的一个策略组合是否符合核的定义，即对于当前策略组合，是否存在一个联盟所引起的另一个策略组合阻塞当前策略组合，若没有联盟阻塞当前策略组合，则该策略组合就是核，否则就不属于核.下面是对函数1的具体描述.2πC表示在联盟C上生成的策略组合，s-C表示联盟C以外的Agent的策略组合.首先生成联盟C，构成联盟的原则是目标未满足的Agent可以构成联盟；然后改变联盟C中Agent的策略，而保持C以外的Agent的策略不变，通过和2πC的笛卡尔积，构成新的策略组合SC；最后检测SC中是否存在策略组合s′阻塞s，即s′是否使联盟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是任意的一个联盟，S是G上的所有的策略组合.假设存在一个策略组合s′∈S，使联盟C以外的所有Agent在s和s′执行相同的决策，并且联盟C内的Agent在s′所得的收益比在s中的收益多.但是因为s是CSP(G)的解，也就是对于每个Agent的目标都会被满足，即φ1∧φ2∧…∧φn=1.而且本文的布尔GameG的收益是二元的，即非1即0.所以联盟C内的Agent在s′所得的收益最多和在s中的收益一样多，结论与假设和核的定义相互矛盾，因此Ss⊆core(G).
证毕.
一般求核问题可以看做产生策略和比较测试的过程，即先产生策略然后再比较检测该策略是否符合φ3∧φ1=1，如定义5所述.而算法1根据命题3，可以不必考虑比较检测的步骤,因此大大缩短了算法的时间复杂度.同样地，算法1也同样适用于布尔Game求纯策略纳什均衡.
定理1. 在最坏情况下，算法1的时间复杂度为O(|N|×2k)，其中k表示布尔Game目标中决策变量的最大值.
证明. 直观来看，在布尔GameG的超图结构的超树分解J(G)中，每个结点都需要生成它们的策略，即在每个Agent目标上生成策略，因为只有根结点能生成所有的策略，其他结点生成的策略是在之前结点的基础上完成的，所以第1个结点中目标的决策变量数在算法的运行效率上起决定性作用.那么最坏的情况就是根结点的目标中决策变量数最大且每个结点都包含这样的决策变量数k时，此时每个结点生成策略的时间复杂度是2k.最后需要在所有结点上生成策略，于是算法的复杂度为|N|×2k.
证毕.
定理2. 在最坏情况下，函数1的时间复杂度为O(2|VC|)，其中|VC|表示该策略中可以组成联盟中的决策变量数.
证明. 函数1的关键步骤是对新生成的带联盟的策略组合集SC进行逐个检测，而SC的个数就是2|VC|.所以在最坏情况下需遍历完整个SC，所以函数1的时间复杂度为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).
根据例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的超图结构
把每个Agent的目标所包含的决策变量视作一条超边，那么可以得到与HG4相对应的超树分解.因为HG4是无环超图，它的超树分解就是它所对应的连接图JT(G4)，如图5所示.
Fig. 5 The join tree on H(G4)图5 H(G4)生成的连接树
下面求解G4的属于约束满足解的核.根据算法1得到图6的执行过程,图6是从左到右执行的.详细描述如下：根据命题3，可以得到满足布尔GameG4中的φ1∧φ2∧φ3∧φ4=1的赋值一定是G4的核.1)根据G4的连接树结构，得到r3={(0,0,1),(0,1,1),(1,1,1)}，即满足φ3=1的赋值.2)生成和测试φ3的子结点φ1，根据命题3，在以上的结果中只需以r3的结果为基础连续生成和测试，那么生成决策变量a,b,c的策略是(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,1,0),(1,1,1).3)经过测试得到满足的策略集{(0,0,0,1),(0,0,1,1),(0,1,0,1),(0,1,1,1),(1,1,0,1),(1,1,1,1)}.同理，每个结点都需要在之前求得的结果上生成策略并进行测试，这在很大程度上降低了生成策略和测试的时间.每个结点都遍历过后得到满足φ1∧φ2∧φ3∧φ4=1的策略，也是G4的核，对应于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 执行过程的真值表
下面根据算法2求解布尔Game的全部核.根据Agent间的依赖图获得稳定集，得到小规模的布尔Game，在小规模的布尔Game中排除一些不是核的解.如图7所示，
RA
(1)={1,2}，
RA
(2)={1,2}.当
B
1
={1,2}时，
R
(
B
1
)={1,2}⊆
B
，所以
B
1
={1,2}是稳定集.同理，集合
B
2
={1,2,3}和
B
3
={1,2,4}是稳定集.所以
G
4
所有稳定集的集合
从小到大为{
B
1
,
B
2
,
B
3
,
N
}.
Fig. 7 Dependency graph among Agent of G4图7 G4中Agent间的依赖图
s-C)是否优于(0,0,0,0).比较得出(0,0,0,1)≻(0,0,0,0)，于是(0,0,0,0)被联盟C阻塞了，所以(0,0,0,0)不是GB1的核.和上述过程相同，对于其他的策略也需要被检验是否被某个联盟阻塞，进而得到核.于是最后得到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步执行过程
因为B1⊂B2，所以求解G4映射在B2上的子布尔GameGB2的核.此时根据命题2，通过core(GB1)×2π3得到GB2需要判断的策略集，2π3是π3上的解释.与求GB1的核的过程相同，遍历所有策略，在每个策略上生成联盟，再检测联盟是否阻塞该策略,具体的执行过程如表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步执行过程
因为B2B3且B2⊂N，所以最后求解布尔GameG的核.与求GB1的核的过程相同，通过core(GB2)×2f得到在G上的待验证策略集.然后遍历所有策略，在每个策略上生成联盟，再检测联盟是否阻塞该策略.具体的执行过程如表4所示.最终求得的布尔GameG的核对应于(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的最后一步执行过程
6 实验分析
本节对算法1、算法2和已有的求核算法进行实验对比，并进行相应的分析，来证明本文提出算法的有效性.由于布尔Game是新兴的框架，在实际中应用不多，数据较缺乏，所以本节采用随机生成的布尔Game来模拟数据，以此来验证本文给出的算法的效率.
6.1 随机生成布尔Game
本节构建了一个随机生成的布尔Game模型[19]，该模型可以根据需要构建适用于算法1的无环超图的布尔Game，也可以构造无特殊结构的布尔Game.
通过以下8个参数的约束下随机生成布尔Game：
1) Agent的数量|N|;
2) 每个Agent控制决策变量的数量b;
3) 目标中二元运算符(∨和∧)的最大值m;
4) 目标存在一个合取运算符的概率p(相反的是析取运算符);
5) 目标中决策变量取非的概率n;
6) 每个Agent是否包含至少一个自己所控制的变量(默认为否，以s表示);
7) 是否附加超图无环的约束(默认为否，以0表示);
8) 为保证每次运行程序时得到的布尔Game相同，设置seed.
按上述约束，设置参数|N|=5，b=2，m=3，p=0.5，n=0.5，seed=1，其他取默认值，生成的随机的布尔Game的数据格式如下：
①bgAgent 5
②a1p1p20
③a2p3p40
④a3p5p60
⑤a4p7p80
⑥a5p9p100
⑦ 1 (-p6& (p7;(p7;p9)))
⑧ 2 (-p8&p6)
⑨ 3 (p6;-p2)
⑩ 4 (p5;(p10;p7))
数据的行①以bg来表示一个布尔Game的开始，后面表示Agent的个数.行②～⑥格式相同，其中p1,p2,…,p10表示决策变量，a表示一个Agent的开始的标识，以行②为例，Agent 1控制的决策变量为p1和p2，最后都以0为该Agent的结束标识.而行⑦～格式相同，以行⑦为例开头的数字1表示Agent 1，后面便是Agent 1的目标，其中，“-”表示取否，“;”表示析取，“&”表示合取，即Agent的目标为p6∧(p7∨(p7∨p9)).
这里考虑的二元运算符只有合取和析取.因为根据蕴含等值等式A→B⟺A∨B和等价等值式A↔B⟺(A→B)∧(B→A)⟺(A∧B)∨(A∧B)，可以将目标中的蕴含符和等价符转换为只包含析取和合取的命题公式.为了使得随机布尔Game具有多样性，这里通过设置参数m把不同Agent的目标的长度设置一定的差异，并且对于每个Agent目标中的二元运算符的数量都在[1，m]区间.
6.2 实验环境和评估标准
本文的实验的环境为：计算机操作系统是Windows7 64 b，硬件内存为8 GB DDR 3，主频为3.2 GHz的i5-4700英特尔处理器.程序的实现通过C++程序语言实现.实验的数据是根据6.1节描述随机生成的模拟数据.
本文以算法的运行时间为算法效率优劣的评估标准,分别设置2组实验，即对算法1和算法2进行实验.1)在超图无环的布尔Game上对算法1和可满足性问题的穷举算法进行实验对比，来验证算法1的相对效率和影响算法效率的因素.2)在一般布尔Game上运用本文提出的算法2和一般的穷举算法进行实验对比，和检验不同参数对算法效率的影响.考虑到实验中影响实验结果的变量比较多，所以采用控制变量法进行实验对比.本实验的主要自变量为Agent的数量|N|、决策变量的数量|V|以及每个目标中存在的二元运算符的个数.为了降低特殊布尔Game对算法的影响和方便观察实验结果，每个自变量对应因变量的取值为不同的100个布尔Game运行时间的中位数的对数，时间的单位为毫秒(ms).而且为了防止程序运行时间过长，设置超时时间为5 min，无论是否求得核，只要超过5 min就终止程序.
6.3 布尔Game的约束满足求解实验
Fig. 8 Experiment of solving core of Boolean games with a constraint satisfaction solution图8 无环布尔Game求可满足核的实验
本节在存在约束满足解的无环布尔Game的数据集上进行实验，实验结果如图8所示.该实验对一般的穷举法、NashEvaluation算法[25]和算法1进行比较.这里的NashEvaluation算法是通过多次遍历超图的超树分解，最后通过半连接操作求得约束满足解的算法.以Agent的数量为自变量进行3组实验，每组实验分设不同的决策变量数和最多二元运算符数，纵向对比这2个参数对算法的影响.通过每个Agenti控制相同的决策变量数目|πi|来决定总的决策变量数|V|，目标φi中的决策变量数可以通过二元运算符的个数得到.分别设置(2,3)，(2,6)，(4,6)三组参数对进行实验，以参数对(2,3)为例，其中参数2表示每个Agent控制的决策变量数为2个，参数3表示每个Agent目标中最多包含的二元运算符的数目为3个.
通过图8的实验结果可以得出，在存在约束满足解的无环布尔Game中，算法1明显比一般的穷举法高效得多.穷举法和算法1的运行时间都随着Agent的数量的增加而增加，穷举法的运算时间变化比较剧烈的原因是它需要穷举出所有的策略组合，而这样的过程所耗的时间是指数级增长的.当决策变量的个数达到40时，穷举法就超出了5 min.反观算法1的曲线比较平滑，图8的(a)和(b)可以看出，算法1的时间复杂度和所有决策变量的数目的关系不大，而与目标中二元运算符的数目有关，即包含决策变量最多的目标有关系.所以一旦固定了二元运算符的数量，算法1就只受到Agent个数的影响，这也从实验的角度验证了定理1的正确性.与穷举法对比，算法1的效率较高是因为它考虑了每个Agent目标之间的关系，即不同Agent之间的相关变量存在相交的部分，而且通过超树分解，将所有的决策变量分解为更小的组，从而大大降低了策略生成的次数.
在NashEvaluation算法和算法1的比较中，可以发现本文提出的算法1比NashEvaluation算法更高效.这是因为NashEvaluation算法对超树进行了3次遍历并进行了半连接处理；而算法1只是对超树进行了一次的遍历，因为在这个过程中，每个结点被遍历时都是在先前结点计算得到的解上计算，这在一定程度上减少了策略的检测个数.而且可以发现，在中小规模的布尔Game中2个算法的效率相差不大，而在大规模的布尔Game求解中算法1相对较好.从图8的(a),(b)和(c)可以看到，NashEvaluation算法和算法1一样，都是受m和Agent个数N的影响比较大.需要说明的是图8中纵坐标中SCBG是“求解布尔Game的核”的缩写.
6.4 基于稳定集分解的布尔Game求核实验
本节在不存在任何限制的布尔Game的数据集上进行实验，测试算法2的效率.这里只在每个Agent上控制2个决策变量，目标中包含3个二元操作符的布尔Game上进行实验测试.
通过图9可得，对于2个算法，当Agent个数增加到30个，相应的决策变量数就增加到了60个，这时布尔Game的核的求解就到了一定的界限.但在30个Agent之前，算法2所达到的效果还是相对明显的，在一定程度上提高了计算核的效率.所以算法2只是适用于Agent的个数和决策变量的数目不太多的情况下，虽然在通过Agent间的依赖关系分解了原始布尔Game，但在局部的子布尔Game的求核算法中仍然是指数级的.对于剩余的待检测策略，在比较的过程中，每个策略需要的对比次数至少是2|V|.所以该算法只能适用于中小规模的无约束满足解的布尔Game求核.
Fig. 9 Experiment of solving core of general Boolean games图9 一般布尔Game求核实验
6.5 实验结论
通过6.3节、6.4节的实验分析，可以得出本文给出的算法1适用于求解超图无环布尔Game的约束满足解，算法1受Agent和对应相关变量(目标中的决策变量)的影响比较大，而跟整个决策变量集的大小无关.当相关变量数固定时，算法1与Agent数属于线性关系；当Agent数固定时，算法1与最大相关变量是指数关系.实验证明这种将布尔Game的决策变量集通过目标分解的方法，大大降低了生成策略组合的过程，从而提高了求核的效率.并且在与NashEvaluation算法的比较中，算法1在大规模的布尔Game的可满足核的求解上相对高效.
算法2适用于中小规模的布尔Game，规模是指布尔Game的Agent数量和决策变量数的大小.通过稳定集分解布尔Game的方法，在一定程度上降低了求核的运行时间，但是也存在弊端，就是当布尔Game规模过大时，被分解得到的子布尔Game规模虽然相对于较小，但规模相对于一般问题还是过大.所以该算法对于中小规模的布尔Game是适用的.
7 结论和未来工作
本文主要研究了2个问题:1)求解布尔Game的可满足性问题的解；2)求解布尔Game的所有核.在问题1上引入约束满足问题的超图表示，对于有无环超图的布尔Game，利用超树分解来降低求可满足解的可行空间，给出了基于超树分解的求布尔Game可满足解的算法，该算法在很大程度上缩小了问题的规模，提高了求解效率.在问题2上通过Agent间的依赖关系图得到稳定集，利用稳定集分解布尔Game来降低求核的可行空间，给出了基于稳定集分解的布尔Game求核算法，提高了求解核的效率.最后以随机生成的布尔Game实验验证了上述2种算法的有效性.
本文的未来工作包括：
1) 将Agent间的依赖关系加入到布尔Game的超树分解中，将超图的结构更接近于布尔Game，研究该结构的核求解问题，找到高效率的核求解算法.
2) 在布尔Game的超图表示中，研究在超图的超树分解的树宽大于等于2时，布尔Game的核求解方法.
3) 在执行决策变量时将单个Agent的操作细分化，将税收、决策变量的约束关系、成本加入到布尔Game中，使得更贴近现实中的博弈.
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.
