论文部分内容阅读
结构化博弈(Structured Games)是新的博弈模型.图型博弈(Graphical Game)、多Agents影响图(Multi-Agent Influence Diagrams)是两种重要的结构化博弈表示模型.求解Nash均衡是结构化博弈模型的核心问题.该文着重研究了图型博弈上Nash均衡求解的相关问题,并对多Agents影响图模型中决策节点策略相关图的生成进行了研究.首先,该文讨论了在τ-离散化的策略空间中,近似Nash均衡的近似度问题.J.Nash证明了在连续的策略空间中Nash均衡的存在性,而在连续空间中求解精确的Nash均衡往往是代价高昂的.将Agent的策略空间按一定的精度τ进行离散化,使得我们可以在一个有限的离散空间中讨论Nash均衡的求解问题,降低了处理问题的复杂程度.但从连续空间到离散空间,由此带来的结果是我们不一定能得到精确的Nash均衡,而可能只获得一定近似度ε的近似Nash均衡.那么给定一个精度τ,在离散空间中,我们至少能获得近似度ε为多少的近似Nash均衡呢?该文给出了一个结论一图型博弈中,在给定博弈模型图形结构、一定的精度τ的前提下,离散空间中至少存在某一相应近似度ε的近似Nash均衡.其次,我们把求解图型博弈的Nash均衡看作是连续空间中的函数优化问题.定义了优化的目标函数,函数的最优解就是Nash均衡.给出了优化目标函数的两个算法.第一,求解Nash均衡的迭代爬山算法.迭代爬山算法是一个局域搜索算法.算法随机生成一个初始策略剖面作为初始解,并用相应评分函数对初始解打分.给定初始解,算法利用博弈的图形结构所反映出的Agents策略的效用独立关系,对初始解进行多策略更新,获得更好评分值的策略剖面,并将获得新剖面作为算法下一轮迭代的初始解.算法不断迭代,直至满足算法终止条件,输出相应结果剖面,作为算法最终解.第二,遗传算法.迭代算法收敛速度快,但我们也同时注意到由于迭代算法是局域搜索算法,算法最终输出的结果可能只是一个局部最优解(一个近似Nash均衡)而非全局最优解(精确Nash均衡),因此,我们又提出了一个求解图型博弈Nash均衡的遗传算法.该算法收敛速度比迭代算法慢,但收敛到精确Nash均衡的概率比迭代算法要大,输出解的质量较高.最后,策略相关图是多Agents影响图上,求解Nash均衡所涉及到的重要的数据结构.利用判定贝叶斯网中随机节点间条件独立关系的Bayes-ball算法,我们构造出多Agents影响图的策略相关图.