(烟台大学计算机与控制工程学院 山东烟台 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(School of Computer and Control Engineering, Yantai University, Yantai, Shandong 264005)
Online:
2018-08-01摘要/Abstract
摘要: 布尔Game是一种重要的多Agent合作求解框架,它利用命题逻辑来表达静态的Agent博弈场景.其中每个Agent的目标采用命题公式来表示,其目标是否满足取决于命题公式的赋值.目前布尔Game多从知识表示角度和纳什均衡计算的角度来研究,从联盟角度研究核的求解却不多.布尔Game求核是生成策略组合然后在策略组合内对比的过程.首先,通过以布尔Game的决策变量为顶点、以目标为超边,构成布尔Game上的超图结构来求满足核的约束满足的解.其次,以Agent为顶点、以Agent间的依赖关系为边构成的有向依赖图,可以将布尔Game根据稳定集分解为规模上更小的布尔Game.这2种结构简化了求核的生成过程和比较过程,进而在一定程度上提高了布尔Game求核效率.然后基于超图的超树分解和依赖图的稳定集分解,给出了不同的布尔Game的求核算法.最后实验验证了算法的有效性.
参考文献
相关文章 6
[1] | 于亚新, 张文超, 李振国, 李莹. 基于超图的EBSN个性化推荐及优化算法[J]. 计算机研究与发展, 2020, 57(12): 2556-2570. |
[2] | 郭彩华,王斌,朱怀杰,杨晓春. 增量的动态社会网络匿名化技术[J]. 计算机研究与发展, 2016, 53(6): 1352-1364. |
[3] | 王艺源,欧阳丹彤,张立明,张永刚. 利用CSP求解极小碰集的方法[J]. 计算机研究与发展, 2015, 52(3): 588-595. |
[4] | 宋金玲, 刘国华, 黄立明, 朱彩云,. k-匿名方法中相关视图集和准标识符的求解算法[J]. , 2009, 46(1): 77-88. |
[5] | 郝忠孝, 顾照鹏,. 无内部冲突数据库模式满足P\-3及无β环判定问题研究[J]. , 2008, 45(6): -. |
[6] | 刘越畅 姜云飞 钱 红. 基于问题结构的启发式策略在析取时态问题求解中的应用[J]. , 2008, 45(11): 1840-1849. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3752