布尔Game的核求解算法  

An Algorithm for Computing Core of Boolean Game

作　　者：王博 刘惊雷 Wang Bo;Liu Jinglei(School of Computer and Control Engineering,Yantai University,Yantai,Shandong 26400)

机构地区：[1]烟台大学计算机与控制工程学院,山东烟台264005

出　　处：《计算机研究与发展》2018年第8期1735-1750,共16页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61572419;61773331;61703360);山东省高等学校科技计划项目(J17KA091)~~

摘　　要：布尔Game是一种重要的多Agent合作求解框架,它利用命题逻辑来表达静态的Agent博弈场景.其中每个Agent的目标采用命题公式来表示,其目标是否满足取决于命题公式的赋值.目前布尔Game多从知识表示角度和纳什均衡计算的角度来研究,从联盟角度研究核的求解却不多.布尔Game求核是生成策略组合然后在策略组合内对比的过程.首先,通过以布尔Game的决策变量为顶点、以目标为超边,构成布尔Game上的超图结构来求满足核的约束满足的解.其次,以Agent为顶点、以Agent间的依赖关系为边构成的有向依赖图,可以将布尔Game根据稳定集分解为规模上更小的布尔Game.这2种结构简化了求核的生成过程和比较过程,进而在一定程度上提高了布尔Game求核效率.然后基于超图的超树分解和依赖图的稳定集分解,给出了不同的布尔Game的求核算法.最后实验验证了算法的有效性.Boolean game is an important framework to compute the solution of multi-agent cooperation, which represents the static agent games scenario based on propositional logic. In Boolean games, every agent uses propositional formulas to represent its goals, so whether its goals can be satisfied depending on the propositional formulas’ truth value. At present, Boolean game is mainly studied from the knowledge representation perspective and solving pure Nash equilibrium, but computing core from coalitional view is not enough. Computing core of Boolean games is the procedure of generating strategy profiles and comparing with strategy profiles. Firstly, in order to solve the solution of constraint satisfaction problem of Boolean games, we structure hypergraph on Boolean games where the action variables are regarded as the vertices and the goals are regarded as the hyperedge. Secondly, we see agents as the vertices and the dependence relationship between agents as edge to structure a directed dependency graph, which can get a set of stable sets to decompose Boolean games as smaller Boolean games on the scale. These two structures simplify the generation process and comparison process, and then improve the efficiency of computing core of Boolean games to some extent. Then, based on the hypertree decomposition and the stable set decomposition of the dependent graph, we give different methods of computing core of Boolean game. Finally, we verify the validity of this algorithm through the experimental evaluation.

关 键 词：布尔Game 核求解 约束可满足问题 超图 超树分解 稳定集 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]