基于CP-nets的多Agent定性博弈

Game playing based on preference has a very important meaning for agent rational decision making, it can be used widely in artifical intelligence, database system and distributed computing areas. In this project, we study structure properties of CP-nets (conditional preference networks), Nash equilibrium and strong Nash equilibrium compelxity for qualitative game playing. Firstly, algebra structure and its properties of CP-nets are studied based on algebra lattice theory, some special structure CP-nets can express total order and weak order, whereas they can not express lexicographic order; Secondly, by leveraging the conjunctive query technique, we prove that the Nash equilibrium complexity of acyclic CP-nets and bounded hypertree width CP-nets are LOGCFL (logspace-reducible to context-free language). Furthermore, we can construct the Nash equilibrium on cyclic CP-nets by the cycle cut set decomposition technique. All the research results show that some specific CP-nets can be converted into quantialitive game model. More importantly, solving the Nash equilibrium of bounded hypertree width CP-nets not only is hightly parallelizable, but also guarantees the stability for multi-agents cooperation.

基于偏好的博弈论对Agent的理性决策具有重要意义，它可广泛使用在人工智能，数据库系统及分布式计算等场景中。本项目以CP-nets (conditional preference networks，条件偏好网)作为定性博弈模型，研究该图模型的结构特性，以及对纳什均衡复杂度的影响问题。首先利用代数格理论证明完全CP-nets可构成代数格，特殊结构CP-nets可表达全序和弱序关系，但不能表达词典序；其次利用数据库理论中的合取查询技术，证明无环CP-nets纳什均衡的复杂度为LOGCFL，并基于环割集分解技术给出带环CP-nets上的纳什均衡解的构造方法。研究结果表明，作为一种定性偏好模型，一些CP-nets所表达的序可转化为定量偏好来求解。更重要的是，有界超树宽度CP-nets上的纳什均衡求解不仅是可高度并行化，而且保障了多Agent的合作是稳定的。

现实世界的许多决策问题，以及许多机器学习的优化问题都可归结为多agent的博弈问题，以及多agent学习问题。本项目以CP-nets (conditional preference networks，条件偏好网)以及其扩展的偏好模型为基础，研究其定性结构，定量结构和定性结构的关系，CP-nets结构对纳什均衡复杂度的影响问题，以及如何设计机器学习中的算法优化问题。其研究结果为：（1）有界树宽CP-nets上的占优查询，有界树宽布尔game的纳什均衡问题是多项式时间可求解，且联盟的稳定性概念例如核，可利用超树分解方法来实现；（2）CP-nets偏好模型上的推理问题和学习问题紧密相关。当利用信息论的统计计数获取了决策变量之间的依赖关系后，则CP-nets的全局结构可通过消除环的顶点反馈集方法来获得；（3）当从定性偏好转为定量偏好后，许多类型数据，如文本，图像，语音，视频等，都可以看作偏好数据，因此典型的机器学习问题可规约为偏好模型上的学习和推理问题；（4）分析了一类重要的优化方法ADMM（alternating direction method of multiplier，交替方向乘子法）的本质特征和求解过程。阐述了ADMM本质上是多agent的偏好博弈问题，其每一个优化目标或者约束函数可看作一个agent，目标和约束的个数可看做agent的个数，因此ADMM算法的本质是寻求一个纳什均衡解，即在各个agent资源受限情况（如目标函数不同，变量取值范围不同）下，寻求各个agent都会满足各自局部最优的一个赋值；（5）为了解决大规模agent博弈的高复杂度的推理和学习问题，本项目利用了矩阵近似分解方法和随机采样优化方法，来获取agent的潜在偏好，以及agent偏好的低秩结构。这在一定程度上可解决，偏好博弈模型下的大规模agent偏好矩阵的近似问题，为解决大规模agent的纳什均衡解奠定了基础。