ISSN 1000-1239 CN 11-1777/TP

• 人工智能 •

布尔Game的核求解算法

1. (烟台大学计算机与控制工程学院 山东烟台 264005) (bob8190@163.com)
• 出版日期: 2018-08-01
• 基金资助:
国家自然科学基金项目(61572419,61773331,61703360)；山东省高等学校科技计划项目(J17KA091) This work was supported by the National Natural Science Foundation of China (61572419, 61773331, 61703360), and the Project of Shandong Province Higher Educational Science and Technology Program (J17KA091).

An Algorithm for Computing Core of Boolean Game

Wang Bo， Liu Jinglei

1. (School of Computer and Control Engineering, Yantai University, Yantai, Shandong 264005)
• Online: 2018-08-01

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.