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

Abstract: 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.

Key words: Boolean game, computing core, constraint satisfaction problems, hypergraph, hypertree decomposition, stable set