一种面向多Agent交互的博弈Nash均衡求解方法  

A Method for Solving Nash Equilibrium of the Game Oriented to Multi-agent Interactions

作　　者：李劲[1] 岳昆[2] 刘惟一[2] 

机构地区：[1]云南大学软件学院软件工程系,昆明650091 [2]云南大学信息学院计算机科学与工程系,昆明650091

出　　处：《计算机科学》2007年第3期181-185,共5页Computer Science

基　　金：云南大学科研项目(No.2005Q023C;2004Q024C);云南省自然科学基金项目(No.2005F0009Q)。

摘　　要：现有的图型博弈Nash均衡求解方法基本是在离散化剖面空间中搜索求解,最终只能得到近似Nash均衡。针对现有求解方法存在的不足,把求解图型博弈的Nash均衡看作是连续策略空间中的函数优化问题,定义Agents在策略剖面中的效用偏离度之和为优化目标,其最优解就是博弈的Nash均衡。本文基于对实例的分析指出目标函数下降梯度的计算可归结为一组线性规划,进而提出一种求解图型博弈Nash均衡的新型梯度下降算法。算法分析及实验研究表明,对于多Agent交互模型中的相关问题,本文提出的方法可求解任意图结构图型博弈Nash均衡,对于大规模图型博弈也有较好的求解精度和求解效率。Among the existing methods for computing the Nash Equilibrium of graphical games, agents play discretized mixed Strategies. Consequently, only an approximate Nash Equilibrium can be achieved. In this paper, we induce the problem of obtaining an exact Nash Equilibrium into a generic function optimization in a space of continuous strategies. Meanwhile, the objective is defined as the summation of utility regret in strategic profiles, and its corresponding optimized solutions are achieved as Nash equilibrium. Thus, the gradient descent of objective function can be calculated through a set of linear program. Further, a gradient descent algorithm to find exact Nash Equilibrium of Graphical Game with any structure is presented. Our proposed method can be used to get the exact Nash equilibrium of graphical games with arbitrary structures. As well, our method has fairly good precision and efficiency even on the large-scaled graphical games.

关 键 词：多Agent交互模型 图型博弈 NASH均衡 线性规划 梯度下降算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]