APP下载

求解两人博弈纳什平衡问题的定制临近点算法

2018-03-08江彬倩庄杰鹏

福州大学学报(自然科学版) 2018年1期

彭 拯, 江彬倩, 庄杰鹏

(福州大学数学与计算机科学学院, 福建 福州 350116)

0 引言

自从Nash[1-2]对非合作博弈提出了一种被称为纳什平衡解的概念之后, 如何找到非合作博弈的纳什平衡已成为一个非常经典的问题. 纳什平衡问题是经济学与管理科学的基础, 在计算机工程、 生物信息学等各个领域也有着广泛的应用[3-5].

本研究考虑一个简单博弈问题: 有两位局中人A和B, A控制变量x∈X⊂n, B控制变量y∈Y⊂m, A和B的支付函数分别是uA(x,y)与uB(x,y). 注意到, 局中人的支付函数不仅与自身的决策有关, 还依赖于对手的决策. 出于自私性原则, 假定每位局中人以极小化自己的支付函数为目标, 且两位局中人轮流决策. 那么, 这个简单博弈可以数学地描述如下.

然后,B通过求解下列问题得到当前情况下的最优策略

由纳什平衡的定义知, 偶对w*=(x*,y*)是上述博弈的一个纳什平衡解当且仅当

x*=arg min{uA(x,y*)|x∈X},y*=arg min{uB(x*,y)|y∈Y}

针对这种博弈问题, 常见的求解算法包括正则化Gauss-Seidel算法[6], 基于Gauss-Seidel格式的直接迭代算法[7], 基于Nikaido-Isoda目标函数松弛的迭代算法[8], 信赖域算法[9], 等. 特别地, 针对两人非合作博弈问题,Antipin[10]提出了求纳什平衡点的外梯度法.Zhang等[11]借助预测-校正的思想, 通过投影算法获得博弈的广义纳什平衡点.Han等[12]对文献[11]的算法进行修正, 提出了一种改进的两步投影算法, 通过改进校正步的迭代方向来使投影算法更快地收敛.Peng等[13]将两人轮流博弈问题建模成变分不等式组, 在预测-校正过程中利用非精确的临近点交替方向法(InPDA)求得纳什平衡点. 卢……

登录APP查看全文