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

彭 拯, 江彬倩, 庄杰鹏

(福州大学数学与计算机科学学院, 福建 福州 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)求得纳什平衡点. 卢延杰等[14]针对多个局中人参与的博弈提出了类似的算法.

上述这些算法均运用了预测和校正两个步骤来求解博弈问题. 其中校正步可以看成当所有局中人都给出策略之后, 有“第三只手”对他们的策略进行了一次微调. 但是, 出于竞争的公平性考虑, 许多实际情况下的博弈并不允许校正. 针对这种不允许校正博弈的纳什平衡问题, 提出一种不带校正步的定制临近点算法, 并在一定条件下证明了算法全局收敛到纳什平衡点.

全文通篇做如下假设:

假设1 局中人的支付函数uA(x,y)与uB(x,y)都是自身控制变量的可微凸函数, 即: 对于任一固定y∈m,uA(x,y)是x∈X可微凸函数; 对于任一固定的x∈n,uB(x,y)是y∈Y可微凸函数.

记g(x,y)=xuA(x,y),h(x,y)=yuB(x,y). 由假设1, 任意给定y∈m,g(x,y)关于x∈X单调. 同样, 任意给定x∈n,h(x,y)关于y∈Y单调. 根据单调性, 有:

(1)

假设2 决策集X⊂n,Y⊂m是简单有界闭凸集.

在上述假设条件下, 两人博弈的纳什平衡解等价于下列变分不等式组的解:

(2)

这种等价性提示人们, 借助变分不等式的求解方法来计算博弈的纳什平衡点是一种可行的途径[15]. 在众多的求解变分不等式的方法中,He等[16]提出的定制临近点算法 (CPPA) 适用于本文所考虑的博弈问题. 对于线性约束凸优化问题

(3)

定制临近点算法的每一轮迭代包含如下两步:

预测步：

其中：L(x,λ)=θ(x)-λT(Ax-b)为Lagrange函数,λ为Lagrange乘子.

校正步： 定义w=(λ,x),

(4)

受上述算法的启发, 提出一种定制临近点算法, 用以计算前述轮流博弈问题的纳什平衡. 从已知的信息(xk,yk,yk-1)出发, 算法通过求解如下优化问题获得当前策略(xk+1,yk+1)：

这种算法可视为定制临近点算法在博弈论中的应用. 由于算法不带任何校正操作, 它适用于模拟一些不允许校正的实际博弈活动.

1 算法描述及收敛性分析

给出一种求解两人轮流博弈纳什平衡问题的不带校正步的CPPA算法, 然后对算法的全局收敛性进行分析.

算法 1： 求解两人轮流博弈的定制临近点分裂算法, 简记为CPPA.

S0) 初始化. 令ε>0,r,s>0. 对于任意给定的初始局势(x0,y0), 局中人B通过求解下列问题得到y1∈Y：

〈y-y1,h(x0,y1)+s(y1-y0)〉≥0， ∀y∈Y

S1) 迭代计算. 对于给定的(xk,yk,yk-1), 局中人A和B分别求解如下变分不等式, 先后得到当前情况下的最优策略xk+1∈X和yk+1∈Y:

(5)

记W=X×Y,

则式(5)可以写成如下的紧凑形式: 求wk+1∈W, 使得

〈w-wk+1,D(wk+1,wk,wk-1)+G(wk+1-wk)〉≥0, ∀w∈W

(6)

为了保证算法的收敛性, 作如下假设：

假设3 若w*=(x*,y*)∈W是博弈的一个纳什平衡点, 则

(7)

假设3是必要而且合理的. 根据纳什平衡的经济学意义, 任何一个局中人离开平衡状态都会使得所有局中人受到损失, 但在博弈中单方面离开平衡状态则应该受到惩罚, 上述假设正好体现了这种惩罚. 具体来说, 式(7)中的第一个不等式表示若局中人A单方面离开平衡状态,则A将受到惩罚,与A保持平衡状态而对手B离开平衡状态的情况相比较,A的边际损失将更大； 第二个不等式表示若局中人B单方面离开平衡状态,则B将受到惩罚,与B保持平衡状态而对手A离开平衡状态的情况相比较,B的边际损失会更大. 该条件保证了所有局中人为保持利益最大化,尽量保持在平衡状态,没有单方面离开平衡状态的动机.

引理1 对于给定的(wk,wk-1), 设wk+1是由算法CPPA所产生的新迭代点, 若w*=(x*,y*)∈W是博弈问题的一个纳什平衡点, 则

〈wk+1-w*,D(wk+1,wk,wk-1)〉≥0

(8)

证明 由g(x,y)和h(x,y)的单调性, 将(x′,y′)=(xk+1,yk+1)代入式(1), 得到

(9)

将(x,y)=(2xk+1-xk, 2yk-yk-1)代入式(9), 可得

(10)

再将(x,y)=(x*,y*)代入式(9), 可得

(11)

式(10)和式(11)相加, 得到

(12)

把(x,y)=(xk+1, 2yk-yk-1)代入式(7) 的第一个不等式, 再把(x,y)=(2xk+1-xk,yk+1)代入式(7) 的第二个不等式, 得到

(13)

结合式(2)、 (12)和(13), 直接得到式(8). 证毕.

定理 1 设{wk}是由算法CPPA所产生的序列, 若w*是所考虑博弈的一个纳什平衡点, 则

(14)

证明 令w=w*, 由式(6)可得

〈w*-wk+1,G(wk+1-wk)〉≥〈wk+1-w*,D(wk+1,wk,wk-1)〉

根据引理1有：

〈w*-wk+1,G(wk+1-wk)〉≥0

(15)

所以

结合式(15)直接可得式(14). 定理得证.

定理 2 由算法CPPA产生的序列{wk}收敛到所考虑博弈问题的纳什平衡点.

证明 将不等式(14) 相加可得

(16)

于是

同时{wk}是有界序列, 因此收敛. 设w∞是序列{wk}的一个聚点, 且子序列{wkj}收敛于w∞. 将wk=wkj,wk+1=wkj+1代入式(6)得到

〈w-wkj+1,D(wkj+1,wkj,wkj-1)+G(wkj+1-wkj)〉≥0, ∀w∈W

〈w-w∞,D(w∞,w∞,w∞)〉≥0, ∀w∈W

因此,w∞是变分不等式(2)的解, 也是博弈问题的纳什平衡点.

另一方面, 由式(14) 可得

(17)

(18)

所以, 对于任意k≥kj, 由式(17) 和式(18) , 得到

即序列{wk}收敛于w∞. 证毕.

受文献[17] 的启发, 如果局中人对其对手的本轮策略与上一轮策略采用可变权重α, 可将算法CPPA中的迭代计算步 S1 进行简单修正, 得到推广算法如下.

算法 2： 算法推广, ECPPA.

S1. 迭代计算: 对于给定的(xk,yk,yk-1), 局中人A和B通过求解如下变分不等式, 先后获得当前情况下的最优策略xk+1和yk+1:

(19)

变分不等式组(19)可以写成如下紧凑形式

∀w∈W

其中

简单变形可知

其中: Δxk=xk+1-xk(分别地, Δyk-1=yk-yk-1) 为局中人在前后两轮博弈中决策的改变量. 参数α刻画了局中人对其对手的策略变化情况的重视程度. 在模拟计算中, 适当选取α的值能够加快算法的收敛速度. 当α=0时, 每个局中人只考虑对手当前的决策yk(分别地,xk+1), 算法ECPPA还原成原始的临近点分裂算法; 当α>0时, 每个局中人不仅考虑对手当前的决策, 还考虑了对手的改变量Δyk-1(分别地, Δxk); 当α=1时, 算法ECPPA 还原为算法 CPPA. 因此, 由于采用了可变权重α, 算法ECPPA体现了局中人对其对手前后两轮决策一致性的重视程度和博弈的主观性.

当α>0时, 采用与CPPA完全相同的分析方法, 可以证明算法ECPPA的全局收敛到所考虑博弈的纳什平衡点.

2 数值实验

采用数值实验来说明算法CPPA和ECPPA的有效性. 为了保证公平, 所有实验均用Matlab2013a编程, 在Asus笔记本电脑上运行.

例1 考虑一个N=2的双寡头垄断模型[18-19]. 局中人i控制变量xi∈,i=1, 2. 支付函数为

θi=xi(ρ(x1+x2)+λ-d) (i=1, 2)

其中：xi∈[-10, 10];ρ=1;λ=4;d=20. 该博弈的纳什平衡为(16/3, 16/3)T. 选取相同的初始点, 用算法InPDA[13]、 算法CPPA 和算法ECPPA 进行计算. 在所有测试算法中, 设定r,s=2.4, 停止条件为ek≤ε=0.5×10-5, 其他参数设置为:γ=1.6,α=1.3. 随机选取初始点(x,y)T=rand(2, 1)T, 进行100次随机实验, 将算法的平均迭代次数, 平均函数值计算次数及所获得的解列于表1.

表1 例1数值结果Tab.1 Numerical results of example 1

由上表可知, 算法CPPA和ECPPA的迭代次数几乎与算法InPAD 相同, 且都收敛到纳什平衡点, 但算法CPPA与ECPPA 的函数值计算次数约为算法InPAD的一半.

例2 该例取自文献[20-21]. 设两个局中人 A 和 B 轮流博弈, 他们从[0, 10]中先后选取一个数x和y, 要求x+y≤15, 使得下列支付函数最小:

该博弈的纳什平衡点为(5, 9)T和线段[(9, 6)T, (10, 5)T]上所有的点. 采用与例1同样的3种算法计算, 从不同的初始点出发, 所有算法在相同的终止条件下获得相同的纳什平衡点(5.000,9.000)T. 3种算法的迭代次数与函数值计算次数列于表2.

表2 例2数值结果Tab.2 Numerical results of example 2

由表2可知, 算法CPPA的迭代次数几乎是InPDA的两倍, 函数计算次数也接近InPDA. 而算法ECPPA 的迭代次数接近InPDA, 但函数计算次数大约是InPDA的一半. 这说明对于该算例, 算法ECPPA比算法CPPA与InPAD效率更高.

3 结语

为了保证公平性, 实践中的许多博弈往往不允许校正, 针对不允许校正的两人轮流博弈提出了一种计算纳什平衡点的定制临近点分裂算法(CPPA). 在算法CPPA中, 局中人综合考虑对手当前决策和前后两轮决策的改变量, 通过极小化自己的支付函数进行决策. 在一定的条件下证明了算法CPPA全局地收敛到所考虑博弈的纳什平衡点. 同时对算法CPPA进行推广, 对局中人的对手前后两轮决策的改变量引入可变权重α>0, 得到推广的不带校正运算的定制临近点分裂算法 (ECPPA). 数值实验结果表明, 在所有算法都得到纳什平衡点的条件下, 不带校正的算法CPPA与ECPPA的迭代次数接近带有校正的算法InPDA, 而函数计算次数也相对减少, 其中算法 ECPPA的计算效率相对更好. 因此, 该算法是一种求解不允许校正的两人轮流博弈的有效方法.

[1] NASH J. Equilibrium points inn-person games[J]. Proceedings of the National Academy of Science, 1950, 36(1): 48-49.

[2] NASH J. Non-cooperative games[J]. Annals of Mathematics Studies, 1951, 54(3): 286-295.

[3] MYERSON R B. Nash equilibrium and the history of economic theory[J]. Journal of Economic Literature, 1999, 37(3): 1067-1082.

[4] CONTRERAS J, KLUSH M, KRAWCZYK J B. Numerical solutions to Nash-cournot equilibria in coupled constraint electricity markets[J]. IEEE Transactions on Power Systems, 2010, 19(1): 195-206.

[5] FACCHINEI F, KANZOW C. Generalized Nash equilibrium problems[J]. Annals of Operations Research, 2010, 175(1): 177-211.

[6] FACCHINEI F, PICCIALLI V, SCIANDRONE M. Decomposition algorithms for generalized potential games[J]. Computational Optimization& Applications, 2011, 50(2): 237-262.

[7] PANG J S, SCUTARI G, FACCHINEI F,etal. Distributed power allocation with rate constraints in gaussian parallel interference channels[J]. IEEE Transactions on Information Theory, 2008, 54(8): 3471-3489.

[8] URYASEV S, RUBINSTEIN R Y. On relaxation algorithms in computation of noncooperative equilibria[J]. IEEE Transactions on Automatic Control, 1994, 39(6): 1263-1267.

[9] YUAN Y X. A trust region algorithm for Nash equilibrium problems[J]. Pacific Journal of Optimization, 2011, 7(1): 125-138.

[10] ANTIPIN A. Extra-proximal methods for solving two-person nonzero-sum games[J]. Mathematical Programming, 2009, 120(1): 147-177.

[11] ZHANG J, QU B, XIU N. Some projection-like methods for the generalized Nash equilibria[J]. Computational Optimization & Applications, 2010, 45(1): 89-109.

[12] HAN D, ZHANG H, QIAN G,etal. An improved two-step method for solving generalized Nash equilibrium problems[J]. European Journal of Operational Research, 2012, 216(3): 613-623.

[13] PENG Z, ZHU W. An alternating direction method for Nash equilibrium of two-person games with alternating offers[J]. Journal of Optimization Theory and Applications, 2013, 157(2): 533-551.

[14] 卢延杰, 丁卫平, 彭拯. 一种求解Leader-Followers博弈问题的混合分裂算法[J]. 应用数学学报, 2014, 37(6): 1042-1055.

[15] FACCHINEI F, PANG J S. Finite-dimensional variational inequalities and complementarity problems[M]//Springer Series in Operations Research& Financial Engineering. New York: Springer-Verlag, 2003: 625-1222.

[16] HE B, YUAN X, ZHANG W. A customized proximal point algorithm for convex minimization with linear constraints[J]. Computational Optimization & Applications, 2013, 56(3) : 559-572.

[17] JIANG B, PENG Z, DONG Z. A new customized proximal point algorithm for linearly constrained convex optimization [EB/OL]. (2016-4-30)[2016-5-31]. http://www.optimization- online.org/DB_HTML/2016/04/5424.html.

[18] FACHHINEI F, KANZOW C. Penalty methods for the solution of generalized Nash equilibrium problems[J]. Mathematical Programming, 2010, 20(5): 2228-2253.

[19] KRAWCZYK J B, URYASEV S. Relaxation algorithms to find Nash equilibria with economic applications[J]. Environmental Modeling and Assessment, 2000, 5(5): 63-73.

[20] HARKER P T. Generalized Nash games and quasi-variational inequalities[J]. European Journal of Operational Research, 1991, 54(1): 81-94.

[21] OUTRATA J, ZOWE J. A numerical approach to optimization problems with variational inequality constraints[J]. Mathematical Programming, 1995, 68(1): 105-130.