高级检索
    王博, 刘惊雷. 布尔Game的核求解算法[J]. 计算机研究与发展, 2018, 55(8): 1735-1750. DOI: 10.7544/issn1000-1239.2018.20180360
    引用本文: 王博, 刘惊雷. 布尔Game的核求解算法[J]. 计算机研究与发展, 2018, 55(8): 1735-1750. DOI: 10.7544/issn1000-1239.2018.20180360
    Wang Bo, Liu Jinglei. An Algorithm for Computing Core of Boolean Game[J]. Journal of Computer Research and Development, 2018, 55(8): 1735-1750. DOI: 10.7544/issn1000-1239.2018.20180360
    Citation: Wang Bo, Liu Jinglei. An Algorithm for Computing Core of Boolean Game[J]. Journal of Computer Research and Development, 2018, 55(8): 1735-1750. DOI: 10.7544/issn1000-1239.2018.20180360

    布尔Game的核求解算法

    An Algorithm for Computing Core of Boolean Game

    • 摘要: 布尔Game是一种重要的多Agent合作求解框架,它利用命题逻辑来表达静态的Agent博弈场景.其中每个Agent的目标采用命题公式来表示,其目标是否满足取决于命题公式的赋值.目前布尔Game多从知识表示角度和纳什均衡计算的角度来研究,从联盟角度研究核的求解却不多.布尔Game求核是生成策略组合然后在策略组合内对比的过程.首先,通过以布尔Game的决策变量为顶点、以目标为超边,构成布尔Game上的超图结构来求满足核的约束满足的解.其次,以Agent为顶点、以Agent间的依赖关系为边构成的有向依赖图,可以将布尔Game根据稳定集分解为规模上更小的布尔Game.这2种结构简化了求核的生成过程和比较过程,进而在一定程度上提高了布尔Game求核效率.然后基于超图的超树分解和依赖图的稳定集分解,给出了不同的布尔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.

       

    /

    返回文章
    返回