论文部分内容阅读
博弈论在多Agent系统中常用来研究理性并且自利的Agent之间的交互,特别是如何设计交互策略使得整个系统稳定并且尽可能使每个Agent收益最大化。近年来,布尔Game作为新兴的博弈表示框架为分析多Agent系统提供了新的思路。布尔Game是一种逻辑推理的表示方法,它通过命题逻辑来使Agent的理性行为形式化,其中每个Agent都唯一控制一组变量,而且有一个它试图满足的目标,这个目标由命题公式表示。布尔Game不仅运用于模型表示,而且也被应用到了一些实际的场景中,比如交通信号灯的协调、电动汽车充电、项目分配以及自动化控制等。本文研究了布尔G am e的主要研究方向——均衡策略的求解问题,均衡策略主要涉及纳什均衡(Nash equilibrium)和核(The core)。布尔Game下稳定策略求解问题的研究主要集中在非联盟博弈下的纳什均衡,而联盟博弈下核的研究不多,所以本文主要着眼于不同约束场景下核求解算法的研究。核的本质是一组策略组合的集合。对于一个策略组合,如果任何由Agent组成的联盟都不会脱离这个策略组合,那么这个策略组合就属于核。判断布尔Game中核是否非空的(non-empty)问题是∑2P完全问题,显然核的求解过程是典型的非确定性决策问题,包括生成策略和测试策略的两个子过程。因此,优化核的求解算法就是降低这两个子过程搜索空间的过程。本文的目标之一是通过特定的(超)图约束来降低搜索空间求核。第1种方法是首先将布尔Game转换成约束满足问题(CSP),依照的变量不同可以转换成不同的约束满足问题,进而得到布尔Game上的超图结构,(1)根据Agent的目标中所包含的决策变量为顶点构建超图;(2)根据Agent之间的依赖关系构建超图。然后在无环和有界超树宽度约束下的布尔Game上设计了基于超树分解的有效并且高度并行化的求核算法。第2种方法是首先根基Agent见的依赖关系构建有向图,然后根据稳定集分解依赖关系图进而得到子布尔Game,从而在一定程度上降低求解空间。另一个目标是对核的性质深入一步研究。根据是否受成本函数影响核的稳定性,得出了一种不受成本约束的核——硬核。然后给出了硬核的基本性质,硬核是使社会福利最大化的解而且具有唯一性。最后,将求解硬核的问题转化成基于Agent间依赖关系的约束满足问题,给出了基于超树分解求解硬核的算法并实验验证了其有效性。